Abstract
In a cold boot attack a cryptosystem is compromised by analysing a noisy version of its internal state. For instance, if a computer is rebooted the memory contents are rarely fully reset; instead, after the reboot an adversary might recover a noisy image of the old memory contents and use it as a stepping stone for reconstructing secret keys. While such attacks were known for a long time, they recently experienced a revival in the academic literature. Here, typically either RSA-based schemes or blockciphers are targeted.
We observe that essentially no work on cold boot attacks on schemes defined in the discrete logarithm setting (DL) and particularly for elliptic curve cryptography (ECC) has been conducted. In this paper we hence consider cold boot attacks on selected wide-spread implementations of DL-based cryptography. We first introduce a generic framework to analyse cold boot settings and construct corresponding key-recovery algorithms. We then study common in-memory encodings of secret keys (in particular those of the wNAF-based and comb-based ECC implementations used in OpenSSL and PolarSSL, respectively), identify how redundancies can be exploited to make cold boot attacks effective, and develop efficient dedicated key-recovery algorithms. We complete our work by providing theoretical bounds for the success probability of our attacks.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Albrecht, M., Cid, C.: Cold boot key recovery by solving polynomial systems with noise. In: Lopez, J., Tsudik, G. (eds.) ACNS 2011. LNCS, vol. 6715, pp. 57–72. Springer, Heidelberg (2011)
Bos, J.W., Costello, C., Longa, P., Naehrig, M.: Selecting elliptic curves for cryptography: An efficiency and security analysis. Cryptology ePrint Archive, Report 2014/130 (2014). http://eprint.iacr.org/2014/130
Gutmann, P.: Data remanence in semiconductor devices. In: 10th USENIX Security Symposium USENIX, Washington. D.C., USA, August 13–17, 2001
Halderman, J.A., Schoen, S.D., Heninger, N., Clarkson, W., Paul, W., Calandrino, J.A., Feldman, A.J., Appelbaum, J., Felten, E.W.: Lest we remember: cold-boot attacks on encryption keys. Commun. ACM 52(5), 91–98 (2009)
Hankerson, D., Menezes, A., Vanstone, S.: Guide to Elliptic Curve Cryptography. Springer (2004)
Hedabou, M., Pinel, P., Bénéteau, L.: A comb method to render ECC resistant against side channel attacks. Cryptology ePrint Archive, Report 2004/342 (2004). http://eprint.iacr.org/2004/342
Henecka, W., May, A., Meurer, A.: Correcting errors in RSA private keys. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 351–369. Springer, Heidelberg (2010)
Heninger, N., Shacham, H.: Reconstructing RSA private keys from random key bits. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 1–17. Springer, Heidelberg (2009)
Jonsson, J., Kaliski, B.S.: Public-Key Cryptography Standards (PKCS) #1: RSA Cryptography Specifications Version 2.1 (RFC 3447) (2003). https://www.ietf.org/rfc/rfc3447.txt
Kamal, A.A., Youssef, A.M.: Applications of SAT solvers to AES key recovery from decayed key schedule images. Cryptology ePrint Archive, Report 2010/324 (2010). http://eprint.iacr.org/2010/324
Kunihiro, N., Honda, J.: RSA meets DPA: Recovering RSA secret keys from noisy analog data. In: Batina, L., Robshaw, M. (eds.) CHES 2014. LNCS, vol. 8731, pp. 261–278. Springer, Heidelberg (2014)
Kunihiro, N., Shinohara, N., Izu, T.: Recovering RSA secret keys from noisy key bits with erasures and errors. In: Kurosawa, K., Hanaoka, G. (eds.) PKC 2013. LNCS, vol. 7778, pp. 180–197. Springer, Heidelberg (2013)
Lee, H.T., Kim, H.T., Baek, Y.-J., Cheon, J.H.: Correcting errors in private keys obtained from cold boot attacks. In: Kim, H. (ed.) ICISC 2011. LNCS, vol. 7259, pp. 74–87. Springer, Heidelberg (2012)
Lim, C.H., Lee, P.J.: More flexible exponentiation with precomputation. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 95–107. Springer, Heidelberg (1994)
Möller, B.: Improved techniques for fast exponentiation. In: Lee, P.J., Lim, C.H. (eds.) ICISC 2002. LNCS, vol. 2587, pp. 298–312. Springer, Heidelberg (2003)
Paterson, K.G., Polychroniadou, A., Sibborn, D.L.: A coding-theoretic approach to recovering noisy RSA keys. In: Wang, X., Sako, K. (eds.) ASIACRYPT 2012. LNCS, vol. 7658, pp. 386–403. Springer, Heidelberg (2012)
Poettering, B., Sibborn, D.: Cold boot attacks in the discrete logarithm setting. Cryptology ePrint Archive, Report 2015/057 (2015). http://eprint.iacr.org/2015/057
Sarkar, S., Gupta, S.S., Maitra, S.: Reconstruction and error correction of RSA secret parameters from the MSB side. In: WCC 2011 - Workshop on Coding and Cryptography, pp. 7–16. Paris, France, April 2011
Sarkar, S., Maitra, S.: Side channel attack to actual cryptanalysis: Breaking CRT-RSA with low weight decryption exponents. In: Prouff, E., Schaumont, P. (eds.) CHES 2012. LNCS, vol. 7428, pp. 476–493. Springer, Heidelberg (2012)
Scheick, L.Z., Guertin, S.M., Swift, G.M.: Analysis of radiation effects on individual DRAM cells. Nuclear Science, IEEE Transactions on 47(6), 2534–2538 (2000)
Tsow, A.: An improved recovery algorithm for decayed AES key schedule images. In: Jacobson Jr., M.J., Rijmen, V., Safavi-Naini, R. (eds.) sac 2009. lncs, vol. 5867, pp. 215–230. Springer, Heidelberg (2009)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Poettering, B., Sibborn, D.L. (2015). Cold Boot Attacks in the Discrete Logarithm Setting. In: Nyberg, K. (eds) Topics in Cryptology –- CT-RSA 2015. CT-RSA 2015. Lecture Notes in Computer Science(), vol 9048. Springer, Cham. https://doi.org/10.1007/978-3-319-16715-2_24
Download citation
DOI: https://doi.org/10.1007/978-3-319-16715-2_24
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-16714-5
Online ISBN: 978-3-319-16715-2
eBook Packages: Computer ScienceComputer Science (R0)