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 3. Data Encryption Standard Lecture Notes

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

### Block Cipher Operation

 Stream Cipher: Block Cipher:

• A stream cipher encrypts/decrypts one bit at a time

• A block cipher encrypts/decrypts multiple bits at a time

• A stream cipher algorithm defines how to encrypt/decrypt arbitrary-length messages
• Just encrypt/decrypt single bits repeatedly

• A block cipher algorithm does not define how to encrypt/decrypt arbitrary-length messages
• You can only encrypt/decrypt N bits, no more, no less
• Arbitrary-length messages are handled by a separate algorithm called a block cipher mode of operation — see Chapter 5

• A stream cipher's encryption and decryption operations are the same
• Encryption: ciphertext = plaintext xor keystream
• Decryption: plaintext = ciphertext xor keystream

• A block cipher's encryption and decryption operations are different
• To decrypt, run the encryption operation backwards
• The encryption operation must be invertible

• A stream cipher algorithm incorporates both the key and the nonce

• A block cipher algorithm incorporates just the key
• The nonce feeds into the mode of operation

• Examples of block ciphers:

 Cipher Block Size (bits) Key Size (bits) DES* 64 56 Triple-DES* 646464 56112168 HIGHT 64 128 AES** 128128128 128192256 Threefish 2565121024 2565121024 PRESENT 6464 80128

*Former U.S. government standard, now obsolete
**Current U.S. government standard

### Block Cipher Architecture

 Encryption: Decryption:

### Round Functions

• Round function based on a Feistel network

• Round function based on a substitution-permutation network (SPN) — see Chapter 4

### Feistel Networks

• A Feistel network is a way to turn a one-way (noninvertible) function F into a two-way (invertible) round function

 Forward direction (encryption): Reverse direction (decryption): L1 = R0R1 = L0 xor F(R0,subkey) R0 = L1L0 = R1 xor F(L1,subkey)

### The Data Encryption Standard (DES)

• Data Encryption Standard (DES). Federal Information Processing Standards Publication 46-3, October 25, 1999. http://csrc.nist.gov/publications/fips/fips46-3/fips46-3.pdf

• Block size = 64 bits

• Key size = 56 bits

• Number of rounds = 16

• Standard block cipher architecture, plus initial and final bit permutations

• Round function uses a Feistel network

• The Feistel function F contains:
• Permutations
• Substitutions—8 different substitution boxes (S-boxes)

### Triple-DES

• Defined in FIPS PUB 46-3

• Let EK(P) denote DES encryption of plaintext P with key K

• Let DK(C) denote DES decryption of ciphertext C with key K

• Keying Option 1, 168-bit key consisting of three 56-bit keys K1, K2, K3
• Encryption: C = EK3(DK2(EK1(P)))
• Decryption: P = DK3(EK2(DK1(C)))

• Keying Option 2, 112-bit key consisting of two 56-bit keys K1, K2
• Encryption: C = EK1(DK2(EK1(P)))
• Decryption: P = DK1(EK2(DK1(C)))

• Keying Option 3, 56-bit key K1
• Encryption: C = EK1(DK1(EK1(P)))
• Decryption: P = DK1(EK1(DK1(C)))
• For backwards compatibility with regular DES

### HIGHT

• D. Hong, J. Sung, S. Hong, J. Lim, S. Lee, B. Koo, C. Lee, D. Chang, J. Lee, K. Jeong, H. Kim, J. Kim, and S. Chee. HIGHT: a new block cipher suitable for low-resource device. In L. Goubin and M. Matsui, eds. 8th International Workshop on Cryptographic Hardware and Embedded Systems (CHES 2006), Springer LNCS 4249, 2006, pages 46-59.

• An ultralightweight block cipher intended for hardware implementation in limited devices (e.g., smart cards, RFID chips)

• Block size = 64 bits

• Key size = 128 bits

• Number of rounds = 32

• Standard block cipher architecture, plus initial transform and final transform

Hong et al., op. cit.

• Round function uses a generalized Feistel network

Hong et al., op. cit.

F0(x) = (x rotate-left 1) xor (x rotate-left 2) xor (x rotate-left 7)
F1(x) = (x rotate-left 3) xor (x rotate-left 4) xor (x rotate-left 6)

• Key schedule

Hong et al., op. cit.

### Avalanche Effect

• Using a block cipher like HIGHT, encrypt two plaintexts that differ in one bit position, using the same key:
```Key                                 Plaintext           Ciphertext
00000000000000000000000000000000    0000000000000000    01b96c0c49932099
00000000000000000000000000000000    0000000000000001    3a9daf194b016069
```

• Hamming distance of two bit strings = number of bit positions at which the bit strings differ

• With a plaintext Hamming distance of 1, the ciphertext Hamming distance is 23:
```01b96c0c49932099 = 0000 0001 1011 1001 0110 1100 0000 1100 0100 1001 1001 0011 0010 0000 1001 1001
3a9daf194b016069 = 0011 1010 1001 1101 1010 1111 0001 1001 0100 1011 0000 0001 0110 0000 0110 1001
** * **   *   *   **     **    *  * *        *  *  *   *   *        ****
```

• The Avalanche Effect: a tiny change in the plaintext produces a large change in the ciphertext

• This is desirable to conceal plaintext differences from intruders who see only the ciphertext

### Statistical Testing of Block Ciphers

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

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

• Mathematical model of the avalanche effect in an ideal block cipher
• Any change to the plaintext (or key) should cause the ciphertext bits to behave like independent Bernoulli random variables
• Each ciphertext bit either stays the same with probability 0.5, or switches to the opposite with probability 0.5
• Then the ciphertext Hamming distance is expected to obey a binomial (N, 0.5) distribution, where N is the block size in bits
• pr (distance = d) = choose (N, d) 0.5d (1 − 0.5)Nd = choose (N, d) 0.5N
• choose (N, d) = N! / d! / (Nd)!
• x! = x ⋅ (x − 1) ⋅ (x − 2) ⋅ ⋅ ⋅ 2 ⋅ 1

• Avalanche Test — statistical test of the avalanche effect
1. Given: a block cipher, a key, an initial plaintext, and a number of samples S
2. Generate a series of S plaintexts, each at Hamming distance 1 from its predecessor — e.g., using a Gray code
3. Compute a series of S ciphertexts by encrypting these plaintexts
4. Compute the Hamming distance d between each ciphertext and its predecessor
5. Count actual number of occurrences Ad for each d value from 0 to N — a histogram
6. Compute expected number of occurrences Ed for each d value = S ⋅ pr (distance = d)
7. Compute chi-square statistic
• χ2 = sum from d = 0 to N of (AdEd)2 / Ed
8. Compute p-value of χ2
• P-value = probability of observing this χ2 value by chance . . .
• Even if the observed Hamming distances obey the expected probability distribution
• If there is perfect agreement between the actual and observed counts (Ad = Ed), χ2 = 0 and p-value = 1
• As the actual counts deviate from the expected counts, χ2 increases and p-value decreases
9. If the p-value falls below a significance threshold α, then the block cipher fails the test
• Typical α = 0.01

• Perform the Avalanche Test on the block cipher reduced to 1 round, 2 rounds, and so on, up to the full number of rounds

• Example for HIGHT with 1000 samples:
```\$ java AvalancheTest Hight 000102030405060708090a0b0c0d0e0f fedcba9876543210 1000 > av_hight.txt
\$ cat av_hight.txt
. . .
******** SUMMARY ********
round	chi^2	pvalue
1	4.0969e+19	0.0000e+00 ***
2	4.0967e+19	0.0000e+00 ***
3	3.7687e+17	0.0000e+00 ***
4	3.3320e+17	0.0000e+00 ***
5	3.3320e+17	0.0000e+00 ***
6	3.3319e+17	0.0000e+00 ***
7	3.3319e+17	0.0000e+00 ***
8	3.3319e+17	0.0000e+00 ***
9	1.3951e+17	0.0000e+00 ***
10	2.3799e+16	0.0000e+00 ***
11	4.6127e+15	0.0000e+00 ***
12	4.6117e+15	0.0000e+00 ***
13	4.6117e+15	0.0000e+00 ***
14	1.1895e+15	0.0000e+00 ***
15	1.8000e+12	0.0000e+00 ***
16	4.4278e+11	0.0000e+00 ***
17	2.4195e+09	0.0000e+00 ***
18	2.9700e+07	0.0000e+00 ***
19	2.4839e+04	0.0000e+00 ***
20	7.3586e+01	1.9309e-01
21	1.9942e+01	1.0000e+00
22	2.2169e+01	1.0000e+00
23	2.4949e+01	1.0000e+00
24	2.0024e+01	1.0000e+00
25	2.9432e+01	9.9994e-01
26	1.5951e+01	1.0000e+00
27	1.4972e+01	1.0000e+00
28	3.4054e+01	9.9923e-01
29	3.1799e+01	9.9975e-01
30	2.6447e+01	9.9999e-01
31	2.0728e+01	1.0000e+00
32	2.5326e+01	1.0000e+00
```

• For this run, HIGHT reduced to 1 through 19 rounds fails the test (p-value < 0.01)

• HIGHT with 19 or fewer rounds looks like a nonrandom function, HIGHT with 20 or more rounds looks like a random function

• Randomness margin = (32 − 19)/32 = 40.6%

• A good block cipher should have a substantial randomness margin with respect to many different statistical tests

• 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