Nadia Heninger will present her preFPO on Monday May 24 at 2PM in Room 402. The
members of her committee are: Bernard Chazelle, advisor; Ed Felten and Henry Cohn
(MSR New England), readers, Boaz Barak and Moses Charikar, nonreaders. Everyone
is invited to attend her talk. Her abstract follows below.
--------------------------------------------
Title: The mathematics of side-channel attacks
Abstract:
We will look at a collection of mathematical problems suggested by
side-channel 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 side-channel 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 lattice-based
techniques introduced by Coppersmith for finding low-degree roots of
polynomials mod numbers of unknown factorization. We show how this
approach can be extended from the integers to the ring of polynomials,
and give a new proof via lattice basis reduction of Guruswami-Sudan
list-decoding of Reed-Solomon codes. These theorems are in fact
instances of a general approach, which we extend to show how to find
small solutions to polynomials over ideals in number fields.
On Mon, May 17, 2010 at 1:32 PM, Melissa Lawson
thanks, Melissa