CS 513 System Security - Cryptosystem Design and AES

Cryptosystem Design and AES

Lecturer: Professor Fred B. Schneider

Lecture notes by Jed Liu

Cryptosystem Design

With cryptosystems, we desire perfect secrecy, meaning the probability that the contents of some intercepted data corresponds to some plaintext message is unaltered by knowledge of the ciphertext for that message.

Ideally, attacking a cryptosystem should require a brute-force search of the key space. This leads to measuring the strength for cryptosystem by what is known as its work factor, the amount of time needed to decipher a message without knowledge of the key. A cryptosystem is considered secure when its workfactor is exponential in the length of the key: 2^keylen.

Here are some general goals for designing secure encryption algorithms:

confusion: obscuring the connection between the characters in the plaintext and those in the ciphertext. Substitution is a form of this. Note that having confusion does not prevent an attacker from tampering with an encrypted message in a controlled manner and, thereby, causing specific changes to the meaning of plaintext.
diffusion: any change in the key or plaintext causes many characters in the ciphertext to change. The idea is to spread change in the key or plaintext throughout the ciphertext. Permutation is a simple form of diffusion.

As a general rule of thumb, a good encryption algorithm would satisfy the following two criteria:

No output bit should be a linear function of the input bits. In other words, the algorithm must induce non-linearity. This ensures confusion.
Avalanche Criteria: the probability of changing a given bit in the output is ½ when any subset of the input bits are complemented.

Types of Cryptographic Functions

There are three classes of cryptographic functions:

Secret key (symmetric): involves 1 key, known as the secret key
Public key (asymmetric):involves 2 keys, known as the private & public keys
hash: involves 0 keys

Birth of the Advanced Encryption Standard (AES)

AES is currently the the US "standard" secret key cryptosystem, replacing DES (Data Encryption Standard, adopted in 1977). AES is the result of a three year competition. This competition was announced in September 1997 and had entries from 12 different countries. Reviewers from the U.S. and abroad helped narrow the 15 submissions down to five finalists. The one submission that eventually won was called "Rijndael" and was invented by two Belgians, Joan Daemen and Vincent Rijmen.

The fact that this was an international contest acknowledges the existence of strong foreign cryptographers. This is consistent with prior U.S. experience with DES --- all successful attacks on DES were done by people in Israel and Japan. The international nature of the AES selection process is also important, since it paves the way for AES to be used for international commerce.

A Brief History of DES --- How we got to AES

In the early 1970s, the National Security Agency (NSA) and the National Bureau of Standards (NBS, now known as the National Institute of Standards and Technology, or NIST) saw the need for a civilian encryption algorithm. In 1974, IBM proposed "Lucifer", an encryption algorithm that uses 64-bit keys. Two years later, NBS (in consultation with NSA) made a modified version of that algorithm into a standard.

DES takes in 64 bits of data, employs a 56-bit key, and executes 16 cycles of substitution and permutation before outputting 64 bits of encrypted data.

In the summer of 1998, the Electronic Frontier Foundation (EFF) built a DES cracker machine at a cost of $250,000. It had 1536 chips, worked at a rate of 88 billion keys per second, and was able to break a DES encrypted message in 56 hours. One year later, with the cracker working in tandem with 100,000 PCs over the Internet, a DES encrypted message was cracked in only 22 hours.

One common way to make DES more secure today is to encrypt three times using DES. This is known as triple-DES (3DES). 3DES is extremely slow, so a better algorithm was needed.

Requirements for AES

Here's what the contestants were up against in proposing an algorithm for AES:

AES had to be a private key algorithm. I.e. it had to use a shared secret key.
It had to support the following key sizes:
- 128 bits ( = 3.4 x 10³⁸ keys, equivalent to 2560-bit RSA)
- 192 bits ( = 6.2 x 10⁵⁷ keys)
- 256 bits ( = 1.1 x 10⁷⁷ keys)
DES uses only 56-bit keys, giving a key space of 7.2 x 10¹⁶ keys. So, if you were able to search half the DES key space in 1 second, then on average, it would take 149 trillion years to crack a 128-bit AES key. (The universe is at most 20 billion years old!)
It had to satisfy certain engineering criteria: performance, efficiency, implementability, and flexibility. And Rijndael can be implemented easily in both hardware and software, is amenable to instruction-level parallelism, and has realizations that require little memory (so the algorithm can be used in smartcards).
It had to be what is called a block cipher --- an encryption algorithm structured in terms of an internal function and runs that function repeatedly on the input. Each iteration is called a round; AES uses 10 rounds.
AES is also an instance of a Feistel cipher, a special case of a block cipher. The input to such a cipher consists of 2t bits. The input is first divided into 2 parts: L₀ and R₀. The cipher then proceeds in rounds. In the i-th round,
- L_i := R_i-1
- R_i := L_i-1 XOR f(R_i-1, k_i),

where f is some function (all the magic is here!), and k_i is some number derived from the key, to be used in round i.

IDEA --- International Data Encryption Algorithm

IDEA, originally named the Improved Proposed Encryption Standard (IPES), was designed to be efficient in software. It was developed by Xuejia Lai and James Massey in 1991. It operates on a 64-bit plaintext data block and uses a 128-bit key. IDEA is used in PGP to encrypt messages.