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 1PopcntBefore 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 PopcntMost 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 popcntIs this the most efficient method? Hellman’s TMTO 3More Efficient PopcntPre-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 BasicsPre-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 NotationConsider 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 BoxFor TMTO, treat block cipher as black box Details of crypto algorithm not important Hellman’s TMTO 8Hellman’s TMTO AttackChosen 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 attackPre-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 attackTMTO lies between 1. and 2. Hellman’s TMTO 9Chain of EncryptionsAssume 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, Kt1) =End PointHellman’s TMTO 10Encryption ChainCiphertext used as key at next iteration Same (chosen) plaintextP used at each iteration Hellman’s TMTO 11Pre-computationPre-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 AttackMemory: Pre-compute encryption chains and save (SPi, EPi) fori = 0,1,…,m1 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 AttackConsider the computed chain X0 = C, X1 = E(P, X0), X2 = E(P, X1), …Suppose for some i we find Xi= EPj EPjCSPjKSince C= E(P, K) key K should lie before ciphertext C in chain! Hellman’s TMTO 14TMTO AttackSummary 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 = Yti = E(P, Yti1) (always?) Then K =Yti1 (always?) Hellman’s TMTO 15Trudy’s Perfect WorldSuppose 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 WorldNo chains overlap Every ciphertext C is in one chain SP0EP0CEP1SP1KEP2SP2Hellman’s TMTO 17The Real WorldChains are not so well-behaved! Chains can cycle and merge KCEPSPChain 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 IssuesMerging 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 MergingCompute chain asF(E(P, Ki1)) 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 PracticeLet 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 ProbabilityThrow 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 ProbabilityUsing occupancy problem approach Assuming k-bit key and m,t,r defined as previously discussed Then, approximately, P(success) = 1 emtr/kAn upper bound can be given that is slightly “better” Hellman’s TMTO 23Success ProbabilitySuccess probability P(success) = 1 emtr/kHellman’s TMTO 24Distributed TMTOEmploy “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 TMTOSimilar pre-computation, except we have triples: (SPi, EPi,li) fori = 0,1,…,rmWhere 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 TMTOSuppose 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 TMTOIf 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 LineAttack 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

Previous Slide

Similar documents

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