19.7.3 Rainbow tables
In 1980, Martin Hellman – the cryptographer who, four years earlier, published the Diffie-Hellman key agreement protocol – proposed a method for achieving a time-memory trade-off in an exhaustive search attack [80]. Hellman’s method assumes a chosen plaintext attack with a plaintext p0, which is encrypted with a secret key k as
and Eve’s task is to find k. We first define function f as:
with R being a simple reduction. The f(k) function generates a key from a key and so can be used to generate key chains.
The reduction used by Hellman in [80] is simply dropping the last 8 bits of the ciphertext because – remember, it’s 1980! – Hellman uses DES to illustrate his method. Recall that DES encryption operates on a 64-bit plaintext block and produces a 64-bit ciphertext block using a 56-bit key.
Note that Hellman’s method works for any one-way function. So, while the example given in the original paper uses DES encryption, Eve can equally well use the method to break cryptographic hash functions.
During the pre-computation phase, Eve chooses the parameters m and t to trade off time against memory. Eve first draws m starting points S1,…,Sm uniformly at random from the key space. For 1 ≤ i ≤ m, she lets
and computes
for 1 ≤ j ≤ t. Recall that the way f is defined, all elements Xij are keys.
The last element in the i-th key chain, referred to as an endpoint, is equal to ft(Si) and is denoted by Ei as shown in Figure 19.17.
Figure 19.17: Pre-computed hash chains
To reduce the memory needed to store the pre-computations, Eve discards all intermediate values Xij and only stores the pairs (Si,Ei), sorted by Ei.
Now, suppose that Alice chooses a key k′ and computes the ciphertext c0 = ek′(p0). After intercepting that ciphertext, Eve applies reduction R to compute
Eve can now check whether Y 1 is an endpoint. If Y 1 is not an endpoint, the key is not in the next-to-last column in Figure 19.17. If, on the other hand, Y 1 = Ei, then either k′ is in the next to last column (that is, k′ = Xi,t−1) or Ei has more than one inverse image. The latter event is referred to as a false alarm.
If Y 1 = Ei, Eve uses Si to re-compute Xi,1, Xi,2, … until she can compute Xi,t−1 and check whether k′ = Xi,t−1 by verifying that decryption dk′=Xi,t−1(c0) yields the chosen plaintext p0.
If Y 1 is not an endpoint or a false alarm occurred (because Ei has more than one inverse image), Eve computes
and checks whether Y 2 is an endpoint. If Y 2 is not an endpoint, the key k is not in the t − 2nd column. On the other hand, if Y 2 = Ei, Eve checks whether k = Xi,t−2. Eve continues to compute Y 3 = f(Y 2), …, Y t = f(Y t−1) to check whether the key is in the t − 3rd, t − 4th, and so on – up to 0th – column in Figure 19.17.
Leave a Reply