Elliptic Curve timing leaks #869

noloader · 2019-07-26T04:49:09Z

From a private email by Ján Jančár:

Message-ID: 93874bd8-653e-33e9-c429-93712c3f30ba@mail.muni.cz
Subject: Vulnerability disclosure
...

During our research into security of elliptic curve cryptography implementations on smart-cards and in software libraries [1], we have discovered timing leakage in the ECDSA signature generation in the Crypto++ library.

Vulnerability description

When performing ECDSA over binary field curves, Crypto++ leaks the bit-length of the nonce used in scalar multiplication. It also leaks some other currently unknown information, see the attached plots, specifically the 'msb_hist.png' plot.

This leakage can be abused if an attacker is able to measure the duration of signing of a few hundreds or thousands of known messages. The attacker can then use a lattice attack based on the Hidden Number Problem [2] to reconstruct the private key used, as demonstrated in [3] (even remotely!).

See the attached plots and heatmaps for details of the leakage on the standard sect233r1 curve. based on the level of noise present in the attacker's measurements (the lattice attack is very sensitive to noise) and willingness to trade-off computation time, the attack would require from 500 to 10k signatures.

The private key recovery itself, assuming a noise free set of just enough signatures, would then take a few minutes. The leakage is somewhat present in ECDSA over prime field curves as well, but much smaller, I do not know the cause of this.

[1]: ECTester: https://crocs-muni.github.io/ECTester/

[2]: D. Boneh, R. Venkatesan: Hardness of computing the most significant bits of secret keys in Diffie-Hellman and related schemes; https://crypto.stanford.edu/~dabo/abstracts/dhmsb.html

[3]: B. B. Brumley, N. Tuveri: Remote Timing Attacks are Still Practical; https://eprint.iacr.org/2011/232.pdf

It appears nearly all versions of Crypto++ are affected. Based on some research of antique Crypto++, I believe that means Crypto++ 3.2 and forward. Crypto++ 3.2 was released March 20, 2000.

Also posted to the mailing list at ECDSA timing leaks.

denisbider · 2019-07-26T22:43:10Z

Yikes. The finding about sect curves is significant enough, but I'm additionally concerned about this:

The leakage is somewhat present in ECDSA over prime field curves as well, but much smaller, I do not know the cause of this.

To my knowledge, the prime field curves are where ECDSA is more frequently used: for example, the nistp curves are standardized for use in SSH. I am curious about the significance of this "much smaller" leak and what type of addressing it might require.

noloader · 2019-07-28T07:39:27Z

The issue was assigned CVE-2019-14318.

noloader · 2019-07-29T14:31:26Z

The timing attack on the ECDSA nonce length was cleared at Pull Request 870, Commit 80c59bcdb251.

Next on the hit list are the leaks in Add(), Double() and Multiply().


        Use complete addition algorithms in ECP (GH weidai11#869)

This is the initial cut-in of complete addition algorithms according to https://eprint.iacr.org/2015/1060.pdf. There are two outstanding problems. First, HMQV and FHMQV are failing self tests. We need to investigate further. Second, we cannot use the new algorithms on paths where a Montgomery representation is used. We need to investigate further. This cut-in will allow us to proceed on evaluating the timing leaks.


        Fix ECP leakage in Add() and Double() (GH #869, PR #871)

This check-in provides the fix for leaks in ECP's Add() and Double(). The fixes were taken from Joost Renes, Craig Costello, and Lejla Batina's [Complete addition formulas for prime order elliptic curves](https://eprint.iacr.org/2015/1060.pdf). The Pull Request includes two additional changes that were related to testing the primary fix. First, an `AuthenticatedKeyAgreementWithRolesValidate` interface was added. It allows us to test key agreement when roles are involved. Roles are "client", "server", "initiator", "recipient", etc. Second, `SetGlobalSeed` was added to `test.cpp` to help with reproducible results. We had code in two different places that set the seed value for the random number generator. But it was sloppy and doing a poor job since results could not be reproduced under some circumstances.

noloader · 2019-08-05T07:54:52Z

The timing attacks on the ECP (prime fields) were cleared at Pull Request 871, Commit c9ef9420e762.

Next on the hit list are the leaks in EC2N (binary fields).


        Avoid branches in Montgomery Double() (GH #869)


        Avoid branches in Montgomery Add() (GH #869)


        Avoid temporary ECP::Point in ECP Addition and Double

This regains a lot of performance lost to the const-timeness (GH #869)


        Restore ECP ABI (GH #869)

Placing AdditionFunction as an inner class of ECP broke the ABI. We need to maintain the ABI so distros can patch Crypto++ 8.2.

noloader · 2019-08-10T07:00:56Z

A partial patch is available. The patch was created against the Crypto++ 8.2 and Crypto++ 5.6.4 releases. The patch fixes (1) leak in ECDSA nonce length; and (2) leak in prime fields (ECP class). Prime fields are the important one because they are ubiquitous.

The fix is incomplete because it is missing the fix for (3) leak in binary fields (EC2N class). The fix for (3) should be ready in a couple of weeks. Binary fields are less important because nearly no one (no one?) uses them. They have been discouraged for years.

The patches below were produced with diff -u. They can be applied with:

cd cryptopp
patch -p0 < cve-2019-14318.patch

Crypto++ 8.2

Partial patch: cve-2019-14318.patch.zip

Script to create patch: cve-2019-14318.sh.zip

Crypto++ 5.6.4

Partial patch: cve-2019-14318-CryptoPP564.patch.zip

Source for patch: https://github.com/noloader/cryptopp/tree/cve-2019-14318


        libcryptopp: Add patch for CVE-2019-14318

See weidai11/cryptopp#869

zorun · 2019-11-30T18:22:40Z

If this is a serious security issue, can you make a new release with the fix?

noloader added cve Security Bug labels Jul 28, 2019

noloader changed the title ~~ECDSA timing leaks~~ Elliptic Curve timing leaks Jul 29, 2019

noloader added a commit that referenced this issue Aug 6, 2019

Avoid branches in Montgomery Double() (GH #869)

Verified

This commit was signed with a verified signature.

noloader Jeffrey Walton

GPG key ID: B36AB348921B1838 Learn about signing commits

5ae70e2

noloader added a commit that referenced this issue Aug 6, 2019

Avoid branches in Montgomery Add() (GH #869)

Verified

This commit was signed with a verified signature.

noloader Jeffrey Walton

GPG key ID: B36AB348921B1838 Learn about signing commits

0ded321

raphael-st added a commit to macports/macports-ports that referenced this issue Aug 11, 2019

libcryptopp: Add patch for CVE-2019-14318

Loading status checks…

cb08b6c

See weidai11/cryptopp#869

noloader mentioned this issue Aug 26, 2019

Regression in Elliptic Curve Operation on brainpoolP256r1 #878

Open

weidai11/cryptopp

Elliptic Curve timing leaks #869

Elliptic Curve timing leaks #869

noloader commented Jul 26, 2019 •

edited

This comment has been minimized.

denisbider commented Jul 26, 2019

This comment has been minimized.

noloader commented Jul 28, 2019

This comment has been minimized.

noloader commented Jul 29, 2019 •

edited

This comment has been minimized.

noloader commented Aug 5, 2019 •

edited

This comment has been minimized.

noloader commented Aug 10, 2019 •

edited

This comment has been minimized.

zorun commented Nov 30, 2019

weidai11/cryptopp

Join GitHub today

Elliptic Curve timing leaks #869

Elliptic Curve timing leaks #869

Comments

noloader commented Jul 26, 2019 • edited

This comment has been minimized.

denisbider commented Jul 26, 2019

This comment has been minimized.

noloader commented Jul 28, 2019

This comment has been minimized.

noloader commented Jul 29, 2019 • edited

This comment has been minimized.

noloader commented Aug 5, 2019 • edited

This comment has been minimized.

noloader commented Aug 10, 2019 • edited

Crypto++ 8.2

Crypto++ 5.6.4

This comment has been minimized.

zorun commented Nov 30, 2019

noloader commented Jul 26, 2019 •

edited

noloader commented Jul 29, 2019 •

edited

noloader commented Aug 5, 2019 •

edited

noloader commented Aug 10, 2019 •

edited