General Cryptanalytic Methods - Modern Cryptanalysis: Techniques for Advanced Code Breaking - page 123

5.2.2 Hellman Time-Space Trade-off
Another attack, usually simply called the Hellman time-space trade-off , is a chosen (or very probable) plain-
text attack, but a relatively simple one: We choose a single plaintext to encrypt with a variety of keys [7]. This
means that we should be certain that whatever ciphertext we wish to test will correspond to the chosen or prob-
able plaintext.
We start with some large number of keys (say, M keys of the form K i ). We also have the chosen plaintext, P .
Then, we construct a list of ciphertexts, corresponding to encrypting the plaintext with each key, K i :
(Here, we have to adjust the notation slightly so that the second argument of the encryption function is the
key.)
Now, we perform the following computation: Take each calculated from before, and compute
Inotherwords,weareencryptingtheplaintextagain,butthistime using the output of the previous encryption
as the key. If the block size of the output is larger than the key (e.g., DES has a block size of 64, but a key size
of 56, or AES with a block size of 128 and a key size of 256), then we will have to run the output C 0 i through a
reduction function, Reduce.
The reduction function need not be complicated; something simple, such as removing the first few bits, will
suffice. If the block size and key size are the same, then the reduction function is unnecessary.
We then iterate the above procedure, using the new ciphertexts as keys. We will stop after some number of
times (say, S ), each time computing (for a round j )
This process generates the following flow of ciphertexts:
For the attack, we will only actually store the starting points ( values) and final entries ( values), creating
two lists of ciphertexts.
Now, the properties of this list allow us to easily ascertain the key used some portion of the time. For ex-
ample, assume that we intercept the ciphertext A of the known plaintext used to generate our table. If A = for
some i, then we know that A = E ( P,R ( )), and thus the key used is !
However, we do not want to store too much — this just increases our storage requirements, which we always
want to minimize. Depending on how small our final generated list is, we will seldom have a match after one
step. In this case, we iterate using the same idea as above. Let A 0 = A be our original ciphertext; compute A 1 =
E(P, R(A 0 )) . If A 1 matches any of the , then A 1 = E(P,R(A 0 )) = E ( P , R ( )), meaning that A 0 = E ( P,R ( ));
thus, the key used in the original encryption matches the reduction of .
The process repeats, continuing until the A j value equals a value yielding the position to find the key, or
we give up after S times. We would then have run past the left end of the table, where we started generating.