Transcript not 32

Hellman’s TMTO Attack
Hellman’s TMTO
1
Popcnt


Before we consider Hellman’s attack,
consider simpler Time-Memory Trade-Off
“Population count” or popcnt
o Let x be a 32-bit integer
o Define popcnt(x) = number of 1’s in binary
expansion of x

How to compute popcnt(x) efficiently?
Hellman’s TMTO
2
Simple Popcnt
 Most
obvious thing to do is
popcnt(x) // assuming x is 32-bit value
t=0
for i = 0 to 31
t = t + ((x >> i) & 1)
next i
return t
end popcnt
 Is this the most efficient method?
Hellman’s TMTO
3
More Efficient Popcnt
 Pre-compute
popcnt for all 256 bytes
o Store pre-computed values in a table
 Given
x, lookup its bytes in this table
o Sum these values to find popcnt(x)
 See
next slide for pseudo-code…
Hellman’s TMTO
4
More Efficient Popcnt
Initialize: table[i] = popcnt(i) for i = 0,1,…,255
popcnt(x) // assuming x is 32-bit word
p = table[ x & 0xff ]
+ table[ (x >> 8) & 0xff ]
+ table[ (x >> 16) & 0xff ]
+ table[ (x >> 24) & 0xff ]
return p
end popcnt
Hellman’s TMTO
5
Popcnt TMTO
 Advantage(s)?
o Each popcnt now requires 4 steps, not 32
 Disadvantage?
o Pre-computation (one time work)
o Additional storage
 Balance
“time” vs “memory” where…
o Time == popcnt computation(s)
o Memory == storage/pre-computation
Hellman’s TMTO
6
TMTO Basics

Pre-computation
o One-time work
o Results stored in a table


Pre-computation results used to make each
subsequent computation faster
In general, larger pre-computation requires
more initial work and larger “memory”
o But then each computation takes less “time”

Try to balance “memory” and “time”
Hellman’s TMTO
7
Block Cipher Notation
 Consider
a block cipher
C = E(P, K)
where
P is plaintext block of size n
C is ciphertext block of size n
K is key of size k
Hellman’s TMTO
8
Block Cipher as Black Box

For TMTO, treat block cipher as black box

Details of crypto algorithm not relevant
Hellman’s TMTO
9
Hellman’s TMTO Attack

This is a chosen plaintext attack

We choose P

Then we are given corresponding C
o

That is, C = E(P, K)
We want to find the key K
Hellman’s TMTO
10
TMTO Attack

Given: P and C = E(P, K)

Find: key K

Two “obvious” approaches
1. Exhaustive key search
“Memory” is 0, but “time” of 2k-1 for each attack
2. Pre-compute C = E(P, K) for all keys K
Then given any C, simply look up key K in table
“Memory” of 2k but “time” of 0 per attack

TMTO lies between 1. and 2.
Hellman’s TMTO
11
Chain of Encryptions

o

For simplicity, we assume block length n
and key length k are equal, that is, n = k
Attack still works if this does not hold
Define a chain of encryptions as
SP = K0 = Starting Point
K1 = E(P, SP)
K2 = E(P, K1)
:
:
EP = Kt = E(P, Kt1) = End Point
Hellman’s TMTO
12
Encryption Chain


Note that ciphertext from one iteration is
used as key at next iteration
Note also that the same (chosen) plaintext
P used at each iteration
Hellman’s TMTO
13
Pre-computation
 Pre-compute
m encryption chains, each
of length t +1
 Save only the start and end points
(SP0, EP0) SP
0
(SP1, EP1)
SP1
:
(SPm-1, EPm-1) SPm-1
Hellman’s TMTO
EP0
EP1
EPm-1
14
TMTO Attack
 Memory:
Pre-compute encryption
chains and save (SPi, EPi) for i =
0,1,…,m1
o This is one-time work
o Sort based on EPi
 For
each attack for unknown key K do…
o We have P and C = E(P, K) where P is same
plaintext used to compute chains
o Time: Compute a chain (max of t steps)
X0 = C, X1 = E(P, X0), X2 = E(P, X1),…
Hellman’s TMTO
15
TMTO Attack
 Consider
the computed chain
X0 = C, X1 = E(P, X0), X2 = E(P, X1), …
 Suppose for some i we find Xi = EPj
C
SPj
EPj
K
 Since
C = E(P, K) key K appears to lie
just before ciphertext C in this chain!
Hellman’s TMTO
16
TMTO Attack
 Summary
of attack phase: compute
X0 = C, X1 = E(P, X0), X2 = E(P, X1),…
 If for some i we find Xi = EPj then
reconstruct chain from SPj
Y0 = SPj, Y1 = E(P,Y0), Y2 = E(P,Y1),…
 We find C = Yti = E(P, Yti1) (always?)
 So that K = Yti1 (always?)
Hellman’s TMTO
17
Trudy’s Perfect World

Suppose block cipher has k = 56
o

Suppose we can find m = 228 chains each
of length t = 228 with no overlap
o


That is, the key length is 56 bits
Is this realistic?
Then all 256 possible keys covered by
exactly one element of a chain
This looks promising…
Hellman’s TMTO
18
Trudy’s Perfect World




If we can find m = 228 chains each of
length t = 228 and no intersection,
then…
Memory: 228 pairs (SPj, EPi)
Time: about 228 (per attack)
o
o
o
Start at C, find some EPj in about 227 steps
Find K with about 227 more steps
So, work per attack is about 228
o
For Trudy, life doesn’t get any better…
Trivial work and attack never fails!
Hellman’s TMTO
19
Trudy’s Perfect World
 No
chains intersect
 Every
ciphertext C is in one chain
SP0
EP0
C
SP1
SP2
Hellman’s TMTO
EP1
K
EP2
20
The Real World
 Real
chains are not so well-behaved
 Chains can cycle and merge
K
C
EP
SP
 Chain
beginning at C goes to EP
 But chain from SP to EP does not give K
 This looks like Trudy’s nightmare…
Hellman’s TMTO
21
The Real World
 Chains
can cycle and merge
K
C
EP
SP
 This
adversely affects attacks, as
mentioned on previous slide
 It also, adversely affects precomputation and probability of success
 Why?
Hellman’s TMTO
22
Real-World TMTO Issues
 Merging
chains, cycles, false alarms, …
 Pre-computation is lots of work
o Must attack many times to amortize cost
 Success
is not assured
o Depends on initial work, merging, cycles, …
 What
if block size not equal key length?
 What
is the probability of success?
o This is easy to deal with
o This is not so easy to compute…
Hellman’s TMTO
23
To Reduce Merging

Compute chain as F(E(P, Ki1)) where F
permutes the bits
o Then we have F(E(P, K)) = F(C)

Chains computed using different functions
can intersect, but will not merge
SP0
SP1
Hellman’s TMTO
F0 chain
F1 chain
EP1
EP0
24
Hellman’s TMTO in Practice
 Let
m = random starting points for each F
t = encryptions in each chain
r = number of “tables”, i.e., functions F
 Then
mtr pre-computed chain elements
 Each
TMTO attack requires
o Pre-computation is about mtr work
o About mr “memory” (storage), and tr “time”
 If
we choose m = t = r = 2k/3 then
probability of success is at least 0.55
Hellman’s TMTO
25
Success Probability?
 Throw
n balls into m urns
 Expected number of urns that have
at least one ball?
 This is classic “occupancy problem”
o See Feller, Intro. to Probability Theory
 Why
is this relevant to TMTO ?
o “Urns” correspond to keys
o “Balls” correspond to constructing chains
Hellman’s TMTO
26
Success Probability
 Using
occupancy problem approach…
 Assuming k-bit key and m,t,r as
defined on previous slide
o Can choose m = t = r but not necessary
 Then,
approximately,
P(success) = 1  emtr/k
 An upper bound can be given that is
slightly “better”
Hellman’s TMTO
27
Success
Probability
 Success
probability
P(success) = 1  emtr/k
Hellman’s TMTO
28
Distributed TMTO
 Employ
“distinguished points”
 Do not use fixed-length chains
 Instead, compute chain until some
distinguished point is found
 Example of distinguished point:
Hellman’s TMTO
29
Distributed TMTO

Similar pre-computation as before, except
we have triples:
(SPi, EPi, li) for i = 0,1,…,rm
o Where li is the length of the chain
o And r is number of tables
o And m is number of random starting points

Let Mi be the maximum lj for the ith table

Each table has a fixed random function F
Hellman’s TMTO
30
Distributed TMTO

Suppose r computers are available

Each computer deals with one table
o So, only one random function F per computer

“Master” gives computer i values Fi, Mi, C
o And definition of distinguished point

Computer i computes chain beginning with C
and using Fi of (at most) length Mi
Hellman’s TMTO
31
Distributed TMTO

If computer i finds a distinguished point
within Mi steps
o Returns result to “master” for secondary test
o Master searches for K on corresponding chain,
using same approach as in non-distributed TMTO
o False alarms can occur (e.g., distinguished points)

If no distinguished point found in Mi steps
o Computer i gives up, since key not on any Fi chains
Note that computer i does not need to know
any SP or EP or l
 Master knows (SPi, EPi, li) for i = 0,1,…,rm

Hellman’s TMTO
32
TMTO for DES
Attack is feasible against DES
 Recall that for DES, we have k = 56
 Assume that we use m = t = r = 2k/3 ≈ 218.67
 Then pre-computation is about 256 work

o And we store about 237 starting/end point pairs

So, each time attack is conducted…
o …use about 237 “memory” and requires 237 “time”
Hellman’s TMTO
33
TMTO: The Bottom Line
 Attack
is not specific to DES
o Applies to any block cipher
 Inner
working of cipher is not relevant
o But key length is…
 No
fancy math required
o Just a clever algorithm
 Lesson:
crypto!
Hellman’s TMTO
Clever algorithms can break
34