Bitcoin Forum

I wonder if it is something widely known that if you have a bad RNG - then the attacker can empty your cold storage as easy as hot wallets. It is kind of obvious - but when listening to all these talk about 'coins secure in cold storage' I had the feeling that people don't realize this.

Simply throw a coin or dice 160 times and you will have real random number.

Physical coin, that is. I actually had a small logic gate setup that would obtain random bits by pressing a button for an unpredictable interval mod 2 relative to a very fast clock signal, perform von neumann whitening, and report hex digits on a 7-seg display. Assuming my XNOR gates aren't backdoored, this should be a foolproof measure. Or am I mistaken?

show off.

 :P

Only if people are reusing cold storage addresses .

I guess that applies to people using paper wallets, which is another reason those things were bad ideas from the beginning.

If your signing RNG is sufficiently bad your funds can be stolen even if you only ever sign once: If your k some value they've got precomputed in a rainbow table of bad rng outputs they can race you in flight. If your key creation RNG is bad, of course you don't ever have to spend to lose your funds.

Reuse makes it worse-- an RNG with only a couple bits of bias (e.g. using RC4 to generate them) will screw you with enough signatures. And this is indeed a reason "paper wallets" aren't great.  I just wanted to comment to correct the impression that reuse is needed for sufficiently poor rng output to matter. The broken RNG's we've seen (so far!) have mostly been pretty much complete breaks.

128 bits should be enough, you can put them into an PRNG then. You will not get more “security” with a secp256k1 ECDSA key anyway.

This is somewhat misleading.

256-bit ECC is normally described to have 2^128 security. But this is in the limit against insanely expensive attacks.

It's also interesting to consider what the chances are of success against an attacker that only does a small amount of work: An attacker who only performs a small amount of computation would have a success rate that reflects a security level similar to 2^256.

As the attacker does more work, their probability of success increases faster than linearly, until success becomes very likely at around 2^128.  It's worth mentioning that with only somewhat more than 2^128 work an attacker breaks almost all keys, not just one, so a very high work factor attacker needs basically only operation on average per key they break.

It works like this because the discrete log breaking is effectively a collision search. You build a huge table of points along a path, and when you find that you've looped back to where you've been before, you know that the table passed through the value you started on, and so you can just walk through it to find your discrete log.  When your table is small unlikely to find a loop. As it grows sufficiently big almost any point you start with joins into a loop and can be used to break any key fast.

Some attackers are perfectly happy to try negative expectation attacks with a low probability of success just in case-- if you've ever typed a sentence from atlas shrugged into some brainwallet site and checked the address, then maybe you were one of those attackers too, having additional security against them isn't bad, and using full entropy keys can help.   That said, I'm sure you could not feel bad at all about using 256 bits of 'untrustworthy randomness' from the computer and then rolling dice for another 128 bits and summing them.

There may also be other attacks on ECDSA if we know that the key is confined to a particular subspace. I'm not aware of any that would be interesting, especially with the data fed into a PRNG, but having a full 256 bits of 'some' kind of entropy probably costs you nothing, and also protects you against things like finding out that popular hex-dice dice were biased and only really had 48 bits of entropy. So why not?

There are implementations out there getting the initial key creation wrong too, not just signing?

To my knowledge no with the exception of so called "brain wallets".  Humans are amazingly bad at generating entropy and will very often vastly overestimate the amount of entropy in a password or passphrase.  Many brainwallets even those not hacked "yet" are vulnerable to brute force attacks.

Welcome back DnT, you've been missed ;).

Absolutely. The implementation with the wrong signing RNG generating recent discussion was absolutely equally exposed for newly created keys as well.  It's just that the ratio of newly created wallets to signatures from existing ones is low (and perhaps the thefts related to new wallet with bad keys more latent).

It is possible that the recent hack of Bitstamp is due to weak RNG.

I don't quite understand what you mean here. You sign using the key - this is a deterministic operation, there is no RNG involved - the RNG is used to generate the key.

Signing leaks information about the key - so this can aid the attacker - but it is not the only way.

Until very recently, this was not true for any Bitcoin clients.

The common way of performing ECDSA signatures requires 256 bits of new entropy for every signature, and if you get it wrong it's possible to reveal your private key.

It is also possible someone built a quantum computer and used Shor's algorithm to break the private key from the public key.   Both scenarios are possible but improbable.  The easiest way to get a private key is to get the private key.  Gain unauthorized access to the server, copy wallet, transfer coins.

http://en.wikipedia.org/wiki/Occam%27s_razor

Correct.  The security of ECDSA requires that all signatures from the same private key have a unique secret k value.  If the k value is the same for two signatures involving the same private key then with some simple math the private key can be computed from the public key and signature.  The k only has to be unique and secret large number not random but the most common way to get a unique and secret large number is to generate one randomly.

There is a solution which is deterministic signatures (RFC 6979).  It is more widely used than two years ago but it is not universal.  IIRC the reference client still uses random k values.  https://tools.ietf.org/html/rfc6979

The bad news is that RRNG weaknesses can either be accidental or intentional and sometimes nearly impossible to detect.   The good news is that with HD wallets, deterministic signatures, and some manual entropy source (dice, deck of cards, flipping coins, etc) it is possible to create a wallet and a lifetime of transactions which never uses a single bit from a potentially compromised PRNG.

Thanks, NSA.

I'm sure it's been handy for ECDSA to be vulnerable to leaking private keys every time there's a signing event, and also to leak private private keys through variable-time operations.

The flip side is Bitcoin is the anti NSA.  It is like a canary in the coal mine for crypto flaws.  A while back there was a flaw in the PRNG used by the Android OS.  Now this affected a huge number of crypto applications beyond just Bitcoin but to a hacker who discovered this the easiest and most immediate payoff was to steal coins from insecure transactions.  A relatively few Bitcoins were stolen and the OS patched.  It is very likely this was a development error and not an intentional flaw but either way it has now been fixed and everyone (even non Bitcoiners) are safer because of it.

In the absence of a public compromise, the more widely a cryptographic system is used and the more direct the payoff the more assurance I would place in the system over less used systems of similar security.  For that reason I trust the secp256k1 curve more than other ECC curves.  I trust ECDSA a lot more than RSA and I would trust SHA-2 family of hashes more than other hashing algorithms.  The $4B in the Bitcoin network is one giant canary.

As someone who I don't like quoting said, "Bitcoin has become the universal bug bounty."

I did not mean to say that private key was obtained from public key. By weak RNG, I meant the scenario of reused R value (https://bitcointalk.org/index.php?topic=581411.0), which might be the case for Bitstamp. Because, it is now known that multiple people are now scanning the blockchain for this vulnerability.

There is no indication for this on the blockchain.  For the bitstamp incident, there has been no repeated R value on any of the compromised addresses.  I'm pretty sure that this is not the problem here. Even if they used a weak RNG, it is more likely that the attacker hacked the computer storing the private keys than that he hacked the computer storing their private code, analysed their code for weaknesses, found a weak RNG and then broke it.

As for paper wallets.  I always thought that you dispose a paper wallet once you use it to pay from it.  Import the private key and then transfer some money to your hot wallet and the rest to a fresh paper wallet.  This way you have no problems with weak signatures (as long as they are not so weak that you can break them faster than the transaction is confirmed).  Using RFC6979 is still a good idea.

Preventing that the private key of your paper wallet was generated by a bad RNG is another important issue.  And you need some trusted offline computer running a trusted program to generate the paper wallet.  Even using the OS secure random number generator can be problematic: If you boot a well-known Linux image especially if you do this in a virtual machine it may not gather enough entropy (randomness), since the boot process is very deterministic.  A hardware RNG (or just a physical coin or die that you throw often enough) may help here.  Alternatively, let the system run for a while and gather more entropy from keystrokes and mouse movements before generating the keys.

The attack on the OS secure RNG is probably not practical as there is still a lot of randomness that an attacker needs to account for.  However, it would be a bad idea to make a boot image that generates a paper wallet automatically on boot without any user interaction and any hardware rng device (I wouldn't be surprised if such an image already exists).