Attacks on ECDSA

The security of ECDSA is vital to assure the integrity of any ECC signature-based system. An adversary who launches an attack against Alice aims at obtaining a valid signature on a single message $m$ in an unauthorized manner. Johnson, Menezes, and Vanstone (2001)Don Johnson, Alfred Menezes, and Scott Vanstone. The elliptic curve digital signature algorithm (ECDSA). International Journal of Information Security, 1(1):36-63, Aug 2001 classify the attacks on ECDSA into three categories:

1. Attacks on the ECDLP.
2. Attacks on the hash function employed.
3. Attacks on the ephemeral key.

In the following points, we describe these attacks in more detail.

Attacks on the ECDLP

This type of attack intends to derive the private key $d$ from Alice’s domain parameters $D=(p, A, B, P, n, h)$ and her public key $Q$, which is equivalent to solving the ECDLP. We outlined the possible attacks in this lesson. An adversary who successfully grabs Alice’s private key can subsequently forge her signature on any message of their own choice.

Attacks on the hash function employed

An attack against ECDSA can be successfully launched if the underlying hash function isn’t preimage resistant or collision-resistant (see this definition :Security_Requirements_of_Hash_Functions ). Consequently, the security requirements of hash functions are crucial to maintaining the integrity of ECDSA.

• Hankerson et al. (2006)Darrel Hankerson, Alfred J. Menezes, and Scott Vanstone. Guide to Elliptic Curve Cryptography. Springer Professional Computing. New York, 2006. Springer. give the following strategy to forge a signature if $H$ isn’t preimage resistant: Eve arbitrarily selects an integer $l$ and computes $Q+l P=\left(x_{R}, y_{R}\right)$. Then, she computes $r \equiv x_{R} \space\space mod \space n$. In the last step, she sets $s=r$ and computes $e \equiv r l \space\space mod \space n$. Since $H$ isn’t preimage resistant, Eve is able to find a message $m$ such that $e=H(m)$. Now, $(r, s)$ is a valid signature for $m$ and a public key $Q$.

Proof

In accordance with Algorithm 3, we omit step 1, but compute $Q+l P=\left(x_{R}, y_{R}\right)$ and then $r \equiv x_{R} \space\space mod \space n$ in step 3. Then, we skip step 4 , set $s=r$ and compute $e \equiv r l \space\space mod \space n$ in step 5. Hence, we obtain the signature $(r, s)$. Now, we claim that we find $m$ such that $H(m)=e$, since $H$ isn’t preimage resistant.

Now, the following happens during the ECDSA signature verification (Algorithm 4 :Algorithm_4 ): one computes $e=H(m)$. Then it is $$u_{1}=e w=e s^{-1}

and $$u_{2}=r w=r s^{-1}.

Since $e \equiv r l \space\space mod \space n$ and $s=r \equiv x_{R} \space\space mod \space n$, it follows that

$$(x_{1}, y_{1})=X=u_{1}P+u_2Q = \{e\}_{rl}\{s^{-1}\}_{r^{-1}}P + r\{s^{-1}\}_{r^{-1}}Q =rlr^{-1}P + rr^{-1}Q = lP + Q,$$

thus $x_{1}=x_{R}$ and therefore $v=r$.

• An insufficient collision resistance of the employed hash function $H$ would undermine the non-repudiation of the signature $(r, s)$ on a message $m$. If the underlying hash function isn’t collision-resistant, an adversary thus may be able to repudiate signatures by adopting the following strategy: they first generate two different messages, $m$ and $m^{\prime}$, such that $H(m)=$ $H\left(m^{\prime}\right)$. Since the signature generation algorithm uses $e=H(m)=H\left(m^{\prime}\right)$ (see step 5 of Algorithm 3 :Algorithm_3 ), every valid signature for $m$ is also a valid signature for $m^{\prime}$. Therefore, the adversary can sign message $m$ but later claims to have signed the message $m^{\prime}$.

Subtracting (1) from (2) gives

$$k\left(s_{1}-s_{2}\right) \equiv e_{1}-e_{2} \quad \space\space mod \space n$$

and hence

$$k \equiv\left(e_{1}-e_{2}\right)\left(s_{1}-s_{2}\right)^{-1} .$$

Thus, if the ephemeral key $k$ is used twice, the adversary can determine $k$ and then recover the private key $d$. Consequently, $k$ is to be generated randomly for each message to sign.