CM30173: Cryptography
eserved@d =[@let@token art II
CM30173:
Cryptography
Part II
After DES: Triple
DES
Double-DES?
Triple-DES?
After DES: The
Advanced
Encryption
Standard
A new competition
Rijndael: The chosen
cipher
Security of AES
After DES: Triple DES
After DES: The Advanced Encryption Standard
Part II
Private-key cryptography: block ciphers
CM30173: CryptographyPart II
CM30173:
Cryptography
Part II
After DES: Triple
DES
Double-DES?
Triple-DES?
After DES: The
Advanced
Encryption
Standard
A new competition
Rijndael: The chosen
cipher
Security of AES
After DES: Triple DES
After DES: The Advanced Encryption Standard
Double-DES?
Triple-DES?
Triple DES? Two variants
Variant 1: Three keys
Select three independent keys k1, k2, k3. Encryption is
defined by
e(k1,k2,k3)(x) = e
DES
k3
(dDESk2 (e
DES
k1
(x)))
Variant 2: Two keys
Select two independent keys k1, k2. Encryption is
defined by
e(k1,k2)(x) = e
DES
k1
(dDESk2 (e
DES
k1
(x)))
CM30173: CryptographyPart II
CM30173:
Cryptography
Part II
After DES: Triple
DES
Double-DES?
Triple-DES?
After DES: The
Advanced
Encryption
Standard
A new competition
Rijndael: The chosen
cipher
Security of AES
After DES: Triple DES
After DES: The Advanced Encryption Standard
Double-DES?
Triple-DES?
Security of Triple-DES
Variant 1:
Naive exhaustive search: 2168
Meet in the middle attack: 2112
Variant 2:
Naive exhaustive search: 2112
Di↵erential and linear cryptanalysis become more
di�cult
CM30173: CryptographyPart II
CM30173:
Cryptography
Part II
After DES: Triple
DES
Double-DES?
Triple-DES?
After DES: The
Advanced
Encryption
Standard
A new competition
Rijndael: The chosen
cipher
Security of AES
After DES: Triple DES
After DES: The Advanced Encryption Standard
Double-DES?
Triple-DES?
3DES: the standard
Triple-DES or 3DES became the standard,
replacing DES in 1999.
It continues to be used in many systems.
AES will replace 3DES but currently coexist as
FIPS approved algorithms.
Why was a replacement still needed?
Small block size
Speed
Implementation inconveniences
CM30173: CryptographyPart II
CM30173:
Cryptography
Part II
After DES: Triple
DES
Double-DES?
Triple-DES?
After DES: The
Advanced
Encryption
Standard
A new competition
Rijndael: The chosen
cipher
Security of AES
After DES: Triple DES
After DES: The Advanced Encryption Standard
Double-DES?
Triple-DES?
3DES: the standard
Triple-DES or 3DES became the standard,
replacing DES in 1999.
It continues to be used in many systems.
AES will replace 3DES but currently coexist as
FIPS approved algorithms.
Why was a replacement still needed?
Small block size
Speed
Implementation inconveniences
CM30173: CryptographyPart II
CM30173:
Cryptography
Part II
After DES: Triple
DES
Double-DES?
Triple-DES?
After DES: The
Advanced
Encryption
Standard
A new competition
Rijndael: The chosen
cipher
Security of AES
After DES: Triple DES
After DES: The Advanced Encryption Standard
Double-DES?
Triple-DES?
3DES: the standard
Triple-DES or 3DES became the standard,
replacing DES in 1999.
It continues to be used in many systems.
AES will replace 3DES but currently coexist as
FIPS approved algorithms.
Why was a replacement still needed?
Small block size
Speed
Implementation inconveniences
CM30173: CryptographyPart II
CM30173:
Cryptography
Part II
After DES: Triple
DES
Double-DES?
Triple-DES?
After DES: The
Advanced
Encryption
Standard
A new competition
Rijndael: The chosen
cipher
Security of AES
After DES: Triple DES
After DES: The Advanced Encryption Standard
A new competition
Rijndael: The chosen cipher
Security of AES
Timeline
Jan 1997: NIST (formally the NBS) begins the
process of choosing a replacement for DES.
Sept 1997: Formal call for algorithms
June 1998: Submissions due
August 1998: First AES Candidate Conference
March 1999: Second AES Candidate Conference
August 1999: 5 finalists are selected by NIST
April 2000: Third AES Candidate Conference
Oct 2000: Rijndael selected
Feb 2001: Draft is made available for public review
and comment
Nov 2001: AES adopted as a standard and FIPS
publication 197 is published
CM30173: CryptographyPart II
CM30173:
Cryptography
Part II
After DES: Triple
DES
Double-DES?
Triple-DES?
After DES: The
Advanced
Encryption
Standard
A new competition
Rijndael: The chosen
cipher
Security of AES
After DES: Triple DES
After DES: The Advanced Encryption Standard
A new competition
Rijndael: The chosen cipher
Security of AES
Criteria and evaluation
Necessary criteria:
Block length: 128 bit
Support key lengths of 128, 192 and 256 bits
Should be available worldwide on a royalty free
basis
Evaluated according to
security
cost
algorithm and implementation characteristics
CM30173: CryptographyPart II
CM30173:
Cryptography
Part II
After DES: Triple
DES
Double-DES?
Triple-DES?
After DES: The
Advanced
Encryption
Standard
A new competition
Rijndael: The chosen
cipher
Security of AES
After DES: Triple DES
After DES: The Advanced Encryption Standard
A new competition
Rijndael: The chosen cipher
Security of AES
Criteria and evaluation
Necessary criteria:
Block length: 128 bit
Support key lengths of 128, 192 and 256 bits
Should be available worldwide on a royalty free
basis
Evaluated according to
security
cost
algorithm and implementation characteristics
CM30173: CryptographyPart II
CM30173:
Cryptography
Part II
After DES: Triple
DES
Double-DES?
Triple-DES?
After DES: The
Advanced
Encryption
Standard
A new competition
Rijndael: The chosen
cipher
Security of AES
After DES: Triple DES
After DES: The Advanced Encryption Standard
A new competition
Rijndael: The chosen cipher
Security of AES
Criteria and evaluation
Necessary criteria:
Block length: 128 bit
Support key lengths of 128, 192 and 256 bits
Should be available worldwide on a royalty free
basis
Evaluated according to
security
cost
algorithm and implementation characteristics
CM30173: CryptographyPart II
CM30173:
Cryptography
Part II
After DES: Triple
DES
Double-DES?
Triple-DES?
After DES: The
Advanced
Encryption
Standard
A new competition
Rijndael: The chosen
cipher
Security of AES
After DES: Triple DES
After DES: The Advanced Encryption Standard
A new competition
Rijndael: The chosen cipher
Security of AES
Criteria and evaluation
Necessary criteria:
Block length: 128 bit
Support key lengths of 128, 192 and 256 bits
Should be available worldwide on a royalty free
basis
Evaluated according to
security
cost
algorithm and implementation characteristics
CM30173: CryptographyPart II
CM30173:
Cryptography
Part II
After DES: Triple
DES
Double-DES?
Triple-DES?
After DES: The
Advanced
Encryption
Standard
A new competition
Rijndael: The chosen
cipher
Security of AES
After DES: Triple DES
After DES: The Advanced Encryption Standard
A new competition
Rijndael: The chosen cipher
Security of AES
Criteria and evaluation
Necessary criteria:
Block length: 128 bit
Support key lengths of 128, 192 and 256 bits
Should be available worldwide on a royalty free
basis
Evaluated according to
security
cost
algorithm and implementation characteristics
CM30173: CryptographyPart II
CM30173:
Cryptography
Part II
After DES: Triple
DES
Double-DES?
Triple-DES?
After DES: The
Advanced
Encryption
Standard
A new competition
Rijndael: The chosen
cipher
Security of AES
After DES: Triple DES
After DES: The Advanced Encryption Standard
A new competition
Rijndael: The chosen cipher
Security of AES
Rijndael: The chosen cipher
Invented by two Belguim researchers: Daemen and
Rijmen
Iterated cipher with structure similar to an SPN
Number of round depends on key size:
key size: 128 192 256
Nr 10 12 14
CM30173: CryptographyPart II
CM30173:
Cryptography
Part II
After DES: Triple
DES
Double-DES?
Triple-DES?
After DES: The
Advanced
Encryption
Standard
A new competition
Rijndael: The chosen
cipher
Security of AES
After DES: Triple DES
After DES: The Advanced Encryption Standard
A new competition
Rijndael: The chosen cipher
Security of AES
Representation of state
In the 128 bit case, for instance, the plaintext is 16
bytes long: x0x1 . . . x15
state is represented as a 4 by 4 array of bytes:
x0 x4 x8 x12
x1 x5 x9 x13
x2 x6 x10 x14
x3 x7 x11 x15
CM30173: CryptographyPart II
CM30173:
Cryptography
Part II
After DES: Triple
DES
Double-DES?
Triple-DES?
After DES: The
Advanced
Encryption
Standard
A new competition
Rijndael: The chosen
cipher
Security of AES
After DES: Triple DES
After DES: The Advanced Encryption Standard
A new competition
Rijndael: The chosen cipher
Security of AES
SubBytes(state)
The state array is substituted byte by byte, each
substitution uses the same S-box.
It is represented as a 16 by 16 array with the rows
and columns indexed by hexadecimal numbers.
Unlike DES the AES S-box is algebraically
defined using operations in a finite field
CM30173: CryptographyPart II
CM30173:
Cryptography
Part II
After DES: Triple
DES
Double-DES?
Triple-DES?
After DES: The
Advanced
Encryption
Standard
A new competition
Rijndael: The chosen
cipher
Security of AES
After DES: Triple DES
After DES: The Advanced Encryption Standard
A new competition
Rijndael: The chosen cipher
Security of AES
ShiftRows(state)
a b c d
e f g h
i j k l
m n o p
�!
a b c d
f g h e
k l i j
p m n o
CM30173: CryptographyPart II
CM30173:
Cryptography
Part II
After DES: Triple
DES
Double-DES?
Triple-DES?
After DES: The
Advanced
Encryption
Standard
A new competition
Rijndael: The chosen
cipher
Security of AES
After DES: Triple DES
After DES: The Advanced Encryption Standard
A new competition
Rijndael: The chosen cipher
Security of AES
MixColumns(state)
A linear transformation (multiplication by a matrix
in the finite field) is applied to each column of the
state array
Each input byte a↵ects all output bytes
The e↵ect is to linearly combine the bytes in the
column
CM30173: CryptographyPart II
CM30173:
Cryptography
Part II
After DES: Triple
DES
Double-DES?
Triple-DES?
After DES: The
Advanced
Encryption
Standard
A new competition
Rijndael: The chosen
cipher
Security of AES
After DES: Triple DES
After DES: The Advanced Encryption Standard
A new competition
Rijndael: The chosen cipher
Security of AES
High level description
Algorithm (AES)
state = plaintext block
AddRoundKey(state,k0)
for r = 1 to Nr � 1 do
Substitution: SubBytes(state)
Permutation: ShiftRows(state)
Linear transformation: MixColumns(state)
AddRoundKey(state,kr)
end do
Substitution: SubBytes(state)
Permutation: ShiftRows(state)
AddRoundKey(state,kNr)
ciphertext block = state
CM30173: CryptographyPart II
CM30173:
Cryptography
Part II
After DES: Triple
DES
Double-DES?
Triple-DES?
After DES: The
Advanced
Encryption
Standard
A new competition
Rijndael: The chosen
cipher
Security of AES
After DES: Triple DES
After DES: The Advanced Encryption Standard
A new competition
Rijndael: The chosen cipher
Security of AES
Security of AES
Protection against di↵erential cryptanalysis:
The use of the finite field operation to construct
the S-box produces a di↵erence distribution table in
which entries are close to uniform
MixColumns, the linear transformation, promotes a
“wide trail” of active S-boxes
The best known attacks are on variants with a reduced
number of rounds ( 10).
Up to July 2009, AES was secure against all
cryptanalytic attacks. There were no known
attacks faster than exhaustive search.
CM30173: CryptographyPart II
CM30173:
Cryptography
Part II
After DES: Triple
DES
Double-DES?
Triple-DES?
After DES: The
Advanced
Encryption
Standard
A new competition
Rijndael: The chosen
cipher
Security of AES
After DES: Triple DES
After DES: The Advanced Encryption Standard
A new competition
Rijndael: The chosen cipher
Security of AES
Security of AES
Protection against di↵erential cryptanalysis:
The use of the finite field operation to construct
the S-box produces a di↵erence distribution table in
which entries are close to uniform
MixColumns, the linear transformation, promotes a
“wide trail” of active S-boxes
The best known attacks are on variants with a reduced
number of rounds ( 10).
Up to July 2009, AES was secure against all
cryptanalytic attacks. There were no known
attacks faster than exhaustive search.
CM30173: CryptographyPart II
CM30173:
Cryptography
Part II
After DES: Triple
DES
Double-DES?
Triple-DES?
After DES: The
Advanced
Encryption
Standard
A new competition
Rijndael: The chosen
cipher
Security of AES
After DES: Triple DES
After DES: The Advanced Encryption Standard
A new competition
Rijndael: The chosen cipher
Security of AES
Attacks on AES
There are known side-channel attacks on AES,
exploiting timing properties of its implementation on
known
In July 2009, researchers described di↵erent related key
attacks on AES. These are (variously):
Feasible for reduced-round versions of 256-bit AES
(245 complexity for a 10-round version).
Theoretically better than brute force but not
feasible (2119 complexity) for the full 14-round
version.
In 2011, a theoretical key-recovery attack on full AES
was published which is better than brute force by a
factor of about 4.
CM30173: CryptographyPart II