Paper 2024/1125
Revisiting PACD-based Attacks on RSA-CRT
, IDEMIA, IDEMIAAbstract
In this work, we use some recent developments in lattice-based cryptanalytic tools to revisit a fault attack on RSA-CRT signatures based on the Partial Approximate Common Divisor (PACD) problem. By reducing the PACD to a Hidden Number Problem (HNP) instance, we decrease the number of required faulted bits from 32 to 7 in the case of a 1024-bit RSA. We successfully apply the attack to RSA instances up to 8192-bit and present an enhanced analysis of the error-tolerance in the Bounded Distance Decoding (BDD) with predicate approach. Finally, evaluating the impact of standard side-channel and fault countermeasures, we show that merely verifying the signature before output is not an adequate protection against this attack. The reduction from PACD to HNP might be of independent interest.
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- Preprint.
- Keywords
- Lattice reductionsRSA-CRTPACDHNPBDD with Predicat
- Contact author(s)
-
guillaume barbu @ idemia com
laurent gremy @ idemia com
roch lescuyer @ idemia com - History
- 2024-07-12: approved
- 2024-07-10: received
- See all versions
- Short URL
- https://ia.cr/2024/1125
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/1125,
author = {Guillaume Barbu and Laurent Grémy and Roch Lescuyer},
title = {Revisiting {PACD}-based Attacks on {RSA}-{CRT}},
howpublished = {Cryptology ePrint Archive, Paper 2024/1125},
year = {2024},
note = {\url{https://eprint.iacr.org/2024/1125}},
url = {https://eprint.iacr.org/2024/1125}
}
