The Mathematics of Side-Channel Attacks

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 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 Reed-Solomon codes along with a natural extension to multi-point algebraic geometric codes, as well as an algorithm to find small solutions to polynomials over ideals in number fields.