Hellman’s TMTO Attack

Please download to get full document.

View again

of 29
5 views
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.

Download

Document Related
Document Description
Hellman’s TMTO Attack. Popcnt. Before we consider Hellman’s attack, consider simpler T ime- M emory T rade- O ff “Population count” or 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 ) efficiently?.
Document Share
Document Transcript
Hellman’s TMTO AttackHellman’s TMTO 1Popcnt
  • Before we consider Hellman’s attack, consider simpler Time-Memory Trade-Off
  • “Population count” or 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) efficiently?
  • Hellman’s TMTO 2Simple Popcnt
  • Most obvious thing to do is
  • popcnt(x) // assuming x is 32-bit valuet = 0 for i = 0 to 31t = t + ((x >> i) & 1) next i return t end popcnt
  • Is this the most efficient method?
  • Hellman’s TMTO 3More Efficient Popcnt
  • Pre-compute popcnt for all 256 bytes
  • Store pre-computed values in a table
  • Given x, lookup its bytes in this table
  • Sum these values to find popcnt(x)
  • Note that pre-computation is done once
  • Each popcnt now requires 4 steps, not 32
  • Hellman’s TMTO 4More Efficient PopcntInitialize: table[i] = popcnt(i) for i = 0,1,…,255 popcnt(x) // assuming x is 32-bit wordp = table[x & 0xff] + table[(x >> 8) & 0xff] + table[(x >> 16) & 0xff] + table[(x >> 24) & 0xff] return p end popcntHellman’s TMTO 5TMTO Basics
  • Pre-computation
  • One-time work
  • Results stored in a table
  • Pre-computation results used to make each subsequent computation faster
  • Try to balance “memory” and “time”
  • In general, larger pre-computation requires more initial work and larger “memory” but then each computation takes less “time”
  • Hellman’s TMTO 6Block Cipher Notation
  • Consider a block cipher
  • C = E(P, K) whereP is plaintext block of size nC is ciphertext block of size nK is key of size kHellman’s TMTO 7Block Cipher as Black Box
  • For TMTO, treat block cipher as black box
  • Details of crypto algorithm not important
  • Hellman’s TMTO 8Hellman’s TMTO Attack
  • Chosen plaintext attack: choose P and obtain C, where C = E(P, K)
  • Want to find the key K
  • Two “obvious” approaches
  • Exhaustive key search
  • “Memory” is 0, but “time” of 2k-1 for each attack
  • Pre-computeC = E(P, K)for all keysK
  • Given C, simply look up key K in the table“Memory” of 2k but “time” of 0 for each attack
  • TMTO lies between 1. and 2.
  • Hellman’s TMTO 9Chain of Encryptions
  • Assume block length n and key length k are equal: n = k
  • Then a chain of encryptions is
  • SP = K0 =Starting PointK1 = E(P, SP)K2 = E(P, K1) : :EP = Kt = E(P, Kt1) =End PointHellman’s TMTO 10Encryption Chain
  • Ciphertext used as key at next iteration
  • Same (chosen) plaintextP used at each iteration
  • Hellman’s TMTO 11Pre-computation
  • Pre-compute m encryption chains, each of length t +1
  • Save only the start and end points
  • (SP0, EP0) (SP1, EP1) :(SPm-1, EPm-1)EP0SP0EP1SP1EPm-1SPm-1Hellman’s TMTO 12TMTO Attack
  • Memory: Pre-compute encryption chains and save (SPi, EPi) fori = 0,1,…,m1
  • This is one-time work
  • Must be sorted on EPi
  • To attack a particular unknown key K
  • For the same chosen P used to find chains, we know C where C = E(P, K) and K is unknown key
  • Time: Compute the chain (maximum of t steps)
  • X0 = C, X1 = E(P, X0), X2 = E(P, X1),…Hellman’s TMTO 13TMTO Attack
  • Consider the computed chain
  • X0 = C, X1 = E(P, X0), X2 = E(P, X1), …
  • Suppose for some i we find Xi= EPj
  • EPjCSPjK
  • Since C= E(P, K) key K should lie before ciphertext C in chain!
  • Hellman’s TMTO 14TMTO Attack
  • Summary of attack phase: we compute chain
  • 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),…
  • Find C = Yti = E(P, Yti1) (always?)
  • Then K =Yti1 (always?)
  • Hellman’s TMTO 15Trudy’s Perfect World
  • Suppose block cipher has k = 56
  • That is, the key length is 56 bits
  • Spse we find m = 228 chains each of length t = 228 and no chains overlap (unrealistic)
  • Memory:228 pairs (SPj, EPi)
  • Time: about 228 (per attack)
  • Start at C, find some EPj in about 227 steps
  • Find K with about 227 more steps
  • Attack never fails!
  • Hellman’s TMTO 16Trudy’s Perfect World
  • No chains overlap
  • Every ciphertext C is in one chain
  • SP0EP0CEP1SP1KEP2SP2Hellman’s TMTO 17The Real World
  • Chains are not so well-behaved!
  • Chains can cycle and merge
  • KCEPSP
  • Chain beginning at C goes to EP
  • But chain from SP to EP does not give K
  • Is this Trudy’s nightmare?
  • Hellman’s TMTO 18Real-World TMTO Issues
  • Merging chains, cycles, false alarms, etc.
  • Pre-computation is lots of work
  • Must attack many times to amortize cost
  • Success is not assured
  • Probability depends on initial work
  • What if block size not equal key length?
  • This is easy to deal with
  • What is the probability of success?
  • This is not so easy to compute…
  • Hellman’s TMTO 19To Reduce Merging
  • Compute chain asF(E(P, Ki1)) where F permutes the bits
  • Chains computed using different functions can intersect, but they will not merge
  • SP0F0 chainEP1SP1F1 chainEP0Hellman’s TMTO 20Hellman’s TMTO in Practice
  • Let
  • m = random starting points for each F
  • t = encryptions in each chain
  • r = number of “tables”, i.e., random functions F
  • Then mtr = total pre-computed chain elements
  • Pre-computation is about mtr work
  • Each TMTO attack requires
  • About mr “memory” and about tr “time”
  • If we choose m = t = r = 2k/3 then probability of success is at least 0.55
  • Hellman’s TMTO 21Success Probability
  • Throw n balls into m urns
  • What is expected number of urns that have at least one ball?
  • This is classic “occupancy” problem
  • See Feller, Intro. to Probability Theory
  • Why is this relevant to TMTO attack?
  • “Urns” correspond to keys
  • “Balls” correspond to constructing chains
  • Hellman’s TMTO 22Success Probability
  • Using occupancy problem approach
  • Assuming k-bit key and m,t,r defined as previously discussed
  • Then, approximately,
  • P(success) = 1 emtr/k
  • An upper bound can be given that is slightly “better”
  • Hellman’s TMTO 23Success Probability
  • Success probability
  • P(success) = 1 emtr/kHellman’s TMTO 24Distributed TMTO
  • Employ “distiguished points”
  • Do not use fixed-length chains
  • Instead, compute chain until some distinguished point is found
  • Example of distinguished point:
  • Hellman’s TMTO 25Distributed TMTO
  • Similar pre-computation, except we have triples:
  • (SPi, EPi,li) fori = 0,1,…,rm
  • Where li is the length of the chain
  • And r is number of tables
  • 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 26Distributed TMTO
  • Suppose r computers are available
  • Each computer deals with one table
  • That is, one random function F
  • “Server” gives computer i the values Fi, Mi, C and definition of distinguished point
  • Computer i computes chain beginning from C using Fi of (at most) length Mi
  • Hellman’s TMTO 27Distributed TMTO
  • If computer i finds a distinguished point within Mi steps
  • Returns result to “server” for secondary test
  • Server searches for K on corresponding chain (same as in non-distributed TMTO)
  • False alarms possible (distinguished points)
  • If no distinguished point found in Mi steps
  • Computer i gives up
  • Key cannot lie on any Fi chains
  • Note that computer i does not need any SP
  • Only server needs (SPi, EPi,li) fori = 0,1,…,rm
  • Hellman’s TMTO 28TMTO: The Bottom Line
  • Attack is feasible against DES
  • Pre-computation is about 256 work
  • Each attack requires about
  • 237 “memory” and 237 “time”
  • Attack not particular to DES
  • No fancy math is required!
  • Lesson: Clever algorithms can break crypto!
  • Hellman’s TMTO 29
    Search Related
    We Need Your Support
    Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

    Thanks to everyone for your continued support.

    No, Thanks