Suggestions for Further Reading
Kocher introduces the concept of side-channel attacks in his seminal paper [155]. This paper describes further details about the timing attack (like a derivation of the choice of the sample size k) and some experimental results.
Timing attacks in various forms are applicable to other systems. Kocher [155] himself suggests a chosen message attack on an RSA implementation based on CRT (Algorithm 5.4). Carol, in an attempt to guess Alice’s public key d, tries to guess the factor p (or q) of the modulus n using a timing attack. She starts by letting Alice sign a message y (c in Algorithm 5.4) close to an initial guess of p. The CRT-based algorithm first reduces y modulo p and modulo q before performing the modular exponentiations. If y < p already, then the initial reduction modulo p returns (almost) immediately, whereas if y ≥ p, the reduction involves at least one subtraction. This gives a variation in the timings based on the value of p. This fact is exploited by the attack to arrive at better and better approximations of p.
A known-message timing attack (in addition to the chosen message attack mentioned in the last paragraph) on the CRT-based RSA signature scheme is proposed by Kocher in the same paper [155]. Kocher also explains a timing attack on the signature algorithm DSA (Algorithm 5.43), based on the dependence of the modular reduction of H(M) + ds modulo r on the bits of the signer’s private key d.
Large scale implementations of timing attacks are reported in the technical reports [77, 259] from the Crypto group of Université catholique de Louvain. These implementations study Montgomery exponentiation.
Kocher [155] mentions the possibility of power attacks. However, a concrete description is first published in Kocher et al. [156], which explains both SPA and DPA. DES is the basic target of this paper, though possibilities for using these techniques against public-key systems are also mentioned.
Several variants of the basic DPA model described in the text have been proposed. Messerges et al. [200] describe attacks against smart-card implementations of exponentiation-based public-key systems. Also consult Aigner and Oswald’s tutorial [9] for a recent survey.
DPA seems to be the most threatening of all side-channel attacks. Many papers suggesting countermeasures against DPA have appeared. Chari et al. [45] propose a masking method. Messerges [199] applies this idea to a form suitable for AES.[4] Messerges’ countermeasure is broken in [63] using a multi-bit DPA. Some other useful papers on DPA include [10, 55, 201].
[4] AES is an abbreviation for advanced encryption standard which is a US-government standard that supersedes the older standard DES. AES uses the Rijndael cipher [219].
Boneh et al. [30, 31] from the Bellcore Lab. announce the first systematic study of fault attacks on asymmetric-key cryptosystems. They explain fault attacks on RSA (with and without CRT), the Rabin signature scheme, the Feige–Fiat–Shamir identification protocol and on the Schnorr identification protocol. These attacks are collectively known as Bellcore attacks.
Arjen K. Lenstra points out that the fault attack on CRT-based RSA does not require the valid signature. Joye and Quisquater propose some generalizations of the Bellcore–Lenstra attack. A form of this attack is applicable to elliptic-curve cryptosystems. The paper [142] talks about these developments.
Bao et al. [17] propose fault attacks on DSA, ElGamal and Schnorr signatures. They also describe variants of the fault analysis of RSA based on square-and-multiply algorithms. Zheng and Matsumoto [315] indicate the possibilities of attacking the random bit generator in a smart card.
Biham and Shamir [22] investigate fault analysis of symmetric-key ciphers and introduce the concept of differential fault analysis. Anderson and Kuhn [11] also study fault analysis of symmetric-key ciphers. Aumüller et al. [15] publish their practical experiences regarding physical realizations of faults in smart cards. They also suggest countermeasures against such attacks.
James A. Muir’s work [215] is a very readable and extensive survey on side-channel cryptanalysis. Also look at Boneh’s survey [29].
Because of small key sizes, elliptic-curve cryptosystems are very attractive for implementation in smart cards. It is, therefore, necessary to provide effective countermeasures against side-channel attacks (most importantly, against the DPA) for elliptic-curve cryptosystems. Many recent articles discuss this issue. Coron [62] suggests the use of random projective coordinates to avoid the costly (and power-consuming) field inversion operation needed for adding and doubling of points. Möller [206] proposes a non-conventional way of carrying out the double-and-add procedure. Izu and Takagi [138] describe a Montgomery-type point addition scheme resistant against side-channel attacks. An improved version of this algorithm, that works for a more general class of elliptic curves, is presented in Izu et al. [137].
Young and Yung introduce the concept of SETUP in [307]. The PAP SETUP on RSA and the ElGamal signature SETUP are from this paper which also includes attacks on DSA and Kerberos authentication protocol. In a later paper [308], Young and Yung categorizes SETUP in three types: regular, weak and strong. Strong SETUPs are proposed for Diffie–Hellman key exchange and for RSA. The third reference [309] from the same authors extends the ideas of kleptography further and provides backdoor routines for several other cryptographic schemes.
Crépeau and Slakmon [70] adopt a more informal approach and discuss several backdoors for RSA key generation. In addition to the trapdoors with hidden small private and public exponents, described in the text, they propose a trapdoor that hides small prime public exponent. They also present an improved version of the PAP routine. Unlike Young and Yung, they suggest symmetric techniques for designing fe, fd. Symmetric techniques endanger universal protection of the attacker, but continue to make perfect sense in the context of black-box cryptography.