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 4. Advanced Encryption Standard Lecture Notes

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

### Substitution-Permutation Network (SPN) Round Function

• Each layer must be invertible
• Subkey Addition Layer is typically just exclusive-or and is therefore invertible
• Substitution Layer consists of multiple substitution boxes (S-boxes); each S-box is a bijection and is therefore invertible
• Permutation Layer rearranges the data in a fixed pattern and is therefore invertible

### The Advanced Encryption Standard (AES)

• Advanced Encryption Standard (AES). Federal Information Processing Standards Publication 197, November 26, 2001. http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf

• Block size = 128 bits

• Key size = 128, 192, or 256 bits

• Number of rounds = 10, 12, or 14, respectively

• Standard block cipher architecture

• Round function uses a SPN with an additional Mixing Layer

• AES round function

Neils Ferguson and Bruce Schneier, Practical Cryptography (Wiley Publishing, 2003), page 55.

### AES Attacks

• State of AES attacks as of late 2010:
• A. Kaminsky, M. Kurdziel, and S. Radziszowski. An overview of cryptanalysis research for the Advanced Encryption Standard. IEEE Military Communications Conference 2010 (MILCOM 2010), pages 1853-1859, San Jose, CA, USA, November 2010.
(PDF) (Slide presentation)

• In August 2011, a key recovery attack (not a related key attack) on the full AES (not reduced-round AES) better than brute force (but just a little) was published:
• A. Bogdanov, D. Khovratovich, and C. Rechberger. Biclique cryptanalysis of the full AES. Cryptology ePrint Archive, Report 2011/449, August 31, 2011. http://eprint.iacr.org/2011/449
• Breaks AES-128 with 2126.1 work
• Breaks AES-192 with 2189.7 work
• Breaks AES-256 with 2254.4 work
• Also includes new breaks on reduced-round AES and on AES-based hash functions
• AES is now (theoretically) broken!

### Side Channel Attacks

• Attacks against the software implementations of the algorithms, not the algorithms themselves

• Timing attacks
• Exploit the fact that the time to do table lookups (e.g., S-box lookups) in software is not constant; it is input-dependent; specifically, it is key-dependent
• If a lookup table entry is in the CPU cache, it takes less time to access (cache hit)
• If a lookup table entry is not in the CPU cache, it takes more time to access (cache miss)
• Measuring variations in the running time of AES software while performing encryptions leaks information about the key
• Bernstein was able to find a 128-bit AES key in a few hours
• Tromer, Osvik, and Shamir were able to find a 128-bit AES key in 65 milliseconds of measurements and 3 seconds of analysis
• E. Tromer, D. Osvik, and A. Shamir. Efficient cache attacks on AES, and countermeasures. Journal of Cryptology, July 24, 2009.

• Power attacks
• Exploit the fact that the electrical power consumed to do table lookups (e.g., S-box lookups) in software is not constant; it is input-dependent; specifically, it is key-dependent
• If a lookup table entry is in the CPU cache, it takes less power to access (cache hit) -- main memory is not involved
• If a lookup table entry is not in the CPU cache, it takes more power to access (cache miss) -- main memory is involved
• Measuring spikes in the power consumption while performing encryptions leaks information about the key
• Many papers describe and simulate power attacks on AES, but none I've found report results of running the attacks on actual hardware

• Intel's AES instruction set
• New machine instructions debuted in Intel's Westmere processor in January 2010
• Instructions do the AES encryption round function, decryption round function, and key expansion in hardware
• AES encryption and decryption will be much faster than in software
• Instruction timing will be input-independent to foil timing attacks
• Not clear whether power consumption will be input-independent

### Threefish

• The Skein hash function, a SHA-3 finalist candidate, is built on top of the Threefish block cipher

• N. Ferguson, S. Lucks, B. Schneier, D. Whiting, M. Bellare, T. Kohno, J. Callas, and J. Walker. The Skein hash function family. Version 1.3, October 1, 2010. http://www.skein-hash.info/sites/default/files/skein1.3.pdf, retrieved 09-Feb-2015.

• Threefish versions
• Threefish-256: 256-bit block, 256-bit key, 72 rounds
• Threefish-512: 512-bit block, 512-bit key, 72 rounds
• Threefish-1024: 1024-bit block, 1024-bit key, 80 rounds

• Standard block cipher architecture

• Round function uses a SPN, with a subkey added every four rounds — diagram shows Threefish-512:

Ferguson et al., op. cit.

• The "Mix" function takes the place of an S-box:

Ferguson et al., op. cit.

• Generation of one subkey — key schedule has an additional 128-bit "tweak" input, as well as the key:

Ferguson et al., op. cit.

### PRESENT

• A. Bogdanov, L. Knudsen, G. Leander, C. Paar, A. Poschmann, M. Robshaw, Y. Seurin, and C. Vikkelsoe. PRESENT: an ultra-lightweight block cipher. In P. Paillier and I. Verbauwhede, eds. 9th International Workshop on Cryptographic Hardware and Embedded Systems (CHES 2007), Springer LNCS 4727, 2007.

• Another ultralightweight block cipher, like HIGHT

• Block size = 64 bits

• Key size = 80 or 128 bits

• Number of rounds = 31

• Standard block cipher architecture

Bogdanov et al., op. cit.

• Round function uses a SPN

• Two rounds of PRESENT showing the SPN:

Bogdanov et al., op. cit.

• The PRESENT S-box:

 x 0 1 2 3 4 5 6 7 8 9 A B C D E F S[x] C 5 6 B 9 0 A D 3 E F 8 4 7 1 2

Bogdanov et al., op. cit.

• The PRESENT key schedule (80-bit key)
• Subkey = key register bits 79–16 (64 most significant bits)
• Key register update algorithm:
• Rotate key register 61 bits left
• Apply PRESENT S-box to key register bits 79–76 (4 most significant bits)
• Exclusive-or round number into key register bits 19–15

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