Attack k-reuse

Prerequisites:

1. Elliptic Curves

2. Elliptic Curves Digital Signature Authentication

In this section, we will discuss an attack on Elliptic Curve Digital Signature and Authentication- attack due to improper implementation of ECDSA, leading to knowledge of the private key of the signer and forging of signatures.

Before we move onto the attack, it is important for the reader to know how signatures are generated using Elliptic Curves: Signature Generation using Elliptic Curves

Consider a scenario where the signer (Alice) generates two signatures corresponding to two different messages, using the same value of k. As we already know k is any integer between 1 and n-1, where n is the order of the subgroup generated. Let the signature pairs, that have been generated using the same k be (r₁,s₁) and (r₂, s₂).

We will first see that the values of r generated for signing the two messages using the same value k will also be the same ie. r₁ = r₂:

1. We know that , and k is common for two signatures generated.

   • Hence for and we can write: .

We have signature pairs for two messages M1 and M2 equal to (r, s₁) and (r, s₂) respectively, generated using the same k. The next step is to retrieve the value of k and then use it to get the value of Alice's private key (Signer's private key). To retrieve the value of k, we can write:

1. , where z₁ and z₂ are L_n left-most bits of HASH(M1) and HASH(M2) respectively.

2. Subtracting s₁ from s₂ we get:

   • 

3. Thus,

   • 

Now that we have the value of k, we can calculate Alice's private key. We can use any of the two signatures (the ones that are generated using the same k) to retrieve the value of d_A (Alice's private key):

The attacker can use the private key d_A to generate a valid signature of any message M.

References

1. Wikipedia- ECDSA

2. Andrea Corbellini's blog