Symmetric-Key Cryptography

Lecturer: Tom Roeder
Lecture notes by Tom Roeder


Table of Contents

1 One-key operations: Symmetric Cryptography

A Message Authentication Code (MAC) is a keyed scheme that provides authentication, like a signature, but only between two hosts. A MAC takes a key k and a message m and produces a tag t = MAC(m, k) such that it is hard for anyone that does not know k to produce a tag t' and message m' such that t' = MAC(m', k).

One well-studied and popular MAC, called HMAC, uses hash functions to compute a MAC. It is constructed as follows, where || represents concatenation:

HMAC(m, k) = h( (k XOR opad) || h( (k XOR ipad) || m) )

where opad = (01011100) and ipad = (00110110). The values of opad and ipad were carefully chosen to ensure that each input bit of the message affects all the bits of the output.

A MAC is an instance of a one-key primitive built on a zero-key primitive. MACs achieve integrity. A major goal of one-key or symmetric cryptography primitives, however, is to enable confidential communication between two parties.

1.1 High level and history

1.1.1 Motivation: Confidential Communication

Alice and Bob are spending their last few moments together before being separated. How can they pass information confidentially once they're separated? One idea would be to share a key now that they could later use to encode their communication. Confidential communication is one of the original motivating problems in cryptography. Early techniques for confidential communication used simple permutations and letter-rearranging games, but the 20th century saw cryptography move squarely into the domain of mathematics.

1.1.2 DES and modern cryptography

Much of the development of modern cryptography was spurred on by the acceptance, in 1976 of an algorithm from IBM (with collaboration by the NSA) that became the Data Encryption Standard (DES), a federal standard for shared-key encryption. Cryptographers at the time worried that the NSA had modified the algorithm to make it weaker, reducing the effective key length to 56 bits from 64 bits and modifying some of the internal structures. A great deal of research in the ensuing decades went into cryptanalysis of DES and related schemes. In the early 90's, however, the (public) discovery of differential cryptanalysis made it clear that no structural weaknesses had been introduced. In fact, differential cryptanalysis of DES revealed that IBM and the NSA knew about differential cryptanalysis 20 years earlier, since internal DES structures were much more resistant to this form of attack than they would have been if they had been chosen at random.

The secretive process by which DES was chosen and modified was a major cause of concern and distrust in the cryptographic community. More recently, the Advanced Encryption Standard (AES) was chosen as a replacement for DES via a much improved and entirely public process of proposals and cryptanalysis.

1.2 Definitions for Encryption

To define shared-key encryption, we first assume that a key is shared between two principals. Later lectures will show how to discharge this sharing obligation under different setup assumptions.

For our purposes, an encryption scheme consists of two functions, an Encryption function E that takes a key and a message (known as the plaintext) and outputs an encoded message (known as the ciphertext), and a decryption function D that takes a key and a ciphertext and outputs plaintext. When there is no possibility of confusion about the encryption function being used, a message m encrypted under a key k is written {m}k. Two main properties should hold for an encryption function.

  1. (Completeness) Given any message m and key k, encrypted messages can always be decrypted: Dk(Ek(m)) = m.
  2. (Semantic Security) Loosely speaking, this property requires that it is hard to invert an encryption function without knowing the key. To state this property more formally requires a notion of the appropriate attack model: an adversary that attempts to break the scheme might have various sources of information.

Semantic Security can only be achieved under probabilistic encryption schemes, but most common schemes are deterministic. One way to get a probabilistic scheme from deterministic scheme is to concatenate a random string to the message before encrypting: E'k(m) = Ek(m || r). Then decryption simply removes the random string: D'k(m || r) = m.

1.3 Nonces

A nonce is a bit string that satisfies Uniqueness (also known as Freshness), which means that it has not occurred before in a given run of a protocol. Nonces might also satisfy Unpredictability, which effectively requires pseudo-randomness: no adversary can predict the next nonce that will be chosen by any principal. There are several common sources of nonces.

1.4 One-Time Pad Encryption

Given the attack models and definitions of encryption shown above, it may seem that encryption schemes must be very complex to construct. Although there are many complex and useful encryption schemes, there is at least one scheme that is provably, perfectly secure. It just happens not to be practical in most contexts. This scheme is called One-Time Pad (OTP) encryption and was proven to be secure by Shannon in 1949. The functions are computed as follows: A and B agree on a random number k that is as long as the message they later want to send.

Note that since k is chosen at random and not known to an adversary, the output of this scheme is indistinguishable to an adversary from a random number. But it suffers from several drawbacks.

1.5 Types and Modes of Encryption

Encryption functions normally take a fixed-size input to a fixed-size output, so encryption of longer units of data must be done in one of two ways: either a block is encrypted at a time and the blocks are somehow joined together to make the ciphertext, or a longer key is generated from a shorter one and XOR'd against the plaintext to make the ciphertext. Schemes of the former type are called block ciphers, and schemes of the latter type are called stream ciphers.

1.5.1 Block ciphers

Block ciphers take as input the key and a block, often the same size as the key. Further, the first block is often augmented by a block called the initialization vector, which can add some randomness to the encryption.

1.5.2 Stream ciphers

Unlike block ciphers, stream ciphers (such as RC4) produce a pseudo-random sequence of bits that are then combined with the message to give an encryption. Since the combining operation is often XOR, naive implementations of these schemes can be vulnerable to the sort of bit-flipping attacks on Non-Malleability that we have seen before.

Two types of stream ciphers exist: synchronous, in which state is kept by the encryption algorithm but is not correlated with the plaintext or ciphertext, and self-synchronizing, in which some information from the plaintext or ciphertext is used to inform the operation of the cipher.

1.5.3 Degenerate Keys and IVs

Depending on the particular encryption scheme, some choices of keys and IVs are not recommended. For instance, it is never recommended to use a key as an initialization vector; some attacks can on block ciphers reveal the IV. Normally it is recommended that the IV be chosen randomly each time.

Similarly, some encryption schemes have a small number of weak keys that do not produce as random an output as encryption under other keys would. Cryptographic libraries normally provide key generation functions that avoid producing such keys.

1.6 Practical Examples

1.6.1 DES

The history of DES was discussed above. It was the first encryption algorithm to be publicly certified by the NSA, and it stimulated great interest in block ciphers. DES runs 16 rounds of an iterated block cipher on a block size 64 with a 56-bit key (there are other bits in the key that are used for other purposes). DES is no longer secure; with modern hardware, the entire space of keys can be searched in short order.

An obvious simple improvement to DES would be to encrypt encryptions with a second key: 2DESk1, k2(m) = DESk1(DESk2(m)). 2DES turns out to be vulnerable to attacks called meet-in-the-middle, which reduces the security to the security of DES. So, the common replacement for DES is 3DES, also called TripleDES: 3DESk1, k2, k3 = DESk1(DESk2(DESk3(m))). TripleDES has an effective key length of 112 bits, well outside the range of current brute force attacks. But there is a new encryption standard that is recommended for use instead of DES.

1.6.2 AES

The Advanced Encryption Standard (AES) was chosen in 2001 as the winner of a 5-year contest to replace the then outdated and insecure DES. AES is a version of the Rijndael algorithm designed by Joan Daemen and Vincent Rijmen. AES is also an iterated block cipher, with 10, 12, or 14 rounds for key sizes 128, 192, and 256 bits, respectively.

AES provides high performance symmetric key encryption and decryption. Although multitudes of cryptographers have examined it over the last 10 years or so, no substantial attacks against the algorithm itself have been published, so far.