Reused R values again

[johoe]

Strange things happening...
https://blockchain.info/address/1NEBmytquNcVKcQtVbVYCEXg7tNkN12QGK

this address was fine until today. It had 10 outgoing transactions last week but all with good R values.
Today it had a new transaction with bad R value.

AFAIK bc.i has set up an autosweeper for known addresses (and they have the complete list from me).  Also their wallet should forbid sending money to such an address.  At the moment I see no funds in any weak address.

[amaclin]

AFAIK bc.i has set up an autosweeper for known addresses (and they have the complete list from me).  Also their wallet should forbid sending money to such an address.  At the moment I see no funds in any weak address.

Let us make fixes on https://bitcoin.org/en/faq#what-are-the-advantages-of-bitcoin

What are the advantages of Bitcoin?

Payment freedom - It is possible to send and receive any amount of money instantly anywhere in the world at any time. No bank holidays. No borders. No imposed limits. Bitcoin allows its users to be in full control of their money.

Very low fees - Bitcoin payments are currently processed with either no fees or extremely small fees. Users may include fees with transactions to receive priority processing, which results in faster confirmation of transactions by the network. Additionally, merchant processors exist to assist merchants in processing transactions, converting bitcoins to fiat currency and depositing funds directly into merchants' bank accounts daily. As these services are based on Bitcoin, they can be offered for much lower fees than with PayPal or credit card networks.

Fewer risks for merchants - Bitcoin transactions are secure, irreversible, and do not contain customers’ sensitive or personal information. This protects merchants from losses caused by fraud or fraudulent chargebacks, and there is no need for PCI compliance. Merchants can easily expand to new markets where either credit cards are not available or fraud rates are unacceptably high. The net results are lower fees, larger markets, and fewer administrative costs.

Security and control - Bitcoin users are in full control of their transactions; it is impossible for merchants to force unwanted or unnoticed charges as can happen with other payment methods. Bitcoin payments can be made without personal information tied to the transaction. This offers strong protection against identity theft. Bitcoin users can also protect their money with backup and encryption.

Transparent and neutral - All information concerning the Bitcoin money supply itself is readily available on the block chain for anybody to verify and use in real-time. No individual or organization can control or manipulate the Bitcoin protocol because it is cryptographically secure. This allows the core of Bitcoin to be trusted for being completely neutral, transparent and predictable.

[CIYAM]

The issues here are not with the Bitcoin protocol but with blockchain.info's poor quality software.

It would probably have been better that ECDSA sigs didn't rely upon *random* values at all (then none of this mess would have happened).

My guess is we probably have the NSA to thank for *encouraging* the use of such random values (being a great attack vector).

[cr1776]

The issues here are not with the Bitcoin protocol but with blockchain.info's poor quality software.

It would probably have been better that ECDSA sigs didn't rely upon *random* values at all (then none of this mess would have happened).

My guess is we probably have the NSA to thank for *encouraging* the use of such random values (being a great attack vector).

Exactly.  Blockchain.info != bitcoin.

[johoe]

I just noticed that I accidently swiped 7041 Satoshi from an address not related to this incident and sent it to blockchain.info  .

https://blockchain.info/address/127sp9ZQ2y2NbW3p8L37wgkvfRfxceWL64

To the owner of 127sp9ZQ2y2NbW3p8L37wgkvfRfxceWL64:
I still have >.9 BTC that I swiped from one of your other addresses.  You can contact me if you want it back.  Send me a message signed with the address from which I took the BTC, and I try to verify that you didn't just crack the address the same way I did.  And please tell us, which program is producing the weak signatures.

This was an address that I already cracked in October so it is not blockchain.info related.

[lontivero]

@amaclin the problem that I see with all companies providing bitcoin services is that they introduce almost systemic risks in the bitcoin ecosystem. I mean, even when this is not a systemic issue, it is big enough to be an *almost* systemic issue. That is not good, sadly.

[Supercomputing]

... If I understood you correctly, if you seed the RNG with time-stamps from that short period you bump into the transactions which haven't had reused R values, that's how you got this private key?

https://github.com/blockchain/My-Wallet/commit/98d5a7ca59ef04d06ac6aee468634b12975a0f5c

In a nutshell, just poor seeding of the RNG.

Because line 29 was missing from the original source code file (rng.js), the length of the key variable used in the function below ARC4init(key) from prng4.js is always 0. Which means you are left with only 256 possible seeds. Each of the 256 possible seeds produces its own sequence of numbers (which you can assign to some variable, for example k or d, etc) which can be used for secp256k1 point multiplication.

secp256k1: (G=base point, k=ECDSA nonce, d=private key)
point R = k*G (used for ECDSA: k and x-coordinate)
point Q = d*G (public key)

// Initialize arcfour context from key, an array of ints, each from [0..255]
function ARC4init(key) {
  var i, j, t;
  for(i = 0; i < 256; ++i)
    this.S = i;
  j = 0;
  for(i = 0; i < 256; ++i) {
    j = (j + this.S + key[i % key.length]) & 255;
    t = this.S;
    this.S = this.S[j];
    this.S[j] = t;
  }
  this.i = 0;
  this.j = 0;
}

[amaclin]

Because line 29 was missing from the original source code file (rng.js), the length of the key variable used in the function below ARC4init(key) from prng4.js is always 0. Which means you are left with only 256 possible seeds.

I do not understand. Sorry. I do not have expirience with js and different browsers.
What brunch do we use? 'Real Rand' case or Math.random? Why key.length is 0 and how does "% key.length" works? Division by zero?

[johoe]

Because line 29 was missing from the original source code file (rng.js), the length of the key variable used in the function below ARC4init(key) from prng4.js is always 0. Which means you are left with only 256 possible seeds.

I do not understand. Sorry. I do not have expirience with js and different browsers.
What brunch do we use? 'Real Rand' case or Math.random? Why key.length is 0 and how does "% key.length" works? Division by zero?

I solved this by try and error.  But now I get it.  key.length is 0 so "% key.length" returns NaN, which means it accesses the array at NaN, where all the values were written, because the postfix operator ++  returns NaN on undefined and NaN.   Is this correct?

JavaScript has strange semantics.

[amaclin]

I solved this by try and error.  But now I get it.  key.length is 0 so "% key.length" returns NaN, which means it accesses the array at NaN, where all the values were written, because the postfix operator ++  returns NaN on undefined and NaN.   Is this correct?

This is brainfuck.

[itod]

Because line 29 was missing from the original source code file (rng.js), the length of the key variable used in the function below ARC4init(key) from prng4.js is always 0. Which means you are left with only 256 possible seeds.

I do not understand. Sorry. I do not have expirience with js and different browsers.
What brunch do we use? 'Real Rand' case or Math.random? Why key.length is 0 and how does "% key.length" works? Division by zero?

I solved this by try and error.  But now I get it.  key.length is 0 so "% key.length" returns NaN, which means it accesses the array at NaN, where all the values were written, because the postfix operator ++  returns NaN on undefined and NaN.   Is this correct?

JavaScript has strange semantics.

If you don't use this code to generate your list, which code do you use?!? I'm confused, was convinced you've used their exact buggy code.

[Supercomputing]

Because line 29 was missing from the original source code file (rng.js), the length of the key variable used in the function below ARC4init(key) from prng4.js is always 0. Which means you are left with only 256 possible seeds.

I do not understand. Sorry. I do not have expirience with js and different browsers.
What brunch do we use? 'Real Rand' case or Math.random? Why key.length is 0 and how does "% key.length" works? Division by zero?

I solved this by try and error.  But now I get it.  key.length is 0 so "% key.length" returns NaN, which means it accesses the array at NaN, where all the values were written, because the postfix operator ++  returns NaN on undefined and NaN.   Is this correct?

JavaScript has strange semantics.

That's correct. Even though by specification NaN is Not-a-Number, that memory location (key[i % 0]) still holds some unknown value. So when modulo 256 ((key[1 % 0]) & 255) , it should return some number less than 256.

[Billyboy402]

I'm a little confused with all the tech junks that is being talked about here. Can u plz tell me in simple terms that if I use blockchain.info to create an address, download the paper wallet containing the private key and keep it and the password safe, then am I secured ?

I can see gmaxwell was talking about some try-catch which may kill the entropy in the seed. Is that present in blockchain.info as well ?

You better use an offline copy of bitaddress to generate your paper wallet.

https://bitcoinpaperwallet.com
https://www.bitaddress.org

i try this today
20 min download ubuntu and the wallets on 2nd USB , 20 min to add it to a USB , Boot up Ubuntu and print , would take any one less then 1hr from start to finish

[johoe]

I solved this by try and error.  But now I get it.  key.length is 0 so "% key.length" returns NaN, which means it accesses the array at NaN, where all the values were written, because the postfix operator ++  returns NaN on undefined and NaN.   Is this correct?

JavaScript has strange semantics.

If you don't use this code to generate your list, which code do you use?!? I'm confused, was convinced you've used their exact buggy code.

I just extracted the important parts from the javascript file.  I understood from zootreeves's the comment in the github that all this initialization/Math.rand stuff was unimportant as the missing initialization would prevent the rng_pool to be filled properly.  All I had to simulate was the prng (which is more or less the standard rc4 stream cipher).  So I first tried to get the numbers from the prng initialized with zeros.  When this didn't work out (actually I would have found some values using this code, but I only looked for one particular value), I tried variations of this, initializing it with an array of length 1.

I just looked in the stream produced by the prng for one particular k value that I broke earlier and that occurred several times on the block chain.  When this was successful I knew I had the right solution.

There were still some unknowns, e.g., there are two candidates for k.  First, I didn't check the JavaScript code if it really takes the bytes from the stream to build numbers, whether it is big or little-endian and so forth.  When the first try didn't succeed, I read most of the relevant JavaScript code to check my assumptions.  It took some time until I realized that I had to play with the initialization of the prng.

[itod]

I solved this by try and error.  But now I get it.  key.length is 0 so "% key.length" returns NaN, which means it accesses the array at NaN, where all the values were written, because the postfix operator ++  returns NaN on undefined and NaN.   Is this correct?

JavaScript has strange semantics.

If you don't use this code to generate your list, which code do you use?!? I'm confused, was convinced you've used their exact buggy code.

I just extracted the important parts from the javascript file.  I understood from zootreeves's the comment in the github that all this initialization/Math.rand stuff was unimportant as the missing initialization would prevent the rng_pool to be filled properly.  All I had to simulate was the prng (which is more or less the standard rc4 stream cipher).  So I first tried to get the numbers from the prng initialized with zeros.  When this didn't work out (actually I would have found some values using this code, but I only looked for one particular value), I tried variations of this, initializing it with an array of length 1.

I just looked in the stream produced by the prng for one particular k value that I broke earlier and that occurred several times on the block chain.  When this was successful I knew I had the right solution.

There were still some unknowns, e.g., there are two candidates for k.  First, I didn't check the JavaScript code if it really takes the bytes from the stream to build numbers, whether it is big or little-endian and so forth.  When the first try didn't succeed, I read most of the relevant JavaScript code to check my assumptions.  It took some time until I realized that I had to play with the initialization of the prng.

Is this all browser dependable, on how many browser have you tested? Do you get the same k values in all browsers?

[johoe]

I just extracted the important parts from the javascript file.  I understood from zootreeves's the comment in the github that all this initialization/Math.rand stuff was unimportant as the missing initialization would prevent the rng_pool to be filled properly.  All I had to simulate was the prng (which is more or less the standard rc4 stream cipher).  So I first tried to get the numbers from the prng initialized with zeros.  When this didn't work out (actually I would have found some values using this code, but I only looked for one particular value), I tried variations of this, initializing it with an array of length 1.

I just looked in the stream produced by the prng for one particular k value that I broke earlier and that occurred several times on the block chain.  When this was successful I knew I had the right solution.

There were still some unknowns, e.g., there are two candidates for k.  First, I didn't check the JavaScript code if it really takes the bytes from the stream to build numbers, whether it is big or little-endian and so forth.  When the first try didn't succeed, I read most of the relevant JavaScript code to check my assumptions.  It took some time until I realized that I had to play with the initialization of the prng.

Is this all browser dependable, on how many browser have you tested? Do you get the same k values in all browsers?

You misunderstand.  I didn't test it in a browser, I copied the JavaScript code and changed it into a Java program so that it would go through my Java compiler.  But JavaScript is standardized; the particular behavior with NaN and undefined should be handled by all compliant browser in the same way.

The k values are actually computed by my program that breaks keys with reused R values in signatures (also written in Java).  Computing the k value is an important step to get the private key.  It is only possible if R is reused, but I had enough reused R values that I knew at least some of the k values.  And I knew that the k value must haven been produced by the random number generator directly.

That there are two possible k values is because of the way ECDSA works.  They compute the point k*G, and take its x coordinate. This is the r value (Personally, I usually use R to denote k*G but when I say R value in this thread I refer to the x coordinate of R).   There are two points on the curve with the same x coordinate, namely  k*G and -k*G.  So there is no way to know the sign of k.

[CIYAM]

I copied the JavaScript code and changed it into a Java program so that it would go through my Java compiler.

Did you use some special tool to do this (as JavaScript has nothing to do with Java and I am pretty sure trying to change JavaScript into C++ would be no simple task without a very specialised tool so I can't see how changing it into Java would actually be much easier)?

[johoe]

I copied the JavaScript code and changed it into a Java program so that it would go through my Java compiler.

Did you use some special tool to do this (as JavaScript has nothing to do with Java and I am pretty sure trying to change JavaScript into C++ would be no simple task without a very specialised tool so I can't see how changing it into Java would actually be much easier)?

I used emacs The prng code is 30 lines.  It was trivial to resolve the few syntactic differences by hand.

Okay, I hope everybody closed the browser tab with the blockchain.info wallet that he opened 10 days ago. Because now everyone following this topic will implement his own rng cracker.

[CIYAM]

The prng code is 30 lines.  It was trivial to resolve the few syntactic differences by hand.

Hmm... I used to test potential employees with less than 30 lines of C++ that only one out of one hundred understood perfectly so I guess that you must be an extremely good programmer.

[JorgeStolfi]

The prng code is 30 lines.  It was trivial to resolve the few syntactic differences by hand.

Hmm... I used to test potential employees with less than 30 lines of C++ that only one out of one hundred understood perfectly so I guess that you must be an extremely good programmer.

But a C++ program is a C program encrypted with a very strong encryption method.