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

This is the context for the main paper, On the Importance of Checking Computations, by Boneh, DeMillo and Lipton, published October 31, 1996.

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.

Proofs and Theorems

Assuming the presence of a certain type of fault, the authors prove that implementations of RSA public-key cryptography and several other cryptographic protocols can be broken without direct factoring. For the math, cryptography and security communities, this discovery has interesting implications, since RSA and almost all other public-key cryptosystems rely for their security largely on the supposed difficulty of factoring an integer into primes, or, in some cases, of solving discrete logarithms.

For end-users, the discovery signifies that a security device or system that contains the private key of an RSA public/private key pair may be compromised while performing such functions as obtaining digital signatures, executing authentication tasks, and deciphering encrypted messages. All these functions are important to secure communications, but as electronic commerce progresses, the need to protect digital signatures from unauthorized use will become essential to the credibility of an electronically based economic structure.

It is important to emphasize that the security of RSA and other algorithms, as such, is not being questioned in this research. Only the security of particular implementations is at risk as a result of fault-based cryptanalysis -- and these implementations may well be protected through simple modifications to the cryptographic processing being performed. Of course, it's only simple if you know what to look for.

In the early stages of Bellcore's study of fault-based cryptanalysis, the attack model required one correct cryptographic signature, plus hundreds of faulty signatures -- all on the same message. Hence, the attack was impractical and of mainly theoretical interest to the security community.

After the threat model was refined, it required one correct signature and only a single faulty signature on the same message. This application of the technique was thus more practical than the first. However, the attack can be thwarted -- for example, by "random padding," which appends random bits to a message before signing the resultant composite message. That means that it is impossible to sign the same message twice, either correctly or incorrectly.

Bellcore's study of fault-based cryptanalysis has progressed to an even more refined stage. In the third refinement of fault-based cryptanalysis, Bellcore describes an attack scenario called "one strike and you're out," or OSYO. In this scenario, one half of a computation called the Chinese Remainder Theorem, or CRT, is derived incorrectly, and one half correctly. The result is a single faulty signature that can be used to find, almost instantaneously, the RSA modulus. This single faulty signature is the only one required to achieve the attack; the corresponding correct signature is not needed.

Again, it is important to point out that asymmetric and symmetric key algorithms themselves are not discredited by this research. Only certain implementations are at risk.

For RSA without CRT, the attack is theoretically possible but not yet practical, because it would require the attacker to observe multiple signatures having specific faults. However, Rabin's Signature Scheme uses CRT, and therefore is vulnerable to the attack described above.

Vulnerable Cryptosystems

The authors generalize their work to attacks on other implementations of RSA and to other cryptographic systems.

When they apply their fault-based cryptanalysis to authentication -- as opposed to digital signature -- applications, the authors presume a specific type of fault called "register faults." In this case, they assume that the circuitry of the computing device contains no faults, but that a value stored in a register is corrupted. When register faults are used, the attack extends to the Fiat-Shamir, Schnorr, and Guillou-Quisquater public- key identification schemes.

These cryptographic systems are implemented currently in enterprise-wide, public and private networks. Any computing device in the network that calculates cryptographic data can generate the faults that are used in the attacks described here. Thus, the fault might be observed at the periphery of a network where, for example, a smart card and card reader exchange data. It could also be observed on a central server, an end-user computing system, or a PC card such as those used in notebook computers to facilitate remote access to corporate networks.

Not only public-key, but secret-key (or symmetric-key) cryptosystems, such as DES, are vulnerable to fault-based attacks. Soon after Bellcore's success in applying fault-based cryptanalysis to public-key cryptography was reported, two Israeli scientists announced that they had found a way to apply fault-based methods to secret-key cryptography. On October 18, Eli Biham of The Technion, and Adi Shamir of the Weizman Institute circulated email that described the attack and acknowledged the pioneering contribution of Bellcore's DeMillo, Boneh and Lipton, whose ideas were the starting point of their new attack.

A large installed base of security systems uses DES. However, public-key systems based on RSA are becoming popular for their ability to facilitate -- in conjunction with certification authorities -- secure electronic commerce. For a large population of users who have had no prior communication with each other to exchange secure transactions, public-key systems are more practical than secret-key systems.

Status

As of October 30, 1996, the status of research into the fault-based cryptanalysis is summarized in the following table:

Preventing Fault-Based Cryptanalysis

Fault-based cryptanalysis can exploit inherent faults, created faults (for example, faults created by a subtle, non-invasive influence on chip-level calculations), or faults planted at the chip level during design and/or manufacturing.

The designers of security systems and components can defend those systems and components against fault-based cryptanalysis by taking certain steps. Among these are the following:

1. Protect authentication schemes. In "On the Importance of Checking Computations," one of the attacks on authentication schemes relies on a fault in the internal memory of the device. The device should be able to detect and correct its own fault.
2. Protect signature schemes. RSA algorithms are used to make sure that the sender of a digital message is who he or she claims to be. The algorithm uses the sender's private key to compute a short file, which then becomes the digital signature for the transmission. The attack under discussion here exploits a fault that might occur while the signature is being computed. Signature verification -- checking the signature before the messsage is sent -- can overcome this attack.

Cryptosystems should be fault-tolerant. Their fault-tolerance can be ensured by verifying the computations and protecting the internal memory. Note that the cryptographic protocols under consideration are interactive, challenge-and-response procedures, and the computing device has to "remember" what data it sent during an exchange. In one of the attack models, the memory that stores this so-called state of the device is altered. One way to verify a computation is to repeat it. However, even if the recomputing is performed with an alternate method, the recomputation may not be effective if the error us due to a software or hardware bug, or to faults that may have been planted during the design and manufacture of the computing device. In that case, repeating the computation would merely reproduce the same error. Sometimes verification algorithms are more efficient than merely recomputing a calculation. For the RSA signature applications, certainly verification algorithms are more efficient than recomputing the signature. Moreover, in signature schemes, the signing party should always verify his or her own signature by using a verification algorithm before releasing the signature for use in secure electronic transmissions.

Research Status and Direction

In addition to exploring ways to refine fault-based cryptanalysis, and thus to reveal new vulnerabilities in security systems, Bellcore research scientists seek to find defense mechanisms against the attacks. Clearly, the security industry is a dynamic enterprise that must cope with a constantly moving target -- that is, the constantly improving skills and techniques of the attackers.

Go to Bellcore's main smart-card page