Security analysis of CRT-based cryptosystems |
| |
Authors: | Katsuyuki Okeya Tsuyoshi Takagi |
| |
Affiliation: | (1) Systems Development Laboratory, Hitachi Ltd., 1099 Ohzenji, Asao-ku Kawasaki, 215-0013, Japan;(2) Future University-Hakodate, Japan, 116-2 Kamedanakano-cho, Hakodate Hokkaido, 041-8655, Japan |
| |
Abstract: | A side channel attack (SCA) is a serious attack on the implementation of cryptosystems, which can break the secret key using
side channel information such as timing, power consumption, etc. Recently, Boneh et al. showed that SSL is vulnerable to SCA
if the attacker gets access to the local network of the server. Therefore, public-key infrastructure eventually becomes a
target of SCA. In this paper, we investigate the security of RSA cryptosystem using the Chinese remainder theorem (CRT) in
the sense of SCA. Novak first proposed a simple power analysis (SPA) against the CRT part using the difference of message
modulo p and modulo q. In this paper, we apply Novak’s attack to the other CRT-based cryptosystems, namely Multi-Prime RSA, Multi-Exponent RSA,
Rabin cryptosystem, and HIME(R) cryptosystem. Novak-type attack strictly depends on how to implement the CRT. We examine the
operations related to CRT of these cryptosystems, and show that an extended Novak-type attack is effective on them. Moreover,
we present a novel attack called zero-multiplication attack. The attacker tries to guess the secret prime by producing ciphertexts
that cause a multiplication with zero during the decryption, which is easily detected by power analysis. Our experimental
result shows that the timing with the zero multiplication is reduced about 10% from the standard one. Finally, we propose
countermeasures against these attacks. The proposed countermeasures are based on the ciphertext blinding, but they require
no inversion operation. The overhead of the proposed scheme is only about 1–5% of the whole decryption if the bit length of
modulus is 1,024. |
| |
Keywords: | RSA Multi-Prime RSA Factoring Chinese remainder theorem Side channel attacks PKCS #1 |
本文献已被 SpringerLink 等数据库收录! |
|