Transcript Digital Rights Management

Once Upon a Time-Memory
Tradeoff
Mark Stamp
Department of Computer Science
San Jose State University
This talk…
 Non-cryptanalytic
TMTOs
 Crypto background
 Hellman’s cryptanalytic TMTO
 Distributed TMTO
 Conclusions
TMTO
2
Non-crypto TMTOs
 Popcnt
 Shank’s
algorithm
TMTO
3
Popcnt
 Let
x be a 32-bit integer
 Define popcnt(x) = number of 1’s in
binary expansion of x
 How to compute popcnt(x) ?
TMTO
4
Simple popcnt
popcnt(x)
t=0
for i = 0 to 31
t = t + (x >> i) & 1
next i
return t
end popcnt
TMTO
5
Efficient popcnt
Initialize: table[i] = popcnt(i) for i = 0,1,…,255
popcnt(x)
t = table[ x & 0xff ]
+ table[ (x >> 8) & 0xff ]
+ table[ (x >> 16) & 0xff ]
+ table[ (x >> 24) & 0xff ]
return t
end popcnt
TMTO
6
Discrete Log
 Let
p be prime, g  {1,2,…, p1} s.t. for
any n there is a k with n = gk mod p
 Discrete log: given m  {1,2,…, p1}
find e s.t. m = ge mod p
 Notation: e = logg(m)
 Could try each value in {1,2,…, p1} to
find e that works
TMTO
7
Shank’s algorithm
Shank’s is a TMTO for discrete log
 Given m, we want e = logg(m)
A. Compute list Lr as follows

1.
2.
Let r = sqrt(p  1) and compute grj mod p
for j = 0,1,…,r  1
Let Lr be the list of ( j, grj mod p) sorted
on second coordinate
TMTO
8
Shank’s alg (continued)
B. Compute list Lm as follows
1.
2.
Compute mgi mod p for i = 0,1,…,r  1
Let Lm be the list of (i, mgi mod p)
sorted on second coordinate
TMTO
9
Shank’s alg. (cont. again)
C. Then e = logg(m) is found by
1.
2.

Find elements of Lr and Lm that agree in
2nd coordinates, say, ( j, x)  Lr and
(i, x)  Lm
Then e = logg(m) = rj + i mod (p  1) since
grj = mgi mod p
Shank’s: baby step, giant step
TMTO
10
Shank’s algorithm (example)

Suppose p = 257, g = 3. Then r = 16 and Lr is
(0,1)
(3,2)
(6,4)
(9,8)
(12,16)
(15,32) (2,64) (5,128) (13,129) (10,193)
(7,225) (4,241) (1,249) (14,253) (11,255) (8,256)

Suppose m = 132. Then Lm is
(9,23) (1,44) (3,62)
(5,64) (8,69)
(12,77) (15,79) (6,107) (0,132) (10,179)
(2,186) (4,192) (13,197) (7,207) (11,231) (14,237)

From Lr and Lm we find (2,64) and (5,64).
Then log3(132) = 2  16 + 5 = 37 and
easy to verify 337 = 132 mod 257
TMTO
11
Block cipher
Consider a block cipher
C = E(P, K)
where
P is plaintext of length n
C is ciphertext of length n
K is key of length k
TMTO
12
Block Cipher
TMTO
13
Chosen plaintext attack


We choose P and obtain C, where
C = E(P, K)
Want to find the key K
1.
2.

Exhaustive key search
Table pre-computation
TMTO lies between 1. and 2.
TMTO
14
Chain of encryptions
Assume n = k. Then a chain is
SP = K0 = Starting Point
K1 = E(P, SP)
K2 = E(P, K1)
:
:
EP = Kt = E(P, Kt1) = End Point
TMTO
15
Chain (another view)
TMTO
16
Pre-computation
 Compute
m encryption chains, each of
length t +1
 Save only start and end points
(SP0, EP0)
(SP1, EP1)
:
(SPm-1, EPm-1)
TMTO
17
TMTO Attack
 Memory:
Given (SPi, EPi), i = 0,1,…,m1
 For chosen P compute
C = E(P, K)
 The key K is unknown
 Time: Compute chain (max of t steps)
X0 = C, X1 = E(P, X0), X2 = E(P, X1),…
TMTO
18
Attack (continued)
 Given
the chain
X0 = C, X1 = E(P, X0), X2 = E(P, X1),…
 Suppose we find Xi = EPj
 Then C might be in chain (SPj, EPj)
 Assume C is in chain (SPj, EPj)
TMTO
19
Attack (continued again)
 Given
C is in the chain (SPj, EPj)
and Xi = EPj
 Re-compute chain (SPj, EPj)
Y0 = SPj, Y1 = E(P,Y0), Y2 = E(P,Y1),…
 Then C = Yti = E(P, Yti1)
 And Yti1 = K (always?)
TMTO
20
In a perfect world




Suppose the block cipher has 56 bit key
Suppose we find m = 228 chains, each of
length t = 228 and no chains overlap
Memory: 228 pairs (SPj, EPj)
Time: about 228 (for attack)
1.
2.
Find C in about 227 tries
Find K with about 227 more tries
TMTO
21
In a perfect world
 All
chains distinct
 Ciphertext C lies within a chain
SP0
EP0
C
SP1
EP1
EP2
SP2
TMTO
22
In the real world
 Chains
are not so well-behaved
 Chains cycle and merge
C
EP
SP
TMTO
23
To reduce merging
 Compute
chain as Ki = F(E(P, Ki1)) where
F is a permutation
 Choose r different functions F
 For each F choose m random SP
 Each chain of length t
TMTO
24
Notation
= number of random starting points
for each function F
 t = length of each chain
 r = number of “random” functions F
 Note: mtr = total number of computed
chain elements
m
TMTO
25
Real-world issues
 False
alarms, avoid cycles, reduce
merging, etc.
 Pre-computation is lots of work (must
be amortized over many attacks)
 Success is not assured
 What if block size not equal key length?
 What is the probability of success?
TMTO
26
Probability of success
 Occupancy
problem: b balls distributed
with uniform probability to c cells
 Let pl(b,c) be probability of l empty
cells. Feller [3] shows
TMTO
27
Success probability (continued)
 Poisson
approx to pl(b,c) is
pl() = el/l! where  = ceb/c
 So expected number of empty cells is
TMTO
28
Success probability (still more)
 Expected
number of occupied cells is
c   = c(1  eb/c)
 Therefore
P(cell i is occupied) = 1  eb/c
 TMTO attack succeeds if and only if
the “cell” with key K is “occupied”
TMTO
29
Success prob (last word, almost)
mtr
---2k2
2k1
2k
2k+1
2k+2
P(success) = 1 
-------------
k

mtr/2
e
0.22
0.39
0.63
0.86
0.98
TMTO
30
The bottom line
 Choose
m = t = r = 2k/3 and probability of
success is about 0.63 (at least 0.55 by
a more careful analysis)
 Pre-computation is O(mtr) work
 Each TMTO attack requires O(mr)
“memory” and O(tr) “time”
TMTO
31
Distinguished points
 Let
a distinguished point be of the form
(x0,x1,…,xs1,0,0,…,0)
 Construct chain until distinguished point
is found
 If no distinguished point is found within
max steps, don’t save chain
 Then every EP is distinguished
TMTO
32
Distinguished points +/
Disadvantages
Chains are variable length
 Some extra work to find chains
 Triples (SP, EP, length)


Advantage
Distributed attack is very nice
 Why? One client for each F then client only needs
(P, C) and F and max chain length  no data!

TMTO
33
References
[1] M. Hellman, A cryptanalytic time-memory tradeoff,
IEEE Trans on Info Thy, Vol. 26, No. 4, July 1980,
pp. 401-406
[2] J.Borst, et al., On the time-memory tradeoff between
exhaustive key search and table precomputation,
http://www.esat.kuleuven.ac.be/~borst/downloadable/tm.ps.gz
[3] W. Feller, An Introduction to Probability Theory and Its
Applications, volume 1, Wiley (1968)
[4] M. Stamp, Once upon a time-memory tradeoff,
http://www.cs.sjsu.edu/faculty/stamp/articles/tmto.pdf
TMTO
34