
Speaker Nadia Heninger Affiliation Princeton University Host Yael Kalai Duration 01:00:11 Date recorded 28 January 2011 We will look at a collection of mathematical problems suggested by sidechannel attacks against public key cryptosystems, and how the techniques inspired by this work relate to a variety of different applications. First, we discuss the cold boot attack, a sidechannel attack against disk encryption systems that uses the phenomenon of DRAM remanence to recover encryption keys from a running computer. In the course of the attack, however, there may be errors introduced in the keys that the attacker obtains. It turns out that the structure of the key data in an AES key schedule can allow an attacker to more efficiently recover the private key in the presence of such errors. We extend this idea to a RSA private keys, and show how the structure of RSA private key data can allow an attacker to recover a key in the presence of random errors from 27% of the bits of the original key. Most previous work on RSA key recovery used the latticebased techniques introduced by Coppersmith for finding lowdegree roots of polynomials modulo numbers of unknown factorization. We will show how powerful analogies from algebraic number theory allow us to translate this theorem from the ring of integers to the ring of polynomials and beyond. This sort of intellectual arbitrage allows us to give a faster algorithm for list decoding of ReedSolomon codes along with a natural extension to multipoint algebraic geometric codes, as well as an algorithm to find small solutions to polynomials over ideals in number fields.
©2011 Microsoft Corporation. All rights reserved.
By the same speakerPeople also watched 