indutny
Invalid signature generation and private key exposure.
I have noticed that the elliptic library v. 6.5.7 may generate incorrect ECDSA signatures and also verify incorrect ECDSA signatures. An example for an invalid signature that is verified as true is the following (all values are in hexadecimal):
curve: "secp224r1"
messageDigest: "SHA-256",
publicKeyUncompressed: "04afb8a1081da80211db6983ab7c94e4f5b8a13c939da4bbc0e7acdf6b3939f24928a427a783632fc520c78e78ee9452d6afb205e1c6e03ca2"
publicKeyCompressed: "02afb8a1081da80211db6983ab7c94e4f5b8a13c939da4bbc0e7acdf6b"
msg: "049a27b5204bb2be"
sig: "303c021c344cc8cd2571137ce4186ffd03ee7626e9d91ede7ea3afd45aeaf6b2021c2e4743bde502b2c1dda87c55a4451e5956e04e38e68257311d89def3"
Similar miscalculations can happen whenever the size of the message digest is longer than the size of the curve. A possible cause for the error is the function truncateToN in the file ec/index.js
EC.prototype._truncateToN = function _truncateToN(msg, truncOnly) {
var delta = msg.byteLength() * 8 - this.n.bitLength();
if (delta > 0)
msg = msg.ushrn(delta);
if (!truncOnly && msg.cmp(this.n) >= 0)
return msg.sub(this.n);
else
return msg;
};
This code uses the length of the integer msg to compute the length of the truncation. The correct method would be to use the length of the message digest from which the integer msg is computed. If the first byte of the message digest is 0 then this function truncates incorrectly.
I have briefly looked at potential key leakages since ECDSA implementations using RFC 6979 are notoriously brittle when the implementation contains arithmetic errors. My impression is that the bug is likely not exploitable under normal assumptions (attacker can perform a chosen message attack, but the signer hashes before signing). The situation is less clear in a prehash setup where the attacker can select the message digest without providing proof that the prehash is actually the result of the hash.
It may of course be the case that the library is only intended for a selection of curve/hash combinations. However, neither the documentation nor the API, nor the implementation accepting any size of hashes provide any indication what is supported.
Slightly annoyed ping.
The vulnerability still exists in 6.6.0 and it is quite unclear what the current efforts are to fix this (or whether there are even efforts to fix this). I believe Snyk is aware of the problem, I don't know if there are other parties still analyzing the vulnerability. Hence some coordination would be very helpful. Otherwise there is some danger to drag this out even more.
I have more questions, such as whether additional analysis and recommendations should be added to the current CVE or if issuing a new CVE would be less confusing. Again organizing this would help to avoid overlapping and potentially contradicting reports.
I've also tested the latest version of the library. The vulnerability still exists in version 6.6.1.
According to my tests this issue is still unfixed. This is concerning since the problem is more severe than originally thought. I.e. faulty signatures generated by this library can expose the private key (as demonstrated in https://github.com/indutny/elliptic/issues/322).
Are there any efforts to fix this or has the library been abandoned?
i tried the POC given by Snyk. For version 6.5.7, the signature verification fails proving the issue exists. However, when i upgrade elliptic to 6.6.1 and run the POC code again, the signature verification succeeds => seems this issue does not exists in 6.6.1.
Hello, I'm sorry if I said something out of line.
I'm not well about cryptography fields and could't understand the status accurately, so if you don't mind, could you tell me about the bellow?
- The vulnerability that a possibility to fail verification of valid signatures, reported in CVE-2024-48948, is fixed in v6.6.0?
- The one more vulnerability to be able to find the private key reported by @bleichenbacher-daniel is not fixed in v6.6.0 and the issue is also possible before v6.6.0?
Thank you
The issue is an incorrect implementation rsp. use of the function _truncateToN .
There are multiple places in the code where an incorrect implementation (or incorrect use) of _truncateToN can break signature generation and signature verification and the elliptic implementation does seem to be careless in multiple places. I.e., _truncateToN is called before the computation of the RFC 6979 nonce and again after the computation of the nonce. The original PoC contains an example where the error happens before the RFC 6979 computation. The new failure is a case where the error happens after the RFC 6979 computation. An example is here: https://github.com/indutny/elliptic/pull/322#issuecomment-2463004218 . The example given there still fails in version 6.6.1 As described this leads to a signature using a nonce k that is linearly correlated with the correct nonce. If an attacker has a faulty signature and the corresponding correct signature then it is possible to find the private key. I.e., I have code that extract the private key from a faulty signature generated by elliptic and a correct signature generated by pyca. This code has not been published, but I don't think it is difficult to rediscover the attack.
The property that enables the attack is that these signatures are almost correct, but not quite. There are other cases (e.g. cases with longer hashes such as secp256r1 with SHA-512) where the generated signature deviates more significantly from the correct ones. In such cases it is more difficult to find a working attack.
The set of test vectors that I'm using is here: https://github.com/bleichenbacher-daniel/Rooterberg/blob/main/test_vectors/ecdsa/ecdsa_rfc6979_secp521r1_sha_512.json About 1 in 256 signatures is currently incorrect.
@bleichenbacher-daniel Thank you for comments. I read https://github.com/indutny/elliptic/pull/322#issuecomment-2463004218 . Could you tell me a little more? I want to clarify what problems are fixed and still remained. In that comment and above reply, I think the following 3 points are pointed out. That's correct ?
- function _truncateToN has still bugs and incorrect signature may be generated in v6.6.1 (or doesn't have bugs but is used with improper usage).
- We can find private key from combination of a correct signature created by some correct implemention and an incorrect signeture created by Elliptic v6.6.1 with same key, curve and so on.
- It's desired that we regenerate signature if we generated signature with Elliptic to avoid exposure of private key.
Also, this may be my misunderstanding, I wonder that the signature created by Elliptic is allways same value when same key, curve, hash and message is used. That is because I think different k is selected every time when signature is created and that makes the signature different value every time.
I'm not sure what the state of the library is.
I'm not aware of any efforts to fix the library or any efforts to coordinate the analysis of the bugs in this library. The latest version I've tested is version 6.6.1. As pointed out earlier this version is vulnerable. I'm also not aware of any advisory with regard to key revocation. Since in some cases signatures can leak private keys without the interaction of an adversary it would make sense to revoke such keys.
There are a number of factors that contribute to the weakness of this library. One is the use of RFC 6979 to generate deterministic signatures. Deterministic signatures schemes always generate the same signature, when key, hash and message are the same. A significant disadvantage of this scheme is that small implementation errors are very often disastrous, when an attacker can learn a faulty and the corresponding correct signature (or a different faulty signature). Note, that such a situation can actually happen when a library is being updated. A faulty signature by itself can be difficult to exploit. If the same message is being signed a second time after updating the library then the combination of faulty and correct signature can subsequently leak the private key.
A second factor that contributes to the weakness of this library is the interface. Typically, ECDSA signature generation takes a message as input. The implementation hashes this input and then generates a signature for the hash. Elliptic, however, has an interface that accepts the hash of the message in various formats. This makes the implementation fragile and susceptible to fault attacks already pointed out. @ChALkeR found a really nice one exploiting an incorrect conversion. Yet another factor is the documentation that appears to be incomplete. For example I've tried to test against test vectors with different hash functions using features I could only find in the unit tests, but without getting the expected results.
This interface not only makes it difficult to get a correct implementation, it also makes it difficult to test the implementation. It is completely plausible (perhaps likely) that there are still undetected critical bugs in the library. I.e., the tests I'm running against the library do not try to exploit the open interface an hence have rather low coverage for this library. I'm not trying to do any chosen message attacks, which typically is one of the more difficult types of attack to defend against.
A clean fix should in my opinion start with a clean interface. I.e., sign a message (not a hash) and use Uint8Array internally as the only way to represent byte arrays. I don't see this happening soon, hence the simplest way to prevent potential damage is to switch to another library (and probably revoke your private keys at the same time).
1. secp521r1 and SHA-512
When signing with the secp521r1 curve and SHA-512, the curve length is 521 bits. However, the k value is initially stored as a 66-byte array before being converted to a bit length. Therefore, the _truncateToN function includes the following code to handle bit shifting:
File: lib/elliptic/ec/index.js#L101-L103
var delta = bitLength - this.n.bitLength();
if (delta > 0)
msg = msg.ushrn(delta);
In a random case, if the first byte of k happens to be 0, the total length becomes 65 bytes. Here, bitLength equals 65 * 8 = 520, which is 1 bit short of the 521-bit secp521r1 curve length, making delta = -1. The source code does not handle cases where delta < 0, but it should ideally pad a 0 on the left.
Under normal circumstances, a 66-byte value corresponds to 528 bits, and shifting right by 7 bits results in 521 bits, matching the curve length. Since the above code does not perform this right shift, the final signed k value ends up being a multiple of the expected value.
Suggested Fix
File: lib/elliptic/ec/index.js#L156-L156
// new BN(drbg.generate(this.n.byteLength()));
drbg.generate(this.n.byteLength());
Reason for the Fix
The generate function of the HmacDRBG object returns an array, preserving leading zeros. This allows the _truncateToN function to correctly handle bit shifts. If the value is converted to a BN type, modifications to _truncateToN would be required, making it more complex. The suggested approach is simpler.
2. secp224r1 and SHA-256
When signing with the secp224r1 curve and SHA-256, the curve length is 224 bits, whereas the hash function produces 256-bit outputs. Therefore, when manually hashing msg, it should be right-shifted to retain only the leftmost 224 bits before proceeding with further operations.
When providing a manually computed hash(msg) to the sign function, it's best to pass it in hex or array format. If you pass a BN format and the hash contains leading zero bytes, those zeros may be ignored, causing an incorrect truncation range.
Below is my test code, which successfully passes all your test cases:
const fs = require("fs");
const elliptic = require("elliptic");
const crypto = require("crypto");
const BN = require("bn.js");
const ec = new elliptic.ec("p224");
const cliProgress = require("cli-progress");
function signMessage(privateKeyHex, messageHex) {
const message = Buffer.from(messageHex, "hex");
const hash = crypto.createHash("sha256").update(message).digest("hex");
const privateKey = new BN(privateKeyHex, 16);
const keyPair = ec.keyFromPrivate(privateKey);
const signature = keyPair.sign(hash);
return signature.toDER("hex");
}
const filePath = "./ecdsa_rfc6979_secp224r1_sha_256.json";
const jsonData = JSON.parse(fs.readFileSync(filePath, "utf8"));
const progressBar = new cliProgress.SingleBar(
{
format: "Progress [{bar}] {percentage}% | {value}/{total}",
barCompleteChar: "█",
barIncompleteChar: "░",
hideCursor: true,
},
cliProgress.Presets.shades_classic
);
const tests = jsonData.tests;
const totalTests = tests.length;
let mismatchCount = 0;
progressBar.start(totalTests, 0);
tests.forEach((test, index) => {
const { tcId, privateKey, msg, sig } = test;
const calculatedSig = signMessage(privateKey, msg);
if (calculatedSig !== sig) {
progressBar.stop();
console.log(`\nMismatch found! tcId: ${tcId}`);
console.log(`Expected sig: ${sig}`);
console.log(`Calculated sig: ${calculatedSig}\n`);
mismatchCount++;
progressBar.start(totalTests, index + 1);
}
progressBar.update(index + 1, { tcId });
});
progressBar.stop();
console.log(
`Signature verification completed. Mismatches found: ${mismatchCount}`
);
@bleichenbacher-daniel @indutny
I believe there is some confusion in the discussions going on here and in other places (such as indutny/elliptic#322).
As far as I can tell, there are two (similar but distinct) issues related to incorrect signatures due to leading zeros, which are often conflated in these discussions, leading to confusion regarding what is and isn't fixed.
The first issue, which is tracked as CVE-2024-48948, is related to leading zeros in the message and has been fixed in v6.6.0 (via indutny/elliptic@34c853478c).
Now, there is a second issue that is related to leading zeros during the computation of k, as described in https://github.com/indutny/elliptic/issues/321#issuecomment-2724065638.
Even though this is similar in nature with CVE-2024-48948, it is an Independently Fixable Vulnerability and as such it should be tracked as a separate CVE. According to Section 4.2.11 of the CNA Operational Rules:
CNAs SHOULD assign different CVE IDs to different, Independently Fixable Vulnerabilities.
@indutny, do you agree with this assessment? What is a good medium to discuss and coordinate on disclosing/fixing this second issue?
What is a good medium to discuss and coordinate on disclosing/fixing this second issue?
I would also be interested in a better medium to discuss vulnerabilities of this library (or crypto libraries in general). In particular I would be interested in more streamlined way to report bugs and vulnerabilities, so that users of libraries can make better decisions about which library should be used in cases where maintainers are slow to acknowledge and fix issues.
E.g. in this case here I have a handful of additional issues that need further analysis. As long as there is the possibility that issues are being delayed and ignored, I'm obviously not interested to waste any more time.
npm audit still doesn't warn about this vulnerability, because the maintainer hasn't added a GHSA about it to https://github.com/indutny/elliptic/security
https://docs.github.com/en/code-security/security-advisories/working-with-global-security-advisories-from-the-github-advisory-database/about-the-github-advisory-database https://github.blog/2021-10-07-github-advisory-database-now-powers-npm-audit/
If the maintainer isn't going to file an advisory, it looks like someone needs to open a PR adding it at https://github.com/github/advisory-database/pulls.
