On Thu, Sep 8, 2011 at 9:11 PM, Steve Grubb <sgrubb@xxxxxxxxxx> wrote: > The system being low on entropy is another problem that should be addressed. For our > purposes, we cannot say take it from TPM or RDRND or any plugin board. We have to have > the mathematical analysis that goes with it, we need to know where the entropy comes > from, and a worst case entropy estimation. Much of that is in the driver code's comments or previous email threads. For example, this thread cover many of the issues: http://yarchive.net/comp/linux/dev_random.html There are plenty of others as well. > It has to be documented in detail. Yes. But apart from code comments, what documentation are we talking about? Googling for /dev/random on tldp.org turns up nothing that treats this in any detail. > The only > way we can be certain is if its based on system events. Linux systems are constantly > low on entropy and this really needs addressing. But that is a separate issue. For > real world use, I'd recommend everyone use a TPM chip + rngd and you'll never be short > on random numbers. Yes. Here's something I wrote on the Debian Freedombox list: | No problem on a typical Linux desktop; it does not | do much crypto and /dev/random gets input from | keyboard & mouse movement, disk delays, etc. | However, it might be a major problem for a plug | server that does more crypto, runs headless, and | use solid state storage. | Some plug computers may have a hardware RNG, | which is the best solution, but we cannot count on | that in the general case. | Where the plug has a sound card equivalent, and | it isn't used for sound, there is a good solution | using circuit noise in the card as the basis for | a hardware RNG. | http://www.av8n.com/turbid/paper/turbid.htm | A good academic paper on the problem is: | https://db.usenix.org/publications/library/proceedings/sec98/gutmann.html | However, his software does not turn up in | the Ubuntu repository. Is it in Debian? | Could it be? | Ubuntu, and I assume Debian, does have | Havege, another researcher's solution | to the same problem. | http://www.irisa.fr/caps/projects/hipsor/ Some of that sort of discussion should be in the documentation. I'm not sure how much currently is. > But in the case where we are certifying the OS, we need the > mathematical argument to prove that unaided, things are correct. No, we cannot "prove that unaided, things are correct" if by "correct" you mean urandom output is safe against all conceivable attacks and by "unaided" you mean without new entropy inputs. It is a PRNG, so without reseeding it must be breakable in theory; that comes with the territory. That need not be a problem, though. We cannot /prove/ that any of the ciphers or hashes in widespread use are correct either. In fact, we can prove the opposite; they are all provably breakable by an opponent with enough resources, for extremely large values of enough. Consider a block cipher like AES: there are three known attacks that must break it in theory -- brute force search for the key, or reduce the cipher to a set of equations then feed in some known plaintext/ciphertext pairs and solve for the key, or just collect enough known pairs to build a codebook that breaks the cipher. We know the brute force and codebook attacks are astronomically expensive, and there are good arguments that algebra is as well, but they all work in theory. Despite that, we can use AES with reasonable confidence and with certifications from various government bodies. There are similar arguments for confidence in urandom. The simplest are the size of the state relative to the outputs and the XOR that reduces 160 bits of SHA-1 output to 80 of generator output. More detailed discussion is in the first thread I cited above. Barring a complete failure of SHA-1, an enemy who wants to infer the state from outputs needs astronomically large amounts of both data and effort. -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
