Ross Anderson - Security Engineering

We can visualise block encryption as follows. As before, we have an elf in a box with dice and a scroll. This has on the left a column of plaintexts and on the right a column of ciphertexts. When we ask the elf to encrypt a message, it checks in the left-hand column to see if it has a record of it. If not, it rolls the dice to generate a random ciphertext of the appropriate size (and which doesn't appear yet in the right-hand column of the scroll), and then writes down the plaintext/ciphertext pair in the scroll. If it does find a record, it gives us the corresponding ciphertext from the right-hand column.

When asked to decrypt, the elf does the same, but with the function of the columns reversed: he takes the input ciphertext, looks for it on the right-hand scroll, and if he finds it he gives the message with which it was previously associated. If not, he generates a new message at random, notes it down and gives it to us.

A block cipher is a keyed family of pseudorandom permutations. For each key, we have a single permutation that's independent of all the others. We can think of each key as corresponding to a different scroll. The intuitive idea is that a cipher machine should output the ciphertext given the plaintext and the key, and output the plaintext given the ciphertext and the key, but given only the plaintext and the ciphertext it should output nothing. Furthermore, nobody should be able to infer any information about plaintexts or ciphertexts that it has not yet produced.

We will write a block cipher using the notation established for encryption in the chapter on protocols:

The random permutation model also allows us to define different types of attack on block ciphers. In a known plaintext attack , the opponent is just given a number of randomly chosen inputs and outputs from the oracle corresponding to a target key. In a chosen plaintext attack , the opponent is allowed to put a certain number of plaintext queries and get the corresponding ciphertexts. In a chosen ciphertext attack he gets to make a number of ciphertext queries. In a chosen plaintext/ciphertext attack he is allowed to make queries of either type. Finally, in a related key attack he can make queries that will be answered using keys related to the target key , such as and .

In each case, the objective of the attacker may be either to deduce the answer to a query he hasn't already made (a forgery attack ), or to recover the key (unsurprisingly known as a key recovery attack ).

This precision about attacks is important. When someone discovers a vulnerability in a cryptographic primitive, it may or may not be relevant to your application. Often it won't be, but will have been hyped by the media – so you will need to be able to explain clearly to your boss and your customers why it's not a problem. So you have to look carefully to find out exactly what kind of attack has been found, and what the parameters are. For example, the first major attack announced on the Data Encryption Standard algorithm (differential cryptanalysis) required chosen plaintexts to recover the key, while the next major attack (linear cryptanalysis) improved this to known plaintexts. While these attacks were of huge scientific importance, their practical engineering effect was zero, as no practical systems make that much known text (let alone chosen text) available to an attacker. Such impractical attacks are often referred to as certificational as they affect the cipher's security certification rather than providing a practical exploit. They can have a commercial effect, though: the attacks on DES undermined confidence and started moving people to other ciphers. In some other cases, an attack that started off as certificational has been developed by later ideas into an exploit.

Which sort of attacks you should be worried about depends on your application. With a broadcast entertainment system, for example, a hacker can buy a decoder, watch a lot of movies and compare them with the enciphered broadcast signal; so a known-plaintext attack might be the main threat. But there are surprisingly many applications where chosen-plaintext attacks are possible. A historic example is from World War II, where US analysts learned of Japanese intentions for an island ‘AF’ which they suspected meant Midway. So they arranged for Midway's commander to send an unencrypted message reporting problems with its fresh water condenser, and then intercepted a Japanese report that ‘AF is short of water’. Knowing that Midway was the Japanese objective, Admiral Chester Nimitz was waiting for them and sank four Japanese carriers, turning the tide of the war [1003].

The other attacks are more specialised. Chosen plaintext/ciphertext attacks may be a worry where the threat is a lunchtime attack : someone who gets temporary access to a cryptographic device while its authorised user is out, and tries out the full range of permitted operations for a while with data of their choice. Related-key attacks are a concern where the block cipher is used as a building block in the construction of a hash function (which we'll discuss below). To exclude all such attacks, the goal is semantic security, as discussed above; the cipher should not allow the inference of unauthorised information (whether of plaintexts, ciphertexts or keys) other than with negligible probability.

A public-key encryption algorithm is a special kind of block cipher in which the elf will perform the encryption corresponding to a particular key for anyone who requests it, but will do the decryption operation only for the key's owner. To continue with our analogy, the user might give a secret name to the scroll that only she and the elf know, use the elf's public one-way function to compute a hash of this secret name, publish the hash, and instruct the elf to perform the encryption operation for anybody who quotes this hash. This means that a principal, say Alice, can publish a key and if Bob wants to, he can now encrypt a message and send it to her, even if they have never met. All that is necessary is that they have access to the oracle.

The simplest variation is the trapdoor one-way permutation . This is a computation that anyone can perform, but which can be reversed only by someone who knows a trapdoor such as a secret key. This model is like the ‘one-way function’ model of a cryptographic hash function. Let us state it formally nonetheless: a public key encryption primitive consists of a function which given a random input will return two keys, (the public encryption key) and (the private decryption key) with the properties that