P?ísp?vek M.Hlavá?e p?ijat na prestižní konferenci CHES 2009!
04.06.2009Known-Plaintext-Only Attack on RSA-CRT with Montgomery Multiplication
Martin Hlavac, Charles University in Prague, Czech Republic
The paper describes a new attack on RSA--CRT employing Montgomery exponentiation. Given the amount of so-called final subtractions during the exponentiation of a known message (not chosen, just known), it creates an instance of the well known Hidden Number Problem (HNP, [2]). Solving the problem reveals the factorization of RSA modulus, i.e. breaks the scheme.
The main advantage of the approach compared to other attacks [15,18] is the lack of the chosen plaintext condition. The existing attacks, for instance, cannot harm so-called Active Authentication (AA) mechanism of the recently deployed electronic passports. Here, the challenge, i.e. the plaintext, is jointly chosen by both parties, the passport and the terminal, thus it can not be conveniently chosen by the attacker. The attack described here deals well with such a situation and it is able to solve the HNP instance with 150 measurements filtered from app. 7000. Once the secret key used by the passport during AA is available to the attacker, she can create a fully functional copy of the RFID chip in the passport she observes.
A possible way to obtain the side information needed for the attack within the electromagnetic traces is sketched in the paper. Having no access to high precision measurement equipment, its existence has not been experimentally verified, yet. The attack, however, should be taken into account by the laboratories testing the resilience of (not only) electronic passports to the side channel attacks.
References:
2. Dan Boneh and Ramarathnam Venkatesan. Hardness of computing the most significant bits of secret keys in Diffie-Hellman and related schemes. In Neal Koblitz, editor, CRYPTO, volume 1109 of Lecture Notes in Computer Science, pages 129–142. Springer, 1996.
15. Werner Schindler. A timing attack against RSA with the Chinese Remainder Theorem. In Cetin Kaya Koc and Christof Paar, editors, CHES, volume 1965 of Lecture Notes in Computer Science, pages 109–124. Springer, 2000.
18. Yuuki Tomoeda, Hideyuki Miyake, Atsushi Shimbo, and Shin ichi Kawamura. An SPA-based extension of Schindler’s timing attack against RSA using CRT. IEICE Transactions, 88-A(1):147–153, 2005.
Zdroj: http://www.chesworkshop.org/ches2009/accepted.htmlAutor: PV
Heuristické vyhledání souvisejících článků v archívu NEWS
Pozor - není zdaleka přesné a výsledek je bez záruky...
Chcete-li článek obsahující konkrétní termín - pou·ijte funkci
vyhledávání !
