Closed Bug 1683520 Opened 4 years ago Closed 4 years ago

ECDSA verification fails when it should succeed

Categories

(NSS :: Libraries, defect, P1)

Product:
NSS
Component:
Libraries
Type:
defect

Tracking

(Not tracked)

Status:
RESOLVED FIXED

People

(Reporter: guidovranken, Assigned: bbb)

Details

(Keywords: sec-other, Whiteboard: [nss-fx])

Attachments

(6 files)

nss_ecdsa_verify_poc.cpp
4.29 KB, text/x-c++src
Details
Equivalent operation in OpenSSL
2.46 KB, text/x-csrc
Details
Bug 1683520 - [lib/freebl/ecl] P-384: allow zero scalars in dual scalar multiplication
48 bytes, text/x-phabricator-request
Details | Review
Bug 1683520 - [lib/freebl/ecl] P-521: allow zero scalars in dual scalar multiplication
48 bytes, text/x-phabricator-request
Details | Review
Bug 1683520 - ECCKiila P384, change syntax of nested structs initialization to prevent build isses with GCC 4.8.
48 bytes, text/x-phabricator-request
Details | Review
Bug 1683520 - ECCKiila P521, change syntax of nested structs initialization to prevent build isses with GCC 4.8.
48 bytes, text/x-phabricator-request
Details | Review

User Agent: Mozilla/5.0 (X11; Ubuntu; Linux x86_64; rv:84.0) Gecko/20100101 Firefox/84.0

Steps to reproduce:

ECDSA verification using the following parameters

public key X: 3287081257432259362393812976079081421412151647138720924241920297746134087425717291680098733199669585693238116089896462389392776287267107954818562468740630350
public key Y: 5047884165615205077529306077209628022504281088340332331957752940735437106855961661784277419343640566825146183053470636970974876726952117391717027289712479371
cleartext: {0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00} (59 bytes)
signature R: 2398833381252220480870377713423558965855096706378426427899888394173467690495466969487925690736977872006638457011575098146569145494858882127318415314133391193
signature S: 2318419597317490008949351307731018419258702345790149047845632642305600089435507511726637998566288744337568482741407664437071146659987012556995409299000152793
digest: NULL

using the "ECDSA_VerifyDigest" function (where 'cleartext' is the data that is passed as-is to this function, not hashed) fails, but it succeeds in OpenSSL, Botan and wolfCrypt, which suggests that NSS is wrong.

Probably not a security issue, unless whatever bug is causing this can be exploited into doing the reverse (verifying signatures when it should not), so I'm marking it as security bug just in case.

Actual results:

Print:

Verify: 0

Expected results:

Print:

Verify: 1

Thanks for the report and sorry I didn't get to this before the holidays.

Ben, could you please take a look into this?

Flags: needinfo?(bbeurdouche)

Could you please confirm the public key as you're passing it into NSS (that is, the raw bytes of ecpub.publicValue) and the other libraries? I get:

0x04, 0x00, 0xF5, 0x29, 0x66, 0x80, 0x3F, 0xBB, 0xE4, 0x37, 0x2C, 0x12, 0x0D, 0xE6, 0x00, 0x22, 0x9A, 0xF2, 0x35, 0xD9, 0x50, 0x2C, 0xC8, 0x95, 0x20, 0x79, 0x95, 0x31, 0xD1, 0x6B, 0x53, 0x9F, 0x4C, 0xC9, 0xC9, 0x11, 0x68, 0x77, 0xC9, 0xB8, 0x0C, 0x73, 0x79, 0x40, 0xF9, 0xD7, 0x94, 0x65, 0xE6, 0xE8, 0x35, 0xEC, 0xC4, 0x0C, 0xE1, 0x55, 0x56, 0x7C, 0xA3, 0x30, 0xDB, 0x1D, 0x3D, 0x52, 0x48, 0x87, 0x4E, 0x17, 0x87, 0xD0, 0x7D, 0x58, 0x34, 0xE0, 0x35, 0xD8, 0x5C, 0xC7, 0xCD, 0x4F, 0x53, 0x4F, 0x71, 0x6D, 0xD5, 0x81, 0xF6, 0x65, 0x7A, 0x16, 0x5F, 0xF8, 0xD9, 0xB3, 0x75, 0x7E, 0xA0, 0x14, 0xF0, 0xB8, 0x47, 0xBD, 0xA3, 0x87, 0x3B, 0x44, 0x92, 0x83, 0x80, 0xF5, 0x7F, 0x30, 0xB7, 0xAF, 0xFA, 0x0F, 0x58, 0x67, 0x48, 0x28, 0x07, 0x52, 0x39, 0x7D, 0x2D, 0x9F, 0x96, 0xB0, 0x07, 0x26, 0xEC, 0xC8, 0x0B

and with that value, EC_ValidatePublicKey fails at [1] because the y-coordinate is outside of [0, p−1].

If that's the case, it's interesting that the other libraries consider the signature correct... But maybe I did a conversion wrong.

[1] https://searchfox.org/mozilla-central/source/security/nss/lib/freebl/ecl/ecp_aff.c#266

Your X/Y:

X: 00F52966803FBBE4372C120DE600229AF235D9502CC89520799531D16B539F4CC9C9116877C9B80C737940F9D79465E6E835ECC40CE155567CA330DB1D3D5248874E
Y: 1787D07D5834E035D85CC7CD4F534F716DD581F6657A165FF8D9B3757EA014F0B847BDA3873B44928380F57F30B7AFFA0F586748280752397D2D9F96B00726ECC80B

My X/Y:

X: 00F52966803FBBE4372C120DE600229AF235D9502CC89520799531D16B539F4CC9C9116877C9B80C737940F9D79465E6E835ECC40CE155567CA330DB1D3D5248874E
Y: 01787D07D5834E035D85CC7CD4F534F716DD581F6657A165FF8D9B3757EA014F0B847BDA3873B44928380F57F30B7AFFA0F586748280752397D2D9F96B00726ECC8B

Maybe you're using an old version of Boost that does the conversion from string to binary wrong?

Whatever the cause, to be testing the same parameters as me, put this in the reproducer:

pub = std::vector<uint8_t>({0x04, 0x00, 0xF5, 0x29, 0x66, 0x80, 0x3F, 0xBB, 0xE4, 0x37, 0x2C, 0x12, 0x0D, 0xE6, 0x00, 0x22, 0x9A, 0xF2, 0x35, 0xD9, 0x50, 0x2C, 0xC8, 0x95, 0x20, 0x79, 0x95, 0x31, 0xD1, 0x6B, 0x53, 0x9F, 0x4C, 0xC9, 0xC9, 0x11, 0x68, 0x77, 0xC9, 0xB8, 0x0C, 0x73, 0x79, 0x40, 0xF9, 0xD7, 0x94, 0x65, 0xE6, 0xE8, 0x35, 0xEC, 0xC4, 0x0C, 0xE1, 0x55, 0x56, 0x7C, 0xA3, 0x30, 0xDB, 0x1D, 0x3D, 0x52, 0x48, 0x87, 0x4E, 0x01, 0x78, 0x7D, 0x07, 0xD5, 0x83, 0x4E, 0x03, 0x5D, 0x85, 0xCC, 0x7C, 0xD4, 0xF5, 0x34, 0xF7, 0x16, 0xDD, 0x58, 0x1F, 0x66, 0x57, 0xA1, 0x65, 0xFF, 0x8D, 0x9B, 0x37, 0x57, 0xEA, 0x01, 0x4F, 0x0B, 0x84, 0x7B, 0xDA, 0x38, 0x73, 0xB4, 0x49, 0x28, 0x38, 0x0F, 0x57, 0xF3, 0x0B, 0x7A, 0xFF, 0xA0, 0xF5, 0x86, 0x74, 0x82, 0x80, 0x75, 0x23, 0x97, 0xD2, 0xD9, 0xF9, 0x6B, 0x00, 0x72, 0x6E, 0xCC, 0x8B});

Ack, sorry about that. I had no internet access (to download boost) when I was working on this and I apparently screwed up the conversion.

The problem is this: In point_mul_two_secp521r1 (and point_mul_two_secp384r1, from inspection). It's considered out of range for n1 or n2 to be zero [1] . This isn't always the check we want:

  • ECDSA Sign: n1==k and n2 is NULL. The check is correct, as k must be in [1, n-1].
  • ECDSA Verify: n1 and n2 are the "u1" and "u2" values, either of which may be zero (at least, their values are not checked per the spec). In this case, it's u1.
  • ECDH: n1 is NULL and n2==k. Again this is right, k must be in [1, n-1].

If we skip the != 0 check, verification succeeds.

Now, this code is actually from ECCKiila [2], so we should report to them before deciding whether to fix this ourselves vs. updating the autogenerated code. FWIW: apparently, OpenSSL used to have a similar bug [3].

Nice find :)

[1] https://searchfox.org/mozilla-central/source/security/nss/lib/freebl/ecl/ecp_secp521r1.c#4597
[2] https://gitlab.com/nisec/ecckiila/
[3] http://openssl.6102.n7.nabble.com/ECDSA-verify-fails-when-digest-is-all-zeros-in-0-9-8e-td34477.html

Severity: -- → S3
Priority: -- → P3

Great. Will you report it to ECCKiila? Do you consider this a security issue? If not, I will add it to the public Cryptofuzz bug list.

Yes, I'll reach out to them now.

I don't see any security impact here but if you don't mind, let's check with ECCKiila before we open it.

Hi bbrumley,

This issue (see comment 5) comes from code that is marked "Autogenerated: ECCKiila".

It seems one minimally-invasive fix would be to disable the zero checks on n1 and possibly n2 when are both specified (i.e. only in the verify case).

  • Do you have a preference of whether we fix this in NSS, or import new autogenerated code?
  • Any concern with Guido adding this bug to a public list?

Thanks.

Flags: needinfo?(bbeurdouche) → needinfo?(bbrumley)

u2 is not allowed to be zero.

You have u2 = r/s, so u2 = 0 only holds if r is zero. Which is not allowed in ECDSA.

For u1 = z/s, you get u1=0 iff z=0. Which yea I guess is possible -- with probability roughly the same as guessing a private key.

But yea it should be fixed. We have a few non-critical updates to ECCKiila code in NSS anyway, so I will roll it in when we have time.

Flags: needinfo?(bbrumley)

And thanks for the report!

You're welcome bbrumley. Check out my project https://github.com/guidovranken/cryptofuzz which has found a lot of ECC/ECDSA and other bugs :).

Guido

At first glance the diff looks non-trivial but realize it's mostly fiat changes, plus some code doc.

The relevant part is here

@@ -6423,20 +6500,20 @@ point_mul_two_secp384r1(const mp_int *n1, const mp_int *n2,
     unsigned char b_n2[48];
     mp_err res;
 
-    /* If n2 == NULL, this is just a base-point multiplication. */
-    if (n2 == NULL)
+    /* If n2 == NULL or 0, this is just a base-point multiplication. */
+    if (n2 == NULL || mp_cmp_z(n2) == MP_EQ)
         return point_mul_g_secp384r1(n1, out_x, out_y, group);
 
-    /* If n1 == NULL, this is just an arbitary-point multiplication. */
-    if (n1 == NULL)
+    /* If n1 == NULL or 0, this is just an arbitary-point multiplication. */
+    if (n1 == NULL || mp_cmp_z(n1) == MP_EQ)
         return point_mul_secp384r1(n2, in_x, in_y, out_x, out_y, group);
 
     ARGCHK(in_x != NULL && in_y != NULL && out_x != NULL && out_y != NULL,
            MP_BADARG);

I really did not test this much at all internal to NSS besides running fbectest and ecperf. Guido could you try your reproducer? (You might not have access in Phabricator -- maybe one of the maintainers can help out there? I'm such a Phabricator newb.)

Flags: needinfo?(guidovranken)

The ECCKiila branch with this fix is here.

(I apologize -- I had stale source in D102406. It should be fixed in Phabricator now.)

Keywords: sec-other

I'd like to test your patch but I don't have access to Phabricator so I can't download the diff. Can you post the diff (for NSS, not ECCKilla) here, or can someone give me access?

Flags: needinfo?(guidovranken)

Thanks for the patch. I'm happy to test and review this, but I have a number of competing priorities this week (sorry). I'll set a reminder for myself to come back to this next week.

(In reply to Guido Vranken from comment #17)

I'd like to test your patch but I don't have access to Phabricator so I can't download the diff. Can you post the diff (for NSS, not ECCKilla) here, or can someone give me access?

If you create a Phabricator account, you should have access to the patch.

Flags: needinfo?(kjacobs.bugzilla)

Thank you, Kevin!

I'm using the .clang-format in the root of the repo. Is that the correct one? (It appears to be, in that I see only a single formatting nit in the diff.)

(In reply to bbrumley from comment #19)

Thank you, Kevin!

I'm using the .clang-format in the root of the repo. Is that the correct one? (It appears to be, in that I see only a single formatting nit in the diff.)

Yes, that should be it. On my machine it changes all of these lines:

diff --git a/lib/freebl/ecl/ecp_secp384r1.c b/lib/freebl/ecl/ecp_secp384r1.c
--- a/lib/freebl/ecl/ecp_secp384r1.c
+++ b/lib/freebl/ecl/ecp_secp384r1.c
@@ -6150,7 +6150,7 @@ var_smul_rwnaf(pt_aff_t *out, const unsi
     scalar_rwnaf(rnaf, scalar);
 
 #if defined(_MSC_VER)
-    /* result still unsigned: yes we know */
+/* result still unsigned: yes we know */
 #pragma warning(push)
 #pragma warning(disable : 4146)
... (repeating)...

But we can also format the patch if you're getting different results.

I've confirmed that this patch fixes the issue.

Ben, can you please take this from here?

Flags: needinfo?(kjacobs.bugzilla) → needinfo?(bbeurdouche)

@Kevin
Sure, thanks all!

@Billy
FYI, if you have Docker installed, you should be able to use ./mach clang-format at the root of the NSS directory.
This will run a correctly configured clang-format from a Docker VM. I can assist if this doesn't work well for you... : )

@Guido
If you can't/don't want to use Phabricator I can send you the raw diff

Flags: needinfo?(bbrumley)

I have Phabricator account now. When I click on bbrumley's patch, I get:

Access Denied: Restricted Differential Revision
You do not have permission to view this object.
Users with the "Can View" capability:

This object has a custom policy controlling who can take this action.
The owner of a revision can always view and edit it.If a revision belongs to a repository, other users must be able to view the repository in order to view the revision.

Nevermind, it works now.

Hey Guido,

Very interesting find!

Indeed, secp256r1 (P-256) has a different code path than the curves under consideration here, P-384 and P-521. So I think you should file that under a distinct issue.

(My 2c: it's unclear to me if your new issue is related to curve-specific code or generically at the EC layer.)

bbrumley: Can't reproduce it for other curves so far, only secp256r1. However this is not a guarantee that the other curves are not affected.

Created a new issue: https://bugzilla.mozilla.org/show_bug.cgi?id=1689574

Whiteboard: [nss-fx]

Hi Billy,
As discussed, I pushed a minor change for nested struct initializations to {{ 0 }} as separate commits on top of your two patches for P384 and P521 so that our CI doesn't complain. These are on separate phabricator patches and have a link to their respective CI runs, you should have been notified by email.

If you think that it works for you, please accept the two patches and I'll push the changes to NSS.
Thanks a lot !
B.

(note that clang-format is failing but it is not blocking, so I'll fix formatting separately so that it is easier for us both ;)

Flags: needinfo?(bbrumley)
Flags: needinfo?(bbeurdouche)
Flags: needinfo?(bbrumley)

Hey Benjamin,

Thanks for the update.

I tried the proposed fix but now ECCKiila CI is nit barfing with clang 11

[ 60%] Building C object CMakeFiles/ecp_test.dir/ecp_secp128r2.c.o
/home/bbrumley/svnrepos/ecckiila/ecp/secp128r2/ecp_secp128r2.c:2664:22: error: missing field 'Y' initializer [-Werror,-Wmissing-field-initializers]
    pt_prj_t Q = {{0}};
                     ^

It is fun, battling the CI for 3 projects, to work around false positives :) The = { 0 } initialize was due to a coverity nit for the gost-engine project -- ECCKiila provides eight standardized curves there.

Ofc I can turn off -Wmissing-field-initializers but that seems kind of arbitrary compared to the -Wmissing-braces NSS is apparently using.

I'll have to think about it.

Fun indeed : )
I think the correct way to do this was the original {0}, and at this point, I don't think it is necessary for you to do unnecessary work on ECCKiila for NSS due to a broken GCC in our CI. So, I am perfectly happy for you to keep {0} as a default, and for me to do a similar manual change to {{0}} next time we want to update this code. Hopefully, I can update that compiler in our CI by then so that it doesn't cause trouble : )
Let me know what works best for you.
Best, B.

Assignee: nobody → bbrumley
Status: UNCONFIRMED → ASSIGNED
Ever confirmed: true
Priority: P3 → P1
Group: crypto-core-security

Thanks a lot Guido and Billy for reporting and updating the code, this is highly appreciated : )
Best, B.

You need to log in before you can comment on or make changes to this bug.

Attachment

General

Creator:
Created:
Updated:
Size: