GNU bug report logs - #47222
Serious bug in Nettle's ecdsa_verify

Please note: This is a static page, with minimal formatting, updated once a day.
Click here to see this page with the latest information and nicer formatting.

Package: guix; Severity: important; Reported by: Mark H Weaver <mhw@HIDDEN>; Keywords: security; dated Thu, 18 Mar 2021 00:24:01 UTC; Maintainer for guix is bug-guix@HIDDEN.

Message received at 47222 <at> debbugs.gnu.org:


Received: (at 47222) by debbugs.gnu.org; 25 Mar 2021 09:52:05 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Thu Mar 25 05:52:05 2021
Received: from localhost ([127.0.0.1]:37168 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.84_2)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1lPMer-0005iN-7f
	for submit <at> debbugs.gnu.org; Thu, 25 Mar 2021 05:52:05 -0400
Received: from eggs.gnu.org ([209.51.188.92]:45966)
 by debbugs.gnu.org with esmtp (Exim 4.84_2)
 (envelope-from <ludo@HIDDEN>) id 1lPMep-0005ht-Pq
 for 47222 <at> debbugs.gnu.org; Thu, 25 Mar 2021 05:52:04 -0400
Received: from fencepost.gnu.org ([2001:470:142:3::e]:47903)
 by eggs.gnu.org with esmtp (Exim 4.90_1)
 (envelope-from <ludo@HIDDEN>)
 id 1lPMei-0007Sp-Bo; Thu, 25 Mar 2021 05:51:56 -0400
Received: from nat-eduroam-36-gw-01-bso.bordeaux.inria.fr
 ([194.199.1.36]:53688 helo=ribbon)
 by fencepost.gnu.org with esmtpsa (TLS1.2:RSA_AES_256_CBC_SHA1:256)
 (Exim 4.82) (envelope-from <ludo@HIDDEN>)
 id 1lPMeh-00042B-Qy; Thu, 25 Mar 2021 05:51:56 -0400
From: =?utf-8?Q?Ludovic_Court=C3=A8s?= <ludo@HIDDEN>
To: Niels =?utf-8?Q?M=C3=B6ller?= <nisse@HIDDEN>
Subject: Re: bug#47222: Serious bug in Nettle's ecdsa_verify
References: <cpfmtuwlv0k.fsf@HIDDEN>
 <875z1kl24h.fsf@HIDDEN>
Date: Thu, 25 Mar 2021 10:51:51 +0100
In-Reply-To: <875z1kl24h.fsf@HIDDEN> (Mark H. Weaver's message of "Sun, 21
 Mar 2021 15:47:47 -0400")
Message-ID: <87h7kzblxk.fsf_-_@HIDDEN>
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/27.1 (gnu/linux)
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
X-Spam-Score: -0.7 (/)
X-Debbugs-Envelope-To: 47222
Cc: 47222 <at> debbugs.gnu.org, nettle-bugs@HIDDEN
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.18
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
X-Spam-Score: -1.7 (-)

Hi Niels,

> 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=E2=80=99m asking because in Guix, the easiest way for us to deploy the fi=
xes
on the =E2=80=98master=E2=80=99 branch would be by =E2=80=9Cgrafting=E2=80=
=9D a new Nettle variant
ABI-compatible with 3.5.1, which is the one packages currently depend on.

Thanks in advance,
Ludo=E2=80=99.




Information forwarded to bug-guix@HIDDEN:
bug#47222; Package guix. Full text available.

Message received at 47222 <at> debbugs.gnu.org:


Received: (at 47222) by debbugs.gnu.org; 21 Mar 2021 19:49:33 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Sun Mar 21 15:49:33 2021
Received: from localhost ([127.0.0.1]:55524 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.84_2)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1lO44r-0008Gy-DR
	for submit <at> debbugs.gnu.org; Sun, 21 Mar 2021 15:49:33 -0400
Received: from world.peace.net ([64.112.178.59]:35174)
 by debbugs.gnu.org with esmtp (Exim 4.84_2)
 (envelope-from <mhw@HIDDEN>) id 1lO44p-0008Gl-58
 for 47222 <at> debbugs.gnu.org; Sun, 21 Mar 2021 15:49:31 -0400
Received: from mhw by world.peace.net with esmtpsa
 (TLS1.3:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92)
 (envelope-from <mhw@HIDDEN>)
 id 1lO44i-0001gt-4n; Sun, 21 Mar 2021 15:49:24 -0400
From: Mark H Weaver <mhw@HIDDEN>
To: 47222 <at> debbugs.gnu.org
Subject: [Niels =?utf-8?Q?M=C3=B6ller=5D?= ANNOUNCE: Nettle-3.7.2
References: <cpfmtuwlv0k.fsf@HIDDEN>
Date: Sun, 21 Mar 2021 15:47:47 -0400
Message-ID: <875z1kl24h.fsf@HIDDEN>
MIME-Version: 1.0
Content-Type: multipart/mixed; boundary="=-=-="
X-Spam-Score: 0.0 (/)
X-Debbugs-Envelope-To: 47222
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.18
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
X-Spam-Score: -1.0 (-)

--=-=-=
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable


-------------------- Start of forwarded message --------------------
From: nisse@HIDDEN (Niels M=C3=B6ller)
To: nettle-bugs@HIDDEN, info-gnu@HIDDEN
Subject: ANNOUNCE: Nettle-3.7.2
Date: Sun, 21 Mar 2021 10:24:11 +0100


--=-=-=
Content-Type: multipart/mixed; boundary="==-=-="

--==-=-=
Content-Type: multipart/signed; boundary="===-=-="

--===-=-=
Content-Type: text/plain; charset=utf-8
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

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.

--=20
Niels M=C3=B6ller. PGP-encrypted email is preferred. Keyid 368C6677.
Internet email is subject to wholesale government surveillance.


--===-=-=
Content-Type: application/pgp-signature; name=signature.asc
Content-Transfer-Encoding: base64

LS0tLS1CRUdJTiBQR1AgU0lHTkFUVVJFLS0tLS0KCmlRRXpCQUVCQ2dBZEZpRUV5MGxpMEhEWGZY
L0xpNk5pY2RqeC96YU1abmNGQW1CWEVMc0FDZ2tRY2RqeC96YU0KWm5lV2tRZi9hTXhBcVF2UC9p
SnBKY1VmZ0gzQTZLMWhyVXp6czJ0VkVoQzQ3blhFc0ZQa0paVldFaUswS2t4UQpTZmo4UjdKNzlQ
LzB4Q0N2NWVvRW1sbGNYZ0hIMitSQVUvdmtFTHVXUFMwTjZIS3NMQVBsQ2Y5THduWXVueXp0Ck84
WkdpZWZ4VEFMQVo5Z2tST3FLTm9RZWppa0ZOTFhmYjRlclcyRXJMQmdnZ1RiVFJVUmp4UlJRSDZ4
dU1lV20KVzZPQlhaZTMzOHNBcUJKMlBWYytiMzZ6eWVXWWZTd0EwUU91WXVndXVZSHNnZHBydk9V
b1kzSldoSHJHdDYxbwpWZkE5bUtNVjZiVjNXZHJvcjdGMm1vejJSVTdFRVNoQlVaWkJBLzV6RUJE
NEE4dE45MkZzT3YyRHV4emplYnk5CkJ6QU1EWHNWc3hXT29JMmE2K2RTbk52Z3E4ZlVrdz09Cj1U
WTRQCi0tLS0tRU5EIFBHUCBTSUdOQVRVUkUtLS0tLQ==
--===-=-=--

--==-=-=
Content-Type: text/plain; charset=utf-8
Content-Disposition: inline

-- 
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.
--==-=-=--

--=-=-=
Content-Type: text/plain

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

--=-=-=--




Information forwarded to bug-guix@HIDDEN:
bug#47222; Package guix. Full text available.
Severity set to 'important' from 'normal' Request was from Ludovic Courtès <ludo@HIDDEN> to control <at> debbugs.gnu.org. Full text available.
Added tag(s) security. Request was from Ludovic Courtès <ludo@HIDDEN> to control <at> debbugs.gnu.org. Full text available.

Message received at submit <at> debbugs.gnu.org:


Received: (at submit) by debbugs.gnu.org; 18 Mar 2021 00:23:51 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Wed Mar 17 20:23:51 2021
Received: from localhost ([127.0.0.1]:44435 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.84_2)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1lMgS7-0002oY-5o
	for submit <at> debbugs.gnu.org; Wed, 17 Mar 2021 20:23:51 -0400
Received: from lists.gnu.org ([209.51.188.17]:41454)
 by debbugs.gnu.org with esmtp (Exim 4.84_2)
 (envelope-from <mhw@HIDDEN>) id 1lMgS4-0002oP-6D
 for submit <at> debbugs.gnu.org; Wed, 17 Mar 2021 20:23:50 -0400
Received: from eggs.gnu.org ([2001:470:142:3::10]:58878)
 by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256)
 (Exim 4.90_1) (envelope-from <mhw@HIDDEN>) id 1lMgS4-0003jR-04
 for bug-guix@HIDDEN; Wed, 17 Mar 2021 20:23:48 -0400
Received: from world.peace.net ([64.112.178.59]:36592)
 by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256)
 (Exim 4.90_1) (envelope-from <mhw@HIDDEN>) id 1lMgRw-0000AY-R7
 for bug-guix@HIDDEN; Wed, 17 Mar 2021 20:23:47 -0400
Received: from mhw by world.peace.net with esmtpsa
 (TLS1.3:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92)
 (envelope-from <mhw@HIDDEN>)
 id 1lMgRk-0005tF-Cm; Wed, 17 Mar 2021 20:23:28 -0400
From: Mark H Weaver <mhw@HIDDEN>
To: bug-guix@HIDDEN
Subject: Serious bug in Nettle's ecdsa_verify
References: <cpfh7lbmsgz.fsf@HIDDEN>
Date: Wed, 17 Mar 2021 20:21:54 -0400
Message-ID: <87blbhia4i.fsf@HIDDEN>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
Received-SPF: pass client-ip=64.112.178.59; envelope-from=mhw@HIDDEN;
 helo=world.peace.net
X-Spam_score_int: -18
X-Spam_score: -1.9
X-Spam_bar: -
X-Spam_report: (-1.9 / 5.0 requ) BAYES_00=-1.9, SPF_HELO_NONE=0.001,
 SPF_PASS=-0.001 autolearn=ham autolearn_force=no
X-Spam_action: no action
X-Spam-Score: -1.3 (-)
X-Debbugs-Envelope-To: submit
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.18
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
X-Spam-Score: -2.3 (--)

FYI...

-------------------- Start of forwarded message --------------------
From: nisse@HIDDEN (Niels M=C3=B6ller)
To: nettle-bugs@HIDDEN
Subject: ANNOUNCE: Serious bug in Nettle's ecdsa_verify
Date: Tue, 16 Mar 2021 09:07:56 +0100

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

--=20
Niels M=C3=B6ller. PGP-encrypted email is preferred. Keyid 368C6677.
Internet email is subject to wholesale government surveillance.

_______________________________________________
nettle-bugs mailing list
nettle-bugs@HIDDEN
http://lists.lysator.liu.se/mailman/listinfo/nettle-bugs
-------------------- End of forwarded message --------------------




Acknowledgement sent to Mark H Weaver <mhw@HIDDEN>:
New bug report received and forwarded. Copy sent to bug-guix@HIDDEN. Full text available.
Report forwarded to bug-guix@HIDDEN:
bug#47222; Package guix. Full text available.
Please note: This is a static page, with minimal formatting, updated once a day.
Click here to see this page with the latest information and nicer formatting.
Last modified: Thu, 25 Mar 2021 10:00:02 UTC

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997 nCipher Corporation Ltd, 1994-97 Ian Jackson.