ECDSA signature verification succeeds when it should not

[guidovranken]

operation name: ECDSA_Verify
ecc curve: secp256k1
public key X: 83121579216557378445487899878180864668798711284981320763518679672151497189239
public key Y: 35702972027818625020095973668955176475740885849864829235584237564223564379706
msg: {0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe, 
 0xba, 0xae, 0xdc, 0xe6, 0xaf, 0x48, 0xa0, 0x3b, 0xbf, 0xd2, 0x5e, 0x8c, 0xd0, 0x36, 0x41, 0x41} (32 bytes)
signature R: 83121579216557378445487899878180864668798711284981320763518679672151497189239
signature S: 83121579216557378445487899878180864668798711284981320763518679672151497189239
digest: NULL

mbed TLS verifies this ECDSA signature, whereas libgcrypt, Trezor firmware, Botan and probably libsecp256k1 don't.

To reproduce, pass the 'msg' as-in (e.g. without hashing, hence digest: NULL).

[chris-jones-arm]

Hi @guidovranken,

I am having a little trouble reproducing this behaviour at the moment, would it be possible to share your test code?

[guidovranken]

#include <mbedtls/ecdsa.h>

#define CF_CHECK_EQ(expr, res) if ( (expr) != (res) ) { goto end; }
#define CF_CHECK_NE(expr, res) if ( (expr) == (res) ) { goto end; }

int main(void)
{
    mbedtls_ecdsa_context ctx;
    mbedtls_mpi sig_r, sig_s;
    const mbedtls_ecp_curve_info* curve_info = NULL;
    const unsigned char msg[] = {0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe, 
 0xba, 0xae, 0xdc, 0xe6, 0xaf, 0x48, 0xa0, 0x3b, 0xbf, 0xd2, 0x5e, 0x8c, 0xd0, 0x36, 0x41, 0x41};

    mbedtls_ecdsa_init(&ctx);
    mbedtls_mpi_init(&sig_r);
    mbedtls_mpi_init(&sig_s);

    CF_CHECK_NE(curve_info = mbedtls_ecp_curve_info_from_tls_id(22), NULL);

    CF_CHECK_EQ(mbedtls_ecp_group_load(&ctx.grp, curve_info->grp_id), 0);

    /* Pubkey */
    CF_CHECK_EQ(mbedtls_mpi_read_string(&ctx.Q.X, 10, "83121579216557378445487899878180864668798711284981320763518679672151497189239"), 0);
    CF_CHECK_EQ(mbedtls_mpi_read_string(&ctx.Q.Y, 10, "35702972027818625020095973668955176475740885849864829235584237564223564379706"), 0);
    CF_CHECK_EQ(mbedtls_mpi_lset(&ctx.Q.Z, 1), 0);

    /* Signature */
    CF_CHECK_EQ(mbedtls_mpi_read_string(&sig_r, 10, "83121579216557378445487899878180864668798711284981320763518679672151497189239"), 0);
    CF_CHECK_EQ(mbedtls_mpi_read_string(&sig_s, 10, "83121579216557378445487899878180864668798711284981320763518679672151497189239"), 0);

    printf("Verify: %d\n", mbedtls_ecdsa_verify(&ctx.grp, msg, sizeof(msg), &ctx.Q, &sig_r, &sig_s));
end:
    return 0;
}

This prints "Verify: 0" meaning that verification has succeeded.

[gilles-peskine-arm]

The payload is n, the order of the base point of the curve. The signature is (r,s) = (x,x) where x is the x-coordinate of the public key. Following the verification process, using the notation of the Wikipedia article:

1. 1 ≤ x ≤ n
2. [no hashing because this is raw ECDSA, not hash-ECDSA]
3. z = n
4. u1 = n/s mod n = 0; u2 = r/s = 1. (u1, u2) = QA (the public key) is a valid point not at infinity.
5. r = x which is the x-coordinate of the public key.

So unless I got the arithmetic wrong (which is a definite possibility), this is a valid signature of 0. The only reason this signature may be invalid is if there's a restriction that the payload must be in the range 0..n-1, which doesn't sound right to me: when the payload is a hash, it may (with extremely low probability for most common curves) be outside this range.

This presumably turned up after #4199 where we fixed a bug whereby Mbed TLS incorrectly rejected valid signatures of the payload all-bits-zero. @guidovranken Do the other implementations you test work with a payload of all-bits-zero? With a payload that's larger than the order of the curve?

[mpg]

The only reason this signature may be invalid is if there's a restriction that the payload must be in the range 0..n-1, which doesn't sound right to me: when the payload is a hash, it may (with extremely low probability for most common curves) be outside this range.

This is where wikipedia is not the best reference: sec1-v2 has all the details in 4.1.3 step 5 or 4.1.4 step 3, as reference by our helper function derive_mpi(): we keep the appropriate number of bits then reduce mo N. So I don't think there's any kind of ambiguity there.

This presumably turned up after #4199

I'm not even sure we need "presumably" here: I've confirmed that the reproducer posted above (thanks for that btw!) starts printing "Verify: 0" right after #4199 was merged.

[gilles-peskine-arm]

This is where wikipedia is not the best reference: sec1-v2 has all the details

Right, I generally don't expect Wikipedia to have all the details of the checks needed during verification. I was using it as a conveniently available reference for notation. In the case of ECDSA verification, though, there are indeed no extra checks here.

[guidovranken]

Are you now allowing all payloads which are 0 (or curve order) to verify?

I found this as well:

  | operation name: ECDSA_Verify
-- | --
  | ecc curve: secp256r1
  | public key X: 1
  | public key Y: 2
  | 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} (30 bytes)
  | signature R: 1
  | signature S: 1
  | digest: NULL
  |  
  | Module mbed TLS result:
  |  
  | true
  |  
  | Module Botan result:
  |  
  | false

First of all I don't think that is correct and second this makes it susceptible to fault injections.

[mpg]

Are you now allowing all payloads which are 0 (or curve order) to verify?

We are now allowing the payload to be 0 or curve order (see #1792 and #4261 for reports (the second by you) and # #4199 for the fix), however I think we only accept this payload if the other values are valid - just like any other payload.

For you latest example, using wikipedia's notations for convenience, we have:

• z = 0
• u1 = 0, u2 = 1
• (x1, y1) = 0 * G + 1 * Q_A = Q_A = (1,2)
• hence x1 == 1 == r and the signature is valid

Again, we can see that the signature generation algorithm can generate this signature if it picks d_A (the long-term private key) as k (the ephemeral scalar):

• z = 0
• k = 1 (random)
• (x1, y1) = k * G = Q_A
• r = x1 = x(Q_A)
• s = (0 + r * d_A) / k = r * d_A / d_A = r
• output (x(Q_A), x(Q_A))

Surely any signature that can be generated by the generation routine should be accepted by the verification routine.

By the way both examples mentioned in this issue (the one that opens it and the one in your last comment) fall in this category:

• payload is zero or curve order (after truncation)
• r = s = x(Q_A)

Unless I've missed something big, those are all valid signatures. Also, if I change the value of r or s, Mbed TLS starts rejecting the modified signatures. So it looks to me that we are indeed accepting signatures of the 0 (or equivalent) payload and rejecting invalid ones.

First of all I don't think that is correct

I'm sorry, I don't think I understand what's not correct. Could you clarify?

second this makes it susceptible to fault injections

If we're talking about active physical attacks, those are currently outside our threat model.

[gilles-peskine-arm]

Both @mpg and I have compared this case against SEC1 and we believe that Mbed TLS is following the standard correctly. Therefore I am closing this issue. If you still think there's a bug in Mbed TLS, please let us know where the mistake is in our analysis.

[4a6f656c]

@gilles-peskine-arm @mpg (cc @guidovranken) - while the math may be correct, ECDSA signature verification works on the basis that the public key (Qu in SEC 1) is valid. As far as I can tell, the given point is not actually on the secp256k1 curve and hence verification should refuse to proceed (this is detailed in SEC 1 section 4.1.2, which refers to 3.2.2, which in turn refers to 3.2.2.1). I presume that mbedtls_ecp_check_pubkey would fail in this case (although I've not actually confirmed).

[guidovranken]

Ah, of course. Thanks Joel! Fixed: https://github.com/guidovranken/cryptofuzz/commit/8b25a1fb3f639000b8f86fb99bfa5ff38800ac18

[4a6f656c]

@guidovranken while that works for the fuzzer, it is fairly bad form for a library to report successful verification when given an invalid public key... I would still consider this a fairly significant bug in mbed.

[gilles-peskine-arm]

Apologies for missing this earlier. I do agree now that mbedtls_ecdsa_verify should reject invalid public keys. I hadn't realized that it was supposed to do so, and in fact did do so except in a few edge cases. So we're fixing that in #6190

[maxgerhardt]

Did this issue impact TLS handshakes that use ECC / short Weierstraß curves, e.g. in the sense that a client or server would incorrectly accept a certificate? I see this being listed as "bugfix" in the mbedTLS 3.3.0 release notes, but incorrectly saying a ECDSA signature is valid when it's not because the public key is invalid seems like it a security thing that should have a CVE.

[gilles-peskine-arm]

@maxgerhardt We only issue CVE for security issues and I don't see how this could be a security issue. (At least on its own — of course any bug can be a part of a long attack path.) The ECDSA signature process has two phases: hashing, and the ECC arithmetic calculation. The arithmetic calculation on its own is not secure against forgeries, so we are only concerned with the full hash+sign operation. The bug we're discussing is when the output of the hash phase is all-bits-zero (or the first N bits, if the hash is truncated to fit the curve size). This is impossible with any of the hash algorithms supported by Mbed TLS, or with any of the hash algorithms supported by the TLS protocol. Therefore this bug does not allow any ECDSA forgeries.

(When I claim that an all-bits-zero hash is impossible, I mean this in a practical sense. It is unknown whether a message with an all-bits-zero hash exists. It is mathematically likely that one exists. But we don't know how to find one.)

This could be a component of a larger attack path if, for example, a misconfiguration, a memory corruption bug or an execution glitch attack led to the verify function receiving an all-bits-zero buffer instead of the result of the hash calculation. But there is no known or suspected bug of this kind. There was no known or likely exploit against any system using Mbed TLS. Hence the incorrect verification result was an ordinary bug, not a security hole that required urgent patching.

[maxgerhardt]

Thank you for the explanation, I understand.