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.