CS代考程序代写 chain Cryptography Basics – Block ciphers and modes

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)= xxxxxx01C2’
= xxxxxx0134db9aef = 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!