Chapter Summary

In this chapter, we discuss some indirect ways of attacking public-key cryptosystems. These attacks do not attempt to solve the underlying intractable problems, but watch the decryption device and/or use malicious key generation routines in order to gain information about private keys.

The timing attack works based on the availability of the total times of several private-key operations under the same private key. It successively keeps on guessing bits of the private key by performing some variance calculations.

The power attack requires the availability of the power consumption patterns (also called power traces) of the decrypting (or signing) device during one or more private-key operations. If the measurements are done with good accuracy and resolution, a single power trace may reveal the private key to the attacker; this is called simple power analysis. In practice, however, such power measurements are often contaminated with noise. Differential power analysis requires power traces from several decryption operations under the same private key. The different traces are combined using a technique that reduces the effect of noise.

A fault attack can be mounted by injecting one or more faults in the device performing private-key operations. Fault attacks are discussed in connection with several encryption (RSA), signature (ElGamal, DSA and so on) and authentication (FFS) schemes.

The above three kinds of attacks are collectively called side-channel attacks. Several general and algorithm-specific countermeasures against side-channel attacks are discussed.

Backdoor attacks, on the other hand, are mounted by malicious key generation routines. Young and Yung propose the concept of secretly embedded trapdoor with universal protection (SETUP). In a SETUP-contaminated system, the designer of the key generation routine possesses the exclusive right to steal keys from users. Several examples of backdoor attacks on RSA and ElGamal cryptosystems are described.