The Mechanical Cryptographer: Tolerant Algebraic Side-Channel Attacks using pseudo-Boolean Solvers

Machine solvers are a class of general-purpose software tools which input a set of equations and output a satisfying assignment to these equations (or a proof of unsatisfiability). Solvers are used for a variety of practical applications, from VLSI verification to transportation route planning. Recently several authors have attempted to use solvers to perform one of the most challenging tasks in modern computer science - cryptanalysis of symmetric block ciphers such as AES. To use a solver for cryptanalysis, we provide it with a known plaintext, a known ciphertext and the set of mathematical equations which use an unknown secret key to transform between the two. The solver is then expected to output the secret key which links the given plaintext and ciphertext, thus satisfying the equation set. Fortunately, solvers are not currently capable of directly attacking modern ciphers. However, the situation is drastically different when side-channel data (information leaked from the cryptographic device due to its internal structure) is introduced into the equation. This talk will introduce side-channel cryptographic attacks, survey our latest efforts in using machine solvers to attack cryptosystems, and conclude with a successful attack on the AES cipher which requires surprisingly little side-channel data and computation time. Joint work with Mathieu Renauld, Fran�ois-Xavier Standaert and Avishai Wool