I will answer considering Linux OS, as being one of most popular Unix-like OS (between OSes which have urandom). If you need other OS, please, inform me.
Also I will answer using source code of random.c driver from Linux 3.3.3 Kernel, because it is one of best documentation of /dev/random mechanics. And the other is paper: Analysis of the Linux Random Number Generator, Gutterman
2006, 086.pdf - check pages 4-6 and Figure 2.1 (slides). Then you can check The Linux Pseudorandom Number Generator Revisited, Lacharme 2012, 251.pdf paper. Even wikipedia may be helpful here.
There are several random pools in Linux:
- Primary pool of 512 bytes (128 4-byte words); incoming entropy is added to it;
- Secondary pool of 128 bytes to generate random for
/dev/random
- Urandom pool (or another secondary pool) 128 bytes for
/dev/urandom
Separate entropy counters are maintained for all three pools, but usually the counter of primary pool is mean. The 'available' counter is from primary pool.
When you asks for random data, portion of entropy is extracted from the corresponding secondary pool (using one-way functions involving SHA1), then it is partly added (mixed into) to the pool. Part of extracted data is given to the consumer of random data. Both user and kernel consume entropy, e.g. kernel uses API to random driver for starting processes when ASLR is enabled (it is enabled in most distros). There is interesting example when doing several cat /proc/sys/kernel/random/entropy_avail will stole most entropy, may be this is the your case too, proof at StackOverflow. To monitor entropy_avail you should use some daemon or simple C program which will reread pool several times without process restarting.
When Secondary pool has low entropy, some portion of entropy from Primary pool is extracted (again with using of cryptographic one-way functions), then part of it is remixed back into primary pool and part of it mixed to the consuming pool.
1) How low does entropy have to be for it to be dangerous? If I run cat /proc/sys/kernel/random/entropy_avail i get anything from about 130 to a couple thousand. And it seems to fluctuate quickly.
I would like to consider the entropy_avail as estimation of "how many high-quality random bits may I extract from random source". /dev/random gives only high-quality bits and blocks when there is no entropy left, while /dev/urandom gives bits of any quality. When entropy is high, urandom gives high-quality bits, but when entropy is zero, it gives (probably) cryptographic pseudo-random number sequence (there are better examples of such CSPRNG generators in almost every other popular OS: FreeBsd/OpenBSD,MacOS,MS). But 251.pdf (part 4.3, page 16) says "Consequently, the Linux PRNG without entropy input is assumed to be secure if the internal state is not compromised and if the three pools are initialized by an unknown value."
The maths behind the entropy estimation in Linux is analyzed here (nothing useful for software engineer, just adding and subtracting numbers).
There is source code of /dev/random and /dev/urandom driver: http://lxr.linux.no/linux+v3.3.3/drivers/char/random.c#L261 (you can turn on DEBUG_ENT to see the actual working of the random driver)
/*
* Configuration information
*/
#define INPUT_POOL_WORDS 128
#define OUTPUT_POOL_WORDS 32
#define SEC_XFER_SIZE 512
#define EXTRACT_SIZE 10 --- 10 bytes to be extracted from secondary pools
/*
* The minimum number of bits of entropy before we wake up a read on
* /dev/random. Should be enough to do a significant reseed.
*/
static int random_read_wakeup_thresh = 64;
If the available_entropy is lower than 64 bits, no one will read from /dev/random. So, this is extremely low, and smaller values will block everyone who are reading from /dev/random
/*
* If the entropy count falls under this number of bits, then we
* should wake up processes which are selecting or polling on write
* access to /dev/random.
*/
static int random_write_wakeup_thresh = 128;
If the available_entropy is lower than 128 bits, and there are some good guys who can give us more entropy from userspace, try to ask them to do so. So, even at 128 bits of entropy we are not in best form and willing for getting help.
/*
* When the input pool goes over trickle_thresh, start dropping most
* samples to avoid wasting CPU time and reduce lock contention.
*/
static int trickle_thresh __read_mostly = INPUT_POOL_WORDS * 28;
If there is more than 128*28 = 3584 bits, we are refusing to add all available entropy from external sources (but some "samples" still will be mixed into out primary pool); when there is lot of available entropy, some incoming entropy will be added to secondary pool (but not to urandom pool).
1a) Is an attack feasible at 130, or how low would it have to go (50, 10, 1, 0)? I haven't seen any hard numbers on this. Is the attack just theoretical or how much work would it take to break it in practice?
To carry out effective attack the random driver, I think, attacker should somehow predict state of the primary pool. Check part 2.2 from the http://eprint.iacr.org/2006/086.pdf - Initialization. Primary pool is initially filled on boot of system, and attacker want to predict, how it is initialized (what random sources were used and what was the input data). This may be problem in embedded devices or unattended servers or virtualized servers, which have low number of unpredictable entropy sources. The major sources are: user-generated (keyboard, mice), periphery devices (interrupts, e.g. from network), devices with hard-to-predict response times (hard disk).
Most embedded devices will have no hard disk, low number of periphery devices (and all being standard for the model), no any user sitting in front of booting PC and moving mouse and pressing keys at unpredictable moments of time. Also they may have bad-quality timing resource (entropy data from external source is 32 bits of timestamp and 32 bits of attributes; if you can measure timestamp only according to 32kHz quartz you are in bad situation, much better is to use clock tick counter or modern Intel/AMD CPU, which is 3GHz with some hard-to predict variability).
Embedded devices have standardized setup with standard flash image (usually not updated at whole live time of device), and some devices or Read-only bootable medias (Knoppix, OpenWRT) misimplement saving/restoring of entropy at boot/shutdown. Right implementation is to save 512 bytes from some random to persistent storage at shutdown and feed them back into /dev/random early at boot time (there is also comment here in linux sources: Ensuring unpredictability at system startup; /etc/rc.d/init.d/random script in SysV-era startup systems).
There is fresh overview of some embedded problems and where to search good randomness on them: http://cseweb.ucsd.edu/users/swanson/papers/Oakland2013EarlyEntropy.pdf The conclusion of the work: "Randomness is a fundamental system service. A system
cannot be said to have successfully booted unless it is ready
to provide high-entropy randomness to applications."
I think the most dangerous thing is to generate some keys early after boot on them of in known moments of time on highly embedded device. To hack the keys, hacker is needed to backpredict all entropy sources and to model primary pool state and secondary pool state at the time when key was generated. This task is hard, but sometimes it is easier then attack the key itself. I can't show examples of urandom attacks now, but I think they are exist for some vulnerable installations.
Also I think that debian's edition of openSSL was more fatal than bad random quality: http://www.schneier.com/blog/archives/2008/05/random_number_b.html http://xkcd.com/221/ There were possible only around tens-hundreds thousands of keys for every fixed RSA key size, because urandom input was disabled and the only and best available entropy input for openssl was the process ID, or PID, which is usually limited to 32-65 thousands on linux.
2) Does openssl block until there is sufficient entropy to generate a key? My understanding is that /dev/urandom does not block and is the default, but /dev/random does. I assume /dev/random is not the default for performance/consistency reasons?
openssl will not block (I think, didn't check on modern versions), because there is no clear way to application to detect moment when urandom had too low entropy and switched to almost-fully PRNG mode. There are only several ioctls on /dev/urandom to read avaliable_entropy. openssl only tries to use own PRNG, which is seeded by current time and openssl's pid and data from urandom or from RANDFILE.
http://lxr.linux.no/linux+v3.3.3/drivers/char/random.c#L109
109 * The two other interfaces are two character devices /dev/random and
110 * /dev/urandom. /dev/random is suitable for use when very high
111 * quality randomness is desired (for example, for key generation or
112 * one-time pads), as it will only return a maximum of the number of
113 * bits of randomness (as estimated by the random number generator)
114 * contained in the entropy pool.
115 *
116 * The /dev/urandom device does not have this limit, and will return
117 * as many bytes as are requested. As more and more random bytes are
118 * requested without giving time for the entropy pool to recharge,
119 * this will result in random numbers that are merely cryptographically
120 * strong. For many applications, however, this is acceptable.
So, as says the source of random and urandom, you should not generate long-term keys from urandom, but still can use it to generate sessions keys for doing something not valuable (e.g. session key for SSL to facebook to view some more images with cats).
And when you are asking about openssl key generation, you should define what is the key to be generated. If it is session key for TLS, and you are on server, then using of /dev/random will limit how much clients can connect (there were no so much entropy and /dev/random will block, I think this is one of reasons to use urandom in openSSL).
But when you are generating some 4096-bit RSA key for 20-year SSL certificate, you want to use machine with good sources of external entropy, correct saving/restoring of entropy around reboots and which was used by human for some time.
Actually it is better to generate more valuable keys when true hardware random sources are available (not the Linux LRNG - PRNG), for example some balanced thermal noise measuring scheme (take only the lowest precision bit of Analog-to-digital converter - ADC). There is good hardware random source (thermal noise of loop of invertors with AES of their output) even in modern Intel CPUs (may be in VIA's cpus too, dont' know about AMD or ARM), check the /dev/hwrng device on your servers. Update There are possible flaws in some HW RNG (paper 2013) which are very hard to check, because the flawed random data is encrypted by private key of device maker.
And the only right way of working with high-valuable keys - is to generate them on (inside) certified HSM (Hardware security module) and keep them in full version (full private key) only inside tamper-resistance HSM (try to open such HSM's case, or remove their battery and your private key will evaporate. Funny case is when the key was the most master key of some bank - millions of PIN-codes may be lost in a moment...). Extraction of the private key is allowed only as splitted form - when there are N parts of key distributed around security officers (every part may be encrypted under officer's key) and K of parts are needed to reconstruct original key (e.g. via Shamir's scheme).
The main rule is to estimate the value of the information (e.g. your private photo costs around hundreds-thousands of money; but the SSL certificate of google or facebook costs billions of money), how long the information should be kept secure and how much will be invested to break your information. E.g. It may cost around 100-500 thousands money to setup a rubber-hose cryptanalysis (stealing somebody or something who knows/can access the secret/contains the secret and apply garage wrench/expostulations/soldering iron to get the secret -- soldering iron should be used only to unsolder flash memory chip from flashcard, not to something else), so the HSM and splitted backup of key is the only variant for valuable keys of banks and IT-giants.
2b) Is there a flag or option in openssl where you can choose to use /dev/random instead in case you want to be sure?
There is a hack to force openssl to use data from /dev/random: http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=88728
dd if=/dev/random bs=1 count=1024 of=filename;
export RANDFILE=filename
# use openssl here
(you can verify with strace that openssl actually opened the "filename" to get random and did not open /dev/urandom)
3) On a shared box, is there any way a neighbor could deplete all the randomness on the system, and force you to generate a weak key? It seems like blocking until there was sufficient entropy would solve this (#3) above.
There is a way to deplete most randomness, (even remotely, via TCP-syn cookie generation, see section 3.4 of 086 paper; around 64-128 bits are reserved to be available only to /dev/random, page 18 of 251.pdf). But even when depleted, neighbor can't predict your generated key via urandom cryptographic weakness only by listening to /dev/random and urandom. Both of you will get partial SHA1-s of different parts of SHA1 of pools (each refilled with parts of SHA1 from primary pool), and no one of your should be able to reconstruct state of primary pool. Worst case is when using urandom and there is 0 available_entropy (this may be bit hard to achieve). And even in this case your will get cryptographic pseudo-random generator with unknown seed. The attacker is forced both to hack recursive SHA1 and to precisely guess seed (128 bytes of random information if the entropy is depleted or 512 bytes of primary pool in non-depleted case). This task is unbelievable to be solved even when there is only one user in system which got all output of urandom exclusively (if he still have no primary pool contents at some time).
Root of shared machine can do everything: write kernel module to dump state of primary/secondary pool; emulate that there is 16 millions bits of available entropy while /dev/random will output in loop something like SHA1("THIS IS TRUE RANDOM,BELIEVE ME"); steal memory dump of your openssl process to dump the key; read your stored on the fs private key; intercept the key presses sent from you to "your" openssl as passphrase to decrypt your safely stored private key. And the clever neighbor if he is the Wolf in sheep's clothing, will try to get root access to get your keys.
Clever attacker on shared machine may try to install side-channel attack against your crypto library and crypto algorithm, and there are actual attacks, e.g. using precise cache measurements (Bernstein 2005: "Cache-timing attacks on AES"), even if he lives in other virtual machine. This was one of reasons to e.g. move AES crypto inside the Intel CPU as separate hardware block not prone to cache side-channel leak.
So, don't use public/shared machines or machines out of your control (you should be root or somebody reliable should be) to do crypto with valuable information.
4) Given a public/private key you've already generated - is there any way you can prove it was generated with low entropy?
I think no, if pools were correctly initialized, and their contents is kept secure (no root attacker).
In some very bad embedded installations without timekeeping (device boots to 1970), without pool saving/restoring (or with too late restoring, after urandom read, like in some ubuntus), without any random inputs before key was generated; when keys were generated by some startup script; then attacker may model the state of pool and regenerate the same keys.
And there is a paper with searching of weak keys generated on devices with low entropy: https://www.usenix.org/system/files/conference/usenixsecurity12/sec12-final228.pdf "Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices". They detected bad keys ... by scanning millions of devices and comparing their keys:
In the case of TLS, at least 5.23% of hosts use manufacturer default keys that
were never changed by the owner, and another 0.34% appear to have generated the same keys as one or more other hosts due to malfunctioning random number generators.
And by checking for weakness in keys; again - by comparing a lot of scanned keys, for RSA they found many modules N1 and N2 where N1=p1*q1 and N2=p1*q2. I understand this situation as there are weak keys, but you can't distinguish weak key from good key. But if the key was generated from fixed low-entropy device state (first boot, early generation), then there is some probability to find another device (same HW platform) which generated same p or q as first device (if both, N will be the same).
Even more alarmingly, we are able to compute the private keys for 64,000 (0.50%) of the TLS hosts and 108,000 (1.06%) of the SSH hosts from our scan data
alone by exploiting known weaknesses of RSA and DSA when used with insufficient randomness. In the case of RSA, distinct moduli that share exactly one prime factor will result in public keys that appear distinct but whose private keys are efficiently computable by calculating the greatest common divisor (GCD).
DSA requires the "ephemeral key k" to be generated with lot of entropy. k should not repeat for different messages, but some k were same.
Nearly all (vulnerable hosts) served information identifying them as headless or embedded systems, including routers, server management cards, firewalls, and other network devices. Such devices typically generate keys automatically on first boot, and may have limited entropy sources compared to traditional PCs
.. Linux’s random number generator (RNG) can exhibit a boot-time entropy hole that causes urandom to produce deterministic output under conditions likely to occur in headless and embedded devices.
/dev/randomshouldn't take any more than a few seconds, a minute at the most. As CodesInChaos noted you can have infinite entropy with a PRNG but as far as/dev/randomis concerned, it can be drained quickly but not from a neighbour because it's being gathered at the OS level (if anything multiple VMs on the same machine would increase available entropy). $\endgroup$