Cold storage and bad RNG

[zby]

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.

[Remember remember the 5th of November]

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

[hexafraction]

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?

[jonald_fyookball]

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.

 

[justusranvier]

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.

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.

[gmaxwell]

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.

[bcearl]

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

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.

[gmaxwell]

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?

[justusranvier]

If your key creation RNG is bad, of course you don't ever have to spend to lose your funds.

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

[DeathAndTaxes]

If your key creation RNG is bad, of course you don't ever have to spend to lose your funds.

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.

[dserrano5]

…

Welcome back DnT, you've been missed .

[gmaxwell]

If your key creation RNG is bad, of course you don't ever have to spend to lose your funds.

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

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

[newIndia]

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.

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

[zby]

If your key creation RNG is bad, of course you don't ever have to spend to lose your funds.

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

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.

[justusranvier]

this is a deterministic operation there is no RNG involved

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.

[DeathAndTaxes]

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

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

[DeathAndTaxes]

this is a deterministic operation there is no RNG involved

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.

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.

[justusranvier]

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.

[DeathAndTaxes]

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.

[justusranvier]

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