Block ciphers and modes of operation. DES, AES.
PV018 Vašek Matyáš
External resources
•   Figures used:
http'J/williamstallings. com/Security2e. html
•   Some slides provided by Henric Johnson, Blekinge Inst, of Techn., Sweden (link above)
•   AES standard, etc. (2 presentations in-class) http://csrc. n ist go v/Crypto Toolkit/aes/rijndael/misc/nissc2.pdf
Conventional Encryption
Principles
•   Ar\ encryption scheme has five ingredients:
-  Plaintext
-  Encryption algorithm
-  Secret Key
-  Ciphertext
-  Decryption algorithm
•   Security depends on the secrecy of the key, not the secrecy of the algorithm!
-  Kerckhoff principle
Conventional Encryption
Principles
Secret key shared by sender and recipient
Secret key shared by sender and recipient
Transmitted ciphertext
Plaintext input
y		?	
			
			
			
			
			^^^^__
			
			
Encryption algorithm (e.g.,DES)
Decryption algorithm
(reverse of encryption
algorithm)
Plaintext output
Figure 2.1   Simplified Model of Conventional Encryption
Cryptography
• Classified along three independent dimensions:
-  The type of operations used for transforming plaintext to ciphertext
-  The number of keys used
•  symmetric (single key)
•  asymmetric (two-keys, or public-key encryption)
-  The way in which the plaintext is processed
Average time required for exhaustive key search
Key Size (bits)	Number of Alternative Keys	Time required at 106 Decryption///s
32	232 = 4.3xl09	2.15 milliseconds
56	256 = 7.2xl016	10 hours
128	2128=3.4xl038	5.4 x 1018 years
168	2168=3.7xl050	5.9 xlO30years
Feistel ciphers
•   Block manipulation, with the block
-  Not too small - cipher would not be complicated
-  Not too big - permutations would be complicated
•   Substitution performed on left half of data
-  Round function applied on the right half
-  XORing with the left half
•   Permutation - exchange of the two halves
•   Parameters: key size, block size, number of rounds
Plaintext (2w bits)
Round 1
K,
Round i
K;
Round n
Ciphertext (2w bits)
Figure 3.5 Classical Feistel Network
Conventional Encryption
Algorithms
• Data Encryption Standard (bES)
-  The most widely used encryption scheme
-  The algorithm \s reffered to the Data Encryption Algorithm (OEA)
-  DES is a block cipher
-  The plaintext is processed in 64-bit blocks
-  The key is 56-bits m length
DES - Data Encryption Standard
•   IBM cipher LUCIPHER, modified(!)
-  LUCIPHER - H. Feistel, project for Lloyd's Bank (UK)
-  128bit key-length reduced to 56 bits
-  Design of S-boxes classified
•   US standard in 1977, last renewal in 1994
-  NBS/NIST - FIPS PUB 46
•   64 bit blocks of input/output
•   56 bit key (64 with parity bits)
•   Weak keys (4): Ek(x) = x
•   Semi-weak keys (6 pairs): Ek2( Ekx (x)) = x
64-bit plaintext
56-bit key
Ü
i
Initial Permutation
I
J
Permuted Choice 1
Round 1
i
>
Kl
Permuted Choice 2
H
i
i
Left circular shift
Round 2
>
K2
Permuted Choice 2
H
I
J
Left circular shift
)
C
Round 16
Kl6
C
I
)*46    r                          \      (                 \
4-------------1 Permuted Choice 2 M-----    Left circular shift
32-bit Swap
i
)
f       Inverse Initial        | ^        Permutation        _J
64-bit ciphertext
Figure 3.7   General Depiction of DES Encryption Algorithm
32 bits-
-32 bits-
-28 bits-
-28 bits-
U-i
R*-i
Q-i
D*-l
Expansion/permutation (E table)
/
/
_____±_____
Left shift(s)
Left shift(s)
]
48
XORH-
■á-*r
48
Substition/choice (S-box)
/
/
7
32
Permutation (P)
/
/
32
r____________________J
-►TxORJ
Permutation/contraction (Permuted Choice 2)
7
R;
c«
D*
Figure 3.8   Single Round of DES Algorithm
DES
•  The overall processing at each iteration:
- Li = Ri-i
- Ri = Li-i ® F(Ri-i, Ki)
•  Concerns about:
- The algorithm and the key length (56-bits)
Time to break a code (106
decryptions/j/s)
1U" 104(l 1036 1032 8   102* B   1024 3    l02O 10,ň 10'2 10s HI4 10° lrt-4						
						
						
						
						
						
						
						
						
						
						
						
5056
100
128
150      168
200
Key length (bits)
Breaking DES
•   1977 Diffie & Hellman - design ($20M)
•   1993 M. Wiener - chip design
-  $10M- 21 minutes
-  $1M- 3.5 hours
-  $100k- 35 hours
•   1997 DES-breaking, 70'000 systems, 96 days
•   1998 EFF DES-breaking machine built
-  Special circuits, PC-master
-  $200'000
-  Breaking keys in single hours
DES-based ciphers
•  Double DES: Ek2( Ek, (x))
•  Triple DES (3-DES-3):
- Diffie-Hellman: Ek3( Ek2( Ek^x)))
- Merkle: Ek3 (Dk2 ( Ek, (x)))
•  Triple DES (3-DES-2): Ek, ( Dk, ( Ek, (x)))
DES cryptanalysis
•   Linear cryptanalysis
-  Finding a linear approximation of DES transformation
-  Matsui, Eurocrypť93
-  DES key can be found from 247 known plaintexts
•   Differential cryptanalysis
-  Starting with two plaintext with known XOR difference
-  Determining key bits one after another
-  Murphy ('90), Biham-Shamir (93)
-  Only successful against DES up to eight rounds (214 chosen plaintexts then needed)
-  Standard DES - 0(247), 247 chosen plaintexts needed
Other block ciphers
IDEA: 128bit key, blocks of 64 bit
Blowfish: variable key-length up to 448 bits, 64bit blocks, fast, relatively compact (runs in less than 5K of memory)
RC5: variable key-length up to 2040 bits, 32-,64-, 128-bit blocks, fast, simple
CAST-128: variable key-length 40-128 bits (mult. 8), 64bit blocks
RC2, GHOST, LOKI, FEAL,SQUARE
(DES) Modes of operation -
Block Modes
•  Electronic Codebook Book (ECB)
• the message is broken into independent 64-bit blocks
that are individually encrypted
• C, = DESK1 (P,)
•  Cipher Block Chaining (CBC)
• the message is also broken into 64-bit blocks, but these are linked together in the encryption operation (starting
with an initial vector/value IV)
• Q = DESK1 (Pi ® CM), where d = IV
(DES) Modes of operation -
Stream Modes
•   Cipher FeedBack (CFB)
• the message is treated as a stream of bits, added to the output of the DES, with the result being fed back for the next stage
•  Q = Pj ® DESK1 (CM), where CA = IV
•   Output FeedBack (OFB)
• the message is also treated as a stream of bits, added to the message, but with the feedback being independent of the
message
• Q = Pj (x) O; where O; = DES^O^), and 0.!= IV
Time = 1 Pi
K
DES
Encrypt
I
(a) Encryption
K
Time = 2 p2
DES
Encrypt
T
]
K
Time = TV Ptv
DES
Encrypt
T
]
-TV
K
i
DES
Decrypt
I
(b) Decryption
K
i
-TV
DES
Decrypt

]
K
i
DES
Decrypt

]
TV
Figure3.11   Electronic Codebook (ECB) Mode
ECB issues
•  Repetitions in message can be reflected in ciphertext!!!
- E.g., with messages that change very little, which become a code-book analysis problem
•  Reason - enciphered message blocks are independent of each other.
Time = 1
K
DES
Encrypt
T
(a) Encryption
K
i
DES
Decrypt
rv
1
(b) Decryption
K
K
DES
Encrypt
T
U
i
___J"     DES      "I
w\     Decrypt      |
T
T
Figure 3.12 Cipher Block Chaining (CBC) Mode
CBC issues
•   Each ciphertext block is dependent on all message blocks before it
-  I.e., a change in the message affects the ciphertext block after the change as well as the original block.
•   Initial Value (IV) must be known by both sender and receiver!
-  IV cannot be sent in clear - must either be a fixed value or be sent encrypted in ECB mode before rest of message
•   Caution - end of the message, have to handle a possible last "short" block -padding.
IV
Shift register 64 -j bits I j bits
K-
~Kľ
DES
Encrypt
T^ľ
Select       Discard j bits  |     64 -j bits
1
Shift register 64 -j bits I j bits
K-
I
DES
Encrypt
I
Select       Discard j bits  |     64 - j bits
+ )-----7^-----►Cl        (+
■c2
CM-1"
1
Shift register 64 -j bits I j bits
K-
•       •      •
I
DES
Encrypt
I
Select       Discard j bits |     64 -j bits
-►CM
Pi (a) Encryption
IV
Shift register 64 -j bits I j bits
K-
I
DES
Encrypt
I
Select       Discard j bits  |     64 -j bits
1
Shift register 64 -j bits I j bits
K-
I
DES
Encrypt
I
Select       Discard j bits  |     64 - j bits
CM-V
1
Shift register 64 -j bits I j bits
K-
I
DES
Encrypt
•       •      •
Pi (b) Decryption
I
Select       Discard j bits |     64 -j bits
Figure 3.13 J-Bit Cipher Feedback (CFB) Mode
CFB issues
•   Use when data is bit or byte oriented - a stream mode.
•   The block cipher is use in encryption mode at both ends, with input being a feed-back copy of the ciphertext
•   Can vary the number of bits fed back, trading off efficiency for ease of use.
•   Errors also propagate for several blocks after the error (given by the size of feedback register and shift value).
IV________
Shift register 64 -j bits I j bits
K-
I
DES
Encrypt
I
Select       Discard j bits  |     64 -j bits
ř
pi
(a) Encryption IV
Cl
Shift register 64 -j bits I j bits
K-
I
DES
Encrypt
I
Select       Discard j bits  |     64 -j bits
Pi (b) Decryption
1
Shift register 64 -j bits I j bits
K-
I
DES
Encrypt
I
Select       Discard j bits  |     64 -j bits
1
Shift register 64 -j bits I j bits
K-
I
DES
Encrypt
I
Select       Discard j bits  |     64 -j bits
°M-V
1
Shift register 64 -j bits I j bits
K-
I
DES
Encrypt
•      •       •
I
Select       Discard j bits  |     64 -j bits
f
CM
Pm
°M-V
1
Shift register 64 -j bits I j bits
K-
I
DES
Encrypt
•      •       •
I
Select       Discard j bits  |     64 -j bits
Figure 3.14   J-Bit Output Feedback (OFB) Mode
OFB issues
•   Intended for use where the error feedback is a problem, or where the encryptions (expensive operations) should be done before the message is available.
•   Difference from CFB: the feedback is from the output of the block cipher and is independent of the message, a variation of a Vernam cipher.
•   Again, an IV is needed; and sender and receiver must remain in sync, and some recovery method is needed to ensure this occurs!!!
Advanced Encryption Standard
Exercise
Rumors from NIST in 1996
January 1997 - Official announcement
September 1997 - Call for Proposals
August 1998 - 15 candidates announced
August 1999 - 5 finalists
2 October 2000 - Choice of algorithm
Late 2000, early 2001 - First implementations (PGP 7.0.3)
Spring 2001 - Standard - FIPS
AES finalists
MARS (IBM)
-  high security, large ROM req., no good HW impl.
RC6 (RSA Labs)
-  adequate security, moderate ROM req., average HW impl.
Rijndael (Rijmnen, Daemen - Belgium!)
-  adequate security, fast-SW, low memory req., fast-HW
Serpent (Anderson, Biham, Knudsen)
-  high security, low memory req., slow-SW, fast-HW
Twofish (Schneier et al.)
-  adequate security, high ROM req., average HW impl.
AES-Rijndael
•  Input & Output: 128 bits
•  Key: 128, 192 or 256 bits
•  Processing by bytes - basic units
•  Operations - addition (XOR), multiplication
•   10, 12 or 14 rounds (given by key length)
- Initial Round Key addition
- Last Round slightly different
AES-Rijndael (cont'd)
•    PDF slides from the algorithm authors
http://csrc.nist.gov/CryptoToolkit/aes/rijndael/misc/nissc2.pdf
•    Neat Rijndael animation...
http://www.esat.kuleuven.ac.be/-rijmen/rijndael/Rijndael_Anim.zip
Suggested reading
• A Performance Comparison of the Five AES Finalists - B Schneier, D Whiting
•   http://csrc.nist.gov/CryptoToolkit/aes/round2/conf3/papers/ 17-bschneier.pdf