v2: Restrict ECDSA verify to compact or DER verification without flag

[DavidBuchanan314]

Per the comment here:

https://github.com/paulmillr/noble-curves/blob/fb02e93ff66ecd7bc7257d8f76e6cdf88b54bfa9/src/abstract/weierstrass.ts#L1053-L1060

A signature of one type can be trivially transformed into the other (much like low-s vs high-s).

Perhaps this is the intended behaviour - if so, I think it should be documented much more explicitly

[DavidBuchanan314]

This will also fail to verify valid "compact" signatures that also happen to be valid DER - I'm not sure what the odds of that are, but it seems plausible. This condition could be deliberately induced, to produce consensus-breaking side-effects.

[paulmillr]

compact signatures that also happen to be valid DER

If we're talking about secp256k1, here how this could look like:

• First byte is 0x30
• Second byte is 0x3e
• Then, there need to be 62 bytes of two valid DER integers. Possible byte lengths of such integers:
  • 30, 30
  • 31, 29
  • 32, 28
• DER integers contain integer length as header, which means if there is 30-byte integer, a byte preceding it must be 0x1e (30)

Seems extremely rare, but i'll try to bruteforce it.

The question is, really, how should a better API look like? Your current strategy mitigates this issue.

[paulmillr]

This condition could be deliberately induced, to produce consensus-breaking side-effects

Induced at which point exactly? Could you describe an attack?

[DavidBuchanan314]

It's precisely the same set of attacks that can be performed if low-s checking is absent

Edit: actually I suppose the "accidentally looks like DER" scenario is different to malleability, let me have a think on that...

[DavidBuchanan314]

The question is, really, how should a better API look like? Your current strategy mitigates this issue.

IMHO, a safe api would require the user to explicitly declare the format of their signature, with no automatic guessing. If a user needs to guess a signature format for some reason, they can write their own logic for that, at their own risk - the need to do so must be rare, surely?

[paulmillr]

This is worth considering for the next breaking release, which won't happen soon because of our release cadence (unless there's a probable security issue).

The reason it was made like this is because compact format was added after DER. To simplify verification UX, it was added in the current manner to verify. Not ideal, of course, but at least it worked for all the cases.

It's precisely the same set of attacks that can be performed if low-s checking is absent

High-S malleability allows to produce different signature that would also be valid simply by negating S by its field order. It is trivial.

Here, an attacker needs to find a compact byte sequence which is a valid DER. Seems to happen once per $2^{28.1}$ signatures: $1/256 1/256 5/256 * 3/256$.

However, even if such a sequence is found, it would be invalid DER signature:

verify_in_compact(sig) // true
is_parseable_der(sig) // true
verify_in_der(sig) // false

[paulmillr]

I've written the bruteforcer to find such signatures, nothing interesting so far:

import { secp256k1 } from '@noble/curves/secp256k1';
import { bytesToHex } from '@noble/curves/abstract/utils';

const priv = new Uint8Array(32).fill(4);
const msg = new Uint8Array(32);
const view = new DataView(msg.buffer);

const isValidInt = (i) => i >= 0x1c && i <= 0x20
for (let i = 15455938; ; i++) {
  view.setUint32(0, i);
  const sig = secp256k1.sign(msg, priv).toCompactRawBytes();
  if (sig[0] === 0x30 && sig[1] === 0x3e) {
    console.log(1, i, bytesToHex(sig));
    const len_1 = sig[2];
    const end_1 = 3 + len_1;
    const len_2 = sig[end_1];

    if (isValidInt(len_1)) {
      console.log(' ', 2, len_1, len_2);
      if (isValidInt(len_2)) {
        console.log(3);
        // then len_2 needs to be (64-2-len_1)
      }
      // console.log(sig.subarray(end_1, 1 + end_1))
    }
  }
}

[DavidBuchanan314]

You can bruteforce many orders of magnitude faster by incrementing k rather than picking a random one each time. I'm working on a bruteforcer now, I expect to have a result in ~hours.

[paulmillr]

true == verify_in_compact(sig, msg_a, pub) == verify_in_der(sig, msg_b, pub), is the condition we're looking for.

[DavidBuchanan314]

Hm, the brute-force is actually harder than I first thought. You also need an 02 tag byte in front of each integer.

This makes it a roughly 2^45 search- 2^45 curve point additions, that is. Too slow for my single-threaded python script, but if I could be bothered to write some OpenCL, definitely within reach.

303e1fb4a0abbd0145d61b3d17fb005eef60ac89923874bb7c00bc07c3af894673b21d84260d671a646aeb7ba66c7767a6c08732fca7646592e7115e5d6b7a11 is a valid signature for pubkey 0428f81535b7a9eb436367c89a3f4f35bdfee9ec5562498dee23f2c8dafb7433a6b6ab5f2d70da260113a753de793f58deda0d032f58f2cc9880879750ba5ae494 and message sha256("hello"), and fits the constraints you initially described, but unfortunately it doesn't have those 02 tag bytes so it's not parsed as valid DER.

(getting the 02 bytes would be ~2^16 times more work than that)

[DavidBuchanan314]

I just thought of an alternative strategy that should have it done in ~2^30 steps, will have a go at writing it tomorrow.

[DavidBuchanan314]

import { secp256k1 } from '@noble/curves/secp256k1';
import { sha256 } from '@noble/hashes/sha256';

const hashed = sha256("hello 172790")
const pubkey = "0428f81535b7a9eb436367c89a3f4f35bdfee9ec5562498dee23f2c8dafb7433a6b6ab5f2d70da260113a753de793f58deda0d032f58f2cc9880879750ba5ae494"

// valid compact sig, not valid DER (business as usual)
const sig0 = "6d30e6d7da48a10230a61f84e86633a672a1c95d3c69e0c6af291dbbe7db96482a02d5521fc5d15e3c65df3b77ea2d32b13c10ae4611e28768cb1c6e1dff37fc"
//const sig0_parsed_as_der = secp256k1.Signature.fromDER(sig0) // would throw
const sig0_parsed_as_compact = secp256k1.Signature.fromCompact(sig0)

console.log(secp256k1.verify(sig0, hashed, pubkey)) // true
console.log(secp256k1.verify(sig0_parsed_as_compact, hashed, pubkey)) // true

// valid compact sig, also syntactically valid DER
const sig1 = "303e021f2b50f3e4e236d74c15f4062596ce4ca8c7819f91a1a156187c9072a9675260021b433dcbf8d81115859a8fc3996f3f79192c72a56e6abacd93e72f26"
const sig1_parsed_as_der = secp256k1.Signature.fromDER(sig1)
const sig1_parsed_as_compact = secp256k1.Signature.fromCompact(sig1)

console.log(sig1_parsed_as_der)
console.log(sig1_parsed_as_compact)

console.log(secp256k1.verify(sig1, hashed, pubkey)) // false (!!!)
console.log(secp256k1.verify(sig1_parsed_as_der, hashed, pubkey)) // false
console.log(secp256k1.verify(sig1_parsed_as_compact, hashed, pubkey)) // true

[paulmillr]

It's really cool that you've spent time on this! Thank you.

For the malleability to happen, an attacker would need to have distinct msg_a verifiable=true under sig (der hex) and msg_b verifiable=true under sig_parsed_as_compact. So, two true outputs under different messages.

Even if we don't find it, it is still a bug, as it can be seen from your provided vector - and it should be fixed. Will need to think what could be done. Perhaps a documentation update and then an API adjustment in v2.

[DavidBuchanan314]

For the malleability to happen, an attacker would need to have distinct msg_a verifiable=true under sig (der hex) and msg_b verifiable=true under sig_parsed_as_compact. So, two true outputs under different messages.

I disagree with this assessment. All normal inputs are malleable. For example:

import { secp256k1 } from '@noble/curves/secp256k1';
import { sha256 } from '@noble/hashes/sha256';

const hashed = sha256("hello 172790")
const pubkey = "0428f81535b7a9eb436367c89a3f4f35bdfee9ec5562498dee23f2c8dafb7433a6b6ab5f2d70da260113a753de793f58deda0d032f58f2cc9880879750ba5ae494"

// valid signature, in compact form
const sig0 = "6d30e6d7da48a10230a61f84e86633a672a1c95d3c69e0c6af291dbbe7db96482a02d5521fc5d15e3c65df3b77ea2d32b13c10ae4611e28768cb1c6e1dff37fc"
console.log(secp256k1.verify(sig0, hashed, pubkey)) // true

// without knowledge of the private key, we create a new byte sequence that is also a valid signature
const sig1 = secp256k1.Signature.fromCompact(sig0).toDERHex();
console.log(sig0 != sig1) // true
console.log(secp256k1.verify(sig1, hashed, pubkey)) // also true

Likewise, if the original signature was provided in DER form, an attacker can convert it to compact form.

Avoiding malleability is a relatively niche use-case, but it's the whole reason low-s checking exists[^1], so I think it's reasonable to expect a library that supports low-s checking to be non-malleable in general. I think it would be totally reasonable for you to say "This library does not care about malleability", but if so, I think that choice should be explicitly documented.

[^1]: This document gives some rationale: https://github.com/bitcoin/bips/blob/master/bip-0062.mediawiki

[DavidBuchanan314]

Perhaps a documentation update and then an API adjustment in v2.

But yes, I think this is fine. I think the API as-is is a bit of a footgun, but I'm not aware of anyone currently using it to shoot their foot off, as it were, so there's no urgent need to fix it.

[paulmillr]

Likewise, if the original signature was provided in DER form, an attacker can convert it to compact form.

The attacker could also convert hex to bytes, or to Signature instance. Both bytes and Signatures would also be sigHex != sigBytes; sigHex != sigInstance.