Recovering RSA Secret Keys from Noisy Key Bits with Erasures and Errors

Noboru KUNIHIRO; Naoyuki SHINOHARA; Tetsuya IZU

doi:10.1587/transfun.E97.A.1273

Recovering RSA Secret Keys from Noisy Key Bits with Erasures and Errors

Noboru KUNIHIRO, Naoyuki SHINOHARA, Tetsuya IZU

Full Text Views

0

Share
Cite this

Summary :

We discuss how to recover RSA secret keys from noisy key bits with erasures and errors. There are two known algorithms recovering original secret keys from noisy keys. At Crypto 2009, Heninger and Shacham proposed a method for the case where an erroneous version of secret keys contains only erasures. Subsequently, Henecka et al. proposed a method for an erroneous version containing only errors at Crypto 2010. For physical attacks such as side-channel and cold boot attacks, we need to study key recovery from a noisy secret key containing both erasures and errors. In this paper, we propose a method to recover a secret key from such an erroneous version and analyze the condition for error and erasure rates so that our algorithm succeeds in finding the correct secret key in polynomial time. We also evaluate a theoretical bound to recover the secret key and discuss to what extent our algorithm achieves this bound.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E97-A No.6 pp.1273-1284

Publication Date: 2014/06/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1587/transfun.E97.A.1273

Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

Category

Authors

Noboru KUNIHIRO
  The University of Tokyo
Naoyuki SHINOHARA
  NICT
Tetsuya IZU
  Fujitsu Laboratories

Keyword

RSA, key-recovery, cold boot attack, side-channel attack, maximal likelihood

Cite this

Copy

Noboru KUNIHIRO, Naoyuki SHINOHARA, Tetsuya IZU, "Recovering RSA Secret Keys from Noisy Key Bits with Erasures and Errors" in IEICE TRANSACTIONS on Fundamentals, vol. E97-A, no. 6, pp. 1273-1284, June 2014, doi: 10.1587/transfun.E97.A.1273.
Abstract: We discuss how to recover RSA secret keys from noisy key bits with erasures and errors. There are two known algorithms recovering original secret keys from noisy keys. At Crypto 2009, Heninger and Shacham proposed a method for the case where an erroneous version of secret keys contains only erasures. Subsequently, Henecka et al. proposed a method for an erroneous version containing only errors at Crypto 2010. For physical attacks such as side-channel and cold boot attacks, we need to study key recovery from a noisy secret key containing both erasures and errors. In this paper, we propose a method to recover a secret key from such an erroneous version and analyze the condition for error and erasure rates so that our algorithm succeeds in finding the correct secret key in polynomial time. We also evaluate a theoretical bound to recover the secret key and discuss to what extent our algorithm achieves this bound.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1587/transfun.E97.A.1273/_p

Copy

@ARTICLE{e97-a_6_1273,
author={Noboru KUNIHIRO, Naoyuki SHINOHARA, Tetsuya IZU, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Recovering RSA Secret Keys from Noisy Key Bits with Erasures and Errors},
year={2014},
volume={E97-A},
number={6},
pages={1273-1284},
abstract={We discuss how to recover RSA secret keys from noisy key bits with erasures and errors. There are two known algorithms recovering original secret keys from noisy keys. At Crypto 2009, Heninger and Shacham proposed a method for the case where an erroneous version of secret keys contains only erasures. Subsequently, Henecka et al. proposed a method for an erroneous version containing only errors at Crypto 2010. For physical attacks such as side-channel and cold boot attacks, we need to study key recovery from a noisy secret key containing both erasures and errors. In this paper, we propose a method to recover a secret key from such an erroneous version and analyze the condition for error and erasure rates so that our algorithm succeeds in finding the correct secret key in polynomial time. We also evaluate a theoretical bound to recover the secret key and discuss to what extent our algorithm achieves this bound.},
keywords={},
doi={10.1587/transfun.E97.A.1273},
ISSN={1745-1337},
month={June},}

Copy

TY - JOUR
TI - Recovering RSA Secret Keys from Noisy Key Bits with Erasures and Errors
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1273
EP - 1284
AU - Noboru KUNIHIRO
AU - Naoyuki SHINOHARA
AU - Tetsuya IZU
PY - 2014
DO - 10.1587/transfun.E97.A.1273
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E97-A
IS - 6
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - June 2014
AB - We discuss how to recover RSA secret keys from noisy key bits with erasures and errors. There are two known algorithms recovering original secret keys from noisy keys. At Crypto 2009, Heninger and Shacham proposed a method for the case where an erroneous version of secret keys contains only erasures. Subsequently, Henecka et al. proposed a method for an erroneous version containing only errors at Crypto 2010. For physical attacks such as side-channel and cold boot attacks, we need to study key recovery from a noisy secret key containing both erasures and errors. In this paper, we propose a method to recover a secret key from such an erroneous version and analyze the condition for error and erasure rates so that our algorithm succeeds in finding the correct secret key in polynomial time. We also evaluate a theoretical bound to recover the secret key and discuss to what extent our algorithm achieves this bound.
ER -