undefined | Better HN

0 pointsSAI_Peregrinus3y ago0 comments

It's more properly called 'k'. It's really a secret key, but it has to be unique per-signature. If an attacker can ever guess a single bit of the nonce with probability non-negligibly >50%, they can find the private key of whoever signed the message(s).

It makes ECDSA very brittle, and quite prone to side-channel attacks (since those can get attackers exactly such information.

0 comments

Mindless21123y ago

There's an easy fix for that though -- generate k deterministically using the procedure in RFC6979 [1].

[1] https://datatracker.ietf.org/doc/html/rfc6979#section-3.2

dilippkumar3y ago

> If an attacker can ever guess a single bit of the nonce with probability non-negligibly >50%, they can find the private key of whoever signed the message(s).

This doesn’t seem right. Why wouldn’t someone guess a bit 0, see if the recovered message makes sense, and if it doesn’t, then try bit 1?

It would make the entire scheme useless no? Am I missing something?

Thorrez3y ago

I think they have to get the bit repeatedly and then combine the biased signatures together mathematically to get the key.

drexlspivey3y ago

That makes no sense, how can you get the private key from knowing 1 bit of the nonce?

tptacek3y ago

See, cryptography engineering is sinking in!

Here you go:

https://toadstyle.org/cryptopals/62.txt

What's especially great about this is that it's very easy to accidentally have a biased nonce; in most other areas of cryptography, all you care about when generating random parameters is that they be sufficiently (ie, "128 bit security worth") random. But with ECDSA, you need the entire domain of the k value to be random.

drexlspivey3y ago

Ok but for this scheme you need a large amount of signatures from the same biased RNG which makes sense. I thought that the GP was suggesting that you can recover the key from one signature with just a few bits.

2 more replies

na853y ago

I guess like so:

https://cryptopals.com/sets/8/challenges/62.txt

E: Thomas beat me to it

j / k navigate · click thread line to collapse

0 comments

Mindless21123y ago

There's an easy fix for that though -- generate k deterministically using the procedure in RFC6979 [1].

[1] https://datatracker.ietf.org/doc/html/rfc6979#section-3.2

dilippkumar3y ago

> If an attacker can ever guess a single bit of the nonce with probability non-negligibly >50%, they can find the private key of whoever signed the message(s).

This doesn’t seem right. Why wouldn’t someone guess a bit 0, see if the recovered message makes sense, and if it doesn’t, then try bit 1?

It would make the entire scheme useless no? Am I missing something?

Thorrez3y ago

I think they have to get the bit repeatedly and then combine the biased signatures together mathematically to get the key.

drexlspivey3y ago

That makes no sense, how can you get the private key from knowing 1 bit of the nonce?

tptacek3y ago

See, cryptography engineering is sinking in!

Here you go:

https://toadstyle.org/cryptopals/62.txt

drexlspivey3y ago

2 more replies

na853y ago

I guess like so:

https://cryptopals.com/sets/8/challenges/62.txt

E: Thomas beat me to it

j / k navigate · click thread line to collapse