On the Importance of Checking Computations

[John Young <jya@pipeline.com>]

The Bellcore report,  "On the Importance of Checking Computations" 
on technical details of fault-based cracking reported in today's FT, 
is available at:

     http://www.bellcore.com/SMART/index.html

Here's an outline:

On the Importance of Checking Computations
(Extended abstract)

Don Boneh, Richard A. DeMillo, and Richard J. Lipton
Math and Cryptography Research Group, Bellcore

Abstract: 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. We also show how various authentication
protocols, such as Fiat-Shamir and Schnoor, can be broken
using hardware faults.

1. Introduction

     Transient faults
     Latent faults
     Induced faults

2. Chinese remainder based implementations

     2.1 The RSA system
     2.2 RSA's vulnerability to hardware faults

3. Register faults

4. The Fiat-Shamir identification scheme

     Theorem 4.1

     4.1 A modification of the Fiat-Shamir scheme

5. Attacking Schnoor's identification scheme

     Theorem 5.1

6. Breaking other implementations of RSA

     Theorem 6.1

7. Protecting against an attack based on hardware faults

8. Summary

References

-----

Registration is required for access. Two formats are available: 
Acrobat PDF (112kb) and Postscript PS (86kb).

Before registration, there is a brief "context" at:

     http://www.bellcore.com/SMART/secwp.html

Here's the first two paragraphs:


Context for "On the Importance of Checking Computations"

"On the Importance of Checking Computations" describes a 
fault-based method for breaking various cryptographic 
algorithms and exposes the degree to which computing faults 
can compromise information security. Once the authors -- 
Richard DeMillo, Dan Boneh and Richard Lipton -- articulated 
and proved their conceptual breakthrough, they realized that 
it might be successful in a wide variety of application
scenarios. Fault-based attacks potentially endanger many 
network security products and systems. The paper
summarizes the proof for the basic attack. 

Proof for fault-based cryptanalysis builds on the premise that 
an adversary can observe a faulty computation that occurs 
during cryptographic transactions. The faults that are exploited 
can occur at various sublevels within the logic level of a 
computing device -- that is, in the switching circuitry where 
arithmetic operations are performed or in the register transfer 
area where temporary values are stored in memory. The 
likelihood of faults occurring is not discussed in the paper. 

[Snip balance of Context]