[curves] Sig nonce generation
Samuel Neves
sneves at dei.uc.pt
Fri Jul 25 19:46:06 PDT 2014
On 25-07-2014 18:56, Michael Hamburg wrote:
> 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?
This seems to converge towards PRF_1(msg) xor PRF_2(random()). Since the initial goal was to hedge against PRF_1
failing, the random component appears increasingly unnecessary, in favor of PRF_1(msg) xor PRF_2(msg).
Here we are approaching hash combiner territory, where there is some theoretical groundwork developed [1]. The expected
result of a combiner is that its output is secure as long at least one of the functions is secure. Some relevant results:
- H1(x) xor H2(x) preserves pseudorandomness, but not collision-resistance;
- H1(x) || H2(x) preserves collision-resistance, but not pseudorandomness;
- More complicated combiners, like Comb4P [1], preserve both.
[1] A. Lehmann, " On the Security of Hash Function Combiners", http://tuprints.ulb.tu-darmstadt.de/2094/
More information about the Curves
mailing list