Cryptography Reference
In-Depth Information
Chapter 8
Fault Attacks Against RSA-CRT
Implementation
Chong Hee Kim and Jean-Jacques Quisquater
Abstract
RSA-CRT uses the Chinese Remainder Theorem to speed up the compu-
tation of an RSA decryption or a signature and reduces the size of the data stored in
memory. This implementation is four times faster than the RSA standard implemen-
tation. This is why the CRT implementation of RSA is widely deployed in embedded
systems. However, Boneh et al. showed that an error that occurred during the expo-
nentiation could allow one break the implementation of RSA-CRT in 1997. This is
a very powerful attack as one can easily find the key of RSA with only one faulty
signature. Many countermeasures have been proposed to prevent this attack, but
most of them have failed. In this chapter, we introduce a survey of the attacks and
countermeasures against RSA-CRT implementations.
8.1 Introduction
Ciphertext indistinguishability against adaptive chosen-ciphertext attacks is an impor-
tant security property of many encryption schemes [333]. To achieve indistinguisha-
bility, public key encryption schemes must be probabilistic [165]. Therefore encryp-
tion schemes used in practice introduce redundancy so that a random ciphertext
will be valid with negligible probability. This includes the widely used RSA-OAEP
encryption scheme [30]. There is therefore no need to add a fault detection mecha-
nism: the correctness of the plaintext is explicitly checked by the decryption algo-
rithm. This explains why fault attacks focus on RSA signature schemes.
RSA signatures can be computed in two ways: standard mode and CRT mode.
Each mode is vulnerable to different fault attacks. In this chapter we describe fault
attacks against RSA-CRT mode and countermeasures.
