On the importance of checking cryptographic protocols for faults

Authors: D. Boneh, R. DeMillo, and R. Lipton

We present a theoretical model for breaking various cryptographic schemes by taking advantage of random hardware faults. We show how to attack certain implementations of RSA and Rabin signatures. An implementation of RSA based on the Chinese Remainder Theorem can be broken using a single erroneous signature. Other implementations can be broken using a larger number of erroneous signatures. We also analyze the vulnerability to hardware faults of two identification protocols: Fiat-Shamir and Schnorr. The Fiat-Shamir protocol can be broken after a small number of erroneous executions of the protocol. Schnorr's protocol can also be broken, but a larger number of erroneous executions is needed.

Journal of Cryptology, Springer-Verlag, Vol. 14, No. 2, pp. 101--119, 2001
Extended abstract in proceedings of Eurocrypt '97

Full paper: gzipped-PostScript         [first posted 6/1999 ]