4003-482-01/4005-705-01 Cryptography
Chapter 4. Advanced Encryption Standard
Lecture Notes

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

• Not based on a Feistel network

• Principal concepts
  • 10, 12, or 14 rounds for key sizes of 128, 192, or 256 bits respectively
  • The round function F contains:
    • Round key addition
    • Substitutions -- one S-box
    • Permutations
    • Mixing
  • Round keys derived from block cipher key using a key schedule
  • Decryption done by applying inverses of each transformation in the round function

• 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 2^126.1 work
  • Breaks AES-192 with 2^189.7 work
  • Breaks AES-256 with 2^254.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
    • D. Bernstein. Cache-timing attacks on AES. April 14, 2005. http://cr.yp.to/antiforgery/cachetiming-20050414.pdf
  • 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

Cryptography • 4003-482-01/4005-705-01 • Spring Quarter 2013

Course Page

Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4486 + 2220 = 6706

Home Page

Copyright © 2011 Alan Kaminsky. All rights reserved. Last updated 13-Sep-2011. Please send comments to ark­@­cs.rit.edu.