Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4572 + 2433 = 7005
 Foundations of Cryptography • CSCI 662-01 • Spring Semester 2018
Course Page

## CSCI 662—Foundations of Cryptography Chapter 5. More About Block Ciphers Lecture Notes

Prof. Alan Kaminsky
Rochester Institute of Technology—Department of Computer Science

### Electronic Codebook (ECB) Mode

 ECB encryption ECB decryption

• Pi = Plaintext block i
Ci = Ciphertext block i
EK = Encryption using key K
DK = Decryption using key K

• Problem: The plaintext message's length might not be a multiple of the block size

• Add extra padding bits after the last plaintext bit . . .
• To make the plaintext-plus-padding a multiple of the block size . . .
• In such a way that the decryption can detect and strip off the padding bits
• For example: Append a 1 bit, then append zero or more 0 bits
• The padding is always added, even if the original message is a multiple of the block size

• Problem: Repeated plaintext blocks
• If a plaintext block is repeated, then the ciphertext block will be repeated
• This leaks information about the plaintext

• Solution: Never use ECB

### Cipher Block Chaining (CBC) Mode

 CBC encryption CBC decryption

• Pi = Plaintext block i
Ci = Ciphertext block i
EK = Encryption using key K
DK = Decryption using key K
IV = Initialization vector
+ = Bitwise exclusive-OR (modulo-2 addition)

• Similar to ECB, except the previous ciphertext block is used to randomize the next plaintext block

• Requires padding (same as ECB)

• Requires an initialization vector (IV) to randomize the first plaintext block

• Random IV
• IV = Random number
• Must send IV as an additional block before first ciphertext block

• Nonce-generated IV
• Each message has a unique number, a nonce (number used once), that both sides know
• For example, nonce = message sequence number
• IV = nonce

• If two messages use the same IV (nonce), CBC mode leaks information about the first plaintext blocks of the messages

• Problem: The birthday bound, 2n/2
• The encryption process is an iterated random mapping
• An iterated random mapping can experience a collision, where a later output is the same as an earlier output
• A collision becomes likely once 2n/2 iterations are performed, where n is the size in bits of the value being mapped
• Such a collision can leak information

• Solution: Limit the message size
• Don't encrypt a message longer than 2n/2 blocks, where n is the block size in bits

### Output Feedback (OFB) Mode

 OFB encryption OFB decryption

• Xi = Keystream block i
Pi = Plaintext block i
Ci = Ciphertext block i
EK = Encryption using key K
IV = Initialization vector
+ = Bitwise exclusive-OR (modulo-2 addition)

• A true stream cipher
• Next keystream block generated by encrypting previous keystream block

• Does not require using the decryption algorithm

• Does not require padding; just discard unneeded portion of last keystream block

• Requires an initialization vector (IV) to use as X0 (same as CBC)

• If two messages use the same IV (nonce), OFB mode leaks information about the entire plaintexts of both messages

• Keystream block collisions can occur
• If a later keystream block is the same as an earlier keystream block, the keystream will repeat, which can leak information
• A keystream block collision becomes likely after encrypting 2n/2 blocks, the birthday bound
• So limit message length to the birthday bound

### Cipher Feedback (CFB) Mode

 CFB encryption CFB decryption

• Xi = Keystream block i
Pi = Plaintext block i
Ci = Ciphertext block i
EK = Encryption using key K
IV = Initialization vector
+ = Bitwise exclusive-OR (modulo-2 addition)

• Same as OFB mode, except . . .
• Next keystream block generated by encrypting previous ciphertext block

• No real advantage over OFB mode

• Can be used in a different way to encrypt the plaintext one bit or one byte at a time
• This requires more applications of the encryption function
• This is mainly used for encryption/decryption of a data stream in hardware

### Counter (CTR) Mode

 CTR encryption CTR decryption

• Xi = Keystream block i
Pi = Plaintext block i
Ci = Ciphertext block i
EK = Encryption using key K
IV = Initialization vector
|| = Concatenation
+ = Bitwise exclusive-OR (modulo-2 addition)

• A true stream cipher
• Next keystream block generated by encrypting a counter block

• Does not require padding; just discard unneeded portion of last key block

• Every plaintext block of every message encrypted using a certain key K must use a different counter block
• For example, counter block i = IV concatenated with block number (i)

• Successive counter blocks typically differ in just one, or just a few, bit positions
• But a good block cipher will still yield completely different ciphertexts
• Flipping one bit of plaintext should cause each ciphertext bit to behave like a random coin toss
• A random subset of about half the ciphertext bit positions should end up the same
• A random subset of about half the ciphertext bit positions should end up different
• Avalanche effect

• Unlike CBC, OFB, and CFB modes, CTR mode can encrypt plaintext blocks in parallel

• If two messages use the same IV (nonce), CTR mode leaks information about the entire plaintexts of both messages

• If the counter ever rolls over, the keystream will repeat, which can leak information
• Limit message size to 2c blocks, where c is the counter size in bits

### Statistical Testing of Stream Ciphers

• A statistical test analyzes a stream cipher to determine whether the observed probability distribution of some quantity obeys the expected probability distribution for an ideal stream cipher

• If not, the stream cipher fails the test and is not suitable for secure communication

• Mathematical model of the keystream bits in an ideal stream cipher
• Consider a sequence of keystream nibbles (1 nibble = 4 bits)
• The nibble values are expected to obey a uniform distribution
• pr(nibble = i) = 1/16, 0 ≤ i ≤ 15
• Similar models could be made for 1-bit groups, 2-bit groups, etc. in the keystream

• Frequency Test — statistical test of the nibble frequencies
1. Given: a stream cipher, a key, a nonce, and a number of samples S
2. Generate a series of S keystream bytes; each byte is two nibbles
3. Count actual number of occurrences Ai for each nibble value i = 0 to 15 — a histogram
4. Compute expected number of occurrences Ei for each nibble value i = 2⋅S⋅pr(nibble = i) = 2⋅S⋅1/16 = S/8
5. Compute chi-square statistic
• χ2 = sum from i = 0 to 15 of (AiEi)2 / Ei
6. Compute p-value of χ2
• P-value = probability of observing this χ2 value by chance . . .
• Even if the observed nibble frequencies obey the expected probability distribution
• If there is perfect agreement between the actual and observed counts (Ai = Ei), χ2 = 0 and p-value = 1
• As the actual counts deviate from the expected counts, χ2 increases and p-value decreases
7. If the p-value falls below a significance threshold α, then the block cipher fails the test
• Typical α = 0.01

• Example for the stream cipher PRESENT-80/CTR:
```\$ java FrequencyTest PresentCTR 0001020304050607080910111213 10000
nibble	count	expect
0	1279	1.2500e+03
1	1274	1.2500e+03
2	1217	1.2500e+03
3	1252	1.2500e+03
4	1207	1.2500e+03
5	1294	1.2500e+03
6	1269	1.2500e+03
7	1214	1.2500e+03
8	1233	1.2500e+03
9	1176	1.2500e+03
10	1227	1.2500e+03
11	1274	1.2500e+03
12	1280	1.2500e+03
13	1279	1.2500e+03
14	1263	1.2500e+03
15	1262	1.2500e+03
chi^2  = 1.3501e+01
pvalue = 5.6368e-01
```

• A widely-used suite of statistical tests: the NIST suite
• A. Rukhin, J. Soto, J. Nechvatal, M. Smid, E. Barker, S. Leigh, M. Levenson, M. Vangel, D. Banks, A. Heckert, J. Dray, S. Vo, and L. Bassham. A statistical test suite for random and pseudorandom number generators for cryptographic applications. NIST Special Publication 800-22, Revision 1a, April 2010. http://csrc.nist.gov/groups/ST/toolkit/rng/documents/SP800-22rev1a.pdf

 Foundations of Cryptography • CSCI 662-01 • Spring Semester 2018
Course Page
 Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4572 + 2433 = 7005