7.1. Introduction

The security of public-key cryptographic protocols is based on the apparent intractability of solving some computational problems. If one can factor large integers efficiently, one breaks RSA. In that sense, seeking for good algorithms to solve these problems (like factoring integers) is part of cryptanalysis. Proving that no poly-time algorithm can break RSA enhances the status of the security of the protocol from assumed to provable. On the other hand, developing a poly-time algorithm for breaking RSA (or for factoring integers) makes RSA (and many other protocols) unusable. A temporary set-back to our existing cryptographic tools as it is, it enriches our understanding of the computational problems. In short, breaking the trapdoors of public-key cryptosystems is of both theoretical and practical significance.

But research along these mathematical lines is open-ended. A desperate cryptanalyst may not wait indefinitely for a theoretical negotiation. She tries to find loopholes in the systems, that she can effectively exploit to gain secret information.

A cryptographic protocol must be implemented (in software or hardware) before it can be used. Careless implementations often supply the loopholes that cryptanalysts wait for. For example, a software implementation of a public-key system may allow the private key to be read only from a secure device (a removable medium, like CDROM), but may make copies of the key in the memory of the machine where the decryption routine is executed. If the decryption routine does not lock and eventually flush the memory holding the key, a second user having access to the machine can simply read off the secrets.

Software and hardware implementations often tend to leak out secrets at a level much more subtle than the example just mentioned. A public-key algorithm is a known algorithm and involves a sequence of well-defined steps dictated by the private key. Each step requires its private share of execution time and power consumption. Watching the decrypting device carefully during a private-key operation may reveal information about the exact sequence of basic steps in the algorithm. Random hardware faults during a private-key operation may also compromise security. Such attacks are commonly dubbed as side-channel attacks.

Let us now look at another line of attack. Every user of cryptography is not expected to implement all the routines she uses. On the contrary, most users run precompiled programs available from third parties. How will a user assess the soundness of the products she is using, that is, who will guarantee that there are no (intentional or unintentional) security snags in the products? The key generation software available from a malicious software designer may initiate a clandestine e-mail every time a key pair is generated. It is also possible that a private key supplied by such a program is generated from a small predefined set known to the designer. Even when private keys look random, they need not come with the desired unpredictability necessary for cryptographic usage. Such attacks during key generation are called backdoor attacks.

In short, public-key cryptanalysis at present encompasses trapdoors, backdoors and side channels. The trapdoor methods have already been discussed in Chapter 4. In this chapter, we concentrate on the other attacks on public-key systems.