search

ethereumjs / ethereumjs-monorepo

Monorepo for the Ethereum VM TypeScript Implementation
2.6k stars 760 forks source link

Improve security of signature generation #3801

Open paulmillr opened 1 week ago

paulmillr commented 1 week ago

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)

https://github.com/ethereumjs/ethereumjs-monorepo/blob/e86eace8c6bc4a848c260e6b652fc56e73ac16de/packages/util/src/signature.ts#L37-L42

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

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

paulmillr commented 1 week ago

Viem is on board and implemented the changes today.

jochem-brouwer commented 1 week ago

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 @ e86eace8c6bc4a848c260e6b652fc56e73ac16de). 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? :thinking: (Or am I doing something wrong here?)

paulmillr commented 1 week ago

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.

jochem-brouwer commented 1 week ago

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 commented 1 week ago

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 commented 1 week ago

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: