Serious bug in Nettle's ecdsa

Mark H Weaver wrote on 18 Mar 01:21 +0100

Recipients:(address . bug-guix@gnu.org)

Message-ID:87blbhia4i.fsf@netris.org

FYI...
-------------------- Start of forwarded message --------------------To: nettle-bugs@lists.lysator.liu.se
I've been made aware of a bug in Nettle's code to verify ECDSAsignatures. Certain signatures result in the ecc point multiply functionbeing called with out-of-range scalars, which may give incorrectresults, or crash in an assertion failure. It's an old bug, probablysince Nettle's initial implementation of ECDSA.
I've just pushed fixes for ecdsa_verify, as well as a few other cases ofpotentially out-of-range scalars, to the master-updates branch. I haven'tfully analysed the implications, but I'll describe my currentunderstanding.
I think an assertion failure, useful for a denial-of-service attack, iseasy on the curves where the bitsize of q, the group order, is not anintegral number of words. That's secp224r1, on 64-bit platforms, andsecp521r1.
Even when it's not possible to trigger an assertion failure, it's easyto produce valid-looking input "signatures" that hit out-of rangeintermediate scalar values where point multiplication may misbehave.This applies to all the NIST secp* curves as well as the GOST curves.
To me, it looks very difficult to make it misbehave in such a way thatecdsa_verify will think an invalid signature is valid, but it might bepossible; further analysis is needed. I will not be able to analyze itproperly now, if anyone else would like to look into it, I can provide abit more background.
ed25519 and ed448 may be affected too, but it appears a bit harder tofind inputs that hit out of range values. And since point operations areinherently more robust on these curves, I think they will producecorrect results as long as they don't hit the assert.
Advise on how to deal best with this? My current plan is to prepare a3.7.2 bugfix release (from a new bugfix-only branch, without the newarm64 code). Maybe as soon as tomorrow (Wednesday, european time), or inthe weekend.
Regards,/Niels
-- Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.Internet email is subject to wholesale government surveillance.
_______________________________________________nettle-bugs mailing listnettle-bugs@lists.lysator.liu.sehttp://lists.lysator.liu.se/mailman/listinfo/nettle-bugs-------------------- End of forwarded message --------------------

Ludovic Courtès wrote on 18 Mar 14:27 +0100

control message for bug #47222

Recipients:(address . control@debbugs.gnu.org)

Message-ID:874kh8r3rc.fsf@gnu.org

tags 47222 + securityquit

Ludovic Courtès wrote on 18 Mar 14:27 +0100

Recipients:(address . control@debbugs.gnu.org)

Message-ID:8735wsr3r8.fsf@gnu.org

severity 47222 importantquit

Mark H Weaver wrote on 21 Mar 20:47 +0100

[Niels Möller] ANNOUNCE: Nettle-3.7.2

Recipients:(address . 47222@debbugs.gnu.org)

Message-ID:875z1kl24h.fsf@netris.org

-------------------- Start of forwarded message --------------------From: nisse@lysator.liu.se (Niels Möller)To: nettle-bugs@lists.lysator.liu.se, info-gnu@gnu.orgSubject: ANNOUNCE: Nettle-3.7.2Date: Sun, 21 Mar 2021 10:24:11 +0100

I've prepared a new bug-fix release of Nettle, a low-levelcryptographics library, to fix a serious bug in the function to verifyECDSA signatures. Implications include an assertion failure, which couldbe used for denial-of-service, when verifying signatures on thesecp_224r1 and secp521_r1 curves. More details in NEWS file below.
Upgrading is strongly recomended.
The Nettle home page can be found athttps://www.lysator.liu.se/~nisse/nettle/,and the manual athttps://www.lysator.liu.se/~nisse/nettle/nettle.html.
The release can be downloaded from
https://ftp.gnu.org/gnu/nettle/nettle-3.7.2.tar.gz ftp://ftp.gnu.org/gnu/nettle/nettle-3.7.2.tar.gz https://www.lysator.liu.se/~nisse/archive/nettle-3.7.2.tar.gz
Regards,/Niels
NEWS for the Nettle 3.7.2 release
This is a bugfix release, fixing a bug in ECDSA signature verification that could lead to a denial of service attack (via an assertion failure) or possibly incorrect results. It also fixes a few related problems where scalars are required to be canonically reduced modulo the ECC group order, but in fact may be slightly larger.
Upgrading to the new version is strongly recommended.
Even when no assert is triggered in ecdsa_verify, ECC point multiplication may get invalid intermediate values as input, and produce incorrect results. It's trivial to construct alleged signatures that result in invalid intermediate values. It appears difficult to construct an alleged signature that makes the function misbehave in such a way that an invalid signature is accepted as valid, but such attacks can't be ruled out without further analysis.
Thanks to Guido Vranken for setting up the fuzzer tests that uncovered this problem.
The new version is intended to be fully source and binary compatible with Nettle-3.6. The shared library names are libnettle.so.8.3 and libhogweed.so.6.3, with sonames libnettle.so.8 and libhogweed.so.6.
Bug fixes:
* Fixed bug in ecdsa_verify, and added a corresponding test case.
* Similar fixes to ecc_gostdsa_verify and gostdsa_vko.
* Similar fixes to eddsa signatures. The problem is less severe for these curves, because (i) the potentially out or range value is derived from output of a hash function, making it harder for the attacker to to hit the narrow range of problematic values, and (ii) the ecc operations are inherently more robust, and my current understanding is that unless the corresponding assert is hit, the verify operation should complete with a correct result.
* Fix to ecdsa_sign, which with a very low probability could return out of range signature values, which would be rejected immediately by a verifier.
-- Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.Internet email is subject to wholesale government surveillance.

-- If you have a working or partly working program that you'd liketo offer to the GNU project as a GNU package,see https://www.gnu.org/help/evaluation.html.

-------------------- End of forwarded message --------------------

Ludovic Courtès wrote on 25 Mar 10:51 +0100

Re: bug#47222: Serious bug in Nettle's ecdsa_verify

Recipients:(name . Niels Möller)(address . nisse@lysator.liu.se)

Message-ID:87h7kzblxk.fsf_-_@gnu.org

Hi Niels,

Toggle quote (8 lines)

> I've prepared a new bug-fix release of Nettle, a low-level> cryptographics library, to fix a serious bug in the function to verify> ECDSA signatures. Implications include an assertion failure, which could> be used for denial-of-service, when verifying signatures on the> secp_224r1 and secp521_r1 curves. More details in NEWS file below.>> Upgrading is strongly recomended.

Are there plans to make a new 3.5 release including these fixes?Alternatively, could you provide guidance as to which commits should becherry-picked in 3.5 for downstream distros?
I’m asking because in Guix, the easiest way for us to deploy the fixeson the ‘master’ branch would be by “grafting” a new Nettle variantABI-compatible with 3.5.1, which is the one packages currently depend on.
Thanks in advance,Ludo’.

Niels Möller wrote on 25 Mar 17:21 +0100

Recipients:(name . Ludovic Courtès)(address . ludo@gnu.org)

Message-ID:cpfh7kzjjaj.fsf@slartibartfast.lysator.liu.se

Ludovic Courtès <ludo@gnu.org> writes:

Toggle quote (2 lines)

> Are there plans to make a new 3.5 release including these fixes?

No, I don't plan any 3.5.x release.

Toggle quote (3 lines)

> Alternatively, could you provide guidance as to which commits should be> cherry-picked in 3.5 for downstream distros?

Look at the branch release-3.7-fixes(https://git.lysator.liu.se/nettle/nettle/-/commits/release-3.7-fixes/).The commits since 3.7.1 are the ones you need.
Changes to gostdsa and ed448 will not apply, since those curves didn'texist in nettle-3.5. Changes to ed25519 might not apply cleanly, due torefactoring when adding ed448.

Toggle quote (4 lines)

> I’m asking because in Guix, the easiest way for us to deploy the fixes> on the ‘master’ branch would be by “grafting” a new Nettle variant> ABI-compatible with 3.5.1, which is the one packages currently depend on.

I still recommend upgrading to the latest version. There were an abibreak in 3.6 (so you'd need to recompile lots of guix packages), but noincompatible changes to the (source level) api.
Regards,/Niels
-- Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.Internet email is subject to wholesale government surveillance.

Leo Famulari wrote on 25 Mar 19:16 +0100

Recipients:(name . Niels Möller)(address . nisse@lysator.liu.se)

Message-ID:YFzTkk51ufdpvDGD@jasmine.lan

On Thu, Mar 25, 2021 at 05:21:40PM +0100, Niels Möller wrote:

Toggle quote (4 lines)

> Changes to gostdsa and ed448 will not apply, since those curves didn't> exist in nettle-3.5. Changes to ed25519 might not apply cleanly, due to> refactoring when adding ed448.

Okay.

Toggle quote (8 lines)

> > I’m asking because in Guix, the easiest way for us to deploy the fixes> > on the ‘master’ branch would be by “grafting” a new Nettle variant> > ABI-compatible with 3.5.1, which is the one packages currently depend on.> > I still recommend upgrading to the latest version. There were an abi> break in 3.6 (so you'd need to recompile lots of guix packages), but no> incompatible changes to the (source level) api.

Unfortunately, non-ABI compatible upgrades of nettle cannot be donequickly in Guix. As you point out, we'd have to recompile over >10000packages, and then we'd have to fix any breakage that might occur fromthe upgrade.
We will have to try to cherry-pick the bug fix patches.

Léo Le Bouter wrote on 6 Apr 13:09 +0200

Serious bug in Nettle's ecdsa_verify

Recipients:(address . 47222@debbugs.gnu.org)

Message-ID:082e0d953dd34519b597f675a72299c2e7a4917c.camel@zaclys.net

I am no expert cryptographer, it is likely that if I try backportingsuch patches I will get something wrong that introduces more flaws.
https://security-tracker.debian.org/tracker/CVE-2021-20305- no patchbackported yethttps://packages.ubuntu.com/source/focal/nettle- no patch backportedeither
It would be best if Nettle adopted a forever (or almost) backwardscompatible ABI from now on like curl (https://curl.se/libcurl/abi.html)so that such things don't happen again.
Thank you,Léo

Ludovic Courtès wrote on 16 Apr 22:46 +0200

Recipients:(address . 47222@debbugs.gnu.org)

Message-ID:87im4m2c05.fsf@gnu.org

Hi!
(- Niels, - nettle-bugs)
nisse@lysator.liu.se (Niels Möller) skribis:

Toggle quote (17 lines)> Ludovic Courtès <ludo@gnu.org> writes:>>> Are there plans to make a new 3.5 release including these fixes?>> No, I don't plan any 3.5.x release.>>> Alternatively, could you provide guidance as to which commits should be>> cherry-picked in 3.5 for downstream distros?>> Look at the branch release-3.7-fixes> (https://git.lysator.liu.se/nettle/nettle/-/commits/release-3.7-fixes/).> The commits since 3.7.1 are the ones you need.>> Changes to gostdsa and ed448 will not apply, since those curves didn't> exist in nettle-3.5. Changes to ed25519 might not apply cleanly, due to> refactoring when adding ed448.

I confirm these patches don’t apply, and I’m not comfortable fiddlingwith that.
Leo and I checked and found that Debian doesn’t have 3.5. Do otherdistros have backports of these patches to 3.5?
If not, our options are:
1. to invest in the backport ourselves, with good peer review, ideally getting it stamped by Niels & co;
2. to wait until a full rebuild has come.
It’s not an ideal situation. Thoughts?
Ludo’.

Your comment

Commenting via the web interface is currently disabled.

To comment on this conversation send email to 47222@debbugs.gnu.org

is:open	open issues
is:done	closed issues
submitter:<who>	search issue submitter
author:<who>	search by message author
date:yesterday..now	search by issue date
mdate:3m..2d	search by message date