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 bruteforce 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 nonlinearity. 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 64bit 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 56bit 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 tripleDES (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^{38} keys, equivalent to 2560bit RSA)
 192 bits ( = 6.2 x 10^{57} keys)
 256 bits ( = 1.1 x 10^{77} keys)
DES uses only 56bit keys, giving a key space of 7.2 x 10^{16} 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 128bit 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 instructionlevel 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_{0} and R_{0}. The cipher then
proceeds in rounds. In the ith round,
 L_{i} := R_{i1}
 R_{i} := L_{i1} XOR f(R_{i1}, 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 64bit plaintext data block and uses a
128bit key. IDEA is used in PGP to encrypt messages.
Related Links
In order of appearance: