Invalid signature generation and private key exposure.

[bleichenbacher-daniel]

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.

[bleichenbacher-daniel]

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.

[bleichenbacher-daniel]

I've also tested the latest version of the library. The vulnerability still exists in version 6.6.1.

[bleichenbacher-daniel]

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 #322).

Are there any efforts to fix this or has the library been abandoned?

[sureshaff]

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.

[tomatod]

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

[bleichenbacher-daniel]

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: #322 (comment) . 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.

[tomatod]

@bleichenbacher-daniel
Thank you for comments. I read #322 (comment) . 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.

[bleichenbacher-daniel]

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).