3 ms·
lordnacho, as tptacek wrote below (which also applies to DSA); >a full repeat instantaneously destroys security with a single pair of signatures Roughly--assu
by YAYERKA 10y ago
lordnacho, as tptacek wrote below (which also applies to DSA);
>a full repeat instantaneously destroys security with a single pair of signatures
Roughly--assuming ECDSA parameters (H,K,E,q,G)--where H is a hash function, E the Elliptic Curve over finite field K w/ point G of prime order q. Suppose two different messages m and m' have been signed with private key x using the same (non-ephemeral) random nonce value of k.
According to ECDSA Signing these messages m, m' become signatures (r,s), and (r',s') where;
r = r' = kG,
s = (H(m) + x*r)/k mod q,
s' = (H(m') + x*r)/k mod q.
Observe that,
(H(m) + x*r)/s = k = (H(m') + x*r)/s' mod q.
Or,
x*r(s' - s) = s*H(m') - s'*H(m) mod q.
Which allows us to recover the private key x.
Since,
x = s*H(m') - s'*H(m) / r*(s' - s) mod q.
- tptacek 10y agoThe problem is really much worse than this. You don't merely need a non-repeating nonce (the way you can get away with a GCM nonce that increments by 1 every session): you need an unbiased nonce.
- YAYERKA 10y agoI believe an natural segue here is to remind people about cryptopals (especially set 8). Ie., I don't have the chops and wouldn't attempt to writeup EC/DSA nonce bias and partial key exposure attacks better than you all--not to mention the challenges regarding GCM. Cheers.