We build the backdoor in Bitcoin (ECDSA) or again on kleptography

Hi% username%!
Do you use unofficial bitcoin clients? There is a reason to look at them more closely.
After implementing the backdoor for RSA, I wondered how things were going with the rest of the cryptographic primitives. It turns out that the whole science called kleptografiya deals with the transfer of information in the so-called "subconscious" channels. Those about which nobody knows except the sender and the recipient. Like steganography, only inside cryptoalgorithms.

In general, this class of attacks on cryptoalgorithms is called SETUP (Secretly Embedded Trapdoor with Embedded Protection). That is, there is usually a backdoor and protection, such that even when a backdoor is detected, it will be impossible to know what was being transmitted.

SETUP (I will talk about SETUP in the masculine) can be weak and strong.

Weak SETUP - If you find out the generated keys can not only the attacker, but also the owner of the device on which the compromised software is installed.
Accordingly, Strong SETUP - if only the attacker can find out the keys.
')
Another characteristic is called Leakage bandwidth , it shows how much secret data "leaks" during a repeated encryption / signature process. Denoted by (m, n), which means the leakage of m secret messages / keys for n transmitted.

Such attacks exist for virtually all public key schemes. DSA, ElGamal, Diffie-Helman, everywhere there is a way to transmit at least one bit covertly. Not always it turns out as beautiful as happened with the RSA, but if you want you can find practical application. For example, for ECDSA, a SETUP attack is easier because the key generation parameters (curve, base point, curve order) are known in advance, and in DSA, the corresponding parameters are randomly generated for each key pair.

As we all know, a Bitcoin wallet is a key pair of ECDSA.

Today we will look at a strong SETUP attack (1,2) on ECDSA, that is, an attacker can find out the user's secret key for 2 signatures, and nobody can do this except him.

For a start, let's recall the generated ECDSA signature.

We have the private key d - the number and the public key Q - the point of the elliptic curve is equal to dG, where G is the base point of the curve.

• To sign a random number k is chosen, in the range [1, n-1].
• Calculate the point of the curve (x ₁ , y ₁ ) = k * G
• Calculate r = x ₁ mod N, where N is the order of the curve.
• Calculate s = k ^-1 (H (m) + rd) mod N, where k ^-1 is the number inverse of the modulus of N to k. H (m) - hash of the message being signed.

The signature is a pair (r, s).

As you can see, here k is chosen randomly. We will modify the process a bit so that the attacker can calculate the user's private key d.

The attacking public and private keys are called v and v = vG.

Step one. User generates signature for the first time (sends bitcoins to someone)

Same as in a regular signature. Except that we will need to save k somewhere . Call it k ₁ Get a pair (r1, s1)

Step two (send bitcoins a second time)

We calculate the hidden element of the field Z = a * k ₁ G + b * k ₁ V + h * jG + e * uV,
where a, b, h, e <n - fixed integers; j, u ∈ {0, 1} are random.

a, b, h, e can be generated deterministically, for example using a message hash as a seed for PRNG. This will complicate bookmark detection.

k2 is not chosen randomly, but is now a hash from Z. From the point of the curve we assume that its hash is the X coordinate.
Then everything is as usual, we get a pair (r2, s2).

So, the attacker received pairs (r ₁ , s ₁ ) and (r ₂ , s ₂ ). How can he get the user's private key?

1) Calculate R ₁ ′ = s ^-1 (H (m1) G + r ₁ Q) = (x ₁ ′, y ₁ ′). This is what we do when we check the digital signature.
2) Z ₁ = aR ₁ ′ + b * vR ₁ ′, where v is the attacker's private key
3) For each possible value of j, u we calculate:
Z ₂ = Z ₁ + h * jG + e * uV
k ₂ ′ = H (Z ₂ )
R ₂ ′ = k ₂ ′ G = (x ₂ ′, y ₂ ′)
r ₂ ′ = x ₂ ′ mod n
If r ₂ ′ = r ₂ , then k ₂ ′ = k ₂ , we have found k, this is what we need

Private key d user = (s ₂ k ₂ - h (m ₂ )) × r ₂ ^-1 mod n

As you understand, k ₂ can also be remembered and continue to generate k ₊₁ through the chain, thus giving the attacker the opportunity to find out the user's private key using any two signatures in a row.

There is nothing supernatural here, the attacker just needs to choose the numbers a, b, h, e in advance and place them in the backdoor along with his public key. Or generate them based on the message being signed.

The attack itself, though strong, is unstable. This means that a user who owns his private key can theoretically calculate that k2 is generated in a non-random way. For this purpose, j and u are introduced to diversify the possible values ​​for the case of checking by a vigilant user. They can be made different from 0 and 1, then the options will be even more. True, brutess will have a little longer. In fact, you can not worry too much, all the same, most likely the availability of a bookmark will be revealed only after the fact when the code is sorted out.

I added the working code of this attack to the code of attack on RSA . I see no reason why it would no longer exist, or Trojans for bitcoin, implementing this technique, would not appear. Yes, the Trojans can immediately send the private key (and burn on the first firewall), or they can not send anything at all - the attacker will wait quietly until serious amounts appear on the built-in wallets.