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: 2keylen.

Here are some general goals for designing secure encryption algorithms:

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

Types of Cryptographic Functions

There are three classes of cryptographic functions:

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: where f is some function (all the magic is here!), and ki 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.

Related Links

In order of appearance: