Entropy during private key generation

[mollison]

I want to create a bunch of fresh, empty wallets with the standard client. (Why? Having multiple wallets is something I want for security reasons, and this is just a relatively hassle-free way to do it.)

The most convenient way for me to do this is using a Linux live distro, but I'm worried there my not be enough entropy on such a system.

Can I just check /proc/sys/kernel/random/entropy_avail and make sure this number is above 200? (I'm getting this advice from [1]).

In other words, does the client (or the libraries it's using) actually use /dev/urandom, and if so, what is "enough" entropy?

Thanks.

[1] http://major.io/2007/07/01/check-available-entropy-in-linux/

[Dabs]

Dunno about linux, but in general you can boot it, do random stuff (without connecting to the internet), then create several wallets.

You launch bitcoin-qt, let it create a wallet, encrypt it (optional), then shut it down.
rename that wallet.dat to wallet-01.dat or something.
Repeat.
rename the new wallet to wallet-02.dat or something.
Repeat.

You could also use the standard client to just generate lots of addresses by using -keypool 500 or 1000. Then extract those addresses from all the wallets using pywallet.

If you are concerned about entropy, you simply discard the first wallet.

[jackjack]

I believe the client uses openssl to generate random bytes

[Hei_]

I believe the client uses openssl to generate random bytes

yep

[Shevek]

I believe the client uses openssl to generate random bytes

And openssl harvests the entropy from /dev/random

EDIT: I've just remembered that I installed the package haveged to keep a good pool of entropy in /dev/random

[deepceleron]

I believe the client uses openssl to generate random bytes

And openssl harvests the entropy from /dev/random

Or can be enhanced with Entropy Gathering Daemon.

dev/random can have seed data written to it. More data can be fed with a patch: http://www.linuxfromscratch.org/hints/downloads/files/entropy.txt to use hardware sources like sound card or webcam noise.

[Remember remember the 5th of November]

I believe the client uses openssl to generate random bytes

On Windows it creates random bits from a "screenshot" of the screen if I understood it correctly, additionally it also calls CryptGenRandom API for even more random bits.

[kjj]

You might want to buy an entropykey.

Or, a newish Intel CPU with the RDRAND instruction, but that won't feed the entropy pool in linux directly, so you'd need an offline key generator that was written to use it.

[astor]

You might want to buy an entropykey.

Or, a newish Intel CPU with the RDRAND instruction, but that won't feed the entropy pool in linux directly, so you'd need an offline key generator that was written to use it.

Here it is.

https://github.com/bjencks/rngd-rdrand

[mollison]

Nobody has answered my question. Thanks anyway for those who said intelligent things. However, if someone can provide an actual answer, I'd appreciate it.

It's not true that OpenSSL uses /dev/random, or at least, that's a misleading thing to say.

All OpenSSL versions try to use /dev/urandom by default; starting with version 0.9.7, OpenSSL also tries /dev/random if /dev/urandom is not available. [1]

[1] http://www.openssl.org/support/faq.html

So, again, my question is, can someone who knows about the client code confirm that it's ultimately using /dev/urandom?

If so, is making sure /proc/sys/kernel/random/entropy_avail is a high enough number (and what number is "high enough"?) sufficient?

Personally, I think I know the answers to these things, but I'm not certain, so I wanted to see if someone who knows can back me up. I tried looking at the code before I started this thread, but the answer wasn't obvious, and I'd rather avoid sinking hours into reading the code more carefully.

[deepceleron]

You might want to buy an entropykey.

Or, a newish Intel CPU with the RDRAND instruction, but that won't feed the entropy pool in linux directly, so you'd need an offline key generator that was written to use it.

Here it is.

https://github.com/bjencks/rngd-rdrand

And surprise, that's not a hardware true RNG, "sorry about your encryption, we lied": http://software.intel.com/en-us/blogs/2012/11/17/the-difference-between-rdrand-and-rdseed

"RdSeed is to RdRand as /dev/random is to /dev/urandom. It returns 100% entropy (minus epsilon if you're picky)."
...
"In contrast, RDRAND is the output of a 128-bit PRNG (pseudorandom number generator) that is compliant to NIST SP 800-90A. It is intended for applications that simply need high-quality random numbers ."

You'll need a future Intel CPU with the announced RDSEED instruction for a real hardware source (although  non-convergent, as good as flipping an unfair coin), or a 1999-vintage Intel 810 or 840 chipset, for a real hardware RNG from Intel (I've got one of those in my firewall..)

[deepceleron]

So, again, my question is, can someone who knows about the client code confirm that it's ultimately using /dev/urandom?

The ultimate source of random data for keys is OpenSSL's rand_lib.c. This is where the build options will cause the answer to diverge; when you build Bitcoin, the answer is ultimately dependent upon build config options such as OPENSSL_FIPS (use the FIPS140 engine) and platform.

One would need to investigate the gitian-reproducible Bitcoin builds to give an answer about the official binaries; I've read enough OpenSSL code for this answer that I'm not gonna do this...

[mollison]

Thanks.

I'm having a hard time believing that the answer is that non-straightforward. I mean, probably it uses /dev/urandom except in some weird circumstances that can be ruled out given certain basic assumptions (e.g., standard Linux on x86 without any special-purpose entropy-producing hardware). But yeah, this is just my intuition, I can't actually give evidence for this.

I guess one way to find out (for my particular instance) would be to do some kind of tracing of the actual binary I have to see what files it opens. Assuming it does use /dev/urandom, do you have any idea of how much entropy actually needs to be accumulated before creating another wallet?

And I don't suppose there is any easy way to guarantee some other process doesn't suck up the entropy right before bitcoin uses it?

Honestly, it seems like /dev/random would be better for my purposes, since it'll block until it gets enough entropy. I wonder if I can symlink /dev/urandom to /dev/random or something crazy like that.

[Remember remember the 5th of November]

Thanks.

I'm having a hard time believing that the answer is that non-straightforward. I mean, probably it uses /dev/urandom except in some weird circumstances that can be ruled out given certain basic assumptions (e.g., standard Linux on x86 without any special-purpose entropy-producing hardware). But yeah, this is just my intuition, I can't actually give evidence for this.

I guess one way to find out (for my particular instance) would be to do some kind of tracing of the actual binary I have to see what files it opens. Assuming it does use /dev/urandom, do you have any idea of how much entropy actually needs to be accumulated before creating another wallet?

And I don't suppose there is any easy way to guarantee some other process doesn't suck up the entropy right before bitcoin uses it?

Honestly, it seems like /dev/random would be better for my purposes, since it'll block until it gets enough entropy. I wonder if I can symlink /dev/urandom to /dev/random or something crazy like that.

Everything Bitcoin uses is open source, including Bitcoin itself. So I have no idea why you would want to disassemble the binary. I also think the default seeds that OpenSSL uses are MORE than enough for your needs.

[mollison]

Everything Bitcoin uses is open source, including Bitcoin itself. So I have no idea why you would want to disassemble the binary. I also think the default seeds that OpenSSL uses are MORE than enough for your needs.

I didn't say anything about disassembly. Please read what I wrote instead of ignoring it and saying ignorant things and cluttering up the thread.

And I didn't ask for your opinion about OpenSSL, I asked for specific information (which you have ignored).

[grue]

Everything Bitcoin uses is open source, including Bitcoin itself. So I have no idea why you would want to disassemble the binary. I also think the default seeds that OpenSSL uses are MORE than enough for your needs.

I didn't say anything about disassembly. Please read what I wrote instead of ignoring it and saying ignorant things and cluttering up the thread.

And I didn't ask for your opinion about OpenSSL, I asked for specific information (which you have ignored).

that's what you pretty much said:

I guess one way to find out (for my particular instance) would be to do some kind of tracing of the actual binary I have to see what files it opens.

just look at the openssl code.

[deepceleron]

I suppose I should have posted that rand_bytes returns an error if there is insufficient entropy pool, so any answer it returns should be as strongly crypto-random as the first.

[mollison]

just look at the openssl code.

I would rather defer to experts than look at crypto code and trust my own shaky assumptions about which code paths are being executed and under what circumstances.

[mollison]

I suppose I should have posted that rand_getbytes returns an error if there is insufficient entropy pool, so any answer it returns should be as strongly crypto-random as the first.

Thanks. I really appreciate the help. I couldn't find rand_getbytes, grepping through both the bitcoin source and the openssl source, though. Did you misremember the function name, perhaps?

As long as there is some verification (either in bitcoin or whatever part of openssl that bitcoin uses) that there is sufficient entropy before generating the first address in a new wallet, that would definitely put my concerns to rest.

[AlphaWolf]

Your answer will depend on which "Linux live distro" you're using, and on which hardware.  Recent versions of Ubuntu and Fedora will have OpenSSL 1.0.1+.

As of Fedora 18, rngd is started by default.  If it finds a TPM or if the RDRAND and AES-NI* instructions are available on your Ivy Bridge or later CPU, it will use these as entropy sources to feed to the kernel, keeping the entropy pool topped off.  So...  if you're using Fedora 18 on a system with a TPM or Ivy Bridge processor, you probably don't have to worry about it.  Otherwise... seek ye the source code

If you want more help than that... we need to know which distro you're using so we can look over the specific source without worrying about "that might have changed in a later version, or was changed in a patch by X distro".


*Note, I mention the requirement of AES-NI with RDRAND because there are several documented cases where manufacturers have disabled AES-NI in BIOS, which causes rngd to fail at startup if there is no TPM or other hardware RNG.

[Dabs]

Your answer will depend on which "Linux live distro" you're using, and on which hardware.  Recent versions of Ubuntu and Fedora will have OpenSSL 1.0.1+.

As of Fedora 18, rngd is started by default.  If it finds a TPM or if the RDRAND and AES-NI* instructions are available on your Ivy Bridge or later CPU, it will use these as entropy sources to feed to the kernel, keeping the entropy pool topped off.  So...  if you're using Fedora 18 on a system with a TPM or Ivy Bridge processor, you probably don't have to worry about it.  Otherwise... seek ye the source code

If you want more help than that... we need to know which distro you're using so we can look over the specific source without worrying about "that might have changed in a later version, or was changed in a patch by X distro".


*Note, I mention the requirement of AES-NI with RDRAND because there are several documented cases where manufacturers have disabled AES-NI in BIOS, which causes rngd to fail at startup if there is no TPM or other hardware RNG.

Can you list which distros this applies to? How about Mint? (derived from Ubuntu I think.) What kind of processors does this work on? Intel Core i5 ? Or any chip that TrueCrypt will work with hardware AES acceleration I guess?

[AlphaWolf]

Can you list which distros this applies to? How about Mint? (derived from Ubuntu I think.) What kind of processors does this work on? Intel Core i5 ? Or any chip that TrueCrypt will work with hardware AES acceleration I guess?

I have no idea what other distros run rngd by default.  I'm sure it's available in all major distros, so it can always be installed.  I believe the package is rng-tools.

If TrueCrypt reports that AES Acceleration is available, then the AES-NI requirement is fulfilled.  As to whether your processor supports RDRAND, I believe all Ivy Bridge CPUs do.  Quickest way to check your specific hardware would be to boot a recent Linux distro and type:

cat /proc/cpuinfo | grep -i rand

That was from memory, so there could be a mistake.... but if you receive output, you have RDDRAND, and if you don't...  then sorry.

[mollison]

Your answer will depend on which "Linux live distro" you're using, and on which hardware.  Recent versions of Ubuntu and Fedora will have OpenSSL 1.0.1+.

As of Fedora 18, rngd is started by default.  If it finds a TPM or if the RDRAND and AES-NI* instructions are available on your Ivy Bridge or later CPU, it will use these as entropy sources to feed to the kernel, keeping the entropy pool topped off.  So...  if you're using Fedora 18 on a system with a TPM or Ivy Bridge processor, you probably don't have to worry about it.  Otherwise... seek ye the source code

If you want more help than that... we need to know which distro you're using so we can look over the specific source without worrying about "that might have changed in a later version, or was changed in a patch by X distro".

I don't have any special or new hardware (so, no TPM or Ivy Bridge or later CPU). I don't want to reveal exactly my whole software setup. Not that I have _that_ many bitcoins, but revealing exactly which version of what software I'm running seems to be a very poor security practice.

Regardless of exactly what is going on below the covers, shouldn't OpenSSL be pulling either from /dev/random or /dev/urandom? If so, what's going on beneath the covers doesn't matter, because /dev/random blocks where there is insufficient entropy, and with /dev/urandom, I can check and see how much entropy there is. That's exactly why those things are there - so that there is a standard way to make sure you have enough entropy, regardless of exactly what you are doing.

So, frankly, if bitcoin (and ultimately OpenSSL) are not using one of those two mechanisms, I would find that puzzling. And I would be curious to find out (a) why not; and (b) what is the standard procedure for someone who is not an actual OpenSSL developer to make sure their applications are getting enough entropy.

I somewhat suspect that either bitcoin or OpenSSL does make sure there is enough entropy, and the right person who can confirm that just hasn't shown up. If it doesn't, that would be a good feature to have (and arguably a bug to not have it). In other words, IMHO, the standard client should guarantee that the addresses it generates are always good addresses and you can't predict the next private key based on knowing other private keys generated around the same time on the same platform (modulo the phenomenally unlikely chance of having a collision). And I bet it does, it's just not been publicly documented yet (that I have found).

For example, deepceleron stated "rand_getbytes returns an error if there is insufficient entropy pool." That is almost good enough for me, but I wasn't able to find that function in either OpenSSL or bitcoin, and even if I did, I personally would like someone to reassure me that that function (or something equivalent) is actually going to be executed on a standard Linux setup.

Anyway, AlphaWolf, thanks very much for taking the time to help me, and hopefully you, deepceleron, or someone else can further enlighten me.

[Shevek]

The standard bitcoin client jes uses OpenSSL, and all trust about entropy lies on OpenSSL.

But you have other options. If you can access an entropy source and obtain a set of 256 random bits, then you can create your own prov/pub keys (see bitaddress,com) and import them on your wallet (search for pywallet.py)

There are entropy sources over the net, such as random.org and hotbits.com; you can download a lot of random bits from both, hash them and put the hex string in bitaddress.com

[mollison]

But you have other options. If you can access an entropy source and obtain a set of 256 random bits, then you can create your own prov/pub keys (see bitaddress,com) and import them on your wallet (search for pywallet.py)

There are entropy sources over the net, such as random.org and hotbits.com; you can download a lot of random bits from both, hash them and put the hex string in bitaddress.com

Thanks for your feedback, but I'm aware of all that, and it's just not what I'm asking about.

[AlphaWolf]

I don't have any special or new hardware (so, no TPM or Ivy Bridge or later CPU). I don't want to reveal exactly my whole software setup. Not that I have _that_ many bitcoins, but revealing exactly which version of what software I'm running seems to be a very poor security practice.

If your security relies on people not knowing which distro of Linux you're running, I think you need to rethink your security strategy  

Based on Bitcoin v.0.8.1, and OpenSSL 1.0.1, Bitcoin calls EC_KEY_generate_key, which is found in ec_key.c (OpenSSL).  From there on, it depends on how OpenSSL was compiled as to what will happen next.  Presumably FIPS_mode is not enabled... and one way or another it will end up in bn_rand_range (bn_rand.c.), on down through bnrand, and ultimately end up in either RAND_bytes or RAND_pseudo_bytes in rand_lib.c.

Then we get to this little nugget in rand_lib.c:

Code:

const RAND_METHOD *RAND_get_rand_method(void)
	{
	if (!default_RAND_meth)
		{
#ifndef OPENSSL_NO_ENGINE
		ENGINE *e = ENGINE_get_default_RAND();
		if(e)
			{
			default_RAND_meth = ENGINE_get_RAND(e);
			if(!default_RAND_meth)
				{
				ENGINE_finish(e);
				e = NULL;
				}
			}
		if(e)
			funct_ref = e;
		else
#endif
			default_RAND_meth = RAND_SSLeay();
		}
	return default_RAND_meth;
	}

Is there a default engine set?  No idea.
Was OpenSSL compiled with OPENSSL_NO_ENGINE?  No idea.
If OpenSSL heads off into ENGINE_get_RAND on your system, what engines will it find?  No idea.

If it makes it to RAND_SSLeay, this is OpenSSL's internal PRNG.  OpenSSL claims it is a cryptographically strong PRNG suitable for generating keys.  It also claims that on *nix systems this is seeded by /dev/urandom automagically.

The Bitcoin source seems to take for granted that OpenSSL will use /dev/urandom, but it also seeds the PRNG with the CPU performance counter.  You'll see the note about urandom at the bottom of this excerpt (util.cpp):

Code:

void RandAddSeed()
{
    // Seed with CPU performance counter
    int64 nCounter = GetPerformanceCounter();
    RAND_add(&nCounter, sizeof(nCounter), 1.5);
    memset(&nCounter, 0, sizeof(nCounter));
}

void RandAddSeedPerfmon()
{
    RandAddSeed();

    // This can take up to 2 seconds, so only do it every 10 minutes
    static int64 nLastPerfmon;
    if (GetTime() < nLastPerfmon + 10 * 60)
        return;
    nLastPerfmon = GetTime();

#ifdef WIN32
    // Don't need this on Linux, OpenSSL automatically uses /dev/urandom
    // Seed with the entire set of perfmon data

Really, I don't think you can go wrong.  You implicitly trust the Linux kernel developers and the OpenSSL developers when you use their software...  You're going to get one or the other's implementation of a cryptographically strong PRNG.

EDIT:
I should add...  I saw no evidence that OpenSSL checks entropy_avail when reading /dev/urandom.  I wouldn't expect it to anyway -- /dev/urandom is for non-blocking access, and checking entropy_avail just to block and wait for more entropy rather defeats the purpose  

[mollison]

Sorry for my delay in responding. I'm fairly satisfied on this topic, but I'm going to give my final "conclusions" and "findings" for the sake of posterity.

First, there is a simple test to see if bitcoin-qt and openssl are using /dev/urandom or not on a particular machine with pretty high certainty:

Code:

strace -o output bitcoin-qt

On my system (and probably on practically all modern linux desktops), you will find a read of /dev/urandom in that trace, meaning yes, /dev/urandom is being used.

Interestingly enough, man 4 random has some warnings about NOT using /dev/urandom for certain OTHER (non-bitcoin) cryptographic purposes (obviously, the man page predates bitcoin)...

A read from the /dev/urandom device will not block waiting for  more
entropy.   As  a result,  if  there  is not sufficient entropy in the
entropy pool, the returned values are theoretically vulnerable to a
cryptographic attack on the algorithms used  by  the driver.  Knowledge
of how to do this is not available in the current unclassified lit‐
erature, but it is theoretically possible that such an attack may exist.
If this is a concern in your application, use /dev/random instead.

Also:

If you are unsure about whether you should use /dev/random or /dev/urandom,
then probably  you  want to use the latter.  As a general rule, /dev/urandom
should be used for everything except long-lived GPG/SSL/SSH keys.

I checked out gnupg for the sake of comparison, and it's using /dev/random, which is in accordance with the above advice.

So, from someone who knows enough about cryptography to know that I don't know anything about cryptography  , all this is troubling.

However, gmaxwell has repeatedly (on multiple occasions) assured me on IRC that he knows enough about cryptography to know that it's just not something we should be worried about. Even after I specifically brought up the above warnings. For example:

(12:10:30 AM) gmaxwell: Under certain threat models, like the attacker being on
a common multiuser system with you and being able to monitor 99.9% of the
urandom output, then it's potentially interesting.

It would be nice (though probably suboptimal for other reasons) if bitcoin and openssl had opted to take the route that would be obviously safe to people who are not crypto experts, allowing us to avoid this whole conversation altogether, and allowing people like me to not have to think about how much we "trust" the bitcoin and openssl devs on this. Of course, I do trust those people, but I also lock my doors at night, even though I trust that I live in a safe enough place to not need to.

That's not actually a request or complaint; actually relying on /dev/random would (a) almost certainly be an issue to bring up with openssl, not the bitcoin devs; and (b) would have other major downsides.

Anyway, moving on to more practical matters, here is something (below) that other paranoid people like me can actually do about the situation. (Note that simply simlinking /dev/urandom to /dev/random just caused errors for me, and the post-compile checks for openssl failed for me when I tried to change the openssl code   )

I found on my desktop machine, my entropy is often in the low hundreds, which by all accounts is abnormal. I don't know why - perhaps part of it is that I use a very simply window manager, don't have a lot of stuff running, and hardly ever use the mouse. Probably nothing to be worried about, but it's clearly abnormal, so I was a bit worried.

However, when I went to actually generate my offline wallets, I did use the mouse a lot (plus I was using a different distro than normal), and there was plenty of entropy. How do I know? I wrote a program that checks the entropy in a loop and exits with a complaint if it falls below a user-provided threshhold. The program is provided below for anyone who wants it.

#include <stdio.h>
#include <fcntl.h>
#include <stdlib.h>


#define DEFAULT_THRESH 2000

int get_thresh(int argc, char** argv) {
   int thresh = DEFAULT_THRESH;
   if (argc == 2) {
      thresh = atoi(argv[1]);
   }
   return thresh;
}


int get_ent() {
   int fd = open("/proc/sys/kernel/random/entropy_avail",O_RDONLY);
   char *buf = malloc(4);
   read(fd, buf, 4);
   close(fd);
   int num = atoi(buf);
   free(buf);
   return num;
}

int main(int argc, char** argv) {

   int thresh = get_thresh(argc, argv);

   int last = get_ent();
   int new = 0;
   while(1) {
      new = get_ent();
      if (new != last) {
         printf("%d\n", new);
         if (new < thresh) {
            printf("INSUFFICIENT ENTROPY\n");
            exit(1);
         }
      }
      last = new;
   }
   return 0;
}

[proff]

There was a similar thread not long ago, in which the poster initially expressed mistrust in using the PRNGs provided by Linux and MS Windows to generate private keys. As in your case, it turned out that the concern was not some supposed design flaw in the cryptographic PRNG, but rather that it takes time for a freshly-installed system to seed itself with enough initial entropy. One thing you could do is simply to do random things with the mouse and keyboard and wait a while before generating important keys (the OS's estimate of "entropy available" is only a rule of thumb of course, but certainly at the very least that long). Another is to note that on Linux you can write to /dev/random to feed it entropy from an external source, so if you want you can pipe in an image of a lava lamp, radio static, electronic noise from the CPU, etc.

[AlphaWolf]

Sorry for my delay in responding. I'm fairly satisfied on this topic, but I'm going to give my final "conclusions" and "findings" for the sake of posterity.

First, there is a simple test to see if bitcoin-qt and openssl are using /dev/urandom or not on a particular machine with pretty high certainty:

Code:

strace -o output bitcoin-qt

On my system (and probably on practically all modern linux desktops), you will find a read of /dev/urandom in that trace, meaning yes, /dev/urandom is being used.

You're going to see a read to /dev/urandom on a Linux system one way or another.  What that doesn't tell you (unless you really analyze the strace... or attach dbg) is if the read was just to seed OpenSSL's PRNG, or if it was used as the entropy source for the entire key.  I honestly have no idea which of those options is more cryptographically secure.  Just seeding the PRNG with /dev/urandom would mean /dev/urandom would be less likely to run out of entropy so that seems like a plus.  But then you're also seeding one PRNG with another PRNG... that "feels" wrong to me... but I, like you, am no crypto expert.  However, what gmaxwell said makes sense.  When /dev/urandom has run out of entropy, the obvious mode of operation would be to use the last truly random bits to seed the PRNG until more entropy is available.  In order for someone to take advantage of this situation, they'd have to either:

1.  Have access to your machine at the exact same time that it has run out of entropy and that you're generating keys, in order to view the seed with which each key was generated.
or
2.  See a large enough sequence of numbers generated from the same seed with which your keys were generated to enable them to calculate the seed.

#1 is terribly unlikely... and if they can view the seed, they probably already have access to your keys
#2 is equally unlikely.  Unless you're for some reason broadcasting lots of random numbers from /dev/urandom at the same time you're generating keys, the only way they'd see a string of numbers generated from that seed would be to see your private keys.

And just for fun... #3.  Bitcoin keys are generally single-use.  You sign a transaction, then your change is deposited to a new address/key.  What that means is that the keys are not vulnerable to the same type of attacks that long-lived keys might be.  An RSA key used for securing SSL handshakes on a website might be used billions of times, and an attacker can request new data to be encrypted by it any time he wants.  A key that encrypts your harddisk might be used to encrypt terrabytes of data.  A lack of entropy in a key with those types of usages might be vulnerable to some sort of statistical analysis.  A key that gets used once and thrown away (like Bitcoin keys are *supposed* to) just doesn't have the kind of attack surface area that warrants a 100% random guarantee.

I applaud your security consciousness (I wish my clients would think more like this!), but in this case I think the existing implementation is more than "safe enough".  If you're still wary, I think it's a matter of changing 2 lines of openssl's unix_rand.c (I might have the file name wrong) and openssl will always pick /dev/random first

[kjj]

(12:10:30 AM) gmaxwell: Under certain threat models, like the attacker being on
a common multiuser system with you and being able to monitor 99.9% of the
urandom output, then it's potentially interesting.

For those not following along, /dev/urandom uses a cryptographic pseudo-random number generator when the entropy pool is depleted below the ability to satisfy a request with actual entropy.  CPRNGs are very widely used and very safe.

The weakness that gmaxwell is talking about is that since a CPRNG is deterministic (it is an algorithm that runs on a computer), someone observing a sequence of outputs from it could possibly reconstruct an output that they did not observe.  In practice, this isn't a big deal, because if anyone was in a position to observe the stream, you are already well fucked and they can probably just take your keys directly.

Also, note that he says "potentially interesting".  I'm not current on the literature, but I'm not aware of anyone actually reproducing the missing portion of a stream by using this method.  It is theoretically possible though, and maybe someone has actually done it.  Also, people are aware of the problem and take steps to make it harder.*

A genuine entropy source will provide a stream of bits that have absolutely no relationship to any other bits anywhere in the universe.  Someone watching such a stream go by will not in any way be able to recreate the part of it that you take.

In practice, it comes down to paranoia.  I side with paranoia in theory, but with reality in practice.  As in, I prefer my keys to come from sources as close as possible to actually being genuine entropy sources.  But those suck, so I use RDRAND, EGD, and other sources of high quality pseudo-entropy.  On an offline box, the difference should be negligible.

*  A weak system produces output_i from output_i-1.  A strong system produces {output_i,state_i} from hash(state_i-1).  As long as the hash function is cryptographically strong, observing the stream of output_x doesn't give enough information to recreate state or output_y.  Actual cryptographers (which I am not) undoubtedly have schemes even better than this one.

[mollison]

You're going to see a read to /dev/urandom on a Linux system one way or another.

Well, yes, and no. I mean, if you do strace -o output vim (for example), you will not see /dev/urandom. So, what the output I observed is telling me is (a) /dev/urandom is being used (though as you say, exactly how it's used is unclear); (b) /dev/random is not being used (since it doesn't appear in the trace). Of course, we pretty much highly suspected all this from looking at the OpenSSL code. Anyway, this will provide an easier test for people in the future.

I honestly have no idea which of those options is more cryptographically secure.  Just seeding the PRNG with /dev/urandom would mean /dev/urandom would be less likely to run out of entropy so that seems like a plus.  But then you're also seeding one PRNG with another PRNG... that "feels" wrong to me... but I, like you, am no crypto expert.  However, what gmaxwell said makes sense.  When /dev/urandom has run out of entropy, the obvious mode of operation would be to use the last truly random bits to seed the PRNG until more entropy is available.  In order for someone to take advantage of this situation, they'd have to either:

1.  Have access to your machine at the exact same time that it has run out of entropy and that you're generating keys, in order to view the seed with which each key was generated.
or
2.  See a large enough sequence of numbers generated from the same seed with which your keys were generated to enable them to calculate the seed.

#1 is terribly unlikely... and if they can view the seed, they probably already have access to your keys
#2 is equally unlikely.  Unless you're for some reason broadcasting lots of random numbers from /dev/urandom at the same time you're generating keys, the only way they'd see a string of numbers generated from that seed would be to see your private keys.

And just for fun... #3.  Bitcoin keys are generally single-use.  You sign a transaction, then your change is deposited to a new address/key.  What that means is that the keys are not vulnerable to the same type of attacks that long-lived keys might be.  An RSA key used for securing SSL handshakes on a website might be used billions of times, and an attacker can request new data to be encrypted by it any time he wants.  A key that encrypts your harddisk might be used to encrypt terrabytes of data.  A lack of entropy in a key with those types of usages might be vulnerable to some sort of statistical analysis.  A key that gets used once and thrown away (like Bitcoin keys are *supposed* to) just doesn't have the kind of attack surface area that warrants a 100% random guarantee.

Thanks, this is an extremely helpful clarification. Gmaxwell made very similar points in IRC, but it's helpful to see it all laid out in one place. This explains exactly why the warnings in man 4 random about long-lived GPG/SSL/SSH keys do not apply to long-lived Bitcoin keys, which I didn't quite 100% understand as of my last post (otherwise I would have said it).

If you're still wary, I think it's a matter of changing 2 lines of openssl's unix_rand.c (I might have the file name wrong) and openssl will always pick /dev/random first

I tried that, pretty sure I did it "correctly" (in the sense that I made the obvious changes), and the compile was fine, but there are a bunch of post-compile checks, and while a bunch of them passed just fine, eventually I hit one that did not pass. I think the problem had to do with the test blocking on /dev/random (remember, my machine tends to have very low entropy), and I think the blocking somehow triggered an error - perhaps some kind of timeout. I didn't really investigate. If someone bothers to get it working, hopefully they'll share here in this thread.

[mollison]

In practice, it comes down to paranoia.  I side with paranoia in theory, but with reality in practice.  As in, I prefer my keys to come from sources as close as possible to actually being genuine entropy sources.  But those suck, so I use RDRAND, EGD, and other sources of high quality pseudo-entropy.  On an offline box, the difference should be negligible.

First, thanks for a very informative post.

Now, I want to veer off topic just slightly.

From my point of view, when generating offline wallets, the entire system you use is the trusted computing base. So I wanted to minimize downloading third-party software besides (in my case) a linux distro and bitcoin-qt. Which is already, in my opinion, a very large and not-that-trusted "trusted" computing base. In any given distro, there are thousands of packages, so thousands of upstream projects, and tens to hundreds of package maintainers.

Shouldn't we be worried about this? If not now, perhaps in the future? Couldn't, say, a governmental entity invest the resources needed to compromise this kind of system? Then, they could introduce a bug similar to the following real one posted on the EGD site, for example:

egd-0.6 had a major security problem that caused it to only use a tiny fraction of the entropy it gathered. All users should upgrade immediately.

Besides messing with key generation, they could also potentially attack Armory (both on the offline and online clients) to pass information between them. Or they could modify cp such that if you're trying to copy one of several offline wallets to a USB drive, all of them are copied covertly (and then exposed by a malicious cp on the online system).

I'm posting this here because it's in the same vein of paranoia as the rest of this discussion, plus I already have the attention of some smart people and the non-attention of trolls, but perhaps a new thread would be preferable if people have much to say on this besides, "you're crazy" or "go take a look at this prior thread elsewhere".

[Gavin Andresen]

... In any given distro, there are thousands of packages, so thousands of upstream projects, and tens to hundreds of package maintainers.

Shouldn't we be worried about this?

Sure. That's one of the reasons why I'm reluctant to upgrade the distro/dependencies for the deterministic build process, and generally prefer to use older dependencies rather than the "latest and greatest" of everything. But there's a tradeoff between "risk that an Evil Maintainer slipped something in" and "risk that we ship with an upatched bug" -- e.g. we tend to be on the latest version of OpenSSL, but a few releases behind of Qt4.

PS: if you really want to be completely paranoid, you should only run bitcoin on old hardware/OS manufactured before 2009 so you can be sure the  hardware/firmware/OS doesn't have any wallet-stealing circuits/code lurking....