Chip Security Testing ##### ALL-IN-ONE PLATFORM

##### PHYSICAL ATTACKS

##### EXPERTISE SERVICES

New advanced analytical tools, increased customization options, and improved integration capabilities.

esDynamic

Manage your attack workflows in a powerful and collaborative platform.

Expertise Modules

Executable catalog of attacks and techniques.

Infrastructure

Integrate your lab equipment and remotely manage your bench.

Lab equipments

Upgrade your lab with the latest hardware technologies.

Side Channel Attacks

Evaluate cryptography algorithms from data acquitition to result visualisation.

Fault Injection Attacks

Laser, Electromagnetic or Glitch to exploit a physical disruption.

Security Failure Analysis

Explore photoemission and thermal laser stimulation techniques.

Evaluation Lab

Our team is ready to provide expert analysis of your hardware.

Starter Kits

Build know-how via built-in use cases developed on modern chips.

Cybersecurity Training

Grow expertise with hands-on training modules guided by a coach.

Binary Security Analysis ##### ALL-IN-ONE PLATFORM

##### DIFFERENT USAGES

##### EXPERTISE SERVICES

Get started with 𝗲𝘀𝗥𝗲𝘃𝗲𝗿𝘀𝗲: the collaborative platform for advanced software binary analyses.

esReverse

**Static**,**dynamic**and**stress testing**in a powerful and collaborative platform.Extension: Intel x86, x64

Dynamic analyses for x86/x64 binaries with dedicated emulation frameworks.

Extension: ARM 32, 64

Dynamic analyses for ARM binaries with dedicated emulation frameworks.

Penetration Testing

Identify and exploit system vulnerabilities in a single platform.

Vulnerability Research

Uncover and address security gaps faster and more efficiently.

Code Audit & Verification

Effectively detect and neutralise harmful software.

Digital Forensics

Collaboratively analyse data to ensure thorough investigation.

Software Assessment

Our team is ready to provide expert analysis of your binary code.

Cybersecurity training

Grow expertise with hands-on training modules guided by a coach.

Resources ##### INDUSTRIES

##### ABOUT US

##### FOLLOW US

BlogEmpowering teams with 𝗸𝗻𝗼𝘄-𝗵𝗼𝘄 to build a more secure world through cybersecurity. Join our mission.

Semiconductor

Security Labs

Governmental agencies

Academics

Why eShard?

Our team

Careers

Linkedin

Twitter

Youtube

Gitlab

Github

Back to all articles

Chip Security

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.

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.

*“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…

*« 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.

*“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

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*

*“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.

*“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!

[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]