Bitcoin Forum
May 28, 2024, 10:04:49 AM *
News: Latest Bitcoin Core release: 27.0 [Torrent]
 
   Home   Help Search Login Register More  
Pages: « 1 [2] 3 4 5 6 7 »  All
  Print  
Author Topic: Bad signatures leading to 55.82152538 BTC theft (so far)  (Read 65076 times)
dice64
Jr. Member
*
Offline Offline

Activity: 34
Merit: 1


View Profile WWW
August 11, 2013, 01:40:13 PM
Merited by ABCbits (1)
 #21

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.
gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 4186
Merit: 8435



View Profile WWW
August 11, 2013, 01:43:38 PM
 #22

Chosen by fair dice roll, guaranteed to be random.
physalis
Sr. Member
****
Offline Offline

Activity: 392
Merit: 250



View Profile
August 11, 2013, 02:08:37 PM
 #23

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?
smolen
Hero Member
*****
Offline Offline

Activity: 524
Merit: 500


View Profile
August 11, 2013, 02:15:31 PM
 #24

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

Of course I gave you bad advice. Good one is way out of your price range.
BurtW (OP)
Legendary
*
Offline Offline

Activity: 2646
Merit: 1136

All paid signature campaigns should be banned.


View Profile WWW
August 11, 2013, 02:18:53 PM
Merited by ABCbits (1)
 #25

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

Our family was terrorized by Homeland Security.  Read all about it here:  http://www.jmwagner.com/ and http://www.burtw.com/  Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!
piotr_n
Legendary
*
Offline Offline

Activity: 2053
Merit: 1354


aka tonikt


View Profile WWW
August 11, 2013, 02:36:20 PM
Last edit: August 11, 2013, 03:00:07 PM by piotr_n
 #26

I'm not a java expert, but I believe there is probably something going wrong inside:
Code:
k = new BigInteger(nBitLength, random);

link to source code

.... and then it uses SecureRandom class, that goes into engineNextBytes, which source code I cannot find.

Check out gocoin - my original project of full bitcoin node & cold wallet written in Go.
PGP fingerprint: AB9E A551 E262 A87A 13BB  9059 1BE7 B545 CDF3 FD0E
bigbeninlondon
Hero Member
*****
Offline Offline

Activity: 742
Merit: 500



View Profile
August 11, 2013, 03:00:09 PM
 #27

If a wallet were to keep track of the k values per address, could that then mitigate these kinds of issues?  If you had a list of k values that had been previously used, then when you generated the next transaction you could add a line into the code:

Code:
1    Calculate e = HASH(m), where HASH is a cryptographic hash function, such as SHA-1.
2    Let z be the Ln leftmost bits of e, where Ln is the bit length of the group order n.
3    Select a random integer k from [1, n-1].
*4    If (k, privkey) pair is in kPrivKey dictionary, go to step 4
5    Calculate the curve point (x1, y1) = k * G.
6    Calculate r = x1 (mod n). If r = 0, go back to step 3.
7    Calculate s = k-1(z + r dA) (mod n). If s = 0, go back to step 3.
8    The signature is the pair (r, s).
*9    Insert (k, privkey) into kPrivKey dictionary
piotr_n
Legendary
*
Offline Offline

Activity: 2053
Merit: 1354


aka tonikt


View Profile WWW
August 11, 2013, 03:01:57 PM
Merited by ABCbits (1)
 #28

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.

Check out gocoin - my original project of full bitcoin node & cold wallet written in Go.
PGP fingerprint: AB9E A551 E262 A87A 13BB  9059 1BE7 B545 CDF3 FD0E
bigbeninlondon
Hero Member
*****
Offline Offline

Activity: 742
Merit: 500



View Profile
August 11, 2013, 03:03:49 PM
 #29

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


Sure, but keeping track would make "basically zero" into "actually zero".  And since the wallet has your private keys anyway, adding a small dictionary seems trivial and doesn't add any vulnerability.  What's the downside?
minorman
Legendary
*
Offline Offline

Activity: 945
Merit: 1003



View Profile
August 11, 2013, 03:04:38 PM
 #30

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?



 ██▄                ██        ▄███████▄        ██                  ██      ▄█████████▄ 
 ████              ██      █                  █      ██                  ██      ██                ██
 ██  ▀█            ██    ▄█                  █▄    ██                  ██    ██                  ██
 ██    █▄          ██    ██                  ██    ██                  ██    ▀█                     
 ██      █▄        ██    ██                  ██    ██                  ██      ██                   
 ██        █▄      ██                                  ██                  ██       ▀████████▄   
 ██          █▄    ██    ██                  ██    ██                  ██                        ██ 
 ██            █▄  ██    ██                  ██    ██                  ██                          ██
 ██              █▄██    ██                  ██    ▀█                  █▀    ▄▄                  █▀
 ██                ███      █                  █        █                  █      ██                ██ 
 ██                  ▀█        ▀███████▀            ▀███████▀         ▀█████████▀   











Nousplatform Youtube     
piotr_n
Legendary
*
Offline Offline

Activity: 2053
Merit: 1354


aka tonikt


View Profile WWW
August 11, 2013, 03:06:26 PM
 #31

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.

Check out gocoin - my original project of full bitcoin node & cold wallet written in Go.
PGP fingerprint: AB9E A551 E262 A87A 13BB  9059 1BE7 B545 CDF3 FD0E
bigbeninlondon
Hero Member
*****
Offline Offline

Activity: 742
Merit: 500



View Profile
August 11, 2013, 03:11:59 PM
 #32

So -from a practical point of view- how can users use the Bitcoin Wallet/Blockchain.info apps before the (broken RNG?) can be fixed with an upgrade?



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

What apps are affected?
pand70
Sr. Member
****
Offline Offline

Activity: 476
Merit: 250



View Profile
August 11, 2013, 03:16:01 PM
 #33

It is a random number generation issue and how clients are creating (pseudo)random numbers...

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

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

Anyway this thread is about certain bitcoin wallets probably not working as intended.
Don't turn this into a fud about the bitcoin in general.

piotr_n
Legendary
*
Offline Offline

Activity: 2053
Merit: 1354


aka tonikt


View Profile WWW
August 11, 2013, 03:16:31 PM
 #34

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.

Check out gocoin - my original project of full bitcoin node & cold wallet written in Go.
PGP fingerprint: AB9E A551 E262 A87A 13BB  9059 1BE7 B545 CDF3 FD0E
smolen
Hero Member
*****
Offline Offline

Activity: 524
Merit: 500


View Profile
August 11, 2013, 03:20:12 PM
 #35

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

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

    SecureRandom    random;

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

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

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

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

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

https://github.com/rtyley/spongycastle/blob/spongy-master/sc-light-jdk15on/src/main/java/org/spongycastle/crypto/CipherParameters.java
Code:
public interface CipherParameters
{
}
Where is ParametersWithRandom?

Of course I gave you bad advice. Good one is way out of your price range.
smolen
Hero Member
*****
Offline Offline

Activity: 524
Merit: 500


View Profile
August 11, 2013, 03:32:02 PM
 #36

I think the first step for everyone using the apps in question transfer their funds to a new address that hasn't been used before.
Bad idea, IMO.
You can reveal your key at the very moment when transferring out your funds - if someone intercepts your priv-key-compromising tx while routing it, he can try to spend your cons before you.

I'm pretty sure all the compromised keys have already been robbed, so I'd rather advise to wait for the fix, not moving any coins.
Scanning code would be rather trivial, but to use it on the fly one have to be powerful miner or have very well connected bitcoin network nodes. After funds arrive at fresh address they can be considered safe. Sitting funds protected by disclosed keys are up to the first person to grab.
I'm not going to exploit this situation, I'll just sit back and enjoy the chaos Smiley

Of course I gave you bad advice. Good one is way out of your price range.
BurtW (OP)
Legendary
*
Offline Offline

Activity: 2646
Merit: 1136

All paid signature campaigns should be banned.


View Profile WWW
August 11, 2013, 03:45:47 PM
Last edit: August 11, 2013, 04:01:34 PM by BurtW
 #37

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

Our family was terrorized by Homeland Security.  Read all about it here:  http://www.jmwagner.com/ and http://www.burtw.com/  Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!
smolen
Hero Member
*****
Offline Offline

Activity: 524
Merit: 500


View Profile
August 11, 2013, 03:58:18 PM
 #38

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

Of course I gave you bad advice. Good one is way out of your price range.
Luke-Jr
Legendary
*
expert
Offline Offline

Activity: 2576
Merit: 1186



View Profile
August 11, 2013, 04:20:02 PM
Merited by ABCbits (2)
 #39

This seems like a serious problem!

Apologies if I am asking a question with an obvious answer, but is there a way a user can easily check to see if the same random number was used for a second transaction before broadcasting it?
It's not much of a problem if you're using Bitcoin correctly (ie, not reusing addresses).
That can't possibly be your proposed solution to this problem - "Just never use a bitcoin address more than once"?
No, not the solution.
Just pointing out that this isn't a serious problem, just a problem that's pretty important to address.
On the other hand, if whatever's causing k to be the same is also causing the private keys generated to be weak, that of course definitely would be a very serious problem...
While it makes sense for privacy reasons, it shouldn't need to be done just so you don't get your coins stolen.
Address reuse has never been just a privacy issue.
Even with correctly chosen k values, there are still theoretical coin-stealing risks to address reuse.
And even ignoring coin-stealing risks and privacy issues, there are still other problems from address reuse (that slip my mind at the moment).

Hmm... so none of the clients mentioned re-use an address for change (as this is not something the end-user generally has any control over)?
If a client is reusing addresses like this, it reveals a fundamental misunderstanding of how Bitcoin works.
Then the question I'd be asking myself is, do I want to trust this author got k correct, or doesn't have other subtle problems in their implementation?

piuk
Hero Member
*****
expert
Offline Offline

Activity: 910
Merit: 1005



View Profile WWW
August 11, 2013, 04:20:46 PM
Merited by ABCbits (1)
 #40

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.

Pages: « 1 [2] 3 4 5 6 7 »  All
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!