Attacks on ECDSA

Learn about attacks on ECDSA and their categories in this lesson.

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 mm 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 dd from Alice’s domain parameters D=(p,A,B,P,n,h)D=(p, A, B, P, n, h) and her public key QQ, 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 HH isn’t preimage resistant: Eve arbitrarily selects an integer ll and computes Q+lP=(xR,yR)Q+l P=\left(x_{R}, y_{R}\right). Then, she computes rxR  mod nr \equiv x_{R} \space\space mod \space n. In the last step, she sets s=rs=r and computes erl  mod ne \equiv r l \space\space mod \space n. Since HH isn’t preimage resistant, Eve is able to find a message mm such that e=H(m)e=H(m). Now, (r,s)(r, s) is a valid signature for mm and a public key QQ.


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

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

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

Since erl  mod ne \equiv r l \space\space mod \space n and s=rxR  mod ns=r \equiv x_{R} \space\space mod \space n, it follows that

(x1,y1)=X=u1P+u2Q={e}rl{s1}r1P+r{s1}r1Q=rlr1P+rr1Q=lP+Q,(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 x1=xRx_{1}=x_{R} and therefore v=rv=r.

  • An insufficient collision resistance of the employed hash function HH would undermine the non-repudiation of the signature (r,s)(r, s) on a message mm. 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, mm and mm^{\prime}, such that H(m)=H(m)= H(m)H\left(m^{\prime}\right). Since the signature generation algorithm uses e=H(m)=H(m)e=H(m)=H\left(m^{\prime}\right) (see step 5 of Algorithm 3 :Algorithm_3 ), every valid signature for mm is also a valid signature for mm^{\prime}. Therefore, the adversary can sign message mm but later claims to have signed the message mm^{\prime}.

Subtracting (1) from (2) gives

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

and hence

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

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

Get hands-on with 1200+ tech skills courses.