#StackBounty: #public-key #elliptic-curves #cryptanalysis #signature #dsa Is it safe to reuse a ECDSA nonce for two signatures if the p…

Bounty: 500

We denote the s value of an ECDSA signature $(r, s)$ on a message $m$ as:
$s=frac{H(m)+xr}{k}$

Assume two ECDSA signatures sharing the same nonce $(r, s_1) , (r, s_2)$ on two messages $m_1, m_2$, that verify under two pubkeys $x_1G, x_2G$.

If the two public keys are equal then the secret keys should be equal $x_1 = x_2$ and we can easily recover the $k$ using the standard attack on nonce reuse. Once we know $k$ we can recover the secret key.

$frac{H(m_1)-H(m_2)}{(s_1 – s_2)} =frac{k(H(m_1)-H(m_2))}{H(m_1)-H(m_2)+x_1r – x_2r}$

$x_1 = x_2 rightarrow x_1r – x_2r = 0$

$frac{H(m_1)-H(m_2)}{(s_1 – s_2)} =frac{k(H(m_1)-H(m_2))}{H(m_1)-H(m_2)} = k$

My question is can this attack be made to work if the secret keys are not equal i.e. $x_1 ne x_2$:

$frac{H(m_1)-H(m_2)}{(s_1 – s_2)} =frac{k(H(m_1)-H(m_2))}{H(m_1)-H(m_2)+x_1r – x_2r} = frac{k(H(m_1)-H(m_2))}{H(m_1)-H(m_2)+ (x_1 – x_2)r}$

If you know either $x_1 – x2$ or $frac{x_1}{x_2}$ you should be able to compute $k$ as long as $s_1 ne s_2$.

You can calculate $x_1 – x_2 = frac{H(m_2) – H(m_1)}{r}$ in case where $s_1 – s_2 = 0$. However this case seems to reduce to the hardness of ECDSA since anyone can compute the pubkey for a new message $m_2$ that verifies under first signature $(s, r)$ using public key recovery.

If $s_1 ne s_2$ you can compute $frac{x_1 – x_2}{k}$ which allows you to convert $s_1$ into $s_2$ and vice versa.


Get this bounty!!!

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.