International Association
for Cryptologic Research

Fault attacks are active attacks in which an adversary with physical

access to a cryptographic device, for instance a smartcard, tampers

with the execution of an algorithm to retrieve secret material. Since

the seminal Bellcore attack on RSA signatures, there has been

extensive work to discover new fault attacks against cryptographic

schemes, and to develop countermeasures against such

attacks. Originally focused on high-level algorithmic descriptions,

these works increasingly focus on concrete implementations. While

lowering the abstraction level leads to new fault attacks, it also

makes their discovery significantly more challenging. In order to face

this trend, it is therefore desirable to develop principled,

tool-supported approaches that allow a systematic analysis of the

security of cryptographic implementations against fault attacks.

We propose, implement, and evaluate a new approach for finding fault

attacks against cryptographic implementations. Our approach is based

on identifying implementation-independent mathematical properties we

call fault conditions. We choose them so that it is possible to

recover secret data purely by computing on sufficiently many data

points that satisfy a fault condition. Fault conditions capture the

essence of a large number of attacks from the literature, including

lattice-based attacks on RSA. Moreover, they provide a basis for

discovering automatically new attacks: using fault conditions, we

specify the problem of finding faulted implementations as a program

synthesis problem. Using a specialized form of program synthesis, we

discover multiple faulted implementations on RSA and ECDSA that

realize the fault conditions, and hence lead to fault attacks. Several

of the attacks found by our tool are new, and of independent interest.