Nonces for events bearing hash IDs and signatures

[mleku]

It is a standard practise with EC signatures to use a second level protocol structure of some sort using a random value to prevent hash collisions that will be signed on.

Currently the only entropy value in a NIP-01 event, for instance, is the timestamp.

The specification allows for extra data to be added to events, but a good quality nonce should just be a standard field.

I'm not sure what way is the best to add it, I know that there has been some level of implementation of extra data in go-nostr but for the Event, there really should be a mandatory nonce field, and a recommendation that relays also reject repeating nonces.

Perhaps it could be put into the tags field as this is an open ended structure.

If users sign the very same ID again some time later, an attacker has gained some number of extra bits of clue to how to reverse the pubkey back to the secret key, and a nonce dramatically reduces the chance of this happening.

The way that Nostr uses a single key instead of a HD keychain for event signing makes this a real vulnerability, and it's not a problem easily solved with a cryptographic trick other than adding noise to the messages.

[vitorpamplona]

Just add a "nonce": "" tag like the implementations doing Proof of Work do.

[mleku]

The point here is to make this, ultimately, mandatory for clients because otherwise you expose users to the risk of leaking bits of their keys.

[vitorpamplona]

Wait, how does adding a visible nonce block that from happening? If you want to reverse engineer the keys, and the nonce is available, you just include the nonce in your calculations.

[mikedilger]

The nonce prevents someone from signing the same data twice. The signature scheme is non-deterministic, and if you get two signatures for the same ID that helps your cryptanalysis.

[vitorpamplona]

The nonce prevents someone from signing the same data twice. The signature scheme is non-deterministic, and if you get two signatures for the same ID that helps your cryptanalysis.

That makes sense. So we add the nonce, but in order to make it work we have to change it at every new signature.

Though to be fair, I don't know anybody signing the same payload twice. Even with GiftWraps that can be discarded and recreated at will, we usually randomize the created_at anyway.

[mleku]

The nonce prevents someone from signing the same data twice. The signature scheme is non-deterministic, and if you get two signatures for the same ID that helps your cryptanalysis.

That makes sense. So we add the nonce, but in order to make it work we have to change it at every new signature.

Though to be fair, I don't know anybody signing the same payload twice. Even with GiftWraps that can be discarded and recreated at will, we usually randomize the created_at anyway.

The case of bitcoin wallets that were compromised a while back was pretty notorious, and something that could have been avoided if Bitcoin had stronger recommendations for key cryptography in the specifications.

A timestamp is not sufficiently high entropy to be a strong guarantee against producing the same hash.

[fiatjaf]

There is already a nonce created during the signature process itself, you don't need to add a nonce to the event data for this purpose.

[mleku]

Signatures use a random value, this is true, but if they sign on the same hash, then they leak bits of the secret key, since this lets you isolate the nonce value from the traces of the secret key, that's precisely what I'm proposing this for.

This problem is bigger with secp256k1, also, compared to ed25519, more bits leak from the same hash being signed with a given secret key, due to the nature of the EC group (this is also a problem for HD keychains with secp255k1).

Not bad mouthing the use of secp256k1 btw, I think it's a perfectly fine EC group if you don't make such obvious errors in your protocol design. The NIST P256 group is very close to it, but the secp is more friendly with NSA and this was a big part of the reason why Satoshi chose it. A backdoor on secp256k1 is practically impossible due to its construction.

[mikedilger]

So is the security of this proposal coming from the fact that the random nonce would be added before the hash (in the message) rather than after the hash (in the signature algorithm)? And can you point us to a reference describing the current construction as a weak?

current: Sign(hash(message), random_nonce()) proposed: Sign(hash(message + random_nonce()), random_nonce())

[mleku]

where is the nonce you speak of in your pseudocode?

It has to be provided to the verifier, right? Or else they can't verify the signature. It's not hidden inside the signature so where is it?

I have been working with ECDSA for some time and more recently also schnorr and there is no extra nonce unless you put it in the message.

One message hash, one private key, one signature.

One message hash, one public key, one bit true or false.

where is the nonce in those processes? How can it be in the sign but not in the verify?

[mikedilger]

If it is non-deterministic some randomness must have gone in. So I assumed it was hidden inside the signature. I'm not a cryptographer.

[mleku]

If it is non-deterministic some randomness must have gone in. So I assumed it was hidden inside the signature. I'm not a cryptographer.

I am not 100% sure because I didn't specialize in using Edwards curves, that the ed25519 signatures have built in entropy. Oh, see, ya elarn something every day:

Edwards curve signatures using EdDSA are deterministic based on the secret and the message hash: https://en.wikipedia.org/wiki/EdDSA#Secure_coding

These would be vulnerable to a repeating hash as a plaintext attack vector.

In contrast, the older ECDSA has a separate problem - if the CSPRNG is not giving quality entropy or repeats a nonce:

https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm

The variable k is the importhant one. This led to a vulnerability in a Java implementation back in 2013, and the famous playstation hack was because it wasn't properly random.

So actually, you are correct. If a system has a poor CSPRNG it is not going to help much by putting a poor nonce in the message in addition to the same source of garbage for the signature nonce.

Closing, but pay attention to the point about EdDSA not being more secure given a decent CSPRNG. Attacks on ECDSA are not great in number. EdDSA signatures are deterministic, and it makes sense actually that they are faster because of this.