CRoCS logo

This page describes our discovery of a group of side-channel vulnerabilities in implementations of ECDSA/EdDSA in programmable smart cards and cryptographic software libraries. Our attack allows for practical recovery of the long-term private key. We have found implementations which leak the bit-length of the scalar during scalar multiplication on an elliptic curve. This leakage might seem minuscule as the bit-length presents a very small amount of information present in the scalar. However, in the case of ECDSA/EdDSA signature generation, the leaked bit-length of the random nonce is enough for full recovery of the private key used after observing a few hundreds to a few thousands of signatures on known messages, due to the application of lattice techniques.

We have verified our attack against an Athena IDProtect card, running on an Inside Secure AT90SC chip, for more affected devices see the next section. The attack required 11000 signatures to recover the private key on the standard secp256r1 curve, using an off-the-shelf smart card reader, running on an ordinary Linux laptop with a runtime of a few minutes after the collection of signatures. The total time for the attack, including the collection of signatures was around 30 minutes.

Our attack and proof-of-concept code is inspired by the method of Brumley & Tuveri [3], for more details, see the section on the attack. A paper with an improved method is being prepared.

Primary contact: Jan Jancar ENABLE@JAVASCRIPT j08ny CRoCS_MUNI

Update: Added a list of libraries and cards tested and deemed not vulnerable.

Affected devices and libraries

We have tested our attack on an Athena IDProtect card with CPLC data 010b.0352.0005. We further believe the following devices and cryptographic libraries to be affected:

Devices

Likely affected devices

  • Valid S/A IDflex V with card CPLC data:
    • 010b.0352.0005: FIPS 140-2 certificate 1781 (assumed, not tested)
  • SafeNet eToken 4300 with card CPLC data:
    • 010e.1245.0002: FIPS 140-2 certificate 1800 (assumed, not tested)
  • TecSec Armored Card with card CPLC data:
    • 010e.0264.0001: FIPS 140-2 certificate 1986 (assumed, not tested)
    • 0108.0264.0001: FIPS 140-2 certificate 1992 (assumed, not tested)

Libraries

  • libgcrypt: leakage plots CVE-2019-13627 source fix
    • ECDSA: all versions including 1.8.4, introduced in 1.3.0, fixed in 1.8.5
    • EdDSA: all versions including 1.8.4, introduced in 1.6.0, fixed in 1.8.5
      Update: The EdDSA scalar multiplication code in libgcrypt was leaking, however due to the way it was used, it was likely not exploitable. It did not reduce the scalar which was a SHA512 digest by the curve order, but used the digest directly, thus the leakage did not represent the bit-length of the reduced scalar. Thanks to Daniel J. Bernstein for the note.
  • wolfSSL/wolfCrypt: leakage plots CVE-2019-13628 source fix
    • ECDSA: all versions including 4.0.0, fixed in 4.1.0
      The leakage in wolfSSL/wolfCrypt is minuscule and would be very hard to exploit.
  • MatrixSSL: leakage plots CVE-2019-13629 source no fix
    • ECDSA: all versions including 4.2.1
  • SunEC/OpenJDK/Oracle JDK: leakage plots CVE-2019-2894 source no fix our patch
    • ECDSA over binary field curves: all versions including JDK 12, introduced in JDK 7
  • Crypto++: leakage plots CVE-2019-14318 fix
    • ECDSA over binary field curves: all versions including 8.2.0
    • ECDSA over prime field curves: all versions including 8.2.0, significantly smaller leakage.

Other software

We believe all of the cards above are affected because they share a common ECDSA component (FIPS module 214) , which is described as Athena OS755 ECDSA2 Component on Inside Secure AT90SC A1.0 (Firmware). We have tested the vulnerability only on the Athena IDProtect card with CPLC data 010b.0352.0005 and ATR 3bd518ff8191fe1fc38073c8211309.

We believe that the source of the vulnerability of the aforementioned cards utilizing the Athena ECDSA component is the Atmel Toolbox 00.03.11.05 with the Common Criteria certificate DCSSI-CC-2009/11 (security target, certification report, info page). The security target states the following under security functions (on pages 48 and 49):

- M10.6 the TSF shall provide digital signature confirming to EC-DSA standard.
    - Secure digital signature generate
    - Secure digital signature verify
    - Fast digital signature generate (see note*)
    - Fast digital signature verify (see note*)

- M10.7 the TSF shall provide point multiplication on an elliptical curve, conforming to EC-DSA standard.
    - Secure multiply
    - Fast multiply (see note*)

    * The Fast functions of M10.3, M10.4, M10.5, M10.7, M10.8, M10.9, do not
    offer any DPA/SPA protection and must not be used for secure data.

We assume that the vulnerable Athena cards used the fast and insecure functions. Our hypothesis was confirmed to us after discussions with the vendor, see more in the responsible disclosure section.

Tested implementations deemed secure

Most implementations we analyzed during this research did not show any leakage and are thus likely secure. We cannot be sure of this, as our tests might not be exhaustive due to the complexity of the implementations.

The libraries usually have multiple scalar multiplication algorithms and choose from them based on build options, runtime configuration, curve used, cryptosystem used and operation being performed. Thus, our testing might just not have caught a particular configuration that could still be vulnerable. Below, we list libraries we tested and found not vulnerable:

Libraries

  • OpenSSL 1.1.1d
  • BouncyCastle 1.58
  • BoringSSL 974f4dddf
  • libtomcrypt 1.18.2
  • Botan 2.11.0
  • Microsoft CNG
  • mbedTLS 2.16.0
  • Intel IPP-Crypto

Cards

  • ACS ACOSJ 40K
  • Feitian A22CR
  • G&D SmartCafe 6.0
  • G&D SmartCafe 7.0
  • Infineon CJTOP 80K INF SLJ 52GLA080AL M8.4
  • Infineon SLE78 Universal JCard
  • NXP JCOP31 v2.4.1
  • NXP JCOP CJ2A081
  • NXP JCOP v2.4.2 R2
  • NXP JCOP v2.4.2 R3
  • TaiSYS SIMoME VAULT

See the ECTester documentation for more information about tested libraries.

Questions & Answers

  • Is my device affected?
    See the section on affected devices, also if you have access to an unlocked JavaCard, you can test its vulnerability using our proof-of-concept and other testing tools. If you found a device or a library that is affected but is not present in the list above, please contact us.
  • Is my library affected?
    See the section on affected devices, if it is not there and it is supported by the ECTester tool then it is probably not affected, as we tested it (list of supported libraries). If it is not supported, we did not check. Furthermore, even if it is listed and we have tested it, it still may be vulnerable as cryptographic libraries often contain more than one scalar multiplication algorithm implementation, which can be enabled either by build options or sometimes even at runtime, where different algorithms are used for different classes of curves. We have usually tested the libraries in only one configuration and on a few curves (secp256r1, sect233r1...).
  • Are other devices running on the AT90SC chip affected?
    The AT90SC chip was sold along with the Atmel Toolbox, a cryptographic toolbox utilizing the functionality of the Ad-X cryptographic coprocessor to provide some higher/level cryptographic functionality, such as ECDSA or RSA. This toolbox evolved, as the underlying intellectual property was sold from Atmel to Inside Secure (now called Verimatrix) and finally to WiseKey. The vulnerability is known to be present in one concrete version of the toolbox, the Atmel Toolbox 00.03.11.05 on the AT90SC Family of Devices, as specified in the Common Criteria security target of the toolbox. This version of the toolbox contains two versions of ECDSA functionality, secure and fast, the device using the toolbox is affected if it uses the fast version of the primitive, as the above-specified cards do. We do not know if other versions of this toolbox, and the renamed INSIDE Toolbox or WiseKey Toolbox contain the insecure functionality or if they are vulnerable.
  • Why did the Atmel Toolbox contain explicitly insecure functionality?
    We have no idea. Having functions that perform signing or encryption, but are explicitly marked as insecure is possibly faster but also pointless and dangerous as can be seen from the resulting vulnerabilities.
  • Is there a proof of concept?
    Yes, see the next section.
  • Are there any CVEs for Minerva?
    Yes, the following:
  • What is required to perform the attack?
    The attacker needs to be able to measure the duration of hundreds to thousands of signing operations of known messages. The less noise in the measurement is present, the less signatures the attacker needs. The computation of the private key is then a matter of seconds or minutes.
  • Is this exploitable locally?
    Definitely, if the runtime of signing operations performed by an affected device or library is measurable, locally the amount of noise is not enough to stop the attack. We have verified this against the affected libraries, and the code to do so is present in the PoC.
  • Is this exploitable remotely?
    Maybe, Brumley & Tuveri [3] demonstrate the attack using the loopback interface of the same machine and even between two machines sharing the same network switch. We think this could be extended by collection of a larger amount of signatures and an increase in computation time.
  • I own a vulnerable device, can I fix it?
    Probably not, the vulnerability is present in the underlying firmware, which is inaccessible to the user/administrator of the device. However, the firmware might be updateable by the manufacturer. In the case of a vulnerable library, updating it to the newest version should fix it, as most libraries we notified fixed the issue and released a new version.
  • How did this happen? The devices are certified.

    The FIPS 140-2 certification scheme specifically does not require side-channel resistance to be tested by the lab performing the assessment (see [12] page 12 on Mitigation of other attacks). So even though the FIPS security targets of the aforementioned cards specify resistance against side-channel attacks, no such testing had to be performed. The case of Common Criteria certificate ANSSI-CC-2012/23 can be answered easily as well, the ECDSA functionality of the card is explicitly mentioned to be out of the security requirements. The original Common Criteria certificate DCSSI-CC-2009/11 that introduced the vulnerable functionality did so by stating the functionality is explicitly not protected against SPA/DPA attacks and should not be used on secure data.

    As for the libraries, preventing leakage of the bit-length is surprisingly hard as we analyzed in the section on root causes.

  • Why is it called Minerva?
    We discovered this vulnerability on cards from the Athena SCS manufacturer, which was named after the greek goddess Athena. Minerva is the Roman equivalent.
  • Why the logo?
    Why not? An owl was one of the main symbols of the Roman goddess Minerva. You can download it here in svg (or here in png), it is CC BY 4.0 licensed.

Proof of Concept

The tools can be downloaded from:
Content zip signature tar.gz signature
Proof-of-Concept poc.zip sig poc.tar.gz sig
CPLC checker cplc.zip sig cplc.tar.gz sig
ECDH tester tester.zip sig tester.tar.gz sig
All of the above all.zip sig all.tar.gz sig
The above archives were signed by the PGP key of Jan Jancar, one of the discoverers.

Proof-of-Concept

The Minerva proof-of-concept contains code that exploits the vulnerability against a JavaCard with a target applet, or against targets using several vulnerable libraries.

Contents

applet/ contains code of the target JavaCard applet. It generates an ECC keypair on the secp256r1 curve in the PREPARE command and exports the public key in the response as well as the data that will be signed. Then, in the SIGN command it signs the data using ECDSA with SHA256 and responds with the signature. See build.xml for the ant build script.

attack/ contains two attack scripts. An online one against a JavaCard target in poc.py and an offline one in attack.py. Both are written in Python 3 and use the pyscard library for communication and fpylll library for lattice reduction and CVP solving required for the attack. Both take parameters in the form of a JSON file, which specified what kind of attack is to be performed, see the description in attack.py. The offline attack takes as input a csv file produced by one of the targets or the collection script in collect/ for the target JavaCard applet.

build/ is a directory created by the ant build which contains the CAP file with the built JavaCard applet.

collect/ contains a Python script which collects signatures from the target JavaCard applet and outputs it in a format ready for the offline attack script attack/attack.py.

ext/ contains some third party content, such as the ant-javacard extension (ant-javacard.jar) for the ant build system, which is used to build the applet as well as a version of the JavaCard SDK 2.2.2 (jckit_222).

target/ contains target apps which perform ECDSA signatures using the vulnerable libraries and export the signatures with timing information in format ready for the offline attack script attack/attack.py. See the Makefile for information on building.

Usage with JavaCard
  1. Build the applet via ant build.
  2. Install the applet (build/applet.cap) on the card. For example using GlobalPlatformPro, so doing gp --install build/applet.cap.
  3. Install Python packages from requirements.txt (into a virtualenv). Starting with pip install Cython first, as it is a build dependency of fpylll. fpylll has a somewhat more involved install process, see https://github.com/fplll/fpylll, you will need the current master version of fpylll.
  4. Run ./attack/poc.py. If a USB reader is used, not using other USB devices during the attack makes it more reliable. Also, not using the machine for other computations during the attack limits the noise and makes it more reliable.
  5. Observe a new keypair being generated (the public key is exported from the card and printed) and the attack starting. Observe the reconstructed private key after around 10k-25k signatures. If the attack did not succeed after this time, it is likely that that particular run of the attack will not succeed at all, likely due to noise during the timing measurement.
Usage with libraries
  1. Build the particular target app using the Makefile in the target/ directory.
  2. Run the target, possibly with frequency scaling off, passing the arguments: the chosen curve, hash algorithm and amount of signatures requested. Save the output to a file.
  3. Install Python packages from requirements.txt (into a virtualenv). Starting with pip install Cython first, as it is a build dependency of fpylll. fpylll has a somewhat more involved install process, see https://github.com/fplll/fpylll, you will need the current master version of fpylll.
  4. Run ./attack/attack.py, again passing the arguments: chosen curve, hash algorithm and filename containing the signatures from the target. Observe the reconstructed private key.

CPLC checker

The Minerva CPLC checker uses the Card Production Life Cycle (CPLC) data present on cards under the GlobalPlatform standard to identify vulnerable cards based on a list of known or suspected vulnerable devices.

To run this tool, install the Python requirements from the requirements.txt file, then simply insert the tested card into your reader and run the ./check.py script.

ECDH tester

The Minerva tester is a testing tool for JavaCards which uses ECDH to assess the presence of timing leakage of bit-length in scalar-multiplication. Since it has to use ECDH to control the scalar (the ECDSA API in JavaCard does not allow to choose the random nonce = the scalar) the presence of leakage in ECDH cannot be used to prove the presence of leakage in ECDSA, as the two might be implemented differently and have different side-channel protections. We have observed both cards which leaked in ECDH but not in ECDSA and those that leaked in ECDH and ECDSA.

Contents

applet/ contains code of a target applet. The applet creates an ECC keypair and sets the secp256r1 curve parameters. In the PREPARE command, the applet prepares a private key for ECDH, with bit-length set in the command, the private key simply has the form 1 << (bit_length - 1). In the KEX command the applet performs ECDH with the prepared private key. See build.xml for the ant build script.

build/ is a directory created by the ant build which contains the CAP file with the built JavaCard applet.

reader/ contains code of the tester. It is written in Python 3 and uses the pyscard library for communication.

ext/ contains some third party content, such as the ant-javacard extension (ant-javacard.jar) for the ant build system, which is used to build the applet as well as a version of the JavaCard SDK 2.2.2 (jckit_222).

Usage
  1. Build the applet via ant build.
  2. Install the applet (build/applet.cap) on the card. For example using GlobalPlatformPro, so doing gp --install build/applet.cap.
  3. Install Python packages from requirements.txt (into a virtualenv).
  4. Run ./reader/test.py.
  5. Observe ECDH being performed, with private keys of varying bit-length, after all of the measurements are done a plot will display, showing the dependency of ECDH duration on bit-length (if any), and the correlation of the two. This dependency cannot be directly connected to ECDSA, since a different algorithm might be used for scalar multiplication there (as we observed with one card), but can be taken as guidance that if ECDH leaks, ECDSA might as well (as is the case with another card).

Technical details

Our attack is a lattice attack on the timing leakage of the bit-length of nonces used in ECDSA and other similar signature algorithms, as presented in [3], with minor adaptations. The vulnerable devices and libraries trivially leak the bit-length of the scalar used in scalar multiplication in ECDH, ECDSA and key generation (see the next subsection). The leakage is insignificant for ECDH and key generation as only the bit-length of the private key is leaked, which represents a small amount of always the same information about the private key.

However, in the case of ECDSA or other signature schemes with random nonces, the bit-length of the random nonces is leaked. This is much more significant as each signature then presents new usable information on the private key. The way this information is used to recover the private key is via first converting the problem to an instance of the Hidden Number Problem, which we describe in a section and solving it via lattice reduction techniques.

Leakage

The following images were generated using our tool ECTester.

The images contain heatmaps demonstrating the dependency of signing duration and nonce bit-length, or in general, the dependency of the duration of scalar multiplication on certain bits of the scalar. The example group of images shown first shows a well-behaving implementation with no leakage. For the vulnerable implementations, the length of scalar multiplication is directly dependent on the bit-length of the scalar.

Data collected from 500k signatures on secp256r1.

These images come from OpenSSL, contain no leakage and show how a well-behaving implementation looks like in these types of heatmaps.

Heatmap of nonce MSB and signature time.
Heatmap of nonce MSB and signature time.
Heatmap of nonce Hamming weight and signature time.
Heatmap of nonce Hamming weight and signature time.
Heatmap of nonce bit-length and signature time.
Heatmap of nonce bit-length and signature time.

Figures below are from data collected from 500k signatures on secp256r1.

Plot of private key bit-length and scalar multiplication time.
Clear linear dependency of the length of scalar multiplication on private key bit-length.
Heatmap of nonce MSB and signature time.
Time dependency on bit-length visible in nonce MSB heatmap.
Heatmap of nonce Hamming weight and signature time.
Time dependency on bit-length somewhat visible in nonce Hamming weight heatmap.
Heatmap of nonce bit-length and signature time.
Clear time dependency on nonce bit-length, disturbed by the geometric distribution of bit-length.
Heatmap of nonce bit-length and signature time.
Time dependency clearly visible in grouping of signatures by bit-length.

Figures below are from data collected from 200k signatures on secp256r1 using libgcrypt 1.8.4.

Heatmap of nonce MSB and signature time.
Time dependency on bit-length visible in nonce MSB heatmap.
Heatmap of nonce Hamming weight and signature time.
Time dependency on bit-length somewhat visible in nonce Hamming weight heatmap.
Heatmap of nonce bit-length and signature time.
Clear time dependency on nonce bit-length, disturbed by the geometric distribution of bit-length.

The leakage in wolfCrypt was very small, and potentially not exploitable. Figures below are from data collected from 500k signatures on secp256r1 using wolfSSL 4.0.0.

Heatmap of nonce MSB and signature time.
Time dependency on bit-length visible in nonce MSB heatmap.
Heatmap of nonce Hamming weight and signature time.
Time dependency on bit-length not visible, because it is very small.
Heatmap of nonce bit-length and signature time.
Time dependency on bit-length not visible, because it is very small.

Figures below are from data collected from 120k signatures on secp256r1 using MatrixSSL 4.2.1.

Heatmap of nonce MSB and signature time.
Time dependency on bit-length visible in nonce MSB heatmap.
Heatmap of nonce Hamming weight and signature time.
Time dependency on bit-length somewhat visible in nonce Hamming weight heatmap. Time dependency on Hamming weight is also visible.
Heatmap of nonce bit-length and signature time.
Clear time dependency on nonce bit-length, disturbed by the geometric distribution of bit-length.

Figures below are from data collected from 500k signatures on sect233r1 using JDK 8 SunEC provider.

Heatmap of nonce MSB and signature time.
Time dependency on bit-length visible in nonce MSB heatmap.
Heatmap of nonce Hamming weight and signature time.
Time dependency on bit-length somewhat visible in nonce Hamming weight heatmap.
Heatmap of nonce bit-length and signature time.
Clear time dependency on nonce bit-length, disturbed by the geometric distribution of bit-length.

Figures below are from data collected from 100k signatures on sect233r1 using Crypto++ 8.2.0.

Heatmap of nonce MSB and signature time.
Time dependency on bit-length visible in nonce MSB heatmap.
Heatmap of nonce Hamming weight and signature time.
Time dependency on bit-length somewhat visible in nonce Hamming weight heatmap.
Heatmap of nonce bit-length and signature time.
Clear time dependency on nonce bit-length, disturbed by the geometric distribution of bit-length.

Hidden Number Problem

Boneh & Venkatesan [1] introduced the Hidden Number Problem (HNP), for proving the hardness of computing the most significant bits of keys in the Diffie-Hellman scheme. They also showed a way to solve it by transforming it into a lattice Closest Vector Problem (CVP) solvable via lattice reduction and Babai's nearest plane algorithm. This is useful to us, because in the cases of DSA/ECDSA/EdDSA and even attestation systems such as EPID [8] or ECDAA [9], knowledge of the most significant bits of nonces with the goal of computing the private key can be turned into a Hidden Number Problem instance, which can be turned into an instance of the Closest Vector Problem and solved using the methods of lattice reduction. Next we will introduce the HNP and show how knowledge of most significant bits of nonces can be turned into one for the aforementioned systems.

Notation: In the following text:
  • \( \lfloor x \rfloor_n \) denotes the reduction to \( x \gmod{n} \).
  • \( \lvert x \rvert_n = \min_{a \in \mathbb{Z}} \lvert x - an \rvert\) denotes the distance to the nearest integer multiple of \( n \).
  • \( MSB_l(x) \) denotes an integer \(z \) for \( x \in \mathbb{Z}_n \) which represents the most significant modular bits, s.t. \( \lfloor x - z \rfloor_n < n/2^l \). Note that that such a \(z\) is not unique.
  • \( p \) denotes a prime number, \( g \) is a generator of \( \mathbb{Z}_n \).
  • \( G \) denotes a point of order \( n \) on an elliptic curve, usually the generator.
  • \( d \) denotes the private key, and \( e \)the amount of signatures.
  • \( H(m) \) denotes the rightmost \( \log_2(n) \) bits of the hash of the message \( m \), interpreted as an integer \( \gmod{n} \).
  • \( k \) denotes the nonce used in signing.
Definition 1 (Hidden Number Problem): Given an oracle computing: \[ \mathcal{O}_{g}(x) = MSB_l(a g^x \gmod{p}) \] compute the value of \( a \).
Definition 2 (Generalized Hidden Number Problem): Given an oracle computing: \[ \mathcal{O}_{g,b}(x) = MSB_l(a g^x + b \gmod{p}) \] compute the value of \( a \).
Definition 3 (General Hidden Number Problem): Given an oracle computing: \[ \mathcal{O}_{b}(t) = MSB_l(a t + b \gmod{p}) \] with \( t \) uniformly and independently distributed in \( \mathbb{Z}_p^{\star} \), compute the value of \( a \).
This general problem can be equivalently stated as, given \( e \) inequalities as below, with known \( t_i, u_i \) and \( l_i \) and with unknown \( a \), find it: \[ \lfloor \lfloor t_i a + b \rfloor_p - u_i \rfloor_p \lt p/2^{l_i} \]
ECDSA
In case of ECDSA, given the signature \( (r, s) \in \mathbb{Z}_n \times \mathbb{Z}_n \) on message \( m \): \[ \begin{aligned} r &= ([k]G)_x \pmod{n} \\ s &= k^{-1} (H(m) + r d) \pmod{n} \end{aligned} \] Rewriting we have: \[ \begin{aligned} k &= s^{-1} (H(m) + r d) \pmod{n} \\ k &= s^{-1} H(m) + s^{-1} r d \pmod{n} \end{aligned} \] Information about the most significant bits of \( k \), the nonce, can be used to construct an instance of the HNP.
Definition 4 (ECDSA Hidden Number Problem): Given an oracle for \( MSB_l \) of the nonce \( k \): \[ \begin{aligned} \mathcal{O}_{s,r}(m) &= MSB_l(k \gmod{n}) \\ &= MSB_l(s^{-1} H(m) + s^{-1} r d \gmod{n}) \end{aligned} \] find \( d \) (private key).
The above is essentially the case from definition 3, with \( t = s^{-1} r \) and \(b = s^{-1} H(m) \). However, in this case \(t\) is not completely uniform in \( \mathbb{Z}_n^{\star} \), its distribution is just close enough that we do not have to care about it [2]. We have for \( a_i = \mathcal{O}_{{s_i},{r_i}}(m_i) = MSB_{l_i}(k_i \gmod{n})\): \[ \begin{aligned} \lfloor k_i - a_i \rfloor_n &\lt n/2^{l_i} \\ \lfloor s_i^{-1} (H(m_i) + r_i d) - a_i \rfloor_n &\lt n/2^{l_i} \\ \lfloor s_i^{-1} H(m_i) + s_i^{-1} r_i d - a_i \rfloor_n &\lt n/2^{l_i} \\ \lvert s_i^{-1} H(m_i) + s_i^{-1} r_i d - a_i - n/2^{l_i + 1}\rvert &\lt n/2^{l_i + 1} \\ \lvert s_i^{-1} H(m_i) + s_i^{-1} r_i d - a_i - n/2^{l_i + 1}\rvert_n &\lt n/2^{l_i + 1} \end{aligned} \] The above gives the HNP inequality with \(t_i = s_i^{-1} r_i\) and \(u_i = a_i - s_i^{-1} H(m_i) + n/2^{l_i + 1}\), which is: \[ \lvert t_i d - u_i \rvert_n \lt n/2^{l_i + 1} \] In our case of bit-length leakage, we will only ever create HNP inequalities with \( a_i = \mathcal{O}_{{s_i},{r_i}}(m_i) = MSB_{l_i}(k_i \gmod{n}) = 0 \). Due to the kind of leakage we observe, the bit-length of the nonce, the above inequality \(\lfloor k_i - a_i \rfloor_n < n/2^{l_i} \) does not hold generally, only the weaker inequality \(\lfloor k_i - a_i \rfloor_n < 2^{\lceil \log_2(n) \rceil}/2^{l_i} \) holds. However this stronger inequality allows us to gain one more additional bit per inequality, and on a curve such as secp256r1 the ratio of \( n/2^{\lceil{\log_2(n)\rceil}} \) is around \( 10^{-9}\) so that this is not an issue practically.
EdDSA
In the case of EdDSA, given a signature \( (R, S) \in E(\mathbb{F}_p) \times \mathbb{Z}_n \) on message \(M\) with private key seed hash \(h = (h_0, \ldots, h_{2b - 1}) \), private key \(d\) and public key \( D = [d]G \): \[ \begin{aligned} k &= H(h_b, \ldots, h_{2b-1}, M) \\ R &= [k]G \\ S &= k + H(R, D, M) d \pmod{n} \end{aligned} \] Rewriting, we have: \[ k = S - H(R, D, M) d \pmod{n} \]
Definition 5 (EdDSA Hidden Number Problem): Given an oracle for \( MSB_l \) of the nonce \( k \): \[ \begin{aligned} \mathcal{O}_{S, R}(M) &= MSB_l(k \gmod{n}) \\ &= MSB_l(S - H(R, D, M) d \gmod{n}) \end{aligned} \] find \( d \) (private key).

We have for \( a_i = \mathcal{O}_{{S_i},{R_i}}(M_i) = MSB_{l_i}(k_i \gmod{n}) \): \[ \begin{aligned} \lfloor k_i - a_i \rfloor_n &\lt n/2^{l_i} \\ \lfloor S_i - H(R_i, D, M_i) d - a_i \rfloor_n &\lt n/2^{l_i} \\ \lvert S_i - H(R_i, D, M_i) d - a_i - n/2^{l_i + 1}\rvert &\lt n/2^{l_i + 1} \\ \lvert S_i - H(R_i, D, M_i) d - a_i - n/2^{l_i + 1}\rvert_n &\lt n/2^{l_i + 1} \end{aligned} \] The above gives the HNP inequality with \( t_i = -H(R_i, D, M_i) \) and \( u_i = a_i - S_i + n/2^{l_i + 1}\), which is: \[ \lvert t_i d - u_i \rvert_n \lt n/2^{l_i + 1} \] In our case of bit-length leakage, we will only ever create HNP inequalities with \( a_i = \mathcal{O}_{{S_i},{R_i}}(M_i) = MSB_{l_i}(k_i \gmod{n}) = 0 \).
Solving
Given \( e \) HNP inequalities of the form \( \lvert t_i d - u_i \rvert_n \lt n/2^{l_i + 1} \), we can construct a lattice given by the rows of the matrix \( \mathbf{M} \) [7]: \[ \mathbf{M} = \begin{pmatrix} 2^{l_1 + 1}n & 0 & 0 & \ldots & 0 & 0 \\ 0 & 2^{l_2 +1}n & 0 & \ldots & 0 & 0 \\ & \vdots & & & \vdots & \\ 0 & 0 & 0 & \ldots & 2^{l_e +1}n & 0 \\ 2^{l_1 + 1}t_1 & 2^{l_2 +1}t_2 & 2^{l_3 +1}t_3 & \ldots & 2^{l_e +1}t_e & 1 \end{pmatrix} \] Where \( l_i \) is the amount of known most significant bits of \( k_i \) from the i-th signature. Then, by our construction from the HNP inequalities above, the vector \(\mathbf{u} = ( 2^{l_1 + 1}u_1, \ldots, 2^{l_e + 1}u_e, 0) \) is a vector unusually close to a lattice point. The closest lattice point often has a form \( \mathbf{v} = ( 2^{l_1 + 1} t_1 d, \ldots, 2^{l_e + 1} t_e d, d ) \), finding this lattice point then reveals the private key \( d \). To do so, one needs to solve the Closest Vector Problem. There are several algorithms for solving the CVP, the original paper used Babai's nearest plane algorithm with LLL for lattice reduction. One could also use BKZ for lattice reduction and then solve CVP by enumeration. There is also a technique of transforming an instance of CVP to a Shortest Vector Problem (SVP) by embedding the matrix and the target vector: \[ C = \begin{pmatrix} \mathbf{M} & 0 \\ \mathbf{u} & n \end{pmatrix} \] Then, one can solve SVP by lattice reduction and either looking directly at basis vectors or by further enumeration to find the shortest vector. Our construction contained a number of heuristic arguments, such as "often has a form", or "is unusually close to a lattice point", this shows that the technique is not exact. We also never stated how many HNP inequalities with what \(l_i\) need to be included in the lattice to find the correct private key. Generally, each inequality adds \( l_i \) bits of information and the problem starts to be solvable as soon the lattice contains more information than the unknown information in the private key. Adding inequalities with \( l_i < 2 \) generally does not help, as the growth of lattice dimension offsets any gain of information. Adding dimensions is not for free, runtime of lattice algorithms grows with the number of dimensions significantly. However, adding some overhead of information, such that the lattice contains around \( 1.3 \) times the information of the private key, was shown to improve the success rate.

Full attack

Now that we have knowledge of the timing leakage of bit-length, we need to transform it into knowledge of the most significant bits of the nonce. Our time measurements are inherently noisy and HNP solving via lattice reduction is very sensitive to noise, even one HNP inequality (signature) with wrongly classified most significant bits can lead to a wrong result.

To transform the bit-length leakage to knowledge of MSB, we simply form inequalities that state that \( l_i \) most significant bits are zero. In the above notation this means all the \( a_i \) are zero. If we underestimate the number of zero bits, due to noise, we include less information in the inequality than there is. If we overestimate the number of zero bits, however, we form an incorrect inequality and our solution based on it might be incorrect. To deal with this issue, we use the method introduced by Brumley & Tuveri [3]. We collect signatures and maintain a sorted set of fixed size of signatures with the shortest duration. Suppose we want this set to contain \( e = 130 \) signatures, which will set the dimension of our lattice to \( e + 2 \). Then, after collecting around \( 130 \cdot 4 = 520\) signatures all of those in the set will have at least \( 2 \) zero bits. We could stop here and just use these signatures to create a lattice and reduce it to find the private key, if we are working with a \( 256 \) bit curve, and the signatures gave us \( 260 \) bits of information.

However, the above approach would not utilize the full information in the set of signatures. Around half of them with the shortest duration would have at least \( 3 \) zero bits, a quarter would have at least \( 4 \) and so on. Thus, we can set the \( l_i \) accordingly to this inverse geometric distribution of bit-length and utilize the information in the leak better. This allows for a smaller lattice dimension and larger information overhead, which improves the success rate.

Attack success simulation.
Figure x1:
Attack success simulation for data from the Athena IDProtect card: histogram of number of signatures necessary to obtain an error free set that allows for private key recovery.

Attack success simulation.
Figure x2:
Visualization of the process of collecting signatures on the Athena IDProtect card. With a known private key, one can recompute the correct nonces used in a given signature, plot them and validate how the above attack performs as more signatures are collected. In this example, Liars represent the number of wrongly classified signatures in the set of signatures used to build the lattice, Min liar index shows the smallest index of a liar in the set, as it hits 155, the size of the set in this case, at signature number 12336, that would be the amount of signatures necessary to construct an error-free set of signatures and thus the private key.

Root causes of the vulnerability

We consider there to be several root causes for this group of vulnerabilities. One of them is that knowledge of the fragility of DSA nonces to lattice attacks does not seem to be widespread amongst developers of cryptographic software. There are four issues regarding nonce use in DSA: nonce reuse, bias in nonce randomness, nonce bit-length leaks and other leaks of partial information about nonces. Due to the aforementioned lattice attacks and their variants, all of these issues might lead to a private key recovery attack.

Deterministic generation of nonces, as done in EdDSA or RFC6979 mitigates the issues of nonce reuse and nonce bias. However, it does not address the latter two in any significant way. Deterministic generation of nonces might actually help the attacker in case the attacker has a noisy side-channel leaking nonce bit-length or other information about the nonce. If the attacker can observe the signing of the same message multiple times, they might use the fact that the same nonce was used to significantly reduce the noise in the side-channel.

Another cause for this group of vulnerabilities is that not leaking the bit-length of the scalar used in scalar multiplication is surprisingly hard. Take almost any algorithm that processes the scalar in a left to right fashion, the Montgomery ladder for example, and instantiate it with addition formulas that are incomplete (cannot correctly compute \( \mathcal{O} + P \) or \( 2\mathcal{O} \) in a side-channel indistinguishable way from \( P + Q \) and \( 2P \)), then a side-channel leaking the bit-length will be present.

At the start of the ladder for computing a multiple of point \( G\), the two ladder variables are initialized either as \( R_0 = \mathcal{O} \) and \( R_1 = G \) or as \( R_0 = G \) and \( R_1 = 2G \). In the first case, the computation might start at any bit larger that the most significant set bit in the scalar, i.e. it can be a fixed loop bound, for example on the bit-length of the order of the generator, as seen in algorithm 1. However, until the first set bit is encountered, all of the additions and doublings will involve the point at infinity and because of our assumption that the formulas used are incomplete, they will leak this through some side-channel. This leak might have the form of short-circuiting addition formulas, which check whether the point at infinity was input and short circuit accordingly to satisfy \( \mathcal{O} + P = P \) and \( 2\mathcal{O} = \mathcal{O} \). This is the case in libgcrypt for example, and was the reason why simply fixing a loop bound in scalar multiplication was not enough to fix the issue. The formulas might leak the fact that the point at infinity is present through different channels than timing: power or EM side-channels come to mind, as the point at infinity is often represented using only \( 0 \) or \( 1 \) values, which can often be distinguishable in multiplication and addition on a power trace.

In the second case, the most significant bit of the scalar must be explicitly found, as seen in algorithm 2 and the ladder must start at that bit, because the variables were initialized into a state such that the point at infinity will not appear so that incomplete formulas could be used and no infinity ever handled. If the loop started at some fixed bit past the most significant bit set, this algorithm would compute an incorrect result. However, this clearly leaks the bit-length through timing alone, because of the loop bound on the bit-length of the scalar.

Furthermore, in the name of performance, cryptographic libraries often include multiple optimized scalar multiplication algorithms that are either chosen at compile time or even at runtime, for specific classes of curves, or for use by a specific cryptosystem. This increases the effort necessary to test and verify that all of the possible configurations are constant time and not vulnerable. As mentioned before, there are interactions between the individual components such as addition formulas, coordinate systems and the scalar multiplication algorithm, a change in one of those can make an implementation vulnerable, like using incomplete formulas that short circuit the special cases. The configurations in libraries are often behind many define guards that enable parts of functions, such that even figuring out which scalar multiplication function using which coordinate model and addition formulas gets executed by a library for a particular operation on a particular curve is non-trivial.

Taking the example of the ECC implementation in SunEC/OpenJDK, in the latest version, it contains both a Java implementation of ECC and a native one. The Java one is chosen if one of the secp256r1, secp384r1, secp521r1 curves is detected. The native implementation contains arithmetic for affine, Jacobian and Modified Jacobian coordinates. It contains 4 scalar multiplication algorithms for prime field curves and three wrapper functions which dispatch to appropriate functions. For some reason, the simple scalar multiplication in ECDSA is performed through a call to a multi-scalar multiplication wrapper, which dispatches it to a multi-scalar multiplication function which short circuits to a single-scalar multiplication wrapper, because some of the arguments are null, this wrapper then finally dispatches to the appropriate scalar multiplication function.

The cause of the vulnerability in cards using the Atmel Toolbox 00.03.11.05 is obvious, the toolbox included functionality explicitly marked as not protected against SPA/DPA and timing attacks, which the vulnerable cards decided to use.

Responsible disclosure

Athena IDProtect

We have discovered the vulnerability on 18.03.2019 in the Athena IDProtect card. To confirm its exploitablity we have investigated it in more detail in the following days and constructed a proof-of-concept which can be downloaded above. Following this, we have contacted the responsible party: NXP Semiconductors, on 15.04.2019 at ENABLE@JAVASCRIPT. We chose to contact NXP because the Athena Smart Card Solutions company, which produced the Athena IDProtect cards, no longer exists, as it was bought by NXP in 2015 [11].

NXP Semiconductors confirmed the existence of the vulnerability on 19.04.2019 and stated that they had migrated the former Athena IDProtect product line to their hardware shortly after the acquisition, which effectively mitigated the vulnerability in newer products based on the IDProtect line, long before our discovery, as it was present in the underlying cryptographic library which was replaced along with the hardware. Furthermore, NXP discontinued the former Athena IDProtect line of products a few years after the acquisition.

NXP Semiconductors was able to confirm that the Athena IDProtect card on the AT90SC chip indeed did use the fast and insecure version of the ECDSA functionality from the Atmel Toolbox. Quoting the reply from NXP Semiconductors:

The vulnerability you found is in the Atmel crypto library that implements the ECC cryptography on the affected product. The Athena SCS product affected here is a legacy product which is no longer promoted by NXP.

WiseKey

After communicating with NXP Semiconductors, we contacted WiseKey, the current holder of the intellectual property of the AT90 chip, cryptographic toolbox and associated items, and notified them of the vulnerability in the past versions of the Atmel toolbox. We then explained details of the vulnerability during a call with the WiseKey cryptography team. We have no information on whether current versions of the chip and toolbox are vulnerable.

Libgcrypt

After discovering the vulnerability on a smart-card, we analyzed many open-source cryptographic libraries, we discovered the vulnerability in libgcrypt on 09.07.2019, and notified the libgcrypt security team at ENABLE@JAVASCRIPT on 12.07.2019. We coordinated on mitigating the issue and arrived at a final working patch on 18.07.2019, which was merged on 07.08.2019.

wolfSSL

We discovered the leakage in wolfSSL on 09.07.2019 and notified wolfSSL at ENABLE@JAVASCRIPT on 11.07.2019. We received a patch for testing on 12.07.2019, which fixed the issue. The fix for the issue was merged to the master branch on 17.07.2019.

MatrixSSL

We discovered the vulnerability in MatrixSSL on 11.07.2019, we notified MatrixSSL support at ENABLE@JAVASCRIPT on 11.07.2019 and at ENABLE@JAVASCRIPT (which looked like the maintainer's address from github commits) on 12.07.2019. We have not heard back from any of the addresses. MatrixSSL had a release in the meantime, which fixed some issues but this vulnerability remains unpatched as of 02.10.2019.

Crypto++

We discovered the leakage in Crypto++ on 22.07.2019 and notified the Crypto++ team on 25.07.2019. The main parts of the fix for the issue were merged to the master branch on 29.07.2019 and 05.08.2019.

SunEC

We discovered the leakage in SunEC on 22.07.2019 and notified Oracle at ENABLE@JAVASCRIPT on 26.07.2019. We provided Oracle with a patch mitigating the issue on 14.08.2019. Furthermore, we notified the OpenJDK vulnerability group on 15.09.2019 at ENABLE@JAVASCRIPT. The vulnerability remains unpatched in the public jdk repository as of 02.10.2019.

Team

The vulnerability was discovered by a team at the Centre for Research on Cryptography and Security at Masaryk University in Czech Republic, using the self-developed and open-source ECTester toolkit:

Timeline & Updates

  • 18.03.2019 - Vulnerability discovered.
  • 15.04.2019 - Vulnerability reported to NXP.
  • 11.07.2019 - Vulnerability reported to wolfSSL and MatrixSSL.
  • 12.07.2019 - Vulnerability reported to libgcrypt.
  • 25.07.2019 - Vulnerability reported to Crypto++.
  • 26.07.2019 - Vulnerability reported to Oracle.
  • 13.09.2019 - We published a SHA256 hash of an earlier version of this page to twitter.
  • 02.10.2019 - Release This website was published and the vulnerability disclosed on our twitter.
  • 03.10.2019 - Fixed an issue in the PoC which required the g6k package, which is not available for Python 3.
  • 03.10.2019 - Added a list of implementations we checked and deem secure.
  • 04.10.2019 - Fixed the status of EdDSA in libgcrypt.

Media


References

  1. Dan Boneh, Ramarathnam Venkatesan: Hardness of computing the most significant bits of secret keys in Diffie-Hellman and related schemes (1996) [pdf]
  2. Phong Q. Nguyen, Igor E. Shparlinski: The Insecurity of the Digital Signature Algorithm with Partially Known Nonces (2002) [DOI]
  3. Billy B. Brumley, Nicola Tuveri: Remote Timing Attacks are Still Practical (2011) [ePrint]
  4. Phong Q. Nguyen: The Dark Side of the Hidden Number Problem: Lattice Attacks on DSA (2001) [DOI]
  5. Naomi Benger, Joop van de Pol, Nigel P. Smart, Yuval Yarom: "Ooh Aah... Just a Little Bit" : A small amount of side channel can go a long way (2014) [ePrint]
  6. Joop van de Pol, Nigel P. Smart, Yuval Yarom: Just a Little Bit More (2015) [ePrint]
  7. Keegan Ryan: Return of the Hidden Number Problem: A widespread and novel key extraction attack on ECDSA and DSA (2018) [DOI]
  8. Fergus Dall, Gabrielle De Micheli, Thomas Eisenbarth, Daniel Genkin, Nadia Heninger, Ahmad Moghimi, Yuval Yarom: CacheQuote: Efficiently Recovering Long-term Secrets of SGX EPID via Cache Attacks (2018) [DOI]
  9. FIDO Alliance: FIDO ECDAA Algorithm (2018) [spec]
  10. The FPLLL development team: fplll, a lattice reduction library (2016) [github]
  11. NXP Semiconductors: NXP Acquires Athena SCS (2015) [release]
  12. NIST: FIPS PUB 140-2: SECURITY REQUIREMENTS FOR CRYPTOGRAPHIC MODULES (2001) [pdf]