Cryptographic hash functions, as defined last time, have various applications. Their use for message authentication is common, but, unless it is carefully designed, it can lead to insecure systems.
We conclude the lecture with an overview of how the current standard pseudorandom permutation (AES) works. Next time we begin a study of how to construct pseudorandom permutations (and hence secure MACs and CCA-secure encryption) starting from well-understood assumptions such as the hardness of factoring or discrete log.
1. Hash Functions and Authentication
Suppose is a collision-resistant hash function and is the hash function derived from the Merkle-Damgård transform.
Two popular schemes for message authentication involve using a key , and authenticating a message as either
The first scheme has a serious problem: given the tag of a message of length , we can compute the tag of any message that starts with .
The NMAC scheme works roughly as a scheme of the second type, but with two keys, the first used in place of IV in the Merkle-Damgård transform, the second put at the end of the message.
This is secure assuming that (where is the fixed-length hash function) is a secure MAC for fixed length messages.
An alternative scheme (which is easier to implement given current cryptographic libraries) is HMAC, which uses as a first key and as a second key, where and are two fixed strings. This is secure if, in addition to the assumptions that make NMAC secure, we have that the mapping
is a pseudorandom generator.
2. The AES Pseudorandom Permutation
AES is a pseudorandom permutation with and , or . It was the winner of a competition run by NIST between 1997 and 2000 to create a new encryption standard to replace DES (which had and was nearly broken by that time).
The conjectured security of practical pseudorandom permutations such as AES does not rely on the hardness of a well-defined computational problem, but rather on a combination of design principles and of an understanding of current attack strategies and of methods to defy them.
AES keeps a state, which is initially equal to the input, which is a matrix of bytes. The state is processed in 4 stages. This processing is done 10, 12, or 14 times (depending on key length), and the final state is the output.
- In the first stage, a 128-bit string derived from the key (and dependent on the current round) is added to the state. This is the only stage that depends on the key;
- A fixed bijection (which is part of the specification of AES) is applied to each byte of the state
- The rows of the matrix are shifted (row is shifted places)
- An invertible linear transformation (over the field ) is applied to the matrix
The general structure is common to other conjecturally secure pseudorandom permutations:
- There is one (or more) small “random-like” permutations that are hard-wired in the construction, such as in AES. Traditionally, those hard-wired functions are called “S-boxes.”
- A “key-scheduler” produces several “pseudorandom” strings from the key. (Usually, the scheduler is not a true pseudorandom generator, but does something very simple.)
- The construction proceeds in several rounds. At each round there is some combination of:
- “Confuse:” apply the hard-wired S-boxes locally to the input (Stage 2 in AES)
- “Diffuse:” rearrange bits so as to obscure the local nature of the application of the S-boxes (Stages 3 and 4 in AES)
- “Randomize:” use a string produced by the key-scheduler to add key-dependent randomness to the input (Stage 1 in AES)