An Improved Attack for Recovering Noisy RSA Secret Keys and Its Countermeasure

This paper discusses how to recover RSA secret keys from their noisy version observed by side-channel attacks. At CRYPTO2009, Heninger and Shacham proposed a polynomial time algorithm which recovers an original secret key from some fraction of secret key bits. Then, at CRYPTO2010, Henecka et al. proposed a polynomial time algorithm recovering a correct secret key from the noisy secret key bits with some errors. Then they gave the bound such that the secret key can be recovered in polynomial time. At PKC2013, Kunihiro et al. presented a key-recovery algorithm from the erroneous version of secret key bits with erasures and errors. They also gave a condition for recovering the secret key and its theoretical bound. They pointed out that there is a small gap between their derived condition and the theoretical bound and closing the gap is an open problem. In this paper, we first improve the bound and reduce the computational cost by introducing tighter inequalities than the Hoeffding bound and choosing aggressive parameter settings. Our obtained bound is asymptotically optimal. Further, we show a practical countermeasure against the secret key extraction attack based on our analysis. In the countermeasure, some of the bits in the secret key are intentionally flipped and then the secret key with errors is stored in the memory. With the help of the intentionally added errors, the security is enhanced. For example, it results to be secure against the attacker extracting the secret key with an error rate 0.13 by intentionally adding a 0.15 fraction of errors. Finally, we revisit asymmetric error cases and give a provable bound for crossover probabilities.