1. Birthday paradox and its applications. For more about finding collisions see here.
2. Random function and random permutation statistic.
[see references 2,3,4]

3. Hellman's Time and Memory tradeoff for arbitrary random permutation.

Assume that there are N keys for the cipher E_k. Denote by M the number of memory words required for the attack. By T denote the number of computation steps.

Obvious attacks are: exhaustive search, M = 1, T = N (Known plaintext) and dictionary attack, M=N, T=1, (Chosen plaintext). Hellman's method provides a tradeoff between M and T. This is the method to invert any one way function.

If the blocksize and the key size are equal we can use the cipher as function of the key for some fixed common message (for ex. 8 spaces or "Dear Joe"). If the keysize is shorter that the block size we can reduce the number of bits of the cipher block just by dropping the extra bits. The resulting function can be iterated, it is a random function and the problem of its inversion is equivalent to cryptanalysis of the cipher (i.e. finding the secret key).

Precomputation phase
The idea is to pick m random points (starting points, SP_i) and for each to iterate the function t times arriving at the ending points (EP_i). Array of {SP_i, EP_i} is stored on the disk sorted by EP_i. This is the precomputation phase.

Attack phase
One receives the ciphertext C, reduces it to the key size if necessary and checks if the result  (call it Y1) is one of the EP_i. If it is, then the chances are good that the preimage that was used to calculate the EP_i is the correct key.
Since it is hard to go backwards In order to find this preimage one starts from the corresponding  SP_i and goes t steps forward. If it is not one of the EP_i , the we check if F(Y1) is one of the EP_i, F^2(Y1) is one of the EP_i, etc...

It works best for a functions which consist of single cycle, then MT = N tradeoff is possible. This is possible also for random permutations since on the average a random permutation has a cycle that covers 62% of it and other large cycles.

For the random functions (which is the case of interest for cryptanalysis of ciphers) the tradeoff is much worse it is M = T = N^{2/3}.  It is not clear that better tradeoff is impossible. It is a very interesting open problem. The increase in M and T by extra N^{1/3} is due to the plaguing overlaps of coverage points that decrease the efficiency of the tradeoff and thus Hellman's solution to this problem is to use  N^{1/3} different "reduction functions" thus covering different random graphs related to the same inversion problem. These reduction can be simply -- bit-reordering however for a strong cipher they alter the whole random map to the unrecognizable state.

Another important idea is that of "distinguishing points", instead of storing the
end points after exactly t steps, store only points that have log t leading zeroes. This trick allows to make less disk accesses during the attack.

Reading for this lecture

1. Martin Hellman, "A Cryptanalytic Time-Memory Trade-Off", IEEE Transactions on Information Theory, Vol. IT-26, No.4, July 1980.

2. Philippe Flajolet, Andrew Odlyzko, "Random Mapping Statistics", Lecture Notes in Computer Science 434, EUROCRYPT'89, pp.329-354,1989.

3. Solomon Golomb, "Shift Register Sequences",  pp.175-180, Holden-Day Inc., 1967.
[handout, random permutation statistic]

4. http://www.mathsoft.com/asolve/constant/golomb/golomb.html

Go to the next lecture.