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

  • Yossef Oren | Tel-Aviv University

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

Speaker Details

Yossi Oren is a Ph.D. student at the Computer Network and Security Lab at Tel-Aviv University. His research interests are:

  • Secure Hardware: Power analysis and other hardware attacks and countermeasures on cryptographic devices; Low-resource cryptographic constructions for lightweight computers such as RFID tags
  • Cryptography in the real world: Consumer and voter privacy in the digital era; Web application security
    • Portrait of Jeff Running

      Jeff Running

Series: Microsoft Research Talks