Lattice Wars - Episode II

Introduction

Today, public key cryptography is more and more popular thanks to the ubiquitous usage of digital signatures. Since the beginning of this revolution in cryptography, the Lattice silently plays an important role similar to the Force in the Star Wars movies, balancing between serving the Sith sometimes, and the Jedi on other times.

In this blogpost, because it has become an essential concept, we will highlight both dark and light sides of Lattice through their contributions over more than forty years of public key cryptography, and beyond.

A long time ago on a Crypto Planet

One of the first proposed public key cryptosystems, as an alternative to the famous RSA [RSA78], was proposed by two Jedi, Merkle and Hellman [MH78] in 1978. Based on the subset sum (or knapsack) problem, this quite simple and straightforward algorithm is based on an NP-Complete problem [GJ79]. Despite this, the original version of this cryptosystem was broken five years later by Shamir [Sha84], a Jedi temporarily attracted by the dark side of the Force. Indeed, behind this attack, the Lattice reduction technique, developed in the meantime by Jedi mathematicians Lenstra, Lenstra and Lovàsz [LLL82], [L83]. A powerful weapon was revealed for the first time to the crypto Empire.

From the past comes the future

“When you look at the dark side, careful you must be. For the dark side looks back.” – Yoda

Leveraging on the Lattice tools to attack Merkle-Hellman cryptosystem, Jedi Shamir and Rivest realized a premonition that the Force of Lattice may play against RSA [RS86] when partial information is available to the cryptanalyst. This was first confirmed ten years later when the famous Coppersmith Sith published, in a seminal paper [Cop97], how the Lattice Force can break a small exponent RSA. This was the beginning of the rise of a dark period, summarized in [Dur02] and [Won15S], where the focus was on key size, parameter choice and making protocols safe against chosen ciphertext attacks [Ble98]. Indeed, if there is some partial information available, Lattice Force can convert this star dust to penetrate Jedi secrets. Before looking at these dark stars, let us recall from where the light started to blink…

The Power of the Force

« A Jedi uses the Force for knowledge and defense, never for attack. » — Yoda

When a Jedi comes with a public key cryptosystem, the good practice is to establish the link between an NP Hard problem and the cryptosystem. In the case of Diffie-Hellman (DH) key exchange [DH76], two Force sensitive people D. Boneh and H. Verkatesan [BV96], introduced the Hidden Number Problem (HNP). They showed that computing the most significant bits of the secret key exchanged during the DH protocol from the public keys of the participants is as hard as computing the secret key itself. In this important result, the link is made between DH security and problems in Lattice; proven NP hard to solve (namely, the Closest Vector Problem CVP, and the Shortest Vector Problem SVP). Unfortunately, it took not so much time for the Sith to return and convert the light into deep darkness.

A little loss of Entropy - When a proof becomes a weakness

“Smaller in number are we, but larger in mind.” – Yoda

Because few bits of the secret are as hard to obtain as the whole secret, this means that an oracle can be used by a Sith with the Lattice Force to recover the secret providing very little information. This is the root of Boneh and Vertatesan demonstration. In the meantime, a powerful Sith named P. Kocher [Koc96, KJJ99] brought to the dark side the path to a new kind of partial information retrieval called side-channel. The root of evil is simply that only machines can compute with big numbers involved in public key cryptosystems. By observing the machine, the time it takes, the power it needs, the radiation it emits, the Sith has big potential information to feed his Lattices.

Sith love playing games like the HNP [BV96]... This game consists of finding your secret quantity, say , giving to the Sith little information of resulting multiples of your secret with a sequence of known random multipliers of your choice. By little information it is meant that, an oracle is providing for instance a few bits of each multiple . Using Lattice Force, the Sith can win the game as soon as the Sith has collected enough oracle instances, depending on the game setup.

Since the end of the 20th century, Sith and Jedi have played a lot and pointed several places where the Force of Lattice can leverage implementation or parameter setting weaknesses to attack public key cryptosystems in practice. Not only RSA, like illustrated by ROCA [NSSKM17], but also EC-DSA implementations were broken leveraging side-channel leakages. From timing, e.g. OpenSSL EC-DSA implementation [Won15T], EC-DSA signature operated by some TPM (Trusted Platform Module) devices [MSEH19], or some cryptographic libraries [JSSS20], to the Electromagnetic observation of authentication devices, e.g. A Side Journey to Titan [RLMI21], the last two decades is bringing us many examples of side-channel leakage leveraged as a killing oracle. Even more worrying, a small statistical bias in EC-DSA nonce generation, source of loss of entropy, was shown to allow the computation of hundreds of Bitcoin private keys and dozens of Ethereum, Ripple, SSH, and HTTPS private keys [HB19]. Definitely, today’s public key implementations are hard to achieve properly, and we must keep in mind this advice: “Always pass on what you have learned.” — Yoda

May the Lattice our Future be

“Named must your fear be, before banish it you can.” – Yoda

As we noticed, Lattice are present from the very beginning of the public key story, and will certainly pave the way to our future. As a result of the technology and science progress, the arrival of this new type of computer coupled to “periodicity finding” algorithms, like Shor’s algorithm [Shor94, Shor99] and refinements [Eke18, Kal17], will void the security of most of the Public Key algorithm in use today. But, the light side is bringing a new hope today. Indeed, the Cryptography planet is looking for replacement solutions called Post Quantum Cryptography, PQC for short. Among them, the Lattice light Force plays an important role because periodicity finding algorithms do not seem to be applicable to lattice problems. Indeed, among all proposals collected by NIST PQC Project since 2016 [NIS16], many are based on Lattice problems known to be hard when dimensions are appropriate. After 3 rounds of selection, five among the seven finalists are Lattice based. The choice of the Lattice, structured or not, its dimension can be defined for making the underlying NP-Hard problem instance impossible to solve from the complexity stand point.

The Force Paradox

“Difficult to see. Always in motion is the future.” — Yoda

Even if based on the Lattice problem, a cryptographic algorithm does not escape from the threat of side-channel as shown by [KA21] on FALCON, one of PQC NIST round 3 finalists. In this case, The Jedi proposing FALCON uses Laser Saber (Fast Fourier Transform FFT) inside the design and the noise of the Saber in action (understand the floating point multiplication of FFT coefficients) as a side-channel to recover the secret of the signer. Besides, the dark side of Lattice can also threaten the Lattice-based cryptosystem of the light side, as illustrated by the BLISS attack [GHLY16]. But we learned: in the PQC requirements listed by NIST the side-channel resistance is listed… but what about fault injection?

Beyond the analogy with the Force, to tame the manyfold aspects of Lattices is a must today. The challenges are, on one hand to fully understand and evaluate emerging PQC proposals, and on the other hand to master exploitation of the information obtained by side-channel or fault injection, keeping in mind that these attacks can be done remotely [TBP20, GDTLO19].

May the Force be with cryptologists 😉

PS: We apologize in advance to the cryptologist we qualified as Sith or Jedi in this blog post, but we are sure no one will complain as, of course, we all have, deep inside us, both directions of the Force to make cryptography and security stronger and stronger. The force is strong with them!

References

[RSA78] R. L. Rivest, A. Shamir, and L. Adleman (1978). “A method for obtaining digital signatures and public key cryptosystems”. Commun. of the ACM, 21:120-126, 1978.

[MH78] R. Merkle and M. Hellman (1978), “Hiding information and signatures in trapdoor knapsacks”, IEEE Transactions on Information Theory, Vol. IT-24, No. 5, 1978, pp. 525–530.

[GJ79] M.R.Garey and D.S.Johnson (1979), “Computers and Intractability: A Guide to the Theory of NP–Completeness”, W.H.Freeman & Company, 1979

[Sha84] A. Shamir (1984), “A polynomial-time algorithm for breaking the basic Merkle-Hellman cryptosystem”, IEEE Transactions on Information Theory, Vol. IT-30, No. 5, September 1984, pp. 699–704.

[LLL82] A. K. Lenstra, H. W. Lenstra, Jr., and L. Lovàsz (1982), “Factoring polynomials with rational coefficients”, Mathematische Annalen, Vol. 261, No. 4, 1982, pp. 515–534.

[L83] Lenstra, H. W. (1983), “Integer Programming with a Fixed Number of Variables.” Mathematics of Operations Research, vol. 8, no. 4, INFORMS, 1983, pp. 538–48, http://www.jstor.org/stable/3689168.

[RS86] R. L. Rivest and A. Shamir (1986), “Efficient factoring based on partial information”, Advances in Cryptology— EUROCRYPT ’85, pp. 31–34, LNCS, 219, Springer-Verlag, Berlin, 1986.

[Cop97] D. Coppersmith (1197), “Small solutions to polynomial equations, and low exponent RSA vulnerabilities”. Journal of Cryptology, 10:233-260, 1997.

[Dur02] G. Durfee (2002), “Cryptanalysis of RSA Using Algebraic and Lattice Methods”, Ph.D. Dissertation at Stanford University, June 2002.

[Won15S] D. Wong (2015), “Survey: Lattice Reduction Attacks on RSA” [pdf].

[Ble98] Bleichenbacher, Daniel (1998). "Chosen Ciphertext Attacks Against Protocols Based on the RSA Encryption Standard PKCS #1". Crypto '98: 1–12.

[DH76] W. Diffie, M. E. Hellman (1976). "New Directions in Cryptography". IEEE Transactions on Information Theory. 22 (6): 644–654.

[BV96] D. Boneh, R. Venkatesan (1996), “Hardness of Computing the Most Significant Bits of Secret Keys in Diffie-Hellman and Related Schemes.” CRYPTO (1996).

[Koc96] P. Kocher (1996), “Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems”. [pdf] CRYPTO 1996: 104–113

[KJJ99] P. Kocher, J. Jaffe, B. Jun (1999), “Differential Power Analysis”. In: Wiener M. (eds) Advances in Cryptology — CRYPTO’ 99. CRYPTO 1999. Lecture Notes in Computer Science, vol 1666. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48405-1_25 [pdf]

[NSSKM17] M. Nemec, M. Sys, P. Svenda, D. Klinec, V. Matyas (2017), “The Return of Coppersmith's Attack: Practical Factorization of Widely Used RSA Moduli”, CCS '17: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, October 2017. pp. 1631–1648.

[Won15T] D. Wong (2015). “Timing and Lattice Attacks on a Remote ECDSA OpenSSL Server: How Practical Are They Really?”. https://eprint.iacr.org/2015/839.

[MSEH19] D. Moghimi, B. Sunar, T. Eisenbarth, N. Heninger (2019). “TPM-FAIL: TPM meets Timing and Lattice Attacks”.

[JSSS20] J. Jančár, V. Sedláček, P. Švenda and M. Sýs (2020), “Minerva: The curse of ECDSA nonces Systematic analysis of lattice attacks on noisy leakage of bit-length of ECDSA nonces”, IACR Transactions on Cryptographic Hardware and Embedded Systems,2020 Num. 4, pp 281-308, doi 10.13154/tches.v2020.i4.281-308 [pdf]

[RLMI21] T. Roche, V. Lomné, C. Mutschler and L. Imbert (2021), “A Side Journey to Titan”, 30th USENIX Security Symposium (USENIX Security 21) pp. 231-248, August 2021.

[HB19] J. Breitner, N. Heninger (2019), “Biased Nonce Sense: Lattice Attacks Against Weak ECDSA Signatures in Cryptocurrencies”. Financial Cryptography 2019: 3-20.

[Shor94] P. Shor (1994), “Algorithms for Quantum Computation: Discrete Logarithms and Factoring”. FOCS 1994: 124-134 [pdf]

[Shor99] P. Shor (1999), “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer” [pdf]

[Eke18] M. Ekera (2018), “Quantum algorithms for computing general discrete logarithms and orders with tradeoffs” [pdf]

[Kal17] B. Kaliski (2017), “A Quantum “Magic Box” for the Discrete Logarithm Problem” [pdf]

[NIS16] NIST. Post-Quantum Crypto Project, December 16, 2016. http://csrc.nist.gov/groups/ST/post-quantum-crypto/.

[KA21] E. Karabulut and A. Aysu (2021), "FALCON Down: Breaking FALCON Post-Quantum Signature Scheme through Side-Channel Attacks," 2021 58th ACM/IEEE Design Automation Conference (DAC), 2021, pp. 691-696, doi: 10.1109/DAC18074.2021.9586131.

[GHLY16] L. Groot Bruinderink, A. Hülsing, T. Lange, and Y. Yarom (2016), “Flush, Gauss, and Reload –A Cache Attack on the BLISS Lattice-Based Signature Scheme” in Cryptographic Hardware and Embedded Systems – CHES 2016. LNCS, vol 9813. Springer, Berlin, Heidelberg.

[TBP20] F. Tramèr, D. Boneh and K. Patterson (2020), “Remote Side-Channel attacks on Anonymous Transactions”, 29th USENIX Security Symposium (USENIX Security 20), ISBN 978-1-939133-17-5, pp 2739-2756 [pdf]

[GDTLO19] J.Gravellier,J.-M. Dutertre, Y. Teglia, P. Loubet-Moundi, F. Olivier (2019), “Remote Side-Channel Attacks on Heterogeneous SoC”, Smart Card Research and Advanced Applications, 18th International Conference, CARDIS 2019 [pdf]