Embed a backdoor in Bitcoin (ECDSA) or once again about kleptography

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

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

    SETUP (I'll talk about SETUP in the masculine gender) can be weak and strong.

    Weak SETUP - If you know 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 the repeated encryption / signature process. It is denoted by (m, n), which means the leak of m secret messages / keys for n transmitted.

    Such attacks exist for almost all public key schemes. DSA, ElGamal, Diffie-Helman, everywhere there is a way to transmit at least one bit and transmit it covertly. It is far from always that it turns out as beautiful as it did with RSA, but you can find practical application if you wish. For example, for ECDSA it is easier to conduct a SETUP attack, 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 consider a strong SETUP attack (1,2) against ECDSA, that is, an attacker can find out the user's secret key in 2 signatures, and no one else can do it except him.

    To begin with, simplistically, recall how the ECDSA signature is generated.

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

    • For signature, a random number k is selected in the range [1, n-1].
    • The point of the curve is calculated (x 1 , y 1 ) = k * G
    • It computes r = x 1 mod N, where N is the order of the curve.
    • It computes s = k -1 (H (m) + rd) mod N, where k -1 is the number inverse of N to k modulo N. H (m) is the hash of the message being signed.

    The signature is a pair (r, s).

    Apparently, here k is chosen randomly. We will slightly modify the process so that the attacker can calculate the private key of user d.

    The private and public keys of the attacker are called v and V = vG.

    Step one. The user generates a 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 1 Get the pair (r1, s1)

    Step two (sends bitcoins a second time)

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

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

    k2 is not randomly chosen from us, but is now a hash from Z. We will consider the hash of its X coordinate as a hash from a point on the curve.
    Further, as usual, we get a pair (r2, s2).

    So, the attacker got the pairs (r 1 , s 1 ) and (r 2 , s 2 ). How can he get the user's private key?

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

    The user's private key d = (s 2 k 2 - h (m 2 )) × r 2 -1 mod n

    As you understand , k 2 can also be remembered and continue to generate k +1 in the chain, thus giving the attacker the opportunity to find out the user's private key from any two consecutive signatures.

    There is nothing supernatural here, the attacker only needs to pre-select the numbers a, b, h, e and put them in the backdoor along with his public key. Or generate them based on a signed message.

    The attack itself, although strong, but unstable. This means that a user who owns his private key can theoretically calculate that k2 is generated in a nonrandom fashion. For this, we introduce j, u to diversify the possible values ​​in case of checking by an alert user. They can be made different from 0 and 1, then there will be even more options. True, brute force will take longer. In fact, you don’t have to worry much, all the same, most likely the availability of the bookmark will be found out only after the fact when the code is sorted by bones.

    I added the working code of this attack to the RSA attack code. I don’t see the reasons why there would no longer exist, or the Trojans for bitcoins implementing this technique would not appear. Yes, trojans can immediately send the private key (and burn on the first firewall), or they can not send anything at all - the attacker will quietly wait until serious amounts appear on the spent wallets.

    Also popular now: