Bad signatures leading to 55.82152538 BTC theft (so far)

[dice64]

Hilariously this is how the encryption on the ps3 was broken.

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.

[gmaxwell]

Chosen by fair dice roll, guaranteed to be random.

[physalis]

Hilariously this is how the encryption on the ps3 was broken.

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?

[smolen]

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

[BurtW]

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

[piotr_n]

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.

[bigbeninlondon]

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

[piotr_n]

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.

[bigbeninlondon]

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?

[minorman]

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?

[piotr_n]

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.

[bigbeninlondon]

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?

[pand70]

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.

[piotr_n]

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.

[smolen]

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?

[smolen]

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

[BurtW]

From:

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

[smolen]

The culprit is either the random number generator passed in (if param instanceof ParametersWithRandom) or java.security.SecureRandom, which I would not totally discount as this would be the implementation for the android phone specifically.

Can someone fire debugger, put breakpoint on line with getRandom() and give the code test run?

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.

Yes and IMHO the best way to find out is to debug the code

[Luke-Jr]

This seems like a serious problem!

Apologies if I am asking a question with an obvious answer, but is there a way a user can easily check to see if the same random number was used for a second transaction before broadcasting it?

It's not much of a problem if you're using Bitcoin correctly (ie, not reusing addresses).

That can't possibly be your proposed solution to this problem - "Just never use a bitcoin address more than once"?

No, not the solution.
Just pointing out that this isn't a serious problem, just a problem that's pretty important to address.
On the other hand, if whatever's causing k to be the same is also causing the private keys generated to be weak, that of course definitely would be a very serious problem...

While it makes sense for privacy reasons, it shouldn't need to be done just so you don't get your coins stolen.

Address reuse has never been just a privacy issue.
Even with correctly chosen k values, there are still theoretical coin-stealing risks to address reuse.
And even ignoring coin-stealing risks and privacy issues, there are still other problems from address reuse (that slip my mind at the moment).

Hmm... so none of the clients mentioned re-use an address for change (as this is not something the end-user generally has any control over)?

If a client is reusing addresses like this, it reveals a fundamental misunderstanding of how Bitcoin works.
Then the question I'd be asking myself is, do I want to trust this author got k correct, or doesn't have other subtle problems in their implementation?

[piuk]

Please see this announcement on the issue http://bitcoin.org/en/alert/2013-08-11-android

An update was made to the blockchain.info app yesterday (v 3.52) to fix the problem for newly generated private keys. If you are a user of the blockchain.info android app you can either login through the web interface and send any coins to a new address or update to the latest android app and send all coins to a newly generated address. Alternately please wait for another update will be issued shortly to automatically rekey all android wallets however more testing is needed.