Page137

Philippe Oechslin describes this challenge in his paper “Making a Faster Cryptanalytic Time-Memory Trade-Off”: “Cryptanalytic attacks based on exhaustive search need a lot of computing power or a lot of time to complete. When the same attack has to be carried out multiple times, it may be possible to execute the exhaustive search in advance and store all results in memory. Once this precomputation is done, the attack can be carried out almost instantly. Alas, this method is not practicable because of the large amount of memory needed.”

Rainbow tables rely on a clever time/memory tradeoff. This technique was researched by Martin Hellman (of Diffie-Hellman fame) and improved upon by Philippe Oechslin. Long chains of password-hash (plaintext-ciphertext) pairs are connected. Thousands or millions of pairs may be connected into one chain (called a rainbow chain), and many chains may be formed, connected via a reduction function (which takes a hash and converts it into another possible password). At the end, everything in the chain may be removed, except the first and last entry. These chains may be rebuilt as needed, reconstituting all intermediate entries. This saves a large amount of storage, in exchange for some time and CPU cycles.

Known Plaintext

A known plaintext attack relies on recovering and analyzing a matching plaintext and ciphertext pair: the goal is to derive the key that was used. You may be wondering why you would need the key if you already have the plaintext: recovering the key would allow you to decrypt other ciphertexts encrypted with the same key.

Chosen Plaintext and Adaptive Chosen Plaintext

A cryptanalyst chooses the plaintext to be encrypted in a chosen plaintext attack; the goal is to derive the key. Encrypting without knowing the key is done via an “encryption oracle,” or a device that encrypts without revealing the key. This may sound far-fetched, but it is quite practical: a VPN concentrator encrypts plaintext to ciphertext without revealing the key (only users authorized to manage the device may see the key).

Adaptive-chosen plaintext begins with a chosen plaintext attack in round 1. The cryptanalyst then “adapts” further rounds of encryption based on the previous round.