Comments (16)
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
from noble-curves.
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.
from noble-curves.
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.
from noble-curves.
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.
from noble-curves.
This condition could be deliberately induced, to produce consensus-breaking side-effects
Induced at which point exactly? Could you describe an attack?
from noble-curves.
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...
from noble-curves.
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?
from noble-curves.
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
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
from noble-curves.
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))
}
}
}
from noble-curves.
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.
from noble-curves.
true == verify_in_compact(sig, msg_a, pub) == verify_in_der(sig, msg_b, pub)
, is the condition we're looking for.
from noble-curves.
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)
from noble-curves.
I just thought of an alternative strategy that should have it done in ~2^30 steps, will have a go at writing it tomorrow.
from noble-curves.
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 exists1, 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.
Footnotes
-
This document gives some rationale: https://github.com/bitcoin/bips/blob/master/bip-0062.mediawiki ↩
from noble-curves.
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.
from noble-curves.
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
.
from noble-curves.
Related Issues (20)
- Fp.fromBytes does not mod-reduce by default HOT 2
- What is the difference between getSharedSecret and ECDH_compute_key HOT 1
- Same private keys generate different signatures HOT 1
- P256 signature verification was succeed with 2 public key. HOT 3
- Secure Curves in the Javascript Web Cryptography API - secp256k1, X25519, X448, Ed25519, Ed448 HOT 6
- Wrong signature is generated HOT 8
- seeded (instead of random) ed25519 private key generation? HOT 1
- x25519 encrypt/decrypt? HOT 1
- Signature::fromHex wrong in 1.3.0 HOT 4
- Default bls12_381 is incompatible with Ethereum beacon chain HOT 8
- Incompatibility with old bls12-381 library: not in prime-order subgroup HOT 3
- H2CPoint to ProjectivePoint HOT 2
- Montgomery sample code doesn't compile. (PR submitted) HOT 1
- G2 Curve Points for `bn254.sign()` HOT 1
- Access to Fp types and finalExponentiate method HOT 1
- How do I convert a curve point into a public key? HOT 4
- Hello
- Include sha512_256 in file noble-curves.js HOT 1
- Ideas for v2 HOT 7
- BLS12_381 G1 fromHex() Instantiation Bug HOT 29
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from noble-curves.