Serious bug in Nettle's ecdsa_verify

Done

Details

6 participants

Leo Famulari
Léo Le Bouter
Ludovic Courtès
Mark H Weaver
Niels Möller
(

Owner: unassigned

Submitted by: Mark H Weaver

Severity: important

Mark H Weaver wrote on 18 Mar 2021 01:21

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 ECDSA

signatures. Certain signatures result in the ecc point multiply function

being called with out-of-range scalars, which may give incorrect

results, or crash in an assertion failure. It's an old bug, probably

since Nettle's initial implementation of ECDSA.

I've just pushed fixes for ecdsa_verify, as well as a few other cases of

potentially out-of-range scalars, to the master-updates branch. I haven't

fully analysed the implications, but I'll describe my current

understanding.

I think an assertion failure, useful for a denial-of-service attack, is

easy on the curves where the bitsize of q, the group order, is not an

integral number of words. That's secp224r1, on 64-bit platforms, and

secp521r1.

Even when it's not possible to trigger an assertion failure, it's easy

to produce valid-looking input "signatures" that hit out-of range

intermediate 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 that

ecdsa_verify will think an invalid signature is valid, but it might be

possible; further analysis is needed. I will not be able to analyze it

properly now, if anyone else would like to look into it, I can provide a

bit more background.

ed25519 and ed448 may be affected too, but it appears a bit harder to

find inputs that hit out of range values. And since point operations are

inherently more robust on these curves, I think they will produce

correct results as long as they don't hit the assert.

Advise on how to deal best with this? My current plan is to prepare a

3.7.2 bugfix release (from a new bugfix-only branch, without the new

arm64 code). Maybe as soon as tomorrow (Wednesday, european time), or in

the weekend.

Regards,

/Niels

Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.

Internet email is subject to wholesale government surveillance.

_______________________________________________

nettle-bugs mailing list

nettle-bugs@lists.lysator.liu.se

http://lists.lysator.liu.se/mailman/listinfo/nettle-bugs

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

Ludovic Courtès wrote on 18 Mar 2021 14:27

control message for bug #47222

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

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

tags 47222 + security

quit

Ludovic Courtès wrote on 18 Mar 2021 14:27

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

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

severity 47222 important

quit

Mark H Weaver wrote on 21 Mar 2021 20:47

[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.org
Subject: ANNOUNCE: Nettle-3.7.2
Date: Sun, 21 Mar 2021 10:24:11 +0100

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.

The Nettle home page can be found at

https://www.lysator.liu.se/~nisse/nettle/,and the manual at

https://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 like
to 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 2021 10:51

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 be

cherry-picked in 3.5 for downstream distros?

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.

Thanks in advance,

Ludo’.

Niels Möller wrote on 25 Mar 2021 17:21

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't

exist in nettle-3.5. Changes to ed25519 might not apply cleanly, due to

refactoring 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 abi

break in 3.6 (so you'd need to recompile lots of guix packages), but no

incompatible 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 2021 19:16

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 done
quickly in Guix. As you point out, we'd have to recompile over >10000
packages, and then we'd have to fix any breakage that might occur from
the upgrade.

We will have to try to cherry-pick the bug fix patches.

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

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 backporting

such patches I will get something wrong that introduces more flaws.

https://security-tracker.debian.org/tracker/CVE-2021-20305- no patch

backported yet

https://packages.ubuntu.com/source/focal/nettle- no patch backported

either

It would be best if Nettle adopted a forever (or almost) backwards

compatible 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 2021 22:46

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 fiddling

with that.

Leo and I checked and found that Debian doesn’t have 3.5. Do other

distros 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’.

(

( wrote on 8 Aug 2022 19:11

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

Message-ID:CM0TBR948W8B.2JY3QM6WIGB4A@guix-aspire

We now have nettle 3.7.3, so this isn't an issue anymore. Closing.

-- (

Closed

Your comment

This issue is archived.

To comment on this conversation send an 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