Clef: improve signature security by using extra entropy

[paulmillr]

Problem

Transaction signatures use "nonce" / "k" during their construction. The nonce should never be equal between two different messages. Reusing them would allow attacker to recover private key.

Many years ago, k was generated using system randomness. On some systems with bad quality of randomness, that lead to breakages:

k = random()

Today, the nonce is generated from private key and message hash using RFC 6979:

k = hash_6979(private_key, message)

However, if some issue would be found in serialization / parsing of those, and during generation of nonce, it would still be possible to recover private keys. The technique is described here: https://github.com/pcaversaccio/ecdsa-nonce-reuse-attack.

Impact

Private key leakage, hackers stealing money from users.

This is not some theoretical issue. This happened in the past. Soon there would be announcement of a new hack related to this.

Solution

Use RFC6979 3.6: additional k' extraEntropy to mix-in 32 byte of random data on every signature. It is standard way of doing this. It has been extensively used by Bitcoin for non-taproot transactions, to decrease signature size. In taproot (schnorr) signatures, extraEntropy is used by default and specified in BIP340 spec.

k = hash_6979(private_key, message, extraEntropy)

Disadvantages

• Signatures (r, s) would become non-deterministic and "new" after every signature.
  • They would still be verifiable. This is not a problem for tests because we can specify our own random extraData in tests.

There is no risk for security. If passed-through random is bad, the signature security would be just like today, not worse

[holiman]

cc @fjl @kevaundray @asanso any thoughts about this?

[asanso]

@paulmillr

However, if some issue would be found in serialization / parsing of those, and during generation of nonce, it would still be possible to recover private keys

may you be more specific about this ?

I do not see many things that can go wrong with k = hash_6979(private_key, message)

[paulmillr]

@asanso many things can go wrong, especially in javascript. Private key may be wrongfully serialized. Message may be wrongfully modulo-reduced or not reduced. The modreduce routine itself may crash or emit garbage on some inputs.

You will see a new CVE in one of popular libraries soon. It's bad, keys can be recovered. The nonce was reused while signatures remained the same.

Which disadvantage is there in adding some extra entropy?

[paulmillr]

I know this is not a javascript repo, but it would be great if Geth set a standard for everyone else. Maybe I can create EIP after that.

BIP340 included "default" extraEntropy for a reason.

[asanso]

as a rules of thumbs I am all for security. I wonder how big a problem would be "Signatures (r, s) would become non-deterministic". If this determinism is used somewhere so far.

[namiloh]

Way back, it was not deterministic. We changed that some years ago, and it was a huge gain in "dev ergonomics". Deterministic testcases, transactions, blocks etc. It made a big difference. So it is not a change without cost.

[paulmillr]

Dev ergonomics was not the reason of the change. The reason was added security. After PS3 hack, it was decided that the community can't rely on randomness as sole source of k security. RFC 6979 was created. However RFC 6979 has optional randomness, which Bitcoin is actively using.

If this determinism is used somewhere so far
Deterministic testcases, transactions, blocks etc

You can keep dev ergonomics and pass any value you want in extraEntropy, for tests, or for any other reason. I want to make this opt-out, not opt-in - advanced users would be able to disable it or use their own source of entropy.

Also keep in mind you can't really verify determinism anyhow besides the test cases. Because to verify determinism you will need knowledge of the private key.

[kevaundray]

• @holiman I wonder how geth handles breaking changes since this looks like we would need to modify

func Sign(msg []byte, seckey []byte) ([]byte, error) {

to

func Sign(msg []byte, seckey []byte, randomness []byte) ([]byte, error) {

Where making passing nil for randomness gives the old behaviour

• Is it also possible that apart from tests, the existing ecosystem is relying on the determinism of these signatures?

Asking to understand the impact of this change, if any, on existing users.

[holiman]

@kevaundray well, seems to me a better course would be to not change it, rather deprecate Sign([]byte,[]byte) and add a new method.

Here's the old discussion, btw: #2190

[paulmillr]

Is it also possible that apart from tests, the existing ecosystem is relying on the determinism of these signatures?

We have no knowledge of how people use it.

The old method would still be in place. I would say it doesn't matter as long as they can use prev behavior.