Error Correction and the Cryptographic Key (thesis)
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 give an algorithm to find small solutions to polynomials modulo ideals in number fields and a list-decoding algorithm for multi-point algebraic-geometric codes.