5
$\begingroup$

I've just started working with elliptic curves and ECSDA in particular, so my understanding of the underlying math isn't great. The thing I'm currently stuck on is trying to understand why replay attacks don't work on ECSDA.

For this scenario, the public key, $Q = x \centerdot G$, where $x$ is the private key and $G$ is the generator of size $n$. Additionally, $H(m)$ is the hash of message $m$ and $k$ is a random number in $[1,n-1]$. The signature $(r,s)$ would then be defined as

$\begin{eqnarray*} r &=& (kG)_x \mod n\\ s &=& k^{-1}(H(m) + rx) \mod \ n \end{eqnarray*}$

Now, in this hypothetical attack, the attacker sees $(r,s)$ along with message $m_1$ and wants to send message $m_2$ on the next transmission via replay attack. If my math is correct, and it most assuredly isn't, he could achieve this by keeping the original $r$ and deriving the following:

($mod\ n$ omitted for tidiness)

$\begin{eqnarray} s_1 &=& k^{-1}(H(m_1) + rx)\\ &=& k^{-1}(H(m_1)) + xk^{-1}(kG)_x\\ &=& k^{-1}(H(m_1)) + (xG)_x\\ &=& k^{-1}(H(m_1)) + Q_x\\ k^{-1}(H(m_1)) &=& s_1 - Q_x\\ ...\\ s_2 &=& k^{-1}(H(m_2)) + Q_x\\ s_2 &=& (k^{-1}H(m_2))(H(m_1)H(m_1)^{-1}) + Q_x\\ s_2 &=& (k^{-1}H(m_1))(H(m_2)H(m_1)^{-1}) + Q_x\\ s_2 &=& (s_1 - Q_x)(H(m_2)H(m_1)^{-1}) + Q_x \end{eqnarray}$

$(r, s2)$ is now a valid signature for $m_2$. But that's way too easy to be realistic, so where's the error? The only thing I can think of is if $xk^{-1}(kG)_x \neq (xG)_x$, but it seems like it would need to for the authentication steps to cancel correctly.

If this were a valid attack, then the receiver would need to counter it by logging $r$ to ensure that it's never reused, and I've never heard anyone suggesting doing that.

$\endgroup$

1 Answer 1

10
$\begingroup$

You got tripped up by the fact that there are two different group operations in play here, and they don't play nice with each other. This is implicit in the notation, and it's easy to get tripped up, because the notation expresses both operations in the same way -- but they are not the same. This is arguably a pitfall in the notation: the assumption is that the reader will be careful to keep track of which operation is which and not get tripped up, but as you have seen, it is easy to lose track and be led astray.

When we write $kG$, we are referring to a group operation in the elliptic curve. $kG$ is short-hand for $G+G+G+\dots +G$, where here $+$ represents the elliptic curve point-addition operation (it takes two points on the curve and "adds" them, returning another point on the curve).

When we write $rx$, we are referring to a group addition for the integers modulo $n$. It is short-hand for multiplying the two integers $r$ and $x$ and reducing the result modulo $n$. Note that this operation acts, not on two elliptic curve points, but rather on two integers modulo $n$. It is a totally different operation.

With that understanding, here's where you went wrong. You wanted to write something like $k^{-1} r = k^{-1} (kG) = (k^{-1} k)G=G$. However, that derivation is simply wrong, because it mixes up the two different kind of operations. $kG$ is an elliptic curve operation, so the result is a point. Actually, $r$ is not $kG$; it is an integer given by the x-coordinate of $kG$. This is essential, because when we write $k^{-1} r$ (or $k^{-1} (kG)_x$), we are multiplying two integers using the group operation for integers -- not the elliptic curve group operation.

Even if you adjusted the derivation to $k^{-1} r = k^{-1} (kG)_x = (k^{-1} k)G=G$, it would still be wrong, because of the difference between the elliptic curve point $H$ and its x-coordinate $H_x$; the former is a point on the curve, while the latter is an integer. Different addition/multiplication operations apply to these two different kind of mathematical objects, and they don't cancel each other out.

In fact, in some sense the security of ECDSA relies upon the fact that these two different kinds of operations don't cancel each other and don't play nice with each other. So buried in your question is an insight about elliptic curve cryptography that is pretty fundamental to the whole concept.

$\endgroup$
1
  • $\begingroup$ This is similar to (a generalization of, in fact) having computations mod $p$ and computations mod $q$ for “vanilla” DSA, right? $\endgroup$ Dec 12, 2012 at 17:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.