程序代写代做代考 algorithm chain 17crypto_L05

17crypto_L05

Attacking One Key Systems

Crpto & SecDev 2017 © Ron Poet: Lecture 5 1

Exhaustive Search of the Key Space (Brute Force)

Table Lookup

Time Memory Trade Off

Exhaustive Search of Key Space

� Try every possible key value.
For (key = 1; key <= max_key; key++) { PlainText = Decrypt(CipherText, key) Crpto & SecDev 2017 © Ron Poet: Lecture 5 2 If (PlainText is correct) break; } � If we know part of the plaintext then we have a known plaintext attack and know when we have finished. � If we only have cipher text then we need some way of recognising valid plaintext. Simple Example � Assume our alphabet contains the English letters minus J, Q, Z. � We assign numerical codes and do all calculations mod 23, which is a prime number (all inverses exist). A = 0 G = 6 N = 12 U = 18 B = 1 H = 7 O = 13 V = 19 C = 2 I = 8 P = 14 W = 20 D = 3 K = 9 R = 15 X = 21 E = 4 L = 10 S = 16 Y = 22 F = 5 M = 11 T = 17 Crpto & SecDev 2017 © Ron Poet: Lecture 5 3 Example with Simple Algorithm � The keys are the numbers 2 .. 21. �Encryption multiplies by the key �Decryption multiplies by the inverse of the key � Here is a table of the keys (bold) and their inverses. 1 inv 1 7 inv 10 13 inv 16 18 inv 9 2 inv 12 8 inv 3 14 inv 5 19 inv 17 3 inv 8 9 inv 18 15 inv 20 20 inv 15 4 inv 6 10 inv 7 16 inv 13 21 inv 11 5 inv 14 11 inv 21 17 inv 19 22 inv 22 6 inv 4 12 inv 2 Crpto & SecDev 2017 © Ron Poet: Lecture 5 4 Brute Force Example � Known plaintext = ‘H’ (7), Cipher text = ‘F’(5) � Try keys in order, multiply the cipher text (5) by the inverse of the key. Key = 1: 1*5 = 5 Key = 2: 12*5 = 14 Key = 3: 8*5 = 17 Key = 4: 6*5 = 7 FOUND � The key is 4, which we found quickly. �We were lucky, it only took 4 steps. Crpto & SecDev 2017 © Ron Poet: Lecture 5 5 Brute Force and DES � DES calculations are simple and require a small amount of silicon. � Massively parallel special purpose chip have been built. � 56 bit keys mean the number of keys is 256 ≈ 1017 � For example �with106 processors working at 1 check per µsec Crpto & SecDev 2017 © Ron Poet: Lecture 5 6 �with106 processors working at 1 check per µsec �There will be 1012 checks per second. � It will take 105 seconds, approximately 1 day to break with a known plain text attack. Table Lookup � If we know that a given message will appear in the future (known or chosen plain text). � We can calculate the cipher text C for all possible keys in advance. � We then construct a lookup table of (C, K) pairs, � Indexing the table by the cipher text. Crpto & SecDev 2017 © Ron Poet: Lecture 5 7 � Indexing the table by the cipher text. � When the cipher text C arrives we look it up in the table and find K, which is fast. � Constructing the table may take a long time, but that may not be important. �We want to be able to instantly decode a message as soon as it arrives. � Similar to the EIN table for ENIGMA. Table Lookup Example � Known plaintext = ‘H’ (7) � Find the cipher text values (underlined) for all possible keys. 1: 1*7= 7 7: 7*7= 3 13:13*7=22 18:18*7=11 2: 2*7=14 8: 8*7=10 14:14*7= 6 19:19*7=18 3: 3*7=21 9: 9*7=17 15:15*7=13 20:20*7= 2 4: 4*7= 5 10:10*7= 1 16:16*7=20 21:21*7= 9 5: 5*7=12 11:11*7= 8 17:17*7= 4 22:22*7=16 6: 6*7=19 12:12*7=15 � The underlined numbers are the primary index keys in the table. Crpto & SecDev 2017 © Ron Poet: Lecture 5 8 The Table � The table consists of (C, K) pairs. 1,10 12, 5 2,20 13,15 When cipher text 5 arrives 3, 7 14, 2 Look it up in the table 4,17 15,12 The encryption key is 44,17 15,12 The encryption key is 4 5, 4 16,22 6,14 17, 9 7, 1 18,19 8,11 19, 6 9,21 20,16 10, 8 21, 3 11,18 22,13 Crpto & SecDev 2017 © Ron Poet: Lecture 5 9 Table Lookup and DES � This is a large table, and takes a long time to construct. � Size of the table for DES: �15 bytes per entry (8 bytes for C, 7 bytes for K), and �1017 entries mean about �1018 bytes, which is Crpto & SecDev 2017 © Ron Poet: Lecture 5 10 �1018 bytes, which is �1,000,000 TB. � The time to construct the table is about twice the time for a brute force attack. �We have to use all keys, not stop when we find the right one, which is half way on average. � Lookup time is fast, almost instantaneous. Time Memory Trade Off � This is based on a table, and so is a known or chosen plain text attack. � The size of the table is reduced, while the lookup time is increased. � The table contains many long chains, each containing many keys. � Rather than individual keys. Crpto & SecDev 2017 © Ron Poet: Lecture 5 11 �We only store the first and last element of each chain, reducing the storage. �We must traverse one of the chains when looking up the cipher text, increasing processing time. Constructing One Chain � Assume all data has the same block size as the keys. �We can then choose a value X to stand for both a key K and a cipher text block C. � Choose a random starting value X0. Crpto & SecDev 2017 © Ron Poet: Lecture 5 12 � Calculate X1 = E(X0,P) �We know P, the known plaintext. � The encryption function is C = E(K,P) so that �X0 is being used as a key value while �X1 is a cipher text block. � The next link is X2 = E(X1,P) �X1 is now treated as a key and X2 as cipher text. The Rest of the Chain � Let L be the length of the chain and calculate a sequence of X’s to complete the chain. �Xi = E(Xi-1,P) for 1 <= i <= L � Each X is used alternately as a cipher text block and a key. � Now construct a large number (N) of chains, each starting with a Crpto & SecDev 2017 © Ron Poet: Lecture 5 13 � Now construct a large number (N) of chains, each starting with a different random X0. � Construct a table of all the (XL,X0) pairs, indexed by XL. � When the cipher text C arrives, we look it up in the table. � Our choices of L and N will determine the effectiveness of this algorithm. Example � Start with P=7 as before � Let L (chain length) = 6 and N (number of chains) = 4 for simplicity � Start the 4 chains with random values: X0 X1 X2 X3 X4 X5 X6 12 12*7=15 15*7=13 13*7=22 22*7=16 16*7=20 20*7= 2 13 13*7=22 22*7=16 16*7=20 20*7= 2 2*7=14 14*7= 6 3 3*7=21 21*7= 9 9*7=17 17*7= 4 4*7= 5 5*7=12 11 11*7= 8 8*7=10 10*7= 1 1*7= 7 7*7= 3 3*7=21 � The table contains 24 keys, but some are duplicated (2,16,20,21,22). � Not all the possible keys appear in the table (11,18,19). Crpto & SecDev 2017 © Ron Poet: Lecture 5 14 TMT Table � The table of (XL,X0) pairs is much smaller than the previous table! 2,12 6,13 12, 3 21,11 Crpto & SecDev 2017 © Ron Poet: Lecture 5 15 Cipher is an End Value � If C == XL for one of the table index values XL then it will be found �The encryption key is XL-1 �We can recover it by computing the chain again starting from X0. �That is why we store X0 in the table. � If the cipher text were 12 then it is one of the X6 values in the table.� If the cipher text were 12 then it is one of the X6 values in the table. � The encryption key is 5, the (X5) in the chain. � Lookup 12 in the table, which returns 3, the X0 value. � Construct the sequence again, making L-1 (5) steps to calculate X5 the encryption key, which is 5. Crpto & SecDev 2017 © Ron Poet: Lecture 5 16 Cipher is a Middle Value � If C happened to be one of the XL-1 values then we would not find it in the table. �For example, C=5. � It is in the X0 = 3 chain but not the end value. �Only the end values are table index keys. Crpto & SecDev 2017 © Ron Poet: Lecture 5 17 �Only the end values are table index keys. � If we encrypt the known plaintext using C as the encryption key then we move along all the values in the chains along one place. � In this example, E(5, P) = 12, which is the end value of the chain starting with 3. � It will be a table index (X6) value and we can find it, as we did previously. � We find the encryption key by starting with 3, using 1 fewer steps. Cipher is a Middle Value (2) � In detail, calculate C1 = E(C, P) [= 12 in the example] � If C = XL-1 for one of the chains, then �C1 = E(XL-1, P) = XL an end value. �So C1 will be in the table, which it is in our example � We can look it up and find the corresponding X . Crpto & SecDev 2017 © Ron Poet: Lecture 5 18 � We can look it up and find the corresponding X0. �3 in our example. � Then we find the key XL-2 by recalculating the chain, as before, with L-2 (4) steps, to find the encryption key 4. � We can repeat this process, repeatedly encrypting with C to check for all the values in each of the chains. Probabilistic Attack � If T is the total number of keys to search for. � Then if L * N = T, the chains will contain the right number of keys. � However, there will be some duplicates. �The value in the middle of one chain may be the start of another Crpto & SecDev 2017 © Ron Poet: Lecture 5 19 chain so the following values will be the same. �We don’t know how much duplication there will be. � So we are not guaranteed complete coverage and there is a chance that this attack will not work. � In the example, 3 keys were missing and 5 duplicated. Storage and Performance � If L*N = T, the total number of keys then �Storage is proportional to N, number of chains. �Time is proportional to L, the length of each chain. � DES: T = 1017 assume L = 106 and so N = 1011 Crpto & SecDev 2017 © Ron Poet: Lecture 5 20 �Storage = 1012 = 1 TB � lookup 1,000,000 steps, still fast. � Precompute time O(T) �The same amount of time as an ordinary lookup table.