Entropy during private key generation

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