[curves] Sig nonce generation
mike at shiftleft.org
Fri Jul 25 10:56:20 PDT 2014
I was conveying the results of our signature nonce generation discussion to CFRG, and I realized a problem with PRF(message) xor random().
If your random number generator is broken, it might have near-collisions. Near-collisions lead to near-colliding nonces, which leaks the key. Specifically, it gives the attacker
r1 = k + c1 x, r2 = k+epsilon + c2 x,
where k is the unknown nonce, epsilon is unknown but sparse and thus guessable, c1 and c2 are the known challenges and x is the secret. So the attacker can solve for x as (c2-c1) x = r2-r1-epsilon.
Likewise if you multiply the challenges by the nonce, then the attacker solves (1/c2 - 1/c1) = r2/c2 - r1/c1 - epsilon.
Maybe it’s OK if you somehow munge the random number, like with AES with a secret key?
More information about the Curves