Cryptosystem Design and AES
Lecturer: Professor Fred B. Schneider
Lecture notes by
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:
- 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
- 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
- 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
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.
- AES had to be a private key algorithm. I.e. it had to use a shared
- It had to support the following key sizes:
DES uses only 56-bit keys, giving a key space of 7.2 x 1016 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!)
- 128 bits ( = 3.4 x 1038 keys, equivalent to 2560-bit RSA)
- 192 bits ( = 6.2 x 1057 keys)
- 256 bits ( = 1.1 x 1077 keys)
It had to satisfy certain engineering criteria:
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: L0 and R0. The cipher then
proceeds in rounds. In the i-th round,
- Li := Ri-1
- Ri := Li-1 XOR f(Ri-1, ki),
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.
In order of appearance: