Cryptography Basics – Block ciphers and modes
ECEN 4133 Jan 26, 2021
Alternative to stream cipher:
Block Ciphers
Today’s most common block cipher: AES (Advanced Encryption Standard)
Designed by NIST competition, long public comment/discussion period Widely believed to be secure, but we don’t know how to prove it
Variable key size and block size
We’ll use 128-bit key, 128-bit block (also exist 192-bit and 256-bit versions)
Ten rounds: Split k into ten subkeys, performs set of operations ten times, each with diff. subkey
Each AES round 128-bits in, 128-bit sub-key, 128-bits out
Four steps:
picture as operations on a 4×4 grid of 8-bit values
1. Non-linear step
Run each byte thru a non-linear function (lookup table)
2. Shift step
Circular-shift each row: ith row shifted by i (0-3)
3. Linear-mix step
Treat each column as a 4-vector; multiply by a constant invertible matrix
4. Key-addition step
XOR each byte with corresponding byte of round subkey
To decrypt, just undo the steps, in reverse order
Remaining problem:
How to encrypt longer messages?
Padding
Can only encrypt in units of cipher blocksize, but message might not be multiples of blocksize Solution: Add padding to end of message
Must be able to recognize and remove padding afterward
Common approach:
Add n bytes that have value n
[Caution: What if message ends at a block boundary?]
Cipher modes
We know how to encrypt one block, but what about multiblock messages?
Different methods, called “cipher modes” Straightforward (but bad) approach:
ECB mode (encrypted codebook) Just encrypt each block independently Ci := Ek(Pi)
[Disadvantages? Solutions?]
Cipher modes
We know how to encrypt one block, but what about multiblock messages?
Different methods, called “cipher modes” Straightforward (but bad) approach:
ECB mode (encrypted codebook) Just encrypt each block independently Ci := Ek(Pi)
[Disadvantages? Solutions?]
Plaintext
Pseudorandom
ECB mode
Better (and common):
CBC mode (cipher-block chaining)
For each block Pi: Ci := Ek(Pi xor Ci-1)
(Need to generate random IV (“Initialization Vector”) at start)
[Pros and cons?]
IV
P0
P1
P2
…….
EK EK EK
C0
C1
C2
…….
Padding oracle attack
P1 = TT TT TT TT P2 = 68 65 6c 6c P3 = 6f ?? ?? ??
P1
P2
P3
EK EK EK
C1
C2
C3
Padding oracle attack
P1 =TTTTTTTT P2 = 68 65 6c 6c P3 = 6f 03 03 03
P1
P2
P3
EK EK EK
C1
C2
C3
Padding oracle attack
Decryption:
C1
C2
C3
EK EK EK
P1 = D(C1)IV P2 = D(C2)C1 P3 = D(C3)C2
P1
P2
P3
Padding oracle attack
C1
C2
C3
EK EK EK
D(C3)5b d8 99 ee C2 34 db 9a ed P3 6f 03 03 03
P1 = D(C1)IV P2 = D(C2)C1 P3 = D(C3)C2
P1
P2
P3
Padding oracle attack
C1
C2
C3
EK EK EK
D(C3)5b d8 99 ee C2 34 db 9a 00 P3 6f 03 03 ee
PADDING ERROR
P1 = D(C1)IV P2 = D(C2)C1 P3 = D(C3)C2
P1
P2
P3
Padding oracle attack
C1
C2
C3
EK EK EK
D(C3)5b d8 99 ee C2 34 db 9a 01 P3 6f 03 03 ef
PADDING ERROR
P1 = D(C1)IV P2 = D(C2)C1 P3 = D(C3)C2
P1
P2
P3
Padding oracle attack
C1
C2
C3
EK EK EK
D(C3)5b d8 99 ee C2 34 db 9a 02 P3 6f 03 03 ec
PADDING ERROR
P1 = D(C1)IV P2 = D(C2)C1 P3 = D(C3)C2
P1
P2
P3
Padding oracle attack
C1
C2
C3
EK EK EK
D(C3)5b d8 99 ee C2 34 db 9a .. P3 6f 03 03 ..
PADDING ERROR
P1 = D(C1)IV P2 = D(C2)C1 P3 = D(C3)C2
P1
P2
P3
Padding oracle attack
C1
C2
C3
EK EK EK
D(C3)5b d8 99 ee C2 34 db 9a ef P3 6f 03 03 01
MAC ERROR
P1 = D(C1)IV P2 = D(C2)C1 P3 = D(C3)C2
P1
P2
P3
Padding oracle attack
Original C2 : 34 db 9a ed ModifiedC2’:34 db 9a ef
D(C3)5b d8 99 ee C2 34 db 9a ef P3 6f 03 03 01
MAC ERROR
Padding oracle attack
Original C2 : 34 db 9a ed
ModifiedC2’:34 db 9a ef
To get a MAC Error, It must be: D(C3) C2’ = xx xx xx 01 (valid padding)
So what is D(C3)?
Padding oracle attack
Original C2 : 34 db 9a ed
ModifiedC2’:34 db 9a ef
To get a MAC Error, It must be: D(C3) C2’ = xx xx xx 01 (valid padding)
So what is D(C3)? D(C3)= xxxxxx01C2’
= xxxxxx0134db9aef = xxxxxxee
Also tells us the padding byte:
P3 = D(C3)C2
= xx xx xx ee 34 db 9a ed
= xx xx xx 03
= xx 03 03 03 (valid padding)
Padding oracle attack
C1
C2
C3
EK EK EK
D(C3)5b d8 99 ee C2 34 db 9a ed P3 6f 03 03 03
P1 = D(C1)IV P2 = D(C2)C1 P3 = D(C3)C2
P1
P2
P3
Padding oracle attack
P1
P2
P3
EK EK EK
D(C3)5b d8 99 ee C2 00 dc 9d ea P3 5b 04 04 04
PADDING ERROR
P1 = D(C1)IV P2 = D(C2)C1 P3 = D(C3)C2
C1
C2
C3
Padding oracle attack
P1
P2
P3
EK EK EK
D(C3)5b d8 99 ee C2 01 dc 9d ea P3 5a 04 04 04
PADDING ERROR
P1 = D(C1)IV P2 = D(C2)C1 P3 = D(C3)C2
C1
C2
C3
Padding oracle attack
P1
P2
P3
EK EK EK
D(C3)5b d8 99 ee C2 5f dc 9d ea P3 04 04 04 04
MAC ERROR
P1 = D(C1)IV P2 = D(C2)C1 P3 = D(C3)C2
C1
C2
C3
Other modes
OFB, CFB, etc. – used less often
Counter mode (CTR)
Essentially uses block cipher as a pseudorandom generator XOR ith block of message with Ek(message_id || i)
Turns a block cipher into a stream cipher!
01
EK EK P1 P2 C1 C2
…
Building a secure channel What if you want confidentiality and integrity at the same time?
Building a secure channel What if you want confidentiality and integrity at the same time?
Encrypt, then add integrity, not the other way around (reasons are subtle)
Use separate keys for confidentiality and integrity
Need two shared keys, but only have one? That’s what PRGs are for!
If there’s a reverse (Bob to Alice) channel, use separate keys for that
Modern encryption mode:
Authenticated Encryption
AES-GCM – Galois/Counter Mode
AES in CTR Mode for encryption Galois Hashing for authentication
Assumption we’ve been making so far:
Alice and Bob shared a secret key in advance
Amazing fact:
Alice and Bob can have a public conversation to derive a shared key!