Survey: Recovering cryptographic keys from partial information, by example
Authors
Gabrielle De Micheli, Nadia Heninger
Gabrielle De Micheli
University of California, San Diego, USA
gdemicheli at ucsd dot edu
gdemicheli at ucsd dot edu
Nadia Heninger
University of California, San Diego, USA
nadiah at cs dot ucsd dot edu
nadiah at cs dot ucsd dot edu
Abstract
Side-channel attacks targeting cryptography may leak only partial or indirect information about the secret keys. There are a variety of techniques in the literature for recovering secret keys from partial information. In this work, we survey several of the main families of partial key recovery algorithms for RSA, (EC)DSA, and (elliptic curve) Diffie-Hellman, the classical public-key cryptosystems in common use today. We categorize the known techniques by the structure of the information that is learned by the attacker, and give simplified examples for each technique to illustrate the underlying ideas.
References
[ANT+20]
Diego F. Aranha, Felipe Rodrigues Novaes, Akira Takahashi, Mehdi Tibouchi, and Yuval Yarom.
LadderLeak: breaking ECDSA with less than one bit of nonce leakage.
In Jay Ligatti, Xinming Ou, Jonathan Katz, and Giovanni Vigna, editors, ACM CCS 2020, 225–242. November 2020. ACM Press.
https://doi.org/10.1145/3372297.3417268.
[AS08]
Onur Aciiçmez and Werner Schindler.
A vulnerability in RSA implementations due to instruction cache analysis and its demonstration on OpenSSL.
In Tal Malkin, editor, CT-RSA 2008, volume 4964 of LNCS, 256–273. April 2008. Springer, Heidelberg.
https://doi.org/10.1007/978-3-540-79263-5_16.
[ASK07]
Onur Aciiçmez, Werner Schindler, and Çetin Kaya Koç.
Cache based remote timing attack on the AES.
In Masayuki Abe, editor, CT-RSA 2007, volume 4377 of LNCS, 271–286. February 2007. Springer, Heidelberg.
https://doi.org/10.1007/11967668_18.
[BBG+17]
Daniel J. Bernstein, Joachim Breitner, Daniel Genkin, Leon Groot Bruinderink, Nadia Heninger, Tanja Lange, Christine van Vredendaal, and Yuval Yarom.
Sliding right into disaster: left-to-right sliding windows leak.
In Wieland Fischer and Naofumi Homma, editors, CHES 2017, volume 10529 of LNCS, 555–576. September 2017. Springer, Heidelberg.
https://doi.org/10.1007/978-3-319-66787-4_27.
[BCC+13]
Daniel J. Bernstein, Yun-An Chang, Chen-Mou Cheng, Li-Ping Chou, Nadia Heninger, Tanja Lange, and Nicko van Someren.
Factoring RSA keys from certified smart cards: Coppersmith in the wild.
In Kazue Sako and Palash Sarkar, editors, ASIACRYPT 2013, Part II, volume 8270 of LNCS, 341–360. December 2013. Springer, Heidelberg.
https://doi.org/10.1007/978-3-642-42045-0_18.
[BDF98]
Dan Boneh, Glenn Durfee, and Yair Frankel.
An attack on RSA given a small fraction of the private key bits.
In Kazuo Ohta and Dingyi Pei, editors, ASIACRYPT'98, volume 1514 of LNCS, 25–34. October 1998. Springer, Heidelberg.
https://doi.org/10.1007/3-540-49649-1_3.
[Ber05]
Daniel J. Bernstein.
Cache-timing attacks on AES.
2005.
[Ble98]
Daniel Bleichenbacher.
Chosen ciphertext attacks against protocols based on the RSA encryption standard PKCS #1.
In Hugo Krawczyk, editor, CRYPTO'98, volume 1462 of LNCS, 1–12. August 1998. Springer, Heidelberg.
https://doi.org/10.1007/BFb0055716.
[BM03]
Johannes Blömer and Alexander May.
New partial key exposure attacks on RSA.
In Dan Boneh, editor, CRYPTO 2003, volume 2729 of LNCS, 27–43. August 2003. Springer, Heidelberg.
https://doi.org/10.1007/978-3-540-45146-4_2.
[Boo51]
Andrew D. Booth.
A signed binary mutiplication technique.
Q. J. Mech. Appl. Math., 4(2):236–240, January 1951.
https://doi.org/?
[BR95]
Mihir Bellare and Phillip Rogaway.
Optimal asymmetric encryption.
In Alfredo De Santis, editor, EUROCRYPT'94, volume 950 of LNCS, 92–111. May 1995. Springer, Heidelberg.
https://doi.org/10.1007/BFb0053428.
[BV96]
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'96, volume 1109 of LNCS, 129–142. August 1996. Springer, Heidelberg.
https://doi.org/10.1007/3-540-68697-5_11.
[BvSY14]
Naomi Benger, Joop van de Pol, Nigel P. Smart, and Yuval Yarom.
“ooh aah... just a little bit”: a small amount of side channel can go a long way.
In Lejla Batina and Matthew Robshaw, editors, CHES 2014, volume 8731 of LNCS, 75–92. September 2014. Springer, Heidelberg.
https://doi.org/10.1007/978-3-662-44709-3_5.
[Cop96]
Don Coppersmith.
Finding a small root of a bivariate integer equation; factoring with high bits known.
In Ueli M. Maurer, editor, EUROCRYPT'96, volume 1070 of LNCS, 178–189. May 1996. Springer, Heidelberg.
https://doi.org/10.1007/3-540-68339-9_16.
[DDE+18]
Fergus Dall, Gabrielle De Micheli, Thomas Eisenbarth, Daniel Genkin, Nadia Heninger, Ahmad Moghimi, and Yuval Yarom.
CacheQuote: efficiently recovering long-term secrets of SGX EPID via cache attacks.
IACR TCHES, 2018(2):171–191, 2018.
https://doi.org/10.13154/tches.v2018.i2.171-191.
[DH76]
Whitfield Diffie and Martin E. Hellman.
New directions in cryptography.
IEEE Trans. Information Theory, 22(6):644–654, 1976.
https://doi.org/?
[DHMP13]
Elke De Mulder, Michael Hutter, Mark E. Marson, and Peter Pearson.
Using Bleichenbacher's solution to the hidden number problem to attack nonce leaks in 384-bit ECDSA.
In Guido Bertoni and Jean-Sébastien Coron, editors, CHES 2013, volume 8086 of LNCS, 435–452. August 2013. Springer, Heidelberg.
https://doi.org/10.1007/978-3-642-40349-1_25.
[DPP20]
Gabrielle De Micheli, Rémi Piau, and Cécile Pierrot.
A tale of three signatures: practical attack of ECDSA with wNAF.
In Abderrahmane Nitaj and Amr M. Youssef, editors, AFRICACRYPT 20, volume 12174 of LNCS, 361–381. July 2020. Springer, Heidelberg.
https://doi.org/10.1007/978-3-030-51938-4_18.
[EG85]
Taher El Gamal.
A public key cryptosystem and a signature scheme based on discrete logarithms.
IEEE Trans. Information Theory, 31(4):469–472, 1985.
https://doi.org/?
[EL85]
Wim Van Eck and Neher Laborato.
Electromagnetic radiation from video display units: an eavesdropping risk?
Computers and Security, 4:269–286, 1985.
https://doi.org/?
[FH08]
J. Ferrigno and M. Hlavac.
When AES blinks: introducing optical side channel.
Information Security, IET, 2:94 – 98, 10 2008.
https://doi.org/10.1049/iet-ifs:20080038.
[FWC16]
Shuqin Fan, Wenbo Wang, and Qingfeng Cheng.
Attacking OpenSSL implementation of ECDSA with a few signatures.
In Edgar R. Weippl, Stefan Katzenbeisser, Christopher Kruegel, Andrew C. Myers, and Shai Halevi, editors, ACM CCS 2016, 1505–1515. October 2016. ACM Press.
https://doi.org/10.1145/2976749.2978400.
[Gar59]
Harvey L. Garner.
The residue number system.
IRE Trans. Electron. Computers, EC-8(2):140–147, Jun 1959.
https://doi.org/?
[Gor98]
Daniel M. Gordon.
A survey of fast exponentiation methods.
J. Algorithms, 27(1):129–146, April 1998.
https://doi.org/10.1006/jagm.1997.0913.
[GST14]
Daniel Genkin, Adi Shamir, and Eran Tromer.
RSA key extraction via low-bandwidth acoustic cryptanalysis.
In Juan A. Garay and Rosario Gennaro, editors, CRYPTO 2014, Part I, volume 8616 of LNCS, 444–461. August 2014. Springer, Heidelberg.
https://doi.org/10.1007/978-3-662-44371-2_25.
[HG97]
Nicholas Howgrave-Graham.
Finding small roots of univariate modular equations revisited.
In Michael Darnell, editor, Cryptography and Coding, 131–142. Berlin, Heidelberg, 1997. Springer Berlin Heidelberg.
https://doi.org/?
[HG98]
Nicholas A Howgrave-Graham.
Computational Mathematics Inspired by RSA.
PhD thesis, University of Bath, 1998.
[HG01]
Nick Howgrave-Graham.
Approximate integer common divisors.
In Joseph H. Silverman, editor, Cryptography and Lattices: International Conference, CaLC 2001 Providence, RI, USA, March 29–30, 2001 Revised Papers, 51–66. Berlin, Heidelberg, 2001. Springer Berlin Heidelberg.
https://doi.org/10.1007/3-540-44670-2_6.
[HM08]
Mathias Herrmann and Alexander May.
Solving linear equations modulo divisors: on factoring given any bits.
In Josef Pieprzyk, editor, ASIACRYPT 2008, volume 5350 of LNCS, 406–424. December 2008. Springer, Heidelberg.
https://doi.org/10.1007/978-3-540-89255-7_25.
[HR07]
Martin Hlavác and Tomás Rosa.
Extended hidden number problem and its cryptanalytic applications.
In Eli Biham and Amr M. Youssef, editors, SAC 2006, volume 4356 of LNCS, 114–133. August 2007. Springer, Heidelberg.
https://doi.org/10.1007/978-3-540-74462-7_9.
[HS09]
Nadia Heninger and Hovav Shacham.
Reconstructing RSA private keys from random key bits.
In Shai Halevi, editor, CRYPTO 2009, volume 5677 of LNCS, 1–17. August 2009. Springer, Heidelberg.
https://doi.org/10.1007/978-3-642-03356-8_1.
[HS14]
Michael Hutter and Jörn-Marc Schmidt.
The temperature side channel and heating fault attacks.
In Aurélien Francillon and Pankaj Rohatgi, editors, Smart Card Research and Advanced Applications, 219–235. Cham, 2014. Springer International Publishing.
https://doi.org/?
[HSH+08]
J. Alex Halderman, Seth D. Schoen, Nadia Heninger, William Clarkson, William Paul, Joseph A. Calandrino, Ariel J. Feldman, Jacob Appelbaum, and Edward W. Felten.
Lest we remember: cold boot attacks on encryption keys.
In Paul C. van Oorschot, editor, USENIX Security 2008, 45–60. July / August 2008. USENIX Association.
https://doi.org/?
[IGA+15]
Mehmet Sinan Inci, Berk Gülmezoglu, Gorka Irazoqui Apecechea, Thomas Eisenbarth, and Berk Sunar.
Seriously, get off my cloud! Cross-VM RSA key recovery in a public cloud.
IACR Cryptology ePrint Archive, 2015:898, 2015.
https://doi.org/?
[KHF+19]
Paul Kocher, Jann Horn, Anders Fogh, Daniel Genkin, Daniel Gruss, Werner Haas, Mike Hamburg, Moritz Lipp, Stefan Mangard, Thomas Prescher, Michael Schwarz, and Yuval Yarom.
Spectre attacks: exploiting speculative execution.
In 2019 IEEE Symposium on Security and Privacy, 1–19. May 2019. IEEE Computer Society Press.
https://doi.org/10.1109/SP.2019.00002.
[KJJ99]
Paul C. Kocher, Joshua Jaffe, and Benjamin Jun.
Differential power analysis.
In Michael J. Wiener, editor, CRYPTO'99, volume 1666 of LNCS, 388–397. August 1999. Springer, Heidelberg.
https://doi.org/10.1007/3-540-48405-1_25.
[KJJR11]
Paul Kocher, Joshua Jaffe, Benjamin Jun, and Pankaj Rohatgi.
Introduction to differential power analysis.
Journal of Cryptographic Engineering, 1(1):5–27, Apr 2011.
https://doi.org/10.1007/s13389-011-0006-y.
[Koc96]
Paul C. Kocher.
Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems.
In Neal Koblitz, editor, CRYPTO'96, volume 1109 of LNCS, 104–113. August 1996. Springer, Heidelberg.
https://doi.org/10.1007/3-540-68697-5_9.
[LLL82]
Arjen Klaas Lenstra, Hendrik Willem Lenstra, and László Lovász.
Factoring polynomials with rational coefficients.
Mathematische Annalen, 261(4):515–534, 1982.
https://doi.org/?
[LSG+18]
Moritz Lipp, Michael Schwarz, Daniel Gruss, Thomas Prescher, Werner Haas, Anders Fogh, Jann Horn, Stefan Mangard, Paul Kocher, Daniel Genkin, Yuval Yarom, and Mike Hamburg.
Meltdown: reading kernel memory from user space.
In William Enck and Adrienne Porter Felt, editors, USENIX Security 2018, 973–990. August 2018. USENIX Association.
https://doi.org/?
[May10]
Alexander May.
Using LLL-Reduction for Solving RSA and Factorization Problems, pages 315–348.
Springer Berlin Heidelberg, Berlin, Heidelberg, 2010.
https://doi.org/10.1007/978-3-642-02295-1_10.
[MBA+21]
Robert Merget, Marcus Brinkmann, Nimrod Aviram, Juraj Somorovsky, Johannes Mittmann, and Jörg Schwenk.
Raccoon attack: finding and exploiting most-significant-bit-oracles in TLS-DH(E).
In Michael Bailey and Rachel Greenstadt, editors, USENIX Security 2021, 213–230. August 2021. USENIX Association.
https://doi.org/?
[M{\"o}l03]
Bodo Möller.
Improved techniques for fast exponentiation.
In Pil Joong Lee and Chae Hoon Lim, editors, ICISC 02, volume 2587 of LNCS, 298–312. November 2003. Springer, Heidelberg.
https://doi.org/?
[MVH+20]
Daniel Moghimi, Jo Van Bulck, Nadia Heninger, Frank Piessens, and Berk Sunar.
CopyCat: controlled instruction-level attacks on enclaves.
In Srdjan Capkun and Franziska Roesner, editors, USENIX Security 2020, 469–486. August 2020. USENIX Association.
https://doi.org/?
[NIS13]
Digital Signature Standard (DSS).
National Institute of Standards and Technology, 2013.
[NS02]
Phong Q. Nguyen and Igor Shparlinski.
The insecurity of the digital signature algorithm with partially known nonces.
Journal of Cryptology, 15(3):151–176, June 2002.
https://doi.org/10.1007/s00145-002-0021-3.
[NS03]
Phong Q. Nguyen and Igor E. Shparlinski.
The insecurity of the Elliptic Curve Digital Signature Algorithm with partially known nonces.
Des. Codes Cryptography, 30(2):201–217, 2003.
https://doi.org/?
[NS06]
Phong Nguyen and Damien Stehlé.
LLL on the average.
In Proceedings of the 7th International Conference on Algorithmic Number Theory, ANTS'06, 238–256. Berlin, Heidelberg, 2006. Springer-Verlag.
https://doi.org/?
[OST06]
Dag Arne Osvik, Adi Shamir, and Eran Tromer.
Cache attacks and countermeasures: the case of AES.
In David Pointcheval, editor, CT-RSA 2006, volume 3860 of LNCS, 1–20. February 2006. Springer, Heidelberg.
https://doi.org/10.1007/11605805_1.
[OW99]
Paul C. Oorschot and Michael J. Wiener.
Parallel collision search with cryptanalytic applications.
J. Cryptol., 12(1):1–28, January 1999.
https://doi.org/10.1007/PL00003816.
[Pag02]
D. Page.
Theoretical use of cache memory as a cryptanalytic side-channel.
2002.
[Per05]
Colin Percival.
Cache missing for fun and profit.
In BSDCon 2005. Ottawa, CA, 2005.
https://doi.org/?
[Pol78]
John M. Pollard.
Monte Carlo methods for index computation mod $p$.
Mathematics of Computation, 32:918–924, 1978.
https://doi.org/?
[PPS12]
Kenneth G. Paterson, Antigoni Polychroniadou, and Dale L. Sibborn.
A coding-theoretic approach to recovering noisy RSA keys.
In Xiaoyun Wang and Kazue Sako, editors, ASIACRYPT 2012, volume 7658 of LNCS, 386–403. December 2012. Springer, Heidelberg.
https://doi.org/10.1007/978-3-642-34961-4_24.
[QS01]
Jean-Jacques Quisquater and David Samyde.
Electromagnetic analysis (EMA): measures and counter-measures for smart cards.
In Proceedings of the International Conference on Research in Smart Cards: Smart Card Programming and Security, E-SMART '01, 200–210. London, UK, 2001. Springer-Verlag.
https://doi.org/?
[RH23]
Keegan Ryan and Nadia Heninger.
Fast practical lattice reduction through iterated compression.
In Helena Handschuh and Anna Lysyanskaya, editors, CRYPTO 2023, Part III, volume 14083 of LNCS, 3–36. August 2023. Springer, Heidelberg.
https://doi.org/10.1007/978-3-031-38548-3_1.
[Rup10]
Raminder Singh Ruprai.
Improvements to the Gaudry-Schost Algorithm for Multidimensional discrete logarithm problems and Applications.
PhD thesis, Royal Holloway University of London, 2010.
[Sch87]
C. P. Schnorr.
A hierarchy of polynomial time lattice basis reduction algorithms.
Theor. Comput. Sci., 53(2-3):201–224, August 1987.
https://doi.org/10.1016/0304-3975(87)90064-8.
[Sch90]
Claus-Peter Schnorr.
Efficient identification and signatures for smart cards.
In Gilles Brassard, editor, CRYPTO'89, volume 435 of LNCS, 239–252. August 1990. Springer, Heidelberg.
https://doi.org/10.1007/0-387-34805-0_22.
[SE94]
C. P. Schnorr and M. Euchner.
Lattice basis reduction: improved practical algorithms and solving subset sum problems.
Math. Program., 66(2):181–199, September 1994.
https://doi.org/10.1007/BF01581144.
[Tes00]
Edlyn Teske.
On random walks for Pollard's Rho method.
Mathematics of Computation, 70:809–825, 2000.
https://doi.org/?
[TSS+03]
Yukiyasu Tsunoo, Teruo Saito, Tomoyasu Suzaki, Maki Shigeri, and Hiroshi Miyauchi.
Cryptanalysis of DES implemented on computers with cache.
In Colin D. Walter, Çetin Kaya Koç, and Christof Paar, editors, CHES 2003, volume 2779 of LNCS, 62–76. September 2003. Springer, Heidelberg.
https://doi.org/10.1007/978-3-540-45238-6_6.
[TTA18]
Akira Takahashi, Mehdi Tibouchi, and Masayuki Abe.
New Bleichenbacher records: fault attacks on qDSA signatures.
IACR TCHES, 2018(3):331–371, 2018.
https://doi.org/10.13154/tches.v2018.i3.331-371.
[TTMH02]
Yukiyasu Tsunoo, Etsuko Tsujihara, Kazuhiko Minematsu, and Hiroshi Hiyauchi.
Cryptanalysis of block ciphers implemented on computers with cache.
In International Symposium on Information Theory and Its Applications. Xi'an, CN, October 2002.
https://doi.org/?
[YGH16]
Yuval Yarom, Daniel Genkin, and Nadia Heninger.
CacheBleed: A timing attack on OpenSSL constant time RSA.
In Benedikt Gierlichs and Axel Y. Poschmann, editors, CHES 2016, volume 9813 of LNCS, 346–367. August 2016. Springer, Heidelberg.
https://doi.org/10.1007/978-3-662-53140-2_17.
PDF
History
Submitted: 2024-01-09
Accepted: 2024-03-05
Published: 2024-04-09
Accepted: 2024-03-05
Published: 2024-04-09
How to cite
Gabrielle De Micheli and Nadia Heninger, "Survey: Recovering cryptographic keys from partial information, by example," IACR Communications in Cryptology, vol. 1, no. 1, Apr 09, 2024, doi: 10.62056/ahjbksdja.
License
Copyright is held by the author(s)
This work is licensed under a Creative Commons Attribution (CC BY) license.