Improve security of signature generation

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

k = hash_6979(private_key, message, extraEntropy)

ethereumjs-monorepo/packages/util/src/signature.ts

Lines 37 to 42 in e86eace

	export function ecsign(
	msgHash: Uint8Array,
	privateKey: Uint8Array,
	chainId?: bigint,
	): ECDSASignature {
	const sig = secp256k1.sign(msgHash, privateKey)

In this case it becomes secp256k1.sign(msgHash, privateKey, { extraEntropy: true }).

extraEntropy can also be false, true (auto-fetch random), or Uint8Array which you specify.

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

[paulmillr]

Viem is on board and implemented the changes today.

[jochem-brouwer]

Wow, this confuses me a lot. We had a rule in the past (Homestead fork) where we did not allow flipping certain values (namely we do not allow tx signatures where s > SECP256K1_ORDER_DIV_2). But now I realize that this is only possible when you know the v/r/s values and you can only end up with one other valid signature which yields the same public key. However when we would allow this extra entropy then each sign on the same data with the same private key will yield different v/r/s values.

Test script (in ./packages/tx/test/testSig.spec.ts):

import { bytesToHex } from "ethereum-cryptography/utils";
import { createLegacyTx } from "../src/index.js";

const d = createLegacyTx({})
const p = new Uint8Array(32).fill(0x20)

const s = d.sign(p)
console.log(bytesToHex(s.hash()), s.getSenderAddress().toString())
const s2 = d.sign(p)
console.log(bytesToHex(s2.hash()), s2.getSenderAddress().toString())

Without the extra entropy, change nothing (as of current master @ e86eace). The two signatures will yield the same hash and the same sender, also when started up a different time.

Output:

9a94f6841407ebad6d23d4d80396592902847c6bd14fbdcc4f9d99339312d481 0xb6e610921b0a0f6f608c0e1f29a845552bc6db2c
9a94f6841407ebad6d23d4d80396592902847c6bd14fbdcc4f9d99339312d481 0xb6e610921b0a0f6f608c0e1f29a845552bc6db2c

To add entropy, change ./packages/util/src/signature.ts:

export function ecsign(
  msgHash: Uint8Array,
  privateKey: Uint8Array,
  chainId?: bigint,
): ECDSASignature {
  const sig = secp256k1.sign(msgHash, privateKey, { extraEntropy: true })
  const buf = sig.toCompactRawBytes()

Each time sign is run (also thus the first and second signature on the run) the hash will change but the sender will not.

Sample output:

eacc68ac9306c1c7d53ef351257b470dbfbede13cf29d315f8c1ac2e7c222d72 0xb6e610921b0a0f6f608c0e1f29a845552bc6db2c
d02712f4cdd474503f4dda38b6bafe9f1721f551a9cc51523acee868b15f25f5 0xb6e610921b0a0f6f608c0e1f29a845552bc6db2c

Forgive my novice-ness in cryptography here, but if we add the entropy, then this means that each time if someone uses our libraries and uses the same private key and the same data to sign (i.e. the same transaction), then it will yield a different v/r/s scheme and thus also a different hash. Is this wanted? 🤔 (Or am I doing something wrong here?)

[paulmillr]

then it will yield a different v/r/s scheme and thus also a different hash. Is this wanted

Yes, this is exactly the point. It protects against "bad cryptography". "High-s" is not affected, it would still be low-s.

• Previously, before RFC 6979 existed, it was always the case (different hash).
• After 6979 standardized, signatures became deterministic (same hash).
• After Schnorr signatures standardized (used extensively in Bitcoin), signatures became non-deterministic again (different hash)
  • Schnorr signatures always pass extraEntropy
• Even before Schnorr, Bitcoin did non-determinism with low-R ECDSA signatures

[jochem-brouwer]

I see. Then my follow-up question would be, why is the extraEntropy: true not the default of ecsign? (At least not in the version we are using?)

[paulmillr]

It is not default because it would break tests, which assume deterministic outputs.

It is also not clear which user applications rely on deterministic outputs. But I think it's safe to change in the upcoming major release while keeping a changelog NOTE. As long as there is an option to use no extraEntropy, users should be fine.

Using extraEntropy would massively harden security of cryptography. Again, to prove my point, soon a vulnerability in popular library (not noble) would be disclosed. I can send you more info on it in direct messages. It looks bad and I want to prevent such things in advance.

[paulmillr]

Besides ecsign, EIP712 / EIP191 messages would also need to be edited to use entropy.

By "not clear which user applications rely on deterministic outputs" I mean the following thing:

• End-user applications which verify tx hash or EIP712 sig do not know which tx hash is produced
  • The applications can only verify the fact the signature is valid
  • Nothing is changed for them
• The only place where different signatures may affect something is deep applications, maybe EVM? with access to private keys and such