4 ms·

I thought Ethereum used something like EdDSA where the nonce is deterministically derived from the secret key and message hash using a one-way function

TacticalCoder 5y ago
Yup, this. I don't understand either. The transaction (amount / gas fee / max gas / to / from / code if any / nonce) is hashed using Keccak, then that hash is signed. The transaction also contains the data in the clear. Nodes take the data in the clear, recompute the Keccak hash, recover the signing address from the keccak hash + r,s,v then, if there are enough funds on that signing address, the transaction goes on. How could reusing a nonce once lead to a full compromise? Or is it only if the nonce is reused, but for the exact same transaction, with all the parameters identical, then signed using the same private key but some other random point?
- ulrikrasmussen 5y ago
  It's an inherent property of Schnorr-style signature schemes commonly used for elliptic curves. These rely on the signer generating a random nonce for each generated signature. The nonce is used as a blinding factor, and is necessary to avoid leaking secrets in the generated signature. If the same nonce is used for signing two different messages with the same private key, then anyone can trivially derive the private key. See https://en.m.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm https://en.m.wikipedia.org/wiki/Elliptic_Curve_Digital_Signa... for details - this was famously how Sony accidently revealed the private key used to sign Playstation 3 releases, because they had just used a hardcoded nonce. Anyone could then derive the key without use of brute force via a few modular arithmetic computations. Modern signature schemes such as EdDSA do not have this footgun as they specify a completely deterministic procedure for deriving a fresh nonce for each pair of (message, private key), simply by applying a cryptographic hash function to their concatenation. This is MUCH safer for the implementor, and also simpler to implement because one doesn't have to bother with maintaining a stateful PRNG
saurik 5y ago
There is no way for someone who receives the signature to know you used deterministic k, so the system can't enforce it; I guess the assumption is that once in a blue moon you find someone with a bespoke implementation of the signature algorithm that failed to implement deterministic signatures.
- ulrikrasmussen 5y ago
  That makes sense. I'm just surprised that this many people have apparently rolled their own signature algorithms with this flaw that running a bot to check for it is affordable. It's one of the most well-known mistakes to make in EC signature algorithms, and anyone researching how to implement these signatures should stumble upon high-profile cases such as the Sony private key leak, which should scare them enough to not trust that they can implement a reliable PRNG that won't generate the same nonce twice (with non-negligible probability). But I guess these bots check for a whole catalogue of mistakes, and this is a fairly cheap check to add if you are checking every transaction anyway.
- jmull 5y ago
  I would guess someone is looking for an opportunity to compromise a shared implementation, and then hoover up the proceeds as the compromised implementation is used.

TacticalCoder 5y ago

Yup, this. I don't understand either. The transaction (amount / gas fee / max gas / to / from / code if any / nonce) is hashed using Keccak, then that hash is signed. The transaction also contains the data in the clear. Nodes take the data in the clear, recompute the Keccak hash, recover the signing address from the keccak hash + r,s,v then, if there are enough funds on that signing address, the transaction goes on. How could reusing a nonce once lead to a full compromise? Or is it only if the nonce is reused, but for the exact same transaction, with all the parameters identical, then signed using the same private key but some other random point?

ulrikrasmussen 5y ago
It's an inherent property of Schnorr-style signature schemes commonly used for elliptic curves. These rely on the signer generating a random nonce for each generated signature. The nonce is used as a blinding factor, and is necessary to avoid leaking secrets in the generated signature. If the same nonce is used for signing two different messages with the same private key, then anyone can trivially derive the private key. See https://en.m.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm https://en.m.wikipedia.org/wiki/Elliptic_Curve_Digital_Signa... for details - this was famously how Sony accidently revealed the private key used to sign Playstation 3 releases, because they had just used a hardcoded nonce. Anyone could then derive the key without use of brute force via a few modular arithmetic computations. Modern signature schemes such as EdDSA do not have this footgun as they specify a completely deterministic procedure for deriving a fresh nonce for each pair of (message, private key), simply by applying a cryptographic hash function to their concatenation. This is MUCH safer for the implementor, and also simpler to implement because one doesn't have to bother with maintaining a stateful PRNG

saurik 5y ago

There is no way for someone who receives the signature to know you used deterministic k, so the system can't enforce it; I guess the assumption is that once in a blue moon you find someone with a bespoke implementation of the signature algorithm that failed to implement deterministic signatures.

ulrikrasmussen 5y ago
That makes sense. I'm just surprised that this many people have apparently rolled their own signature algorithms with this flaw that running a bot to check for it is affordable. It's one of the most well-known mistakes to make in EC signature algorithms, and anyone researching how to implement these signatures should stumble upon high-profile cases such as the Sony private key leak, which should scare them enough to not trust that they can implement a reliable PRNG that won't generate the same nonce twice (with non-negligible probability). But I guess these bots check for a whole catalogue of mistakes, and this is a fairly cheap check to add if you are checking every transaction anyway.
jmull 5y ago
I would guess someone is looking for an opportunity to compromise a shared implementation, and then hoover up the proceeds as the compromised implementation is used.