Hi,% username%!
Are you using informal bitcoin client? There is a reason to look at it more closely.
After the implementation of backdoor for RSA I was wondering how things are going with the rest of cryptographic primitives. It turns out that the whole science called kleptografiyazanimaetsya transmission of information in the so-called "unconscious" channels. Such, which is not known to anybody except the sender and the recipient. Like steganography, just inside the cryptographic algorithms.
In general, a class of attacks on cryptographic algorithms called SETUP (Secretly Embedded Trapdoor with Embedded Protection). That is, there is usually a backdoor and and protection, such that even when it detects a backdoor will not be able to find out what was transmitted. Such attacks decide Prisoner's dilemma.
SETUP may be weak and strong.
Weak SETUP - If you know the generated keys can be known not onlly by attacker, but also by the owner of device, on which was the software compromised .
Accordingly ,Strong SETUP - if you know the key can be only find the attacker.
Another , so called characteristic is Leakage bandwidth, which shows how much sensitive data "flows" with repeated encryption process \ signatures. Denoted by (m, n), which means that the leak of secret messages m / n keys for transmission.
And such attacks exist for almost all public key schemes. DSA, ElGamal, Diffie-Helman, everywhere there is a way to at least one bit so secretly pass. Not always it turns out so beautifully as happened with RSA, but you can find practical application. For example, for ECDSA hold SETUP attack easier, because the key generation parameters (curve, base point, the order of the curve) are known in advance, and the corresponding parameters in the DSA are generated randomly for each key pair.
As we all know, purse Bitcoin - a key pair ECDSA.
Today we look at a strong attack SETUP (1.2) on the ECDSA, that is, an attacker can learn the user's private key for 2 signatures, with it, no one but him can not do it.
To begin with let us recall how simplistic generated signature ECDSA.
We have the private key d - number and public key Q - elliptic curve point equal to dG, where G - the base point of the curve.
For signature random number k, in the range [1, n-1].
Calculated curve point (x1, y1) = k * G
Calculated r = x1 mod N, where N - order curve.
Calculate s = k-1 (H (m) + rd) mod N, where k-1 - the number of inverse modulo N to k. H (m) - hash message to be signed.
The signature is the pair (r, s)
As can be seen, here k is randomly selected. We have to slightly modify the process so that an attacker was able to calculate the user's private key d.
Private and public keys attacker is called v and V = vG.
Step One. The user generates a signature for the first time (sends someone Bitcoins)
Same as in the ordinary signature. Except that we will need to be stored somewhere k. Call it k1Poluchaem pair (r1, s1)
Step Two (send Bitcoins second time)
Calculate the hidden element of Z = a * k1 G + b * k1 V + h * jG + e * uV,
where a, b, h, e <n - fixed integers; j, u ∈ {0, 1} - casual.
a, b, h, e can be generated deterministically, for example using a hash of the message as a seed for the PRNG. This will complicate the detection of bookmarks.
k2 we have not chosen by chance, but is now a hash of Z. Hashem from the point of the curve, we assume a hash of its X coordinate.
Further, as usual, we obtain a pair (r2, s2).
And so, the attacker got pairs (r1, s1) and (r2, s2). How did he get the user's private key?
1) Calculate R1 '= s-1 (H (m1) G + r1Q) = (x1', y1 '). This is what we do when checks the digital signature.
2) Z1 = aR1 '+ b * vR1', where v - the private key attacker
3) For each of the possible values of j, u compute:
Z2 = Z1 + h * jG + e * uV
k2 '= H (Z2)
R2 '= k2'G = (x2', y2 ')
r2 '= x2' mod n
If r2 '= r2, then k2' = k2, we found k, this is what we need
The private key d user = (s2k2 - h (m2)) × r2-1 mod n
As you can imagine, k2, too, can remember and continue to generate k + 1 chain, thus giving the attacker the ability to learn user's private key in any two consecutive signatures.
Nothing supernatural is not here, the attacker only need to pick numbers a, b, h, e, and put them in the backdoor with his public key. Or generate them on the basis of the signed message.
Attack itself, though strong, but unstable. This means that the user who owns his private key, can theoretically calculate that k2 is generated non-random manner. For this and introduced j, u, to diversify the possible values for the case of testing alert the user. They can do other than 0 and 1, then the options will be more. However, brute force and have longer. In fact, you can not worry too much, it is still likely presence bookmark it turns out only after the fact when the code disassemble the bones.
Working code of this attack, I added code to the attack on RSA. I see no reason which would no longer exist, or there would be no Trojans for bitcoin, implementing this technique. Yes, Trojans can immediately send private key (and the bedrooms on the first firewall), but can not send anything at all, and quietly wait for the attacker to zatroyanennyh purses appear serious amount.
Source: habrahabr.ru
TRANSLATION
Are you using informal bitcoin client? There is a reason to look at it more closely.
After the implementation of backdoor for RSA I was wondering how things are going with the rest of cryptographic primitives. It turns out that the whole science called kleptografiyazanimaetsya transmission of information in the so-called "unconscious" channels. Such, which is not known to anybody except the sender and the recipient. Like steganography, just inside the cryptographic algorithms.
In general, a class of attacks on cryptographic algorithms called SETUP (Secretly Embedded Trapdoor with Embedded Protection). That is, there is usually a backdoor and and protection, such that even when it detects a backdoor will not be able to find out what was transmitted. Such attacks decide Prisoner's dilemma.
SETUP may be weak and strong.
Weak SETUP - If you know the generated keys can be known not onlly by attacker, but also by the owner of device, on which was the software compromised .
Accordingly ,Strong SETUP - if you know the key can be only find the attacker.
Another , so called characteristic is Leakage bandwidth, which shows how much sensitive data "flows" with repeated encryption process \ signatures. Denoted by (m, n), which means that the leak of secret messages m / n keys for transmission.
And such attacks exist for almost all public key schemes. DSA, ElGamal, Diffie-Helman, everywhere there is a way to at least one bit so secretly pass. Not always it turns out so beautifully as happened with RSA, but you can find practical application. For example, for ECDSA hold SETUP attack easier, because the key generation parameters (curve, base point, the order of the curve) are known in advance, and the corresponding parameters in the DSA are generated randomly for each key pair.
As we all know, purse Bitcoin - a key pair ECDSA.
Today we look at a strong attack SETUP (1.2) on the ECDSA, that is, an attacker can learn the user's private key for 2 signatures, with it, no one but him can not do it.
To begin with let us recall how simplistic generated signature ECDSA.
We have the private key d - number and public key Q - elliptic curve point equal to dG, where G - the base point of the curve.
For signature random number k, in the range [1, n-1].
Calculated curve point (x1, y1) = k * G
Calculated r = x1 mod N, where N - order curve.
Calculate s = k-1 (H (m) + rd) mod N, where k-1 - the number of inverse modulo N to k. H (m) - hash message to be signed.
The signature is the pair (r, s)
As can be seen, here k is randomly selected. We have to slightly modify the process so that an attacker was able to calculate the user's private key d.
Private and public keys attacker is called v and V = vG.
Step One. The user generates a signature for the first time (sends someone Bitcoins)
Same as in the ordinary signature. Except that we will need to be stored somewhere k. Call it k1Poluchaem pair (r1, s1)
Step Two (send Bitcoins second time)
Calculate the hidden element of Z = a * k1 G + b * k1 V + h * jG + e * uV,
where a, b, h, e <n - fixed integers; j, u ∈ {0, 1} - casual.
a, b, h, e can be generated deterministically, for example using a hash of the message as a seed for the PRNG. This will complicate the detection of bookmarks.
k2 we have not chosen by chance, but is now a hash of Z. Hashem from the point of the curve, we assume a hash of its X coordinate.
Further, as usual, we obtain a pair (r2, s2).
And so, the attacker got pairs (r1, s1) and (r2, s2). How did he get the user's private key?
1) Calculate R1 '= s-1 (H (m1) G + r1Q) = (x1', y1 '). This is what we do when checks the digital signature.
2) Z1 = aR1 '+ b * vR1', where v - the private key attacker
3) For each of the possible values of j, u compute:
Z2 = Z1 + h * jG + e * uV
k2 '= H (Z2)
R2 '= k2'G = (x2', y2 ')
r2 '= x2' mod n
If r2 '= r2, then k2' = k2, we found k, this is what we need
The private key d user = (s2k2 - h (m2)) × r2-1 mod n
As you can imagine, k2, too, can remember and continue to generate k + 1 chain, thus giving the attacker the ability to learn user's private key in any two consecutive signatures.
Nothing supernatural is not here, the attacker only need to pick numbers a, b, h, e, and put them in the backdoor with his public key. Or generate them on the basis of the signed message.
Attack itself, though strong, but unstable. This means that the user who owns his private key, can theoretically calculate that k2 is generated non-random manner. For this and introduced j, u, to diversify the possible values for the case of testing alert the user. They can do other than 0 and 1, then the options will be more. However, brute force and have longer. In fact, you can not worry too much, it is still likely presence bookmark it turns out only after the fact when the code disassemble the bones.
Working code of this attack, I added code to the attack on RSA. I see no reason which would no longer exist, or there would be no Trojans for bitcoin, implementing this technique. Yes, Trojans can immediately send private key (and the bedrooms on the first firewall), but can not send anything at all, and quietly wait for the attacker to zatroyanennyh purses appear serious amount.
Source: habrahabr.ru
TRANSLATION
No comments:
Post a Comment