Pages:
Author

Topic: Bad signatures leading to 55.82152538 BTC theft (so far) - page 6. (Read 65147 times)

legendary
Activity: 2646
Merit: 1137
All paid signature campaigns should be banned.
From:

Quote
if (param instanceof ParametersWithRandom)
            {
                ParametersWithRandom    rParam = (ParametersWithRandom)param;

                this.random = rParam.getRandom();
                this.key = (ECPrivateKeyParameters)rParam.getParameters();
            }
            else
            {
                this.random = new SecureRandom();
                this.key = (ECPrivateKeyParameters)param;
            }
The culprit is either the random number generator passed in (if param instanceof ParametersWithRandom) or java.security.SecureRandom.

EDIT:  from what I can tell (correct me if I am wrong) ECPrivateKeyParameters is not an instance of ParametersWithRandom so that leaves us to go dig into java.security.SecureRandom as implemented on the android phone.

https://github.com/rtyley/spongycastle/blob/spongy-master/sc-light-jdk15on/src/main/java/org/spongycastle/crypto/params/ECPrivateKeyParameters.java
hero member
Activity: 524
Merit: 500
I think the first step for everyone using the apps in question transfer their funds to a new address that hasn't been used before.
Bad idea, IMO.
You can reveal your key at the very moment when transferring out your funds - if someone intercepts your priv-key-compromising tx while routing it, he can try to spend your cons before you.

I'm pretty sure all the compromised keys have already been robbed, so I'd rather advise to wait for the fix, not moving any coins.
Scanning code would be rather trivial, but to use it on the fly one have to be powerful miner or have very well connected bitcoin network nodes. After funds arrive at fresh address they can be considered safe. Sitting funds protected by disclosed keys are up to the first person to grab.
I'm not going to exploit this situation, I'll just sit back and enjoy the chaos Smiley
hero member
Activity: 524
Merit: 500
https://github.com/blockchain/My-Wallet-Android/blob/master/bitcoinj-0.8/src/com/google/bitcoin/core/ECKey.java
Code:
import org.spongycastle.crypto.signers.ECDSASigner;
Code:
    /**
     * Signs the given hash and returns the R and S components as BigIntegers. In the Bitcoin protocol, they are
     * usually encoded using DER format, so you want {@link ECKey#signToDER(Sha256Hash)} instead. However sometimes
     * the independent components can be useful, for instance, if you're doing to do further EC maths on them.
     * @throws IllegalStateException if this ECKey doesn't have a private part.
     */
    public ECDSASignature sign(Sha256Hash input) {
        if (priv == null)
            throw new IllegalStateException("This ECKey does not have the private key necessary for signing.");
        [b]ECDSASigner[/b] signer = new ECDSASigner();
        [b]ECPrivateKeyParameters[b] privKey = new ECPrivateKeyParameters(priv, ecParams);
        [b]signer.init(true, privKey);[/b]
        BigInteger[] sigs = signer.generateSignature(input.getBytes());
        return new ECDSASignature(sigs[0], sigs[1]);
    }

https://github.com/rtyley/spongycastle/blob/spongy-master/sc-light-jdk15on/src/main/java/org/spongycastle/crypto/signers/ECDSASigner.java
Code:
import org.spongycastle.crypto.params.ECPrivateKeyParameters;
public class ECDSASigner
    implements ECConstants, DSA
{
    ECKeyParameters key;

    SecureRandom    random;

    public void init(
        boolean                 forSigning,
        CipherParameters        param)
    {
        if (forSigning)
        {
            [b]if (param instanceof ParametersWithRandom)[/b]
            {
                ParametersWithRandom    rParam = (ParametersWithRandom)param;

                this.random = rParam.getRandom();
                this.key = (ECPrivateKeyParameters)rParam.getParameters();
            }
            else
            {
                this.random = new SecureRandom();
                this.key = (ECPrivateKeyParameters)param;
            }
        }
        else
        {
            this.key = (ECPublicKeyParameters)param;
        }
    }

https://github.com/rtyley/spongycastle/blob/spongy-master/sc-light-jdk15on/src/main/java/org/spongycastle/crypto/params/ECPrivateKeyParameters.java
Code:
public class ECPrivateKeyParameters
    extends ECKeyParameters

https://github.com/rtyley/spongycastle/blob/spongy-master/sc-light-jdk15on/src/main/java/org/spongycastle/crypto/params/ECKeyParameters.java
Code:
public class ECKeyParameters
    extends AsymmetricKeyParameter

https://github.com/rtyley/spongycastle/blob/spongy-master/sc-light-jdk15on/src/main/java/org/spongycastle/crypto/params/AsymmetricKeyParameter.java
Code:
public class AsymmetricKeyParameter
    implements CipherParameters

https://github.com/rtyley/spongycastle/blob/spongy-master/sc-light-jdk15on/src/main/java/org/spongycastle/crypto/CipherParameters.java
Code:
public interface CipherParameters
{
}
Where is ParametersWithRandom?
legendary
Activity: 2053
Merit: 1356
aka tonikt
I think the first step for everyone using the apps in question transfer their funds to a new address that hasn't been used before.
Bad idea, IMO.
You can reveal your key at the very moment when transferring out your funds - if someone intercepts your priv-key-compromising tx while routing it, he can try to spend your cons before you.

I'm pretty sure all the compromised keys have already been robbed, so I'd rather advise to wait for the fix, not moving any coins.
sr. member
Activity: 476
Merit: 250
It is a random number generation issue and how clients are creating (pseudo)random numbers...

If the rng works properly there will never be a problem no matter how many transactions you will ever do with a single address.

In the extreme case of not creating random numbers but instead using a fixed one it takes only 2 signatures and your address can be compromised.

Anyway this thread is about certain bitcoin wallets probably not working as intended.
Don't turn this into a fud about the bitcoin in general.
hero member
Activity: 742
Merit: 500
So -from a practical point of view- how can users use the Bitcoin Wallet/Blockchain.info apps before the (broken RNG?) can be fixed with an upgrade?



I think the first step for everyone using the apps in question transfer their funds to a new address that hasn't been used before.

What apps are affected?
legendary
Activity: 2053
Merit: 1356
aka tonikt
So -from a practical point of view- how can users use the Bitcoin Wallet/Blockchain.info apps before the (broken RNG?) can be fixed with an upgrade?
They definitely should not use any of these wallets, before the issue is analyzed and fixed.

Broken RNG can have all kind of bad consequences.
legendary
Activity: 945
Merit: 1003
So -from a practical point of view- how can users use the Bitcoin Wallet/Blockchain.info apps before the (broken RNG?) can be fixed with an upgrade?

hero member
Activity: 742
Merit: 500
If a wallet were to keep track of the k values per address, could that then mitigate these kinds of issues?
If you have an actually working RNG, the chance of picking up the same 256 bit value for a second time is basically zero.


Sure, but keeping track would make "basically zero" into "actually zero".  And since the wallet has your private keys anyway, adding a small dictionary seems trivial and doesn't add any vulnerability.  What's the downside?
legendary
Activity: 2053
Merit: 1356
aka tonikt
If a wallet were to keep track of the k values per address, could that then mitigate these kinds of issues?
If you have an actually working RNG, the chance of picking up the same 256 bit value for a second time is basically zero.
hero member
Activity: 742
Merit: 500
If a wallet were to keep track of the k values per address, could that then mitigate these kinds of issues?  If you had a list of k values that had been previously used, then when you generated the next transaction you could add a line into the code:

Code:
1    Calculate e = HASH(m), where HASH is a cryptographic hash function, such as SHA-1.
2    Let z be the Ln leftmost bits of e, where Ln is the bit length of the group order n.
3    Select a random integer k from [1, n-1].
*4    If (k, privkey) pair is in kPrivKey dictionary, go to step 4
5    Calculate the curve point (x1, y1) = k * G.
6    Calculate r = x1 (mod n). If r = 0, go back to step 3.
7    Calculate s = k-1(z + r dA) (mod n). If s = 0, go back to step 3.
8    The signature is the pair (r, s).
*9    Insert (k, privkey) into kPrivKey dictionary
legendary
Activity: 2053
Merit: 1356
aka tonikt
I'm not a java expert, but I believe there is probably something going wrong inside:
Code:
k = new BigInteger(nBitLength, random);

link to source code

.... and then it uses SecureRandom class, that goes into engineNextBytes, which source code I cannot find.
legendary
Activity: 2646
Merit: 1137
All paid signature campaigns should be banned.
What is the value range for k?

k must be between 1 and p where:

p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F

    = 2^256 − 2^32 − 2^9 − 2^8 − 2^7 − 2^6 − 2^4 − 1
hero member
Activity: 524
Merit: 500
https://github.com/blockchain/My-Wallet-Android/blob/master/bitcoinj-0.8/src/com/google/bitcoin/core/ECKey.java

Code:
import org.spongycastle.crypto.signers.ECDSASigner;
Code:
    /**
     * Signs the given hash and returns the R and S components as BigIntegers. In the Bitcoin protocol, they are
     * usually encoded using DER format, so you want {@link ECKey#signToDER(Sha256Hash)} instead. However sometimes
     * the independent components can be useful, for instance, if you're doing to do further EC maths on them.
     * @throws IllegalStateException if this ECKey doesn't have a private part.
     */
    public ECDSASignature sign(Sha256Hash input) {
        if (priv == null)
            throw new IllegalStateException("This ECKey does not have the private key necessary for signing.");
        ECDSASigner signer = new ECDSASigner();
        ECPrivateKeyParameters privKey = new ECPrivateKeyParameters(priv, ecParams);
        signer.init(true, privKey);
        BigInteger[] sigs = signer.generateSignature(input.getBytes());
        return new ECDSASignature(sigs[0], sigs[1]);
    }

$ ping spongycastle.org
ping: unknown host spongycastle.org
sr. member
Activity: 392
Merit: 250
Hilariously this is how the encryption on the ps3 was broken.

Quote
In December 2010, a group calling itself fail0verflow announced recovery of the ECDSA private key used by Sony to sign software for the PlayStation 3 game console. However, this attack only worked because Sony did not properly implement the algorithm, because k was static instead of random. As pointed out in the signal generation algorithm, this makes d_A solvable and the entire algorithm useless.[4]
http://en.wikipedia.org/wiki/Elliptic_Curve_DSA#Security

They always used a k value of 4, instead of it being random.
The problem with bitcoin is that since we have a public database storing every transaction, it not only needs to be random, it needs to be unique per address.

How likely is a collision here in general, if we're not dealing with a broken RNG (like it seems to be the case with the android wallets)?
What is the value range for k?
staff
Activity: 4284
Merit: 8808
Chosen by fair dice roll, guaranteed to be random.
jr. member
Activity: 34
Merit: 1
Hilariously this is how the encryption on the ps3 was broken.

Quote
In December 2010, a group calling itself fail0verflow announced recovery of the ECDSA private key used by Sony to sign software for the PlayStation 3 game console. However, this attack only worked because Sony did not properly implement the algorithm, because k was static instead of random. As pointed out in the signal generation algorithm, this makes d_A solvable and the entire algorithm useless.[4]
http://en.wikipedia.org/wiki/Elliptic_Curve_DSA#Security

They always used a k value of 4, instead of it being random.
legendary
Activity: 2646
Merit: 1137
All paid signature campaigns should be banned.
I think we have discussed enough "politics" for now and would like to get back to the actual technical issue.  If I get a chance later today I plan to download the source code for the android wallet and see if I can locate the actual signature code and see what they are doing.

I saw this write up a while ago, seems like there are some web wallets which use poor random number generation for every transaction, or as in this case a hardware wallet.

http://www.nilsschneider.net/2013/01/28/recovering-bitcoin-private-keys.html
Thanks for this write up.  It describes exactly what they are doing.

This is the crux here (cleaned up this a bit):
Quote
    Calculate e = HASH(m), where HASH is a cryptographic hash function, such as SHA-1.
    Let z be the Ln leftmost bits of e, where Ln is the bit length of the group order n.
    Select a random integer k from [1, n-1].
    Calculate the curve point (x1, y1) = k * G.
    Calculate r = x1 (mod n). If r = 0, go back to step 3.
    Calculate s = k-1(z + r dA) (mod n). If s = 0, go back to step 3.
    The signature is the pair (r, s).

The same k will lead to the same x1 coordinate, which will lead to the same r.
hero member
Activity: 524
Merit: 500
Of course - I fully agree with you and thanks for pointing it out.
But still, reusing addresses is one of the basic features of Bitcoin - otherwise our life would be so much more complicated.
Bitcoin would have probably never got adopted, in the fist place, if one could not reuse an address.

Moreover, if this is so crucial for security, deterministic wallets do not seem to be a right way to go forward, do they?
I don't pretend to be an expert here, but looks like Bitcoin itself and deterministic wallets are right now out of reach for SAT-solvers and XSL attacks. We'll be alerted about progress in those areas by new yottahashes in mining difficulty Smiley
legendary
Activity: 2053
Merit: 1356
aka tonikt
Even proper reuse of ECDSA private key makes it less secure. Satoshi did very good work protecting Bitcoin from possible future advances in cryptography - new addresses are created whenever it is appropriate, before first (and, ideally, the last) use public key is secret, only hash of it (address) is exposed to the public. But Satoshi did not forbid intentional address reuse, thus making key reuse possible.
Of course - I fully agree with you and thanks for pointing it out.
But still, reusing addresses is one of the core features of Bitcoin - otherwise our life would be so much more complicated.
Bitcoin would have probably never got adopted, in the fist place, if one could not reuse an address.

Moreover, if this is so crucial for security, deterministic wallets do not seem to be a right way to go forward, do they?
Pages:
Jump to: