Bitcoin Forum

Bitcoin => Development & Technical Discussion => Topic started by: BurtW on August 10, 2013, 10:53:13 PM



Title: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: BurtW on August 10, 2013, 10:53:13 PM
I have only seen this discussed in the newbies section so I thought I would open a thread here for a more technical discussion of this issue.

Several people have reported their BTC stolen and sent to https://blockchain.info/address/1HKywxiL4JziqXrzLKhmB6a74ma6kxbSDj

As you can see the address currently contains 55.82152538 stolen coins.

It has been noticed that the coins are all transferred in a few hours after a client improperly signs a transaction by reusing the same random number.  As discussed here:

http://en.wikipedia.org/wiki/Elliptic_Curve_DSA

the reuse of the same k value allows anyone to be able to recover the private key.

It appears that this is what may be happening.

It appears that the bug occurs in both the blockchain.info android wallet and the Andreas Schildbach Android Wallet so I suspect a bug in a crypto library or an implementation detail shared by both applications.

This has been discussed in this thread https://bitcointalk.org/index.php?topic=251743.0 with the more technical posts being these two:

https://bitcointalk.org/index.php?topic=251743.msg2890179#msg2890179
https://bitcointalk.org/index.php?topic=251743.msg2890736#msg2890736

Check out the two transactions posted here (which did lead to a theft of 0.9184236 BTC in this transaction https://blockchain.info/tx/211c135e58dc55bcce4c71dc02eae2dffc5a55387c29e8144bf1cd1e8878e52e)

@Xeno-Genesis

For you the bad transactions were
https://blockchain.info/tx/b6350f4339a59faf09bfc2a4086c2261598f46f257517ce53785145c964799bc
https://blockchain.info/tx/38fbb8a3ff718dd7c8006feb6aa9ed6add1772522781b0db95abb350a859220b

which use the same R-value in the signature.  It is strange that the same random number was generated in two transactions that are four days apart.  This doesn't fit the usual pattern. Which bitcoin client do you use?

The stealing transaction occured less then five hours after the transaction that reused the R-value.




Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: smolen on August 10, 2013, 11:47:04 PM
It has been noticed that the coins are all transferred in a few hours after a client improperly signs a transaction by reusing the same random number.  As discussed here  http://en.wikipedia.org/wiki/Elliptic_Curve_DSA the reuse of the same k value allows anyone to be able to recover the private key.
How long would it take to pool owners to start scanning mempool transactions and replace vulnerable ones?


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: TierNolan on August 11, 2013, 02:16:10 AM
How long would it take to pool owners to start scanning mempool transactions and replace vulnerable ones?

You mean they should crack the private key for the address and then re-do the signature?  That seems only semi-legal.

It may not even fix the problem, all nodes receive all transactions directly.  It would make it slightly harder, the node would have to be always online, rather than only having to scan the block chain every hour or so.


Title: ::sigh::
Post by: gmaxwell on August 11, 2013, 02:26:33 AM
Of course, if these applications didn't constantly reuse addresses the exposure here— whatever the root cause ultimately turns out to be— would be a lot smaller.


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: chriswilmer on August 11, 2013, 04:11:45 AM
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?


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: Luke-Jr on August 11, 2013, 05:40:08 AM
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).


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: gmaxwell on August 11, 2013, 05:48:21 AM
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?
No, no easy way to do that.  Plus the software to actually help you do that would be more complicated than the software required to make super-sure that this can't happen.  (e.g. select the nonce as sha256(message||privkey||random value) — though if your RNG is bad you also need to worry about weak keys))


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: chriswilmer on August 11, 2013, 05:49:09 AM
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?
No, no easy way to do that.  Plus the software to actually help you do that would be more complicated than the software required to make super-sure that this can't happen.  (e.g. select the nonce as sha256(message||privkey||random value) — though if your RNG is bad you also need to worry about weak keys))


Thanks!


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: piotr_n on August 11, 2013, 11:49:08 AM
the reuse of the same k value allows anyone to be able to recover the private key.

It appears that this is what may be happening.

It appears that the bug occurs in both the blockchain.info android wallet and the Andreas Schildbach Android Wallet so I suspect a bug in a crypto library or an implementation detail shared by both applications.
Ouch...

Thanks for the info - I spent the whole morning triple checking if my wallet would not make a similar mistake, by a chance.
Seems that I'm fine, but you got me scared, sir :)


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: dice64 on August 11, 2013, 12:17:18 PM
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


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: physalis on August 11, 2013, 12:29:22 PM
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"?
While it makes sense for privacy reasons, it shouldn't need to be done just so you don't get your coins stolen.

If for example I give someone a bitcoin address so he can make recurring payments of some sort to me, I need to reuse that address. Everything else would just be a major pain in the ass.


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: piotr_n on August 11, 2013, 12:33:26 PM
Yeah. The thesis that reusing an address is not "using Bitcoin correctly", is kind of weird, to say the least. Especially said as a solution for a guy who plays SatoshiDice... :)


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: dice64 on August 11, 2013, 12:47:11 PM
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"?
While it makes sense for privacy reasons, it shouldn't need to be done just so you don't get your coins stolen.

If for example I give someone a bitcoin address so he can make recurring payments of some sort to me, I need to reuse that address. Everything else would just be a major pain in the ass.

You can get every transaction which has been sent by that address and ensure none of its spent outputs have the same signature in the script. But the main problem is random number generation.

Even if you want to make recurring payments, you should still generate an address each time. Otherwise you seriously risk linking your address to your identity. It isn't a pain in the ass, its the best practice for anonymity, regardless of this current bad signature issue.


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: smolen on August 11, 2013, 12:48:49 PM
How long would it take to pool owners to start scanning mempool transactions and replace vulnerable ones?
You mean they should crack the private key for the address and then re-do the signature?  That seems only semi-legal.
Accidentally disclosing private key by using flawed software is the same as accidentally publishing private key on this forum. The key holder effectively waives his right to bitcoins by disclosing the key.


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: piotr_n on August 11, 2013, 12:52:35 PM
If one has a screwed up RNG, not reusing addresses does not make him anyhow safer, if the same generator is used to make new private keys.


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: CIYAM on August 11, 2013, 12:53:29 PM
It's not much of a problem if you're using Bitcoin correctly (ie, not reusing addresses).

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)?


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: smolen on August 11, 2013, 12:54:32 PM
The thesis that reusing an address is not "using Bitcoin correctly", is kind of weird, to say the least.
I'll just repost relevant part of my post from another forum

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.

CURVE    the elliptic curve field and equation used
G    elliptic curve base point, a generator of the elliptic curve with large prime order n
n    integer order of G, means that n * G = O

    Calculate e = \textrm{HASH}(m), where HASH is a cryptographic hash function, such as SHA-1.
    Let z be the L_n leftmost bits of e, where L_n is the bit length of the group order n.
    Select a random integer k from [1, n-1]. - This is what counts
    Calculate the curve point (x_1, y_1) = k * G.
    Calculate r = x_1 \pmod{n}. If r = 0, go back to step 3.
    Calculate s = k^{-1}(z + r d_A) \pmod{n}. If s = 0, go back to step 3.
    The signature is the pair (r, s).
And every (r, s) pair derived from the same dA and exposed to the public means more food for hyperlinearization and SAT-solvers. (Some day those two beasts will meet together and produce fertile offspring :))


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: piotr_n on August 11, 2013, 12:57:12 PM
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?


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: smolen on August 11, 2013, 01:21:23 PM
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 :)


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: BurtW on August 11, 2013, 01:22:13 PM
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.


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: dice64 on August 11, 2013, 01:40:13 PM
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.


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: gmaxwell on August 11, 2013, 01:43:38 PM
Chosen by fair dice roll, guaranteed to be random.


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: physalis on August 11, 2013, 02:08:37 PM
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?


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: smolen on August 11, 2013, 02:15:31 PM
https://github.com/blockchain/My-Wallet-Android/blob/master/bitcoinj-0.8/src/com/google/bitcoin/core/ECKey.java (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


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: BurtW on August 11, 2013, 02:18:53 PM
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


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: piotr_n on August 11, 2013, 02:36:20 PM
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 (http://grepcode.com/file/repo1.maven.org/maven2/com.madgag/scprov-jdk15/1.46.99.2-UNOFFICIAL-ROBERTO-RELEASE/org/spongycastle/crypto/signers/ECDSASigner.java#ECDSASigner.generateSignature%28byte%5B%5D%29)

.... and then it uses SecureRandom class (http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/security/SecureRandom.java#SecureRandom), that goes into engineNextBytes (http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/security/SecureRandomSpi.java#SecureRandomSpi.engineNextBytes%28byte%5B%5D%29), which source code I cannot find.


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: bigbeninlondon on August 11, 2013, 03:00:09 PM
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


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: piotr_n on August 11, 2013, 03:01:57 PM
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.


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: bigbeninlondon on August 11, 2013, 03:03:49 PM
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?


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: minorman on August 11, 2013, 03:04:38 PM
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?



Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: piotr_n on August 11, 2013, 03:06:26 PM
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.


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: bigbeninlondon on August 11, 2013, 03:11:59 PM
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?


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: pand70 on August 11, 2013, 03:16:01 PM
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.


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: piotr_n on August 11, 2013, 03:16:31 PM
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.


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: smolen on August 11, 2013, 03:20:12 PM
https://github.com/blockchain/My-Wallet-Android/blob/master/bitcoinj-0.8/src/com/google/bitcoin/core/ECKey.java (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 (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 (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 (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 (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 (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?


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: smolen on August 11, 2013, 03:32:02 PM
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 :)


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: BurtW on August 11, 2013, 03:45:47 PM
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


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: smolen on August 11, 2013, 03:58:18 PM
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


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: Luke-Jr on August 11, 2013, 04:20:02 PM
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?


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: piuk on August 11, 2013, 04:20:46 PM
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.


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: BurtW on August 11, 2013, 04:21:02 PM
Just some references:

http://developer.android.com/reference/java/security/SecureRandom.html
http://www.cs.cmu.edu/~srini/15-446/android/android-sdk-linux_x86-1.0_r2/docs/reference/java/security/SecureRandom.html

Can someone run the following on the phone?

sr = SecureRandom()
String sr.getAlgorithm()
String sr.getProvider().getName()

and let us know what you find so we know where to look next.
 



Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: Mike Hearn on August 11, 2013, 04:24:38 PM
Hello,

A few days ago user Xeno-Genesis alerted us to some weaknesses in the default Android SecureRandom implementation. You guys are on the right lines - SecureRandom isn't. More technical details will come in the following days. For now, please see the following announcement:

http://bitcoin.org/en/alert/2013-08-11-android



Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: bigbeninlondon on August 11, 2013, 04:25:01 PM
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.

Revealing a key for an address that you should already assume is compromised doesn't sound like a serious issue.  More serious is letting coins sit in an address you should already assume is compromised.


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: smolen on August 11, 2013, 04:26:46 PM
Even with correctly chosen k values, there are still theoretical coin-stealing risks to address reuse.
I saw an odd hint in one of http://en.wikipedia.org/wiki/Nicolas_Courtois (http://en.wikipedia.org/wiki/Nicolas_Courtois) publications that some very novel approach is being developed in this area. For me that's enough to start worry.


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: BurtW on August 11, 2013, 04:28:13 PM
Quote
Android Security Vulnerability
11 August 2013
We recently learned that a component of Android responsible for generating secure random numbers contains critical weaknesses, that render all Android wallets generated to date vulnerable to theft. Because the problem lies with Android itself, this problem will affect you if you have a wallet generated by any Android app. An incomplete list would be Bitcoin Wallet, blockchain.info wallet, BitcoinSpinner and Mycelium Wallet.

In order to re-secure existing wallets, key rotation is necessary. This involves generating a new address with a repaired random number generator and then sending all the money in your wallet back to yourself. If you use an Android wallet then we strongly recommended you upgrade to the latest version available in the Play Store as soon as one becomes available. Once your wallet is rotated, you will need to contact anyone who has stored addresses generated by your phone and give them a new one.

If you use Bitcoin Wallet by Andreas Schildbach, key rotation will occur automatically soon after you upgrade. The old addresses will be marked as insecure in your address book. You will need to make a fresh backup.

Updates for other wallet apps should be released shortly.
Can you tell us which secure random number generator has the problem and also what exactly is meant by the "repaired random number generator".  Are you installing a new secure random number generator provider?


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: Remember remember the 5th of November on August 11, 2013, 04:29:38 PM
I don't think my application is affected https://bitcointalk.org/index.php?topic=101612 as it uses OpenSSL 1.01e internally, so it should be safe I think. However if it is some Linux API that is responsible, then it might be affected too.


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: piotr_n on August 11, 2013, 04:32:46 PM
Hello,

A few days ago user Xeno-Genesis alerted us to some weaknesses in the default Android SecureRandom implementation. You guys are on the right lines - SecureRandom isn't. More technical details will come in the following days. For now, please see the following announcement:

http://bitcoin.org/en/alert/2013-08-11-android
So Google screwed up.

Can you at least disclose if this is version specific, or is it any Android version that is affected?


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: smolen on August 11, 2013, 04:35:59 PM
Are affected phones based on Qualcomm chipset?


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: Mike Hearn on August 11, 2013, 04:42:10 PM
Anything that uses SecureRandom has issues. Yes, we are using a new provider that overrides the old one:

https://code.google.com/p/bitcoin-wallet/source/detail?r=04d2044880d88107ee4a939a516fb4be4cedeaf9&name=bitcoinj-0.10#

You should not assume that using OpenSSL directly is safe. On Jellybean+ the SecureRandom provider is just a shim over the OpenSSL RAND_* functions and Jellybean+ is also affected. However TLS connections are OK.

I realise there's going to be a lot of questions about what exactly is going on here, but I'm not on the Android team and can't talk on their behalf. It's up to them to document exactly how the RNG is broken. Suffice it to say, if you aren't sure if you're affected, you probably are but you are welcome to send me a private message detailing what you're doing and I'll let you know.

Note that reading from /dev/urandom is OK. The kernel level RNG is not broken.


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: jl2012 on August 11, 2013, 04:54:26 PM
If we can't fully trust the random number provided by the system, I wonder if this would help:

Let Xn, for n = 1, 2, 3, ........ be a sequence of random numbers that being used as k for signature

Let Yn, for n = 1, 2, 3, ........ be a sequence of random numbers generated by the system.

X1 = Y1

Xn = SHA256(SHA256(Xn-1)+Yn), for n > 1

Which means when the first random number is generated by the system, we record its SHA256 hash. The hash will be used as a nonce for the next random random

Therefore, even if Yn is constant, Xn is still a pseudo-random number guaranteed by SHA256.


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: Mike Hearn on August 11, 2013, 05:07:08 PM
For what it's worth more modern elliptic curve DSA schemes don't use a random number during signing, exactly to try and avoid this kind of problem (though in our case the keys are weak too - crypto can't really survive a weak RNG). As a result signatures are deterministic. I'm not sure if ECDSA with secp256k1 like we use can be upgraded to use such a scheme - if it could be, that's worth doing.


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: piotr_n on August 11, 2013, 05:13:02 PM
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 :)
Well, after all, considering what we have just learned, that not only the random K value, but also private keys are affected by the broken RNG - moving the coins ASAP to a properly generated address might be a less risky step, indeed. :)


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: Andreas Schildbach on August 11, 2013, 05:17:00 PM
In case you missed it: I put up beta versions of Bitcoin Wallet with a fixed RNG and key-rotation.

https://bitcointalk.org/index.php?topic=271846.0


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: JoelKatz on August 11, 2013, 07:44:05 PM
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?
No, it wouldn't make it actually zero. You have to consider the possibility that the code that checks has a bug in it, fails due to a hardware problem, and so on. If you account correctly, you may find that the added complexity (especially since now you're keeping the old values around instead of getting rid of them) actually increases the chances of a value being reused.


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: bigbeninlondon on August 11, 2013, 08:10:26 PM
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?
No, it wouldn't make it actually zero. You have to consider the possibility that the code that checks has a bug in it, fails due to a hardware problem, and so on. If you account correctly, you may find that the added complexity (especially since now you're keeping the old values around instead of getting rid of them) actually increases the chances of a value being reused.

Fine, you never hit "actually zero" if you always must assume the possibility of your code having bugs in it.  But assuming you code properly, a collision from a random number generator having probability X becomes probability 0 if you iterate until you get a unique number for an address based on historical usage.  Additionally, this approach places less trust in delivered libraries, which is obviously (according to the topic of this discussion) a good approach.  

K must be unique per address per transaction and random.  It is known that most math libraries use PSEUDO-RANDOM generators.  So random is not always guaranteed.  But you CAN guarantee through code that K is unique per address per transaction, even if you cannot guarantee randomness.


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: smolen on August 11, 2013, 08:26:40 PM
a collision from a random number generator having probability X becomes probability 0 if you iterate until you get a unique number
and random number generator becomes random permutation generator


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: JoelKatz on August 11, 2013, 10:01:03 PM
Fine, you never hit "actually zero" if you always must assume the possibility of your code having bugs in it.  But assuming you code properly, a collision from a random number generator having probability X becomes probability 0 if you iterate until you get a unique number for an address based on historical usage.
No, because hardware is not perfect. Keeping the old values around increases the chance that a hardware failure will cause you to use one of them. You have a probability that is so absurdly small on one side that you can't ignore probabilities on the other side just on the grounds that they are very small. If you get to assume the code is proper, why don't I get to assume that a properly-code RNG won't produce collisions?

Quote
Additionally, this approach places less trust in delivered libraries, which is obviously (according to the topic of this discussion) a good approach.
That's a completely different issue. I agree that it might make sense to do this to protect against a broken RNG even while it makes no sense to do this to prevent the absurdly improbable collisions from a working RNG.




Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: molecular on August 11, 2013, 10:07:10 PM
Just some references:

http://developer.android.com/reference/java/security/SecureRandom.html
http://www.cs.cmu.edu/~srini/15-446/android/android-sdk-linux_x86-1.0_r2/docs/reference/java/security/SecureRandom.html

Can someone run the following on the phone?

sr = SecureRandom()
String sr.getAlgorithm()
String sr.getProvider().getName()

and let us know what you find so we know where to look next.
 

found the info that android uses apache harmony implementation:

BTW: The Android implementation is the one from Apache Harmony project. The main implementation is in the file org.apache.harmony.security.provider.crypto.SHA1PRNG_SecureRandomImpl.

EDIT: this might be the implementation (not sure, though): https://android.googlesource.com/platform/libcore-snapshot/+/ics-mr1/luni/src/main/java/org/apache/harmony/security/provider/crypto/SHA1PRNG_SecureRandomImpl.java


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: gmaxwell on August 11, 2013, 11:02:19 PM
A forum newbie emailed me and suggested this link would be informative for the thread: http://www.scribd.com/doc/131955288/Randomly-Failed-The-State-of-Randomness-in-Current-Java-Implementations



Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: Andreas Schildbach on August 11, 2013, 11:24:30 PM
A forum newbie emailed me and suggested this link would be informative for the thread: http://www.scribd.com/doc/131955288/Randomly-Failed-The-State-of-Randomness-in-Current-Java-Implementations

Yes, that's the document that started it all... and it was published >5 months ago.


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: bigbeninlondon on August 12, 2013, 12:19:20 AM
Fine, you never hit "actually zero" if you always must assume the possibility of your code having bugs in it.  But assuming you code properly, a collision from a random number generator having probability X becomes probability 0 if you iterate until you get a unique number for an address based on historical usage.
No, because hardware is not perfect. Keeping the old values around increases the chance that a hardware failure will cause you to use one of them.

Yea, ok, I can see that.  

You have a probability that is so absurdly small on one side that you can't ignore probabilities on the other side just on the grounds that they are very small.

True; for a working package.

If you get to assume the code is proper, why don't I get to assume that a properly-code RNG won't produce collisions?

No, I'm not saying to assume your own code is proper.  My point was that you limit trust in third parties.  Your own code should be verified as well, but you can limit trust on code that you didn't write.

Additionally, this approach places less trust in delivered libraries, which is obviously (according to the topic of this discussion) a good approach.
That's a completely different issue. I agree that it might make sense to do this to protect against a broken RNG

This was my primary point.

Edit: I see that I switched them in my original post.  This one should have come first.

even while it makes no sense to do this to prevent the absurdly improbable collisions from a working RNG.

This was a secondary point that adds value (even if small).



Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: Kyle91 on August 12, 2013, 12:44:16 AM
55...... Holy shit


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: Valle on August 12, 2013, 06:21:00 AM
That paper says that without /dev/random devices (what is a very rare case I believe) SecureRandom use only 31 bits of entropy. It is a horrible situation, but even in this case it is very unlikely that there will be two equal random numbers in signature creation in the whole world.


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: piotr_n on August 12, 2013, 07:27:54 AM
A forum newbie emailed me and suggested this link would be informative for the thread: http://www.scribd.com/doc/131955288/Randomly-Failed-The-State-of-Randomness-in-Current-Java-Implementations

Yes, that's the document that started it all... and it was published >5 months ago.
Unbelievable :)


That paper says that [...] SecureRandom use only 31 bits of entropy. It is a horrible situation, but even in this case it is very unlikely that there will be two equal random numbers in signature creation in the whole world.
Maybe. But having only 31 bits of entropy it's very easy to brute force anything. And we have actually seen two equal random numbers cases - many of such pairs are in the block chain, so it's somehow likely after all.


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: P_Shep on August 12, 2013, 12:48:51 PM
I have to say, I'm somewhat disappointed in the devs not checking to ensure that the random number generator they use, actually works properly and assuming it's all OK, given they know how important the randomness is.


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: piotr_n on August 12, 2013, 12:51:33 PM
I have to say, I'm somewhat disappointed in the devs not checking to ensure that the random number generator they use, actually works properly and assuming it's all OK, given they know how important the randomness is.
Only human.
But I guess that gave all of us a very good lesson.


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: bitpop on August 12, 2013, 01:10:50 PM
I say they add even more entropy. Why not have us swipe around the screen a bit during a transaction?


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: P_Shep on August 12, 2013, 01:29:13 PM
I say they add even more entropy. Why not have us swipe around the screen a bit during a transaction?

I think If I were coding this up, I'd add another layer of entropy on top of the system generated number, just to be sure.
A phone's got to have any number of entropy sources... touch screen, signal levels, compass, g-sensor, time, location, light level...


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: molecular on August 12, 2013, 01:49:23 PM
I say they add even more entropy. Why not have us swipe around the screen a bit during a transaction?

I think If I were coding this up, I'd add another layer of entropy on top of the system generated number, just to be sure.
A phone's got to have any number of entropy sources... touch screen, signal levels, compass, g-sensor, time, location, light level...

Such code would clearly belong into the RNG itself. Doesn't sound good to me to try to add more entropy on the application side. Better approach is to make sure the underlying RNG is secure.

This is not (necessarily) the app developers responsibility.

Problem for the app developer is that RNG is usually "native" in the sense that it's provided by OS/java runtime/(js implementation) as probably should be (better access to hardware). In java you can't even be sure which native implementation is chosen and as an app developer you'd have to check them for all target platforms somehow. On linux for example you also can't be sure what's hiding behind /dev/urandom.

If we were playing "pointing fingers", I'd probably point at google or apache in this case, but not Jan, Andreas,...


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: bitpop on August 12, 2013, 01:53:30 PM
Of course no one is blaming the developers


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: TierNolan on August 12, 2013, 01:54:34 PM
I have to say, I'm somewhat disappointed in the devs not checking to ensure that the random number generator they use, actually works properly and assuming it's all OK, given they know how important the randomness is.

It is pretty much the opposite.  Creating your own cryptographic code is highly risky.

The recommendation is to trust the "professionals".

Having said that, adding extra randomness to a RNG can never make things worse.  Ofc, the devs may break that too, but that is less likely.  Most of the complexity is getting the randomness in the first place.

The SecureRandom class even has a method to do that.

secureRandom.setSeed(long seed) (http://docs.oracle.com/javase/6/docs/api/java/security/SecureRandom.html#setSeed(long)).

Calling this method can never make things worse.

Well, except in one case (see risk :) ).

You have to call .nextInt() (or at least to make it generate at least 1 number).

If you don't then it doesn't seed internally.

This code causes the RNG to be seeded only with the given number.

Code:
SecureRandom r = SecureRandom.getInstance(....);

r.setSeed(0x0123456789ABCDEFL);

However, this code causes it to be seeded with its internal seeding system and then have the number as an extra seed.

Code:
SecureRandom r = SecureRandom.getInstance(....);

r.nextInt();

r.setSeed(0x0123456789ABCDEFL);

The 2nd one is always at least as good as the first.


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: P_Shep on August 12, 2013, 01:57:54 PM
Problem for the app developer is that RNG is usually "native" in the sense that it's provided by OS/java runtime/(js implementation) as probably should be (better access to hardware). In java you can't even be sure which native implementation is chosen and as an app developer you'd have to check them for all target platforms somehow. On linux for example you also can't be sure what's hiding behind /dev/urandom.

Which is why the app developer should sprinkle their own magic dust on the numbers, by whatever means.
If the app developer absolutely, positively knows the numbers generated have to be absolutely, positively unique and random, then they should not rely on that which they can't control or fully understand/know. It's an assumption to far for something that is so crucial.


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: Abdussamad on August 12, 2013, 02:40:44 PM
This is called a leaky abstraction:

http://www.joelonsoftware.com/articles/LeakyAbstractions.html


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: Valle on August 12, 2013, 03:11:09 PM
Okay, but what android device doesn't have /dev/random?


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: Mike Hearn on August 12, 2013, 06:05:07 PM
It's actually quite hard to detect if a RNG is working properly. That's one reason there are occasional failures like this. If it were trivial to write a unit test for an RNG I doubt there'd ever be failures. The problem is bad randomness looks almost the same as good randomness.


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: Remember remember the 5th of November on August 12, 2013, 06:25:05 PM
I have to say, I'm somewhat disappointed in the devs not checking to ensure that the random number generator they use, actually works properly and assuming it's all OK, given they know how important the randomness is.
Right, because the -Qt devs ensured their PRNG was working well.


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: xenog on August 12, 2013, 09:09:01 PM
It's reasonable to expect that the RNG will work fine. You entrust cryptography to cryptography experts. It's an abstraction that usually works well, and if you mess with it even for bening purposes, you may end up breaking it.

See what happened to OpenSSH in Debian a few years ago for an example on why usually writing your own crypto or even messing with existing crypto code is a bad idea.


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: gmaxwell on August 12, 2013, 10:14:44 PM
I have to say, I'm somewhat disappointed in the devs not checking to ensure that the random number generator they use, actually works properly and assuming it's all OK, given they know how important the randomness is.
Right, because the -Qt devs ensured their PRNG was working well.
I'm not sure if you're being snarky here or what. But I personally, and several other people (e.g. I'm aware of jrmithdobbs testing it pretty extensively too) have checked the RNG used in the reference code.  It's really easy to break (EC)DSA with a bad RNG at runtime and that makes me paranoid (e.g. my minor contribution to a netbsd security advisory (http://ftp://ftp.netbsd.org/pub/NetBSD/security/advisories/NetBSD-SA2013-003.txt.asc)).  That isn't to say that any particular flaw might not have gone unnoticed, especially a racy, platform specific, or library version specific issue— go link bitcoind/qt against some some novely broken openssl and all bets are off.

Without knowing all the details here it's hard to do retrospective analysis with the benefit of hindsight to say if something could better have been done here with the android wallets.  The one point I'm aware of is that I think back in January we had some evidence that some bitcoinj users may have had poor nonce entropy, but I think this was chalked up to old bad android. Perhaps in hindsight more exploration should have been done of that issue, or more proactive monitoring of the amount of R reuse.


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: sebastian on August 13, 2013, 04:44:46 AM
But if nonce is selected as "sha256(message||privkey||random value)", you actually don't need a random value.
You can use a simple static 256 bit counter. That would gurantee that no value is ever reused.



What i understand, it does not matter if anyone can guess the nonce, the privkey can ONLY be recovered if 2 signatures share the same nonce.

If then, the counter value could even be published in the transaction, so if multiple clients share the same wallet, they still don't generate conflicting nonces. (The client only search backwards until it reach one of its own transactions, increments that counter with +1 and then signs it own transaction.


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: gmaxwell on August 13, 2013, 05:02:33 AM
What i understand, it does not matter if anyone can guess the nonce, the privkey can ONLY be recovered if 2 signatures share the same nonce.
You understand incorrectly. If K is known a single signature can recover the private key.


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: sebastian on August 13, 2013, 05:21:45 AM
gmaxwell: how? I Think I misused the term "nonce" in my previous text, I mean the random value that is used in nonce calculation, that may not be reused.

If nonce is selected as sha256(message||privkey||R), and you can guess R, you would still need the message (known) and the privkey (secret) to compute the privkey?
so it would be a moment 22 for the attacker?

So then, solving for the private key when one msg is signed with sha256(message||privkey||R) and the other is signed with sha256(message||privkey||R+1), would be impossible unless you can break sha256 in a way allowing solving for privkey?


The flaw here was that if 2 R's was equal, you wouldn't need to compute the unknown value, like solving 2 equations with a unknown, but equal solution X.


Or is it something I have missed?


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: gmaxwell on August 13, 2013, 05:46:24 AM
gmaxwell: how? I Think I misused the term "nonce" in my previous text, I mean the random value that is used in nonce calculation, that may not be reused.
So then, solving for the private key when one msg is signed with sha256(message||privkey||R) and the other is signed with sha256(message||privkey||R+1), would be impossible unless you can break sha256 in a way allowing solving for privkey?
Okay, it wasn't clear that you were still assuming the H(message||private||). Technically you can leave the "R" in that out entirely. The deterministic secret K is fine as far as anyone knows. However, it violates FIPS. So would your counter. For some things people care about this.


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: sebastian on August 14, 2013, 12:35:15 AM
The thing that affects is then that if 2 identical transactions are posted, (same amount and same input and output) then you reveal your privkey.

So I Think that its what happened in android here, identical transactions (m1 == m2) + identical privkey (k1 == k2) and bad RNG (R1 == R2) causes system to generate identical nonces. since sha256(m1||k1||R1) == sha256(m2||k2||R2) if m1 == m2, k1 == k2 and R1 == R2.

if R is then a simple counter, it gurantees against bad RNGs.


Maybe a better idea:

Make nonce be: sha256(message||privkey||random||counter), and "counter" is stored locally.
If RNG is bad/frozen/behaving strange/reusing random numbers, then counter will prevent same nonce from be reused, since its incremented for each transaction, and stored locally.

counter does not need to be published or stored centrally, since its extremely unlikely that 2 RNGs in 2 different clients, generate the same random number for the same transaction, even if the RNGs are extremely bad.



Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: gmaxwell on August 14, 2013, 12:47:04 AM
The thing that affects is then that if 2 identical transactions are posted, (same amount and same input and output) then you reveal your privkey.
No you don't.


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: sebastian on August 14, 2013, 12:50:50 AM
gmaxwell:
Then, what causes the privkey to be revealed? (What this thread is about)

What I have understand, is that if the nonce are reused in a ECDSA signature, the privkey can be calculated, given that you know that the 2 nonces are equal, even if the nonce is unknown, since you simply solve a equation to get the privkey?

since nonce = sha256(message||privkey||random), this means, for nonce to be equal in 2 signatures, message must be identical, privkey must be identical, and the random value must be identical.
So when the bad RNG reuses a random value, for a identical transaction, the privkey can be calculated?


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: gmaxwell on August 14, 2013, 01:01:41 AM
gmaxwell:
Then, what causes the privkey to be revealed? (What this thread is about)
What I have understand, is that if the nonce are reused in a ECDSA signature, the privkey can be calculated, given that you know that the 2 nonces are equal, even if the nonce is unknown, since you simply solve a equation to get the privkey?

Two things can happen,  given two distinct messages with the same unknown K you can recover K, or Given K you can recover the private key.  (also, knowing fairly small amounts of K in several signatures can also allow you to recover the key through more complicated techniques)

If the nonce is H(message||secret)  then if you have identical data being signed you will get a completely identical signature and learn nothing (otherwise I could crack any key by just writing another copy of the same transaction down! :P).  If you have non-identical data being signed you will have non identical nonces.


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: sebastian on August 14, 2013, 01:12:45 AM
now I understand fully...

I misintepreted your post in the beginning of the thread, that the CURRENT technology was that nonce was generated as sha256(message||privkey||Random).
And that had been "cracked" due to bad RNGs.


So if I understand your correctly, the developers have did just nonce = Random_value, where Random_value come from a bad RNG?


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: gmaxwell on August 14, 2013, 01:24:39 AM
So if I understand your correctly, the developers have did just nonce = Random_value, where Random_value come from a bad RNG?
Correct! (and this is what is normally described, e.g. FIPS DSA, so the developers can hardly be blamed).

The idea of making the nonce H(message||secret||random) is to just armor against bad RNGs without making K non-random, though it doesn't need to be non-random— it just need to be secret and distinct per message.


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: smolen on August 14, 2013, 01:50:44 AM
Maybe a better idea:
Make nonce be: sha256(message||privkey||random||counter), and "counter" is stored locally.
That's a resonable emergency workaround for broken RNG, but in the long run it will make Bitcoin weaker. Such postprocessing of random value is not fixing RNG (it's work is done when random is generated), it's part of new, modified in ad-hoc way ECDSA algorithm. While the original one is (reasonably) well studies by a lot of researchers, new algorithm will not attract enough research.
Using counter ties together two sign acts that are supposed to be independent.
This new algorithm uses message and privkey twice, if you look at ECDSA as a huge system of boolean equations (OK, such view is a bit crazy :)) adding sha256(message||privkey ...) to established ECDSA brings in more equations than variables, thus making XSL-style attack a bit easier.


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: gmaxwell on August 14, 2013, 02:38:12 AM
thus making XSL-style attack a bit easier.
I look forward to your paper, as I'm sure DJB (http://ed25519.cr.yp.to/ed25519-20110926.pdf) would as well. :P  (Though sure, if you're not going to go all the way to a deterministic signature, might as well use lots of randomness instead of a counter)


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: TiagoTiago on August 14, 2013, 02:47:45 AM
Given the recent NSA leaks, is it possible the flaw was put there on purpose to make it easier for them to spy on people?


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: smolen on August 14, 2013, 03:29:43 AM
thus making XSL-style attack a bit easier.
I look forward to your paper, as I'm sure DJB (http://ed25519.cr.yp.to/ed25519-20110926.pdf) would as well. :P
Blockchain is more attractive target than Hirsch index :)


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: sebastian on August 14, 2013, 05:11:00 AM
TiagoTiago: No. Revealing or breaking ECDSA in bitcoin does not help anything to reveal anyone's identitity, worse, it would make it even harder to track since 2 users of same wallet make it harder to correlate who owns the wallet.
The anonymity lies in that the correlation between the wallet and the user is unknown. The anonymity is NOT dependant of the secrety of the private key.

The only thing that is dependant of the secrety of the private key, is the safety and ownership of the coins. Eg, if the private key leaks, someone can steal your coins, but nobody can reveal your identity.



smolen: Given that SHA256 is fully safe, the resulting number can be seen as a random value itself. Its not possible to solve for anything in SHA256, since SHA256 is essentially a modulus function, and a modulus function has unlimited number of inputs for a given output.
So a such change is safe. And its not possible to get the counter value and correlate transactions, even if the privkey is stolen. Not even if you know the latest counter value (eg if someone's device is stolen) , since the random value is unknown.
And as you know, there is larger problems than correlated transactions, if the private key is stolen.


So lets implement the change Nonce: sha256(message||privkey||random||counter), that would make the system 100% guranteed safe.
That could be part of the bitcoin specification, so all coders that write a bitcoin client automatically do this by "default".


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: TiagoTiago on August 14, 2013, 05:59:34 AM
It doesn't affect anything other than Bitcoin?


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: molecular on August 14, 2013, 06:56:45 AM
It doesn't affect anything other than Bitcoin?

I've been asking myself this question, also.

Also I still don't know exactly what are the circumstances that have to be met by the environment on the phone for the RNG to produce low-entropy (how low?) random numbers.

It seems to me if these circumstances are met, other apps using SecureRandom would be affected also.



Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: TiagoTiago on August 14, 2013, 07:00:11 AM
And wouldn't that expose data encrypted by other apps to similar security issues?


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: kuzetsa on August 14, 2013, 07:31:40 AM
and people keep telling me my brainwallet probably doesn't have enough entropy because a human made up the passphrase... ;-)


Thanks for reminding me...

I'm going to make available a few mirrors of the brain wallet generator I plan to use:

https://www.bitaddress.org/ (https://www.bitaddress.org/)

XKCD recently demonstrated in a charming little coming that getting a few bits of entropy isn't even that hard:

XKCD: password strength (correct horse battery staple) (http://xkcd.com/936/)


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: smolen on August 14, 2013, 12:11:40 PM
The small and subtle difference between
is fully safe
Quote
Its not possible to solve
Quote
such change is safe
Quote
its not possible to get
Quote
100% guranteed safe
and "based on established expert consensus and published research results Bitcoin can be considered reasonably safe for the foreseeable future" can become something like 1,294,195,554 USD :)


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: bitpop on August 14, 2013, 12:21:37 PM
Some say there is no difference between "complete" and "finished".

Judges.. Please explain the difference in a way that is easy to understand.

His response was: When you marry the right woman, you are "complete". If you marry the wrong woman, you are "finished". And, when the right one catches you with the wrong one, you are "completely finished".


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: JoelKatz on August 14, 2013, 07:40:20 PM
And wouldn't that expose data encrypted by other apps to similar security issues?
No. The issue has nothing to do with exposing encrypted data but with signatures exposing private keys.


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: TiagoTiago on August 14, 2013, 11:09:20 PM
And wouldn't that expose data encrypted by other apps to similar security issues?
No. The issue has nothing to do with exposing encrypted data but with signatures exposing private keys.
Encryption isn't weakened when the random number generator is bad like this?


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: JoelKatz on August 15, 2013, 01:30:54 AM
Encryption isn't weakened when the random number generator is bad like this?
It depends on the type of encryption and the exact details of the bug (which, to my knowledge, still haven't been released). Generally, programs on "small" devices tend to use asymmetric encryption as clients and then they really don't have anything to compromise.

I would be surprised if Bitcoin wallets were literally the only programs affected, but I wouldn't expect there to be very many others.


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: bitpop on August 15, 2013, 02:28:54 AM
Thankfully ssl wasn't affected. Hope my encfs isn't either.


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: Jesse James on August 15, 2013, 06:40:46 AM
Google posted an official post-mortem (http://android-developers.blogspot.com/2013/08/some-securerandom-thoughts.html) of the issue with SecureRandom as well as a fix.

However, I'm kinda confused. My read of the OpenSSL code would lead me to believe that it seeds itself [1 (https://github.com/openssl/openssl/blob/master/crypto/rand/md_rand.c#L408)] [2 (https://github.com/openssl/openssl/blob/master/crypto/rand/rand_unix.c#L237)] with at least 32 (https://github.com/openssl/openssl/blob/master/crypto/rand/rand_lcl.h#L115) bytes from /dev/urandom when you neglect to seed it yourself before hitting up RAND_bytes for randomness.

The proposed fix seeds OpenSSL manually from /dev/urandom (or if the OpenSSL-based SecureRandom isn't being used (non-JellyBean), simply serves randomness directly from /dev/urandom).

It's unclear to me how the proposed fix helps unless there is a flaw in OpenSSL's self seeding.  

Their fix does get rid of the Apache Harmony SecureRandom provider ... which, while bad (64 bits of entropy), mathematically could not have been the cause of the repeated signature nonces given their prevalence.

Even more confusing to me is how an OpenSSL self-seeding issue could lead to the particular pattern of repeated signature nonces observed ... in particular the majority of nonce repeats occurred in the context of the same transaction for sequential inputs. E.g. look at this offending transaction (https://blockchain.info/tx/69557597cc443920e9b9dae54283b77109d0087f2ad7b0ed1364afb0992bb191): 5 signatures; the first 2 share the same nonce as do the last two.  This (https://blockchain.info/tx/569af9e1e4d1c6e02b7574ec551d74a2ccaee1f33b4f9b4191a3c5d81aeeb150) transaction exhibits the exact same pattern.  For this bug to be responsible, the PRNG would literally need to spit out the same 32-bytes back to back. I don't see how this could happen with a thread-locked digest-based PRNG with singleton state (like OpenSSL's default (https://github.com/openssl/openssl/blob/master/crypto/rand/md_rand.c)) ... even if it's state was statically initialized.

I'm sure I'm missing something but if there are any other randomness nerds out there ... I'd love to hear your take.


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: Mike Hearn on August 15, 2013, 09:30:24 AM
Suffice it to say, the workarounds used in the bitcoin apps and the one given in the blog post will resolve the issue with OpenSSL. I presume there are reasons why the exact nature of the bug wasn't disclosed but yes, it can cause repeats in the RNG output.


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: Remember remember the 5th of November on August 15, 2013, 12:26:16 PM
Google posted an official post-mortem (http://android-developers.blogspot.com/2013/08/some-securerandom-thoughts.html) of the issue with SecureRandom as well as a fix.

However, I'm kinda confused. My read of the OpenSSL code would lead me to believe that it seeds itself [1 (https://github.com/openssl/openssl/blob/master/crypto/rand/md_rand.c#L408)] [2 (https://github.com/openssl/openssl/blob/master/crypto/rand/rand_unix.c#L237)] with at least 32 (https://github.com/openssl/openssl/blob/master/crypto/rand/rand_lcl.h#L115) bytes from /dev/urandom when you neglect to seed it yourself before hitting up RAND_bytes for randomness.

The proposed fix seeds OpenSSL manually from /dev/urandom (or if the OpenSSL-based SecureRandom isn't being used (non-JellyBean), simply serves randomness directly from /dev/urandom).

It's unclear to me how the proposed fix helps unless there is a flaw in OpenSSL's self seeding.  

Their fix does get rid of the Apache Harmony SecureRandom provider ... which, while bad (64 bits of entropy), mathematically could not have been the cause of the repeated signature nonces given their prevalence.

Even more confusing to me is how an OpenSSL self-seeding issue could lead to the particular pattern of repeated signature nonces observed ... in particular the majority of nonce repeats occurred in the context of the same transaction for sequential inputs. E.g. look at this offending transaction (https://blockchain.info/tx/69557597cc443920e9b9dae54283b77109d0087f2ad7b0ed1364afb0992bb191): 5 signatures; the first 2 share the same nonce as do the last two.  This (https://blockchain.info/tx/569af9e1e4d1c6e02b7574ec551d74a2ccaee1f33b4f9b4191a3c5d81aeeb150) transaction exhibits the exact same pattern.  For this bug to be responsible, the PRNG would literally need to spit out the same 32-bytes back to back. I don't see how this could happen with a thread-locked digest-based PRNG with singleton state (like OpenSSL's default (https://github.com/openssl/openssl/blob/master/crypto/rand/md_rand.c)) ... even if it's state was statically initialized.

I'm sure I'm missing something but if there are any other randomness nerds out there ... I'd love to hear your take.
Darn, looks like my Android application may be affected after all, I am rolling with my own statically linked OpenSSL library 1.01e I think, so it's not being seeded properly?


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: Jesse James on August 15, 2013, 12:34:25 PM
Suffice it to say, the workarounds used in the bitcoin apps and the one given in the blog post will resolve the issue with OpenSSL. I presume there are reasons why the exact nature of the bug wasn't disclosed but yes, it can cause repeats in the RNG output.

Thanks for the clarification.

I initially overlooked how the Google fix overrides the SecureRandom provider for all releases to date including the JellyBean ones.  I was distracted by the logic in applyOpenSSLFix() thinking it was what was responsible for curing SecureRandom ills on JellyBean ... but now I see it's kinda irrelevant in this context since the OpenSSLRandom provider is simply getting kicked to the curb for now.


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: JoelKatz on August 15, 2013, 09:41:48 PM

Is there any link to the actual bug and the actual fix? I see descriptions of the affects of the bug and suggested workarounds, but not the actual bug itself nor the fix itself.


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: grau on August 16, 2013, 11:16:36 AM
And wouldn't that expose data encrypted by other apps to similar security issues?
No. The issue has nothing to do with exposing encrypted data but with signatures exposing private keys.

In contrary, this is a much bigger issue.

The Android PRNG must be extremely weak (say a joke) that this surfaced in the insignificant number of keys android wallets repeatedly used.

Encryption software usually use a key generated with PRNG, so do secure communication protocols. Pass phrases and asymmetric algorithms often only encrypt that pseudo random key. It is the pseudo random key that is really the secret, and is protecting the data.
Knowing the weakness of the PRNG makes brute forcing of encryption feasible since key space in question is reduced to a joke.

Therefore yes, a lot of encrypted data and communication (that was recorded in the past) is potentially affected by this "bug".
We will never know if it was gross negligence or NSA compliant engineering at work.


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: Mike Hearn on August 16, 2013, 01:54:50 PM
The underlying bug was reported by academics, it wasn't discovered internally by Google. So at some point they will publish a paper just like the guys who found the Harmony bugs did, and you will know the exact details.

Suffice it to say the failure was subtle. It isn't something easily found via code inspection. The NSA doesn't need to engage in monkey tricks anyway, they can just go pressure the providers that most people use or hack the endpoints and circumvent encryption entirely.


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: grau on August 16, 2013, 02:04:55 PM
Suffice it to say the failure was subtle. It isn't something easily found via code inspection.
Sounds like a sophisticated backdoor.

The NSA doesn't need to engage in monkey tricks anyway, they can just go pressure the providers that most people use or hack the endpoints and circumvent encryption entirely.
This is the first time you do not embrace encryption as a solution for a problem.


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: grau on August 16, 2013, 02:32:25 PM
It is known that the NSA employs a lot of bright guys, who certainly not only work on breaking code but also on how to prevent strong code in the first place.
A subtly but still seriously flawed PRNG planted into major operating systems could be a masterpiece of their effort.

It does not need complacency of Google to happen, just brilliance and social engineering on the other side.


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: Dougie on August 16, 2013, 03:29:10 PM
Sue google for your losses! Maybe not. Pretty unfortunate really. I guess someone was bound to write a script to look for these transactions.


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: Mike Hearn on August 16, 2013, 03:39:46 PM
Encryption is a useful tool, I wouldn't want to be without it. It's obviously not a silver bullet. The cypherpunks in the 90's thought writing crypto software would bring about a social revolution. 20 years later we can see they were wrong - no social revolution happened and the state is larger and more powerful than ever. We exist in a world where totalitarian surveillance is the norm.

How much worse would things be without strong crypto? Worse, I'm sure, but significantly worse? Unclear.

I'm very skeptical when people claim Bitcoin will bring about a massive social revolution, or that governments can't control it. Satoshi explicitly disavowed such a claim and I agree with him. The US Government can terminate Bitcoin globally, if it so chooses, which is why extensive lobbying is so essential. It really lives or dies at the whims of some congressmen.

As to the Android RNG bug being an NSA plant - this theory doesn't hold water. There are two RNG failures. One, the Harmony bug published in the RSA paper, has been around for a long time but the Harmony authors couldn't have known Google would build a hugely successful OS on top of their work. For the NSA to somehow get a weak RNG into Harmony would mean they own a time machine and we might as well give up right now. The second failure only impacts Jellybean+ because the SecureRandom implementation was replaced with a shim over OpenSSL. It took less than a year for the problem to be found. Heck most phones don't even run Jellybean yet. If that's their grand plan to undermine crypto, then they suck at it.



Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: grau on August 16, 2013, 04:24:20 PM
I'm very skeptical when people claim Bitcoin will bring about a massive social revolution, or that governments can't control it. Satoshi explicitly disavowed such a claim and I agree with him.
Yes, Bitcoin merely redistributes some riches from those who got lazy and trust their lobby to those who are innovative and trust their math.

The US Government can terminate Bitcoin globally, if it so chooses, which is why extensive lobbying is so essential. It really lives or dies at the whims of some congressmen.
I doubt they could achieve more than a few years of setback. I trust that there are congressmen who recognize, that this is a chance of redistributing on Wall Street, and would love to see that happen.

If that's their grand plan to undermine crypto, then they suck at it.
:D Hope you are right.


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: justusranvier on August 16, 2013, 04:52:42 PM
I'm very skeptical when people claim Bitcoin will bring about a massive social revolution, or that governments can't control it. Satoshi explicitly disavowed such a claim and I agree with him. The US Government can terminate Bitcoin globally, if it so chooses, which is why extensive lobbying is so essential. It really lives or dies at the whims of some congressmen.
You've got the correlation/causation backwards. Bitcoin will not cause a social revolution. Bitcoin will be successful as a consequence of an ongoing social revolution.


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: 2112 on August 16, 2013, 09:42:34 PM
If that's their grand plan to undermine crypto, then they suck at it.
:D Hope you are right.
How do you guys know what was the objective? Maybe Android was just an unintended collateral damage?

Wasn't Crypto AG compromised through the similar means?

http://en.wikipedia.org/wiki/Crypto_AG

Personally I wouldn't know.

So I guess the answer lies somewhere in the changelogs for the affected projects.


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: smolen on August 17, 2013, 12:11:19 AM
So I guess the answer lies somewhere in the changelogs for the affected projects.
Hire incompetent manager, let him hire incompetent programmers, wait for suitable defect, withhold testcase from QA lab half globe away from your headquarter, enjoy plausible deniability.


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: molecular on August 17, 2013, 06:34:33 AM
I know this is an extremely rough estimage, but guesstimating from Number of Transactions excl. popular (http://blockchain.info/charts/n-transactions-excluding-popular) we can speculate that roughly 20 kBTC have been moved from android wallets (assuming the spike is just that).

55 / 20k = 0.2% of funds stolen due to the bad RNG... could've been worse. I feel with the people who lost money, of course.


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: piuk on August 17, 2013, 09:58:59 AM
I know this is an extremely rough estimage, but guesstimating from Number of Transactions excl. popular (http://blockchain.info/charts/n-transactions-excluding-popular) we can speculate that roughly 20 kBTC have been moved from android wallets (assuming the spike is just that).

55 / 20k = 0.2% of funds stolen due to the bad RNG... could've been worse. I feel with the people who lost money, of course.

As of today only 51% of users of the Blockchain.info app have upgraded to a patched release, if the pattern is similar with other apps a fair number of wallets might still be vulnerable. But you are right it definitely could have been worse.


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: jl2012 on August 17, 2013, 10:58:25 AM
I know this is an extremely rough estimage, but guesstimating from Number of Transactions excl. popular (http://blockchain.info/charts/n-transactions-excluding-popular) we can speculate that roughly 20 kBTC have been moved from android wallets (assuming the spike is just that).

55 / 20k = 0.2% of funds stolen due to the bad RNG... could've been worse. I feel with the people who lost money, of course.

As of today only 51% of users of the Blockchain.info app have upgraded to a patched release, if the pattern is similar with other apps a fair number of wallets might still be vulnerable. But you are right it definitely could have been worse.

This is easy to figure out since one could simply screen the blockchain for bad signatures.


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: molecular on August 17, 2013, 08:47:42 PM
I know this is an extremely rough estimage, but guesstimating from Number of Transactions excl. popular (http://blockchain.info/charts/n-transactions-excluding-popular) we can speculate that roughly 20 kBTC have been moved from android wallets (assuming the spike is just that).

55 / 20k = 0.2% of funds stolen due to the bad RNG... could've been worse. I feel with the people who lost money, of course.

As of today only 51% of users of the Blockchain.info app have upgraded to a patched release, if the pattern is similar with other apps a fair number of wallets might still be vulnerable. But you are right it definitely could have been worse.

This is easy to figure out since one could simply screen the blockchain for bad signatures.

I don't understand what you mean. Obviously not all signatures made by android wallets are bad.


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: hyperreal on August 18, 2013, 03:00:32 AM
I know this is an extremely rough estimage, but guesstimating from Number of Transactions excl. popular (http://blockchain.info/charts/n-transactions-excluding-popular) we can speculate that roughly 20 kBTC have been moved from android wallets (assuming the spike is just that).

55 / 20k = 0.2% of funds stolen due to the bad RNG... could've been worse. I feel with the people who lost money, of course.

Is there any evidence theft is the cause of the spike, or is this pure speculation? 

Couldn't a spike just as easily been caused by a large number users rotating keys (as would be expected when an updated is pushed out)?

Or, given the volatility of that graph, couldn't it have likely just been noise?


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: molecular on August 18, 2013, 07:49:32 AM
I know this is an extremely rough estimage, but guesstimating from Number of Transactions excl. popular (http://blockchain.info/charts/n-transactions-excluding-popular) we can speculate that roughly 20 kBTC have been moved from android wallets (assuming the spike is just that).

55 / 20k = 0.2% of funds stolen due to the bad RNG... could've been worse. I feel with the people who lost money, of course.

Is there any evidence theft is the cause of the spike, or is this pure speculation? 

Couldn't a spike just as easily been caused by a large number users rotating keys (as would be expected when an updated is pushed out)?

yeah, that's what I tried to say. Spike caused by key rotations.

Or, given the volatility of that graph, couldn't it have likely just been noise?

Yep. At the time I posted it looked more "spikey". It could still be noise or something else of course. But it's pretty clear that people moved their money. Hard to say how much, of course.


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: Jesse James on August 20, 2013, 01:45:40 AM
Check this out: https://bitcointalk.org/index.php?topic=277595.msg2968228#msg2968228 ... I don't think Android was the cause of most of the bad signatures seen recently (despite it's problems).


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: Nubarius on August 20, 2013, 08:55:51 AM
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


This largest value is different from the one mentioned in the wiki (https://en.bitcoin.it/wiki/Private_key), which is  0xFFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFE BAAE DCE6 AF48 A03B BFD2 5E8C D036 4141. The exact number is not very important, but just out of curiosity, which is the right one?


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: jackjack on August 20, 2013, 09:16:41 AM
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


This largest value is different from the one mentioned in the wiki (https://en.bitcoin.it/wiki/Private_key), which is  0xFFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFE BAAE DCE6 AF48 A03B BFD2 5E8C D036 4141. The exact number is not very important, but just out of curiosity, which is the right one?
The latter
What you wrote is n and is the upper limit
p is just the prims number you use when doing EC operations

By the way its not really an upper limit: n+1 is a pretty valid private key, it's just that it's equal to 1 (as n+1 mod n == 1 mod n)


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: Nubarius on August 20, 2013, 09:19:04 AM
^Ah, I see. Thanks!


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: gmaxwell on August 20, 2013, 09:37:51 AM
By the way its not really an upper limit: n+1 is a pretty valid private key, it's just that it's equal to 1 (as n+1 mod n == 1 mod n)
If you generate that way you will end up with keys which are not equiprobable. The difference from uniform is very small, but its a certificational weakness you should avoid.


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: btcdrak on November 09, 2013, 07:59:02 PM
By the way its not really an upper limit: n+1 is a pretty valid private key, it's just that it's equal to 1 (as n+1 mod n == 1 mod n)
If you generate that way you will end up with keys which are not equiprobable. The difference from uniform is very small, but its a certificational weakness you should avoid.

Is the version of securerandom.js used at bitaddress.org safe? https://github.com/pointbiz/bitaddress.org/blob/master/src/securerandom.js


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: Sukrim on November 09, 2013, 08:30:31 PM
Depends mostly upon where your browser gets it's values for Math.random() from I guess. This is quite off-topic however...

The part about Netscape4 is a bit weird, I wonder how often that triggers.


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: molecular on November 09, 2013, 09:47:11 PM
Depends mostly upon where your browser gets it's values for Math.random() from I guess. This is quite off-topic however...

The part about Netscape4 is a bit weird, I wonder how often that triggers.

netscape4 ?

EDIT: sorry, I see. You're talking about the linked code.


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: jl2012 on November 09, 2013, 11:49:24 PM
By the way its not really an upper limit: n+1 is a pretty valid private key, it's just that it's equal to 1 (as n+1 mod n == 1 mod n)
If you generate that way you will end up with keys which are not equiprobable. The difference from uniform is very small, but its a certificational weakness you should avoid.

Is the version of securerandom.js used at bitaddress.org safe? https://github.com/pointbiz/bitaddress.org/blob/master/src/securerandom.js

I personally don't trust any computer generated random number. All my addresses are generated with other methods with 256bit entropy


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: bitpop on November 10, 2013, 12:40:26 AM
Damn I still use Netscape 4


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: BurtW on December 22, 2013, 06:07:36 AM
That paper says that without /dev/random devices (what is a very rare case I believe) SecureRandom use only 31 bits of entropy. It is a horrible situation, but even in this case it is very unlikely that there will be two equal random numbers in signature creation in the whole world.

Given good "enough" secure random number generation the ECDSA used by Bitcoin works.  Bad random numbers, especially repeated numbers, is fatal to the ECDSA used by Bitcoin.

It has been suggested we move to a new ECDSA algorithm that does not use a random nonce.  We should.


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: mokahless on August 31, 2017, 03:51:39 AM
As of August 24th, the funds are on the move. He waited 4 years to try to avoid detection.

https://blockchain.info/address/1HKywxiL4JziqXrzLKhmB6a74ma6kxbSDj


Title: Re: Bad signatures leading to 55.82152538 BTC theft (so far)
Post by: gmaxwell on August 31, 2017, 05:15:05 AM
He waited 4 years to try to avoid detection.
Unless I'm missing something the party moving these coins may not be the thief... he could have sold them or deposited them in an exchange 4 years ago and they're just moving now.