Re: linux-ipsec: Re: Summary re: /dev/random
At 11:39 AM -0500 8/13/99, Jim Thompson wrote: This thread started over concerns about diskless nodes that want to run IPsec. Worst case, these boxes would not have any slots or other expansion capability. The only source of entropy would be network transactions, which makes me nervous... An interesting alternative, I think, is an add-on RNG which could go on a serial or parallel port. The bandwidth achievable without loading down the machine is limited, but we don't need tremendous speeds, and many PCs used as routers, firewalls, etc. have such ports sitting idle. Even semi-dedicated diskless boxes would *often* have one of those. Of course, such a box already exists. The complete details of its design are available, and purchasing the box gives you the right to reproduce the design (once) such that you can, indeed, verify that you're getting random bits out of the box. I spent some time searching the Web for hardware randomness sources and I have summarized what I found at http://www.world.std.com/~reinhold/truenoise.html. I located several serial port RNG devices and some good sources of white noise that can be plugged into a sound port. I don't think I found the box Mr. Thompson refers to, but I would be glad to add it to the list. I also included serial and USB video cameras, which may be a good source of randomness due to digitization noise, if nothing else. I still feel strongly that diskless machines that are likely to use IPsec or other security software (e.g. SSL) should have a built-in source of randomness, a la the Pentium III. If the other microprocessor manufacturers won't comply, a TRNG should be included on one of the support chips. Randomness generation is so critical to public key cryptography that we should insist it be engineered in, not pasted on. Arnold Reinhold
Re: linux-ipsec: Re: Summary re: /dev/random
At 09:11 PM 8/17/99 -0700, Nick Szabo wrote: how it was prepared. There simply *cannot* be an all-purpose statistical test. Quite so. I'd like to see what Maurer's "universal" test says about the entropy of completely predictable sequences like the following: (1) pi (2) Champernowne's number (0.12345678901011121314151617181920...) Look, no test can distinguish between an arbitrarily large-state PRNG and a 'real' RNG. Pi's digits will appear fully entropic, under MUST, Diehard, etc. Even though its Kolomogorov/Chaitin-complexity is simple (ie, the program that computes Pi is short). Pi is not random, though its digits (and all N-tuples of digits, etc.) are evenly distributed. This *is* a profound point. Dunno about C's number, suspect its the same. Maurer, BTW, points out that his test is only useful if you know you have a real random bitstream generator. (Any faults in this exposition are my own. I have never met or corresponded with Maurer, in fact.) But if you cut through the philosophical boolsheet, and elegant computation-theory definitions of complexity, you are left with a problem: how to measure the entropy of a sample of a source, e.g., /dev/random's input. And it comes down to F log F no matter what algorithm you use to approximate it. The only philosophy you need is this: the Adversary doesn't know the internal (e.g., atomic) state of your hardware. Therefore, the measured state is unpredictable; but it probably isn't uniformly distributed. So you distill it. Until you've got fully independent bits. And you hash and stir it when you read it, for 'security in depth', ie, extra layers of protection. . Again, the question is, what is the alternative? I'm willing to discuss e.g., a function of raw vs. gzip-compressed file size as a measure of entropy. I think my major point is, measure it as best you can. I stumbled upon MUST; its a measure, so easier to handle than a multidimensional spectrum like Diehard; more informative than FIPS-140 binary tests. I am open to suggestions as to how to quantitatively evaluate RNGs, for /dev/r or otherwise. Cheers, David Honig
Re: linux-ipsec: Re: Summary re: /dev/random
Hi Ted -- At 11:41 PM 8/14/99 -0400, you wrote: standard Mathematician's style --- encrypted by formulae guaranteed to make it opaque to all but those who are trained in the peculiar style of Mathematics' papers. ... someone tried to pursuade me to use Maurer's test ... too memory intensive and too CPU intensive You are very wise to be skeptical of mathematical mumbo-jumbo. You mentioned questions about efficiency, but I would like to call into question whether the entropy estimate provided by Maurer's Universal Statistical Test (MUST) would be suitable for our purposes, even if it could be computed for free. Don't be fooled by the Universal name. If you looked it up in a real-world dictionary, you might conclude that Universal means all-purpose or general-purpose. But if you look it up in a mathematical dictionary, you will find that a Universal probability distribution has the property that if we compare it to some other distribution, it is not lower by more than some constant factor. Alas, the "constant" depends on what two distributions are being compared, and there is no uniform bound on it! Oooops! In the language of entropy, a Universal entropy-estimator overestimates the entropy by no more than a constant -- but beware, there is no uniform upper bound on the constant. To illustrate this point, I have invented Denker's Universal Statistical Test (DUST) which I hereby disclose and place in the public domain: According to DUST, the entropy of a string is equal to its length. That's it! Now you may not *like* this test, and you may quite rightly decide that it is not suitable for your purposes, but my point is that according to the mathematical definitions, DUST is just as Universal as MUST. There are profound theoretical reasons to believe it is impossible to calculate a useful lower bound on the entropy of a string without knowing how it was prepared. There simply *cannot* be an all-purpose statistical test. If you were to make the mistake of treating a Universal estimator as an all-purpose estimator, and then applying it in a situation where the input might (in whole or in part) be coming from an adversary, you would lay yourself open to a chosen-seed attack (analogous to a chosen-plaintext attack). On the other side of the same coin, if you *do* know something about how the input was prepared, there obviously are things you can do to improve your estimate of its entropy. For example, in the early stages of a hardware RNG, you could use two input channels, sending the differential-mode signal to the next stage, and using the common-mode signal only for error checking. This is a good way to get rid of a certain type of interference, and could be quite useful in the appropriate circumstances. Returning to the ugly side of the coin, you can see that a small change in the way the inputs were prepared would make this differencing scheme worthless, possibly leading to wild overestimates of the entropy. BOTTOM LINE: *) Incorporating an all-purpose entropy-estimator into /dev/random is impossible. *) Incorporating something that *pretends* to be an all-purpose estimator is a Really Bad Idea. *) The present design appears to be the only sound design: whoever provides the inputs is responsible for providing the estimate of the entropy thereof. If no estimate is provided, zero entropy is attributed. Cheers --- jsd
Re: linux-ipsec: Re: Summary re: /dev/random
On 1999-08-14 12:27:30 -0700, Bill Frantz wrote: It bothers me when people who are in favor of strong crypto automatically assume that anything which makes strong crypto easier will automatically be export controlled. This assertion is clearly wrong. The thing which most makes strong crypto easier is the (slow) general purpose CPU. These have never been export controlled. In DuD 2/1998 (I recall, one of the Roth articles on export control), a case is quoted in which re-exporting a US-fabricated i386 PC to Poland in 1990 is said to have lead to a conviction.
Re: Summary re: /dev/random
Date: Fri, 13 Aug 1999 13:55:29 -0700 From: David Honig [EMAIL PROTECTED] I have posted about using Maurer's Universal Statistical Test to measure entropy. With this tool you can see the effect of various conditioning [see RFC 1750] algorithms. (Of course, if your conditioning is a secure hash, the entropy measure is pinned at maximum). This would provide a better estimation function IMO than the current estimation function, which I consider too generous. With all due respect, Theo. I should point out that the FreeBSD /dev/random driver is an extremely hacked-up, ancient version of my driver. The FreeBSD folks have made all sorts of changes to it, and while I recognize some of the code as being mine, they have made enough changes to it that it really isn't fair to judge it as being my driver. If you examine the latest /dev/random sources in Linux, you will find that it is much, much more conservative about the entropy estimation than the hacked-up 0.95 /dev/random driver found in FreeBSD (the last modified by me in October, 1995 should be a hint that it's not recent). I'm willing to believe that there are still things which can be critized in the current entropy estimation algorithm, but please use something more recent than FreeBSD's /dev/random driver as the basis for your criticism! I looked at your paper, but it is far too technical for me to evaluate without a large amount of meditation, and probably not without tracking down all of the relevant references. (With all due respect, it's written in the standard Mathematician's style --- encrypted by formulae guaranteed to make it opaque to all but those who are trained in the peculiar style of Mathematics' papers. I'm not a mathematician, so it would take far more time that I have right now to decrypt it. I have printed it out and will try to puzzle it out later when I have time.) If I remember correctly, last time someone tried to pursuade me to use Maurer's test (when it was explained to me in Layman's English --- hi Colin!), my problem with it was that it was too memory intensive and too CPU intensive to use in the kernel. I'm quite willing to be proven wrong, if someone wants to try to explain to me Maurer's test and how to do it in English, and then try to pursuade me that it's actually feasible to do it in the kernel. Better yet, send me C source code I'll be happy to consider it. - Ted
Re: linux-ipsec: Re: Summary re: /dev/random
- Original Message - From: Henry Spencer [EMAIL PROTECTED] To: Derek Atkins [EMAIL PROTECTED] Cc: [EMAIL PROTECTED]; [EMAIL PROTECTED] Sent: Sunday, August 15, 1999 12:33 AM Subject: Re: linux-ipsec: Re: Summary re: /dev/random [...] and also they are not running in Intel hardware with a Linux OS... Speak for yourself. Mine are. I think you'd be surprised at how common this has become, in applications which are not severely pressed for performance. The sort of PC that people are discarding, in favor of faster and more modern ones, can route/firewall/security-gateway a T1 quite well. Anything much faster than that probably does need custom hardware... this year. Trere are also commercial products implementing encrypting firewalls on top of a Linux kernel. The vendor of one of them, Watchguard Technologies, has gone public one month ago (http://quote.yahoo.com/q?s=WGRDd=3m). Enzo
RE: linux-ipsec: Re: Summary re: /dev/random
Except that if you are paranoid enough to be worried about some unknown entity flooding your machine with network packets to manipulate the output of /dev/urandom, you are likely to not trust Intel to do RNG in such a way that it can't be fooled with. And if you're that paranoid, you'll soon understand that there is a 60hz (in the US, 50hz many other places) signal present in anything powered from the wall. But if you hang an antenna and a 60hz notch filter off of the RNG circuit, you can increase the gain of the other noise (power supply fan, network cable, printer running, telephone ringer, air conditioner, neighbor's Frigidair, etc.) to the point that the 60 cycle element is less significant. If you read the report on the Intel RNG co-authored by crypto expert Paul Kocher at http://www.cryptography.com/intelRNG.pdf, you will see that Intel has anticipated and designed against this type of noise. The Intel RNG uses the same basic principle as many of the entropy sources which have been discussed here: a relatively low-frequency event occurs and is sampled by a high-frequency timer. The low bits (low bit, in this case) of the high frequency timer is then effectivelly random as long as there is enough variation in the timing of the low frequency event. In this case, the high-frequency "timer" is simply an oscillator, so that we sample it at either a 0 or a 1 state. The low-frequency event is caused by an oscillator itself, one which runs at approximately 1/100 the rate of the high frequency timer. The low frequency oscillator is frequency-modulated by the resistance measured across an undriven resistor. This resistance will vary due to thermal noise, which is the ultimate source of the entropy produced by the chip. In order to reduce environmental interference, the thermal noise is actually measured across a pair of resistors, laid out side by side on the chip, and the difference is used. Environmental signals will affect both resistors (almost) identically, and by taking the difference any effects from the environment are almost eliminated. Even where environmental noise remains, it is being added to the thermal noise of the resistors, and can only add further variation to the period of the low frequency oscillator. As a general principle of information theory, adding a known signal to a random signal will still produce a fully random signal. Known sources of environmental noise will not reduce the randomness output by the chip. And to the extent that the environmental noise is unknown, it actually increases the entropy. For more details, see the report cited above. The chip contains additional stages and design precautions to further improve the quality of the random values produced. The output of the chip has been analyzed with a battery of randomness tests and looks very good. Here is the conclusion from the cryptography.com report: In producing the RNG, Intel applied conservative design, implementation, and testing approaches. Design assumptions about the random source, sampling method, system consistency, and algorithm appear appropriate. Careful attention was paid to analyze and avoid likely failure modes. We believe that the Intel RNG is well-suited for use in cryptographic applications. Direct use of Intel's software libraries should simplify the design and evaluation process for security products. Alternatively, developers can combine data from the Intel RNG with data from other sources. For example, data from the Intel RNG can be safely exclusive-ORed with output from any independent RNG. The Intel RNG will help designers avoid relying on proprietary entropy gathering techniques in critical security routines. We believe the Intel RNG will prevent many RNG failures and improve the integrity and security of cryptographic applications. Cryptographically, we believe that the Intel RNG is strong and that it is unlikely that any computationally feasible test will be found to distinguish data produced by Intel's RNG library from output from a perfect RNG. As a result, we believe that the RNG is by far the most reliable source of secure random data available in the PC.
Re: linux-ipsec: Re: Summary re: /dev/random
At 02:39 PM 8/11/99 -0400, Henry Spencer wrote: And will those hardware RNGs be subject to export control? Betcha they will, assuming export control survives legal challenges. If this isn't "enabling technology", I don't know what is... Hey, there are *legitimate* civilian uses for RNGs. For testing various kinds of communications gear. For true-random dithering. For monte-carlo verification. For soothing-sound generators to help you sleep...
Re: Summary re: /dev/random
Um, pardon my ignorance, but what is the point of a diskless, keyboardless computer that requires such high security? If the only interface is the network, what good is it? I can see being diskless (although why anyone would build a diskless machine in today's world, I have no idea -- it certainly doesn't significantly affect the cost of the machine). I used to have a diskless sun as my workstation. But it still had a keyboard. Did you have a specific usage in mind, here? I certainly cannot imagine a use for such a beast today. Even my palmpilot has user input. -derek "Arnold G. Reinhold" [EMAIL PROTECTED] writes: At 12:25 PM -0400 8/11/99, Theodore Y. Ts'o wrote: Date: Tue, 10 Aug 1999 11:05:44 -0400 From: "Arnold G. Reinhold" [EMAIL PROTECTED] A hardware RNG can also be added at the board level. This takes careful engineering, but is not that expensive. The review of the Pentium III RNG on www.cryptography.com seems to imply that Intel is only claiming patent protection on its whitening circuit, which is superfluous, if not harmful. If so, their RNG design could be copied. I've always thought there was a major opportunity for someone to come up with an ISA (or perhaps even a PCI) board which had one or more circuits (you want more than one for redundancy) that contained a noise diode hooked up to a digitizing circuit. As long as the hardware interface was open, all of the hard parts of a hardware RNG, could be done in software. This thread started over concerns about diskless nodes that want to run IPsec. Worst case, these boxes would not have any slots or other expansion capability. The only source of entropy would be network transactions, which makes me nervous. That is why I feel we should pressure manufacturers of such boards to include hardware RNG capability in one form or another. Generic PC's these days come with audio input or can have a sound card added easily. Open software that would characterize, monitor and whiten the output of an analog noise source connected to the audio-in port would meet a lot of needs. Arnold Reinhold -- Derek Atkins, SB '93 MIT EE, SM '95 MIT Media Laboratory Member, MIT Student Information Processing Board (SIPB) URL: http://web.mit.edu/warlord/ PP-ASEL N1NWH [EMAIL PROTECTED]PGP key available
Re: linux-ipsec: Re: Summary re: /dev/random
Yo Derek! I know a lot of people that use diskless, keyboardless computers as routers and terminal servers. I think a few small companies like Cisco, Ascend, Bay Networks, etc. make these things. :-) They have even been known to sell them as VPN gateways to encrypt local LAN traffic as they route it on to the internet. A few smaller copmanies like Shiva have been known to dabble in them. RGDS GARY On 13 Aug 1999, Derek Atkins wrote: Date: 13 Aug 1999 18:18:03 -0400 From: Derek Atkins [EMAIL PROTECTED] To: Arnold G. Reinhold [EMAIL PROTECTED] Cc: [EMAIL PROTECTED], [EMAIL PROTECTED], Bill Stewart [EMAIL PROTECTED] Subject: linux-ipsec: Re: Summary re: /dev/random Um, pardon my ignorance, but what is the point of a diskless, keyboardless computer that requires such high security? If the only interface is the network, what good is it? I can see being diskless (although why anyone would build a diskless machine in today's world, I have no idea -- it certainly doesn't significantly affect the cost of the machine). I used to have a diskless sun as my workstation. But it still had a keyboard. Did you have a specific usage in mind, here? I certainly cannot imagine a use for such a beast today. Even my palmpilot has user input. -derek "Arnold G. Reinhold" [EMAIL PROTECTED] writes: At 12:25 PM -0400 8/11/99, Theodore Y. Ts'o wrote: Date: Tue, 10 Aug 1999 11:05:44 -0400 From: "Arnold G. Reinhold" [EMAIL PROTECTED] A hardware RNG can also be added at the board level. This takes careful engineering, but is not that expensive. The review of the Pentium III RNG on www.cryptography.com seems to imply that Intel is only claiming patent protection on its whitening circuit, which is superfluous, if not harmful. If so, their RNG design could be copied. I've always thought there was a major opportunity for someone to come up with an ISA (or perhaps even a PCI) board which had one or more circuits (you want more than one for redundancy) that contained a noise diode hooked up to a digitizing circuit. As long as the hardware interface was open, all of the hard parts of a hardware RNG, could be done in software. This thread started over concerns about diskless nodes that want to run IPsec. Worst case, these boxes would not have any slots or other expansion capability. The only source of entropy would be network transactions, which makes me nervous. That is why I feel we should pressure manufacturers of such boards to include hardware RNG capability in one form or another. Generic PC's these days come with audio input or can have a sound card added easily. Open software that would characterize, monitor and whiten the output of an analog noise source connected to the audio-in port would meet a lot of needs. Arnold Reinhold -- Derek Atkins, SB '93 MIT EE, SM '95 MIT Media Laboratory Member, MIT Student Information Processing Board (SIPB) URL: http://web.mit.edu/warlord/ PP-ASEL N1NWH [EMAIL PROTECTED]PGP key available RGDS GARY --- Gary E. Miller Rellim 20340 Empire Ave, Suite E-3, Bend, OR 97701 [EMAIL PROTECTED] Tel:+1(541)382-8588 Fax: +1(541)382-8676
Re: linux-ipsec: Re: Summary re: /dev/random
On 14 Aug 1999, Derek Atkins wrote: Routers and Firewalls are not IPSec endpoints... Firewalls can easily be IPSEC endpoints, if they double as security gateways, which is likely to be common. (Making your firewall speak IPSEC is considerably easier than making all the equipment behind it do likewise.) It is admittedly unlikely for a router to be an IPSEC endpoint except for an administrative channel... unless it is doubling as a security gateway, which is possible. and also they are not running in Intel hardware with a Linux OS... Speak for yourself. Mine are. I think you'd be surprised at how common this has become, in applications which are not severely pressed for performance. The sort of PC that people are discarding, in favor of faster and more modern ones, can route/firewall/security-gateway a T1 quite well. Anything much faster than that probably does need custom hardware... this year. Some of the people who've talked to us about various aspects of Linux FreeS/WAN have had very interesting large-volume applications in mind. Open source, strong security, and cheap Intel hardware are a pretty versatile combination. ...However, there are always multiple network interfaces in a SG (at least one 'inside' and one 'outside' the secure network), so you have the timings of network packets on each network, as well as the timing of packets between the networks. There is considerable debate about whether packet timings are a good source for entropy, since they are at least potentially observable by outsiders. And, again, this is probably not running Linux. Again, speak for yourself. Linux use in that area is growing quickly. Seriously, how many 'inexpensive specialized devices' are going to need strong security? Almost all of them, before too very long. Try making a list of network devices which definitely *do not* need strong security; it's short. Also, a router is certainly not 'inexpensive'... If you're trying to route multiple T3s, true. Otherwise, again, you're behind the times -- routing no longer requires massive horsepower. (Of course, you can still pay a bundle for it if you really insist.) ...Besides, why not just add a hardware RNG? The pieces aren't very expensive, the parts don't really wear out, and then you always have a strong source of random numbers. It's an option, but not always the most attractive one. Being able to do without would be useful. Henry Spencer [EMAIL PROTECTED] ([EMAIL PROTECTED])
Re: linux-ipsec: Re: Summary re: /dev/random
On 13 Aug 1999, Derek Atkins wrote: Um, pardon my ignorance, but what is the point of a diskless, keyboardless computer that requires such high security? If the only interface is the network, what good is it? There are gadgets called "routers" and "firewalls" whose whole reason to exist is their network interfaces. They usually lack keyboards and often lack disks, and the people who install them tend to think about security quite a bit. (although why anyone would build a diskless machine in today's world, I have no idea -- it certainly doesn't significantly affect the cost of the machine). It does affect its noise level, power consumption, and reliability. And you are underestimating how much it can affect the cost of inexpensive specialized devices. Henry Spencer [EMAIL PROTECTED] ([EMAIL PROTECTED])
Re: Summary re: /dev/random
Date: Tue, 10 Aug 1999 11:05:44 -0400 From: "Arnold G. Reinhold" [EMAIL PROTECTED] A hardware RNG can also be added at the board level. This takes careful engineering, but is not that expensive. The review of the Pentium III RNG on www.cryptography.com seems to imply that Intel is only claiming patent protection on its whitening circuit, which is superfluous, if not harmful. If so, their RNG design could be copied. I've always thought there was a major opportunity for someone to come up with an ISA (or perhaps even a PCI) board which had one or more circuits (you want more than one for redundancy) that contained a noise diode hooked up to a digitizing circuit. As long as the hardware interface was open, all of the hard parts of a hardware RNG, could be done in software. Besides the whitner, the other thing that you really have to do (and which makes a hardware RNG harder than some people assume) are checks to make sure it is still functioning correctly, and to switch to another input source if one of the channels starts producing all zeros, or all ones, or some other noticeable pattern. (Something which would be *good* to do periodically is to run an FFT over the raw data sent out from the hardware RNG circuit, and make sure the power spectra doesn't show any obvious changes.) The point is that it should be possible to make an Open Hardware RNG board fairly cheaply, and then someone could work on the some Open Source Software which would actually do all of the hard parts that don't have to be done in silicon. I understand that the Linux Free S/Wan project might not want to rely on such a board being present, but realistically, it's the best way to significantly improve the random number generation, and people who want that level of security should perhaps be willing to pay to put one of these boards in their systems. Sure, we can try to further improve the software /dev/random driver, but I've always considered it to be a temporary stopgap until everyone shipped hardware RNG's as a matter of course in their computers. - Ted P.S. I'm currently attending the Linux World conference/expo, so my e-mail latency will be a bit longer than normal this week. I only skipped through to this thread and read things quickly because it was interesting; my apologies if I haven't responded to anybody's individual e-mail's. If you're around, stop by the VA Linux booth; I'll likely be hanging around there, when I'm not attending the random session at the show. Cheers!
Re: linux-ipsec: Re: Summary re: /dev/random
Paul Koning writes: The most straightforward way to do what's proposed seems to be like this: 1. Make two pools, one for /dev/random, one for /dev/urandom. The former needs an entropy counter, the latter doesn't need it. 2. Create a third pool, which doesn't ned to be big. That's the entropy staging area. It too has an entropy counter. 3. Have the add entropy function stir into that third pool, and credit its entropy counter. 4. Whenever the entropy counter of the staging pool exceeds N bits (a good value for N is probably the hash length), draw N bits from it, and debit its entropy counter by N. If the entropy counter of the /dev/random pool is below K% of its upper bound (K = 75 has been suggested) stir these N bits into the /dev/random pool. Otherwise, alternate between the two pools. Credit the pool's entropy counter by N. Some suggested modifications: The third pool, the entropy staging area, doesn't have to be big. In fact, it doesn't have to be any bigger than the amount of entropy it buffers, perhaps 100 bits or so. This size need only be large enough to prevent exhaustive search by an attacker. 80 or even 60 bits should be enough in practice, but a multiple of 32 like 96 or 128 would be more convenient for some algorithmss. Probably it would want to use a different mechanism than that used in the main random pool since it is so much smaller. A SHA hash context could be used as in Yarrow, but that may be somewhat slow. A 96 bit CRC would be another good choice. Cryptographic strength is not an issue here, just mixing. Having the two pools for /dev/random and /dev/urandom sounds like the right thing to do. However the proposal to favor /dev/random over /dev/urandom ignores the fact that /dev/random is seldom used. The description above calls for entropy to be given preferentially to /dev/random until it is 75% full. But this will starve urandom during the crucial startup phase. As was proposed earlier, it would be better to get initial randomness into /dev/urandom so that it can be well seeded and start producing good random numbers. This should be about one staging-pool size, about 100 bits. Once you have this, you can give entropy to both pools as suggested above. In operation, it is likely that the random pool will be filled and virtually never drawn upon, and it is unnecessary to keep putting more entropy into that pool. The urandom pool will be much more heavily used. It would make sense to have the algorithm for distributing entropy between the pools be aware of this. One possible mechanism would be to keep an entropy counter for both pools. Put the first buffer of entropy into the urandom pool so that it gets off to a good start. Then divide incoming entropy between the pools proportionally to how far they are from full. If both pools are full, divide it equally. If one is full and the other is not, all incoming entropy goes to fill the smaller one. If neither is full, entropy is divided proportionally, so that if one is 100 bits from full and the other is 200 bits from full, the second is twice as likely to get the input. This will cause both pools to constantly be refreshed when the machine is quiescent and not using randomness. When it is active and using /dev/urandom, that pool will get all the incoming entropy once /dev/random is full. This makes the most efficient use of incoming entropy and does not waste it by giving it to an already-full /dev/random pool, which would discard entropy that is already there. Entropy is a scarce and valuable resource in many configurations and it should not be thrown away.
Re: linux-ipsec: Re: Summary re: /dev/random
On Wed, 11 Aug 1999, Anonymous wrote: Everyone seems to be ignoring the fact that there will be a hardware RNG, well designed and carefully analyzed, installed on nearly every Intel based system that is manufactured after 1999. There is no need for a third party board, at least not on Intel architectures. At least not on Intel architectures *with Intel(TM) processors*. And even that assumes that this feature will *continue* to exist on the processors, which is by no means guaranteed. (I'm told that Intel is already mumbling about moving it into the support chipset instead, and I can easily see that it might exist only in some variants.) ...Within the next few years, any system configured as a crypto server or gateway will have built in hardware RNGs provided by the manufacturer. That would be nice. It's a little too early to be sure of that yet. Oh, and by the way, crypto belongs on all the machines, not just the servers and gateways. (Or the machines originally configured as such -- one nice thing about Linux crypto software is that you can turn cast-off desktop machines into excellent crypto gateways.) And will those hardware RNGs be subject to export control? Betcha they will, assuming export control survives legal challenges. If this isn't "enabling technology", I don't know what is... Henry Spencer [EMAIL PROTECTED] ([EMAIL PROTECTED])
Re: Summary re: /dev/random
At 12:25 PM -0400 8/11/99, Theodore Y. Ts'o wrote: Date: Tue, 10 Aug 1999 11:05:44 -0400 From: "Arnold G. Reinhold" [EMAIL PROTECTED] A hardware RNG can also be added at the board level. This takes careful engineering, but is not that expensive. The review of the Pentium III RNG on www.cryptography.com seems to imply that Intel is only claiming patent protection on its whitening circuit, which is superfluous, if not harmful. If so, their RNG design could be copied. I've always thought there was a major opportunity for someone to come up with an ISA (or perhaps even a PCI) board which had one or more circuits (you want more than one for redundancy) that contained a noise diode hooked up to a digitizing circuit. As long as the hardware interface was open, all of the hard parts of a hardware RNG, could be done in software. This thread started over concerns about diskless nodes that want to run IPsec. Worst case, these boxes would not have any slots or other expansion capability. The only source of entropy would be network transactions, which makes me nervous. That is why I feel we should pressure manufacturers of such boards to include hardware RNG capability in one form or another. Generic PC's these days come with audio input or can have a sound card added easily. Open software that would characterize, monitor and whiten the output of an analog noise source connected to the audio-in port would meet a lot of needs. Arnold Reinhold
Re: linux-ipsec: Re: Summary re: /dev/random
On Wed, 11 Aug 1999, Arnold G. Reinhold wrote: This thread started over concerns about diskless nodes that want to run IPsec. Worst case, these boxes would not have any slots or other expansion capability. The only source of entropy would be network transactions, which makes me nervous... An interesting alternative, I think, is an add-on RNG which could go on a serial or parallel port. The bandwidth achievable without loading down the machine is limited, but we don't need tremendous speeds, and many PCs used as routers, firewalls, etc. have such ports sitting idle. Even semi-dedicated diskless boxes would *often* have one of those. The problem with slots is, what flavor do you pick? PCI is, I gather, rather complicated to interface to. Also, since it's the preferred technology for fast networking boards, and tends to come in limited numbers, the PCI slots often are fully spoken for. ISA is a lot simpler, but its days now seem to be numbered. Henry Spencer [EMAIL PROTECTED] ([EMAIL PROTECTED])
Re: linux-ipsec: Re: Summary re: /dev/random
Arnold G. Reinhold [EMAIL PROTECTED] writes: 1. Mr. Kelsey's argument that entropy should only be added in large quanta is compelling, but I wonder if it goes far enough. I would argue that entropy collected from different sources (disk, network, sound card, user input, etc.) should be collected in separate pools, with each pool taped only when enough entropy has been collected in that pool. You have to realize that /dev/random entropy collection doesn't get one bit, add it to the pool, and increment the entropy counter. What happens is that it gets a notification for an interrupt along with the interrupt number, the keyboard scancode, or similar, reads a high-resolution clock (and gets 32 bits from there), and mixes these two numbers (40 bits, usually, I believe) to the pool, and tries to estimate how much entropy the time contained (by calculating first, second and third-order deltas and taking the smallest, I recall). So, for each 40 bits mixed into the pool, a few bits of entropy is credited. How do you propose quantizing this? Collecting all of the bits in a staging area and adding them when the entropy count is big enough? That could mean a kilobit or more of staging area, and per your suggestion the driver would have to have several of them. Gets pretty unwieldy, quickly. Also, this design means that there's always at least 32 bits mixed into the pool at once, and it might not always increase the entropy count at all. In a sense, /dev/random already does quantized collection. -- Osma Ahvenlampi
Re: linux-ipsec: Re: Summary re: /dev/random
"Osma" == Osma Ahvenlampi [EMAIL PROTECTED] writes: Osma Arnold G. Reinhold [EMAIL PROTECTED] writes: 1. Mr. Kelsey's argument that entropy should only be added in large quanta is compelling, but I wonder if it goes far enough. I would argue that entropy collected from different sources (disk, network, sound card, user input, etc.) should be collected in separate pools, with each pool taped only when enough entropy has been collected in that pool. Osma You have to realize that /dev/random entropy collection doesn't Osma get one bit, add it to the pool, and increment the entropy Osma counter Osma So, for each 40 bits mixed into the pool, a few bits of entropy Osma is credited. How do you propose quantizing this? I think this is pretty simple. Right now there's one pool, which is where new stuff is stirred in and then a hash is done over it (that's the outline, the details are a bit more involved). The most straightforward way to do what's proposed seems to be like this: 1. Make two pools, one for /dev/random, one for /dev/urandom. The former needs an entropy counter, the latter doesn't need it. 2. Create a third pool, which doesn't ned to be big. That's the entropy staging area. It too has an entropy counter. 3. Have the add entropy function stir into that third pool, and credit its entropy counter. 4. Whenever the entropy counter of the staging pool exceeds N bits (a good value for N is probably the hash length), draw N bits from it, and debit its entropy counter by N. If the entropy counter of the /dev/random pool is below K% of its upper bound (K = 75 has been suggested) stir these N bits into the /dev/random pool. Otherwise, alternate between the two pools. Credit the pool's entropy counter by N. The above retains the basic structure, its mixing algorithms, entropy bookkeeping, etc. The major delta is the multiple pools and the carrying of entropy from the staging pool to the others. paul
Re: Summary re: /dev/random
I have found this discussion very stimulating and enlightening. I'd like to make a couple of comments: 1. Mr. Kelsey's argument that entropy should only be added in large quanta is compelling, but I wonder if it goes far enough. I would argue that entropy collected from different sources (disk, network, sound card, user input, etc.) should be collected in separate pools, with each pool taped only when enough entropy has been collected in that pool. Mixing sources gives an attacker added opportunities. For example, say entropy is being mixed from disk accesses and from network activity. An attacker could flood his target with network packets he controlled, insuring that there would be few disk entropy deposits in any given quanta release. On the other hand, if the entropy were collected separately, disk activity entropy would completely rekey the PRNG whenever enough accumulated, regardless of network manipulation. Similarly, in a system with a hardware entropy source, adding disk entropy in a mixing mode would serve little purpose, but if the pools were kept separate, disk entropy would be a valuable backup in case the hardware source failed or were compromised. 2. It seems clear that the best solution combines strong crypto primitives with entropy collection. I wonder how much of the resistance expressed in this thread by has to do with concerns about performance. For this reason, I think RC4 deserves further consideration. It is very fast and has a natural entropy pool built in. With some care, I believe RC4 can be used in such a way that attacks on the PRNG can be equated to an attacks on RC4 as a cipher. The cryproanalytic significance of RC4's imperfect whiteness is questionable and can be addressed in a number of ways, if needed. I have some thoughts on a fairly simple and efficient multi-pool PRNG design based on RC4, if anyone is interested. 3. With regard to diskless nodes, I suggest that the cryptographic community should push back by saying that some entropy source is a requirement and come up with a specification (minimum bit rate, maximum acceptable color, testability, open design, etc.). An entropy source spec would reward Intel for doing the right thing and encourage other processor manufacturers to follow their lead. A hardware RNG can also be added at the board level. This takes careful engineering, but is not that expensive. The review of the Pentium III RNG on www.cryptography.com seems to imply that Intel is only claiming patent protection on its whitening circuit, which is superfluous, if not harmful. If so, their RNG design could be copied. Arnold Reinhold
Re: linux-ipsec: Re: Summary re: /dev/random
"Arnold" == Arnold G Reinhold [EMAIL PROTECTED] writes:
Arnold I have found this discussion very stimulating and
Arnold enlightening. I'd like to make a couple of comments:
Arnold 1. Mr. Kelsey's argument that entropy should only be added in
Arnold large quanta is compelling, but I wonder if it goes far
Arnold enough. I would argue that entropy collected from different
Arnold sources (disk, network, sound card, user input, etc.) should
Arnold be collected in separate pools, with each pool taped only
Arnold when enough entropy has been collected in that pool.
Arnold Mixing sources gives an attacker added opportunities. For
Arnold example, say entropy is being mixed from disk accesses and
Arnold from network activity. An attacker could flood his target
Arnold with network packets he controlled, insuring that there would
Arnold be few disk entropy deposits in any given quanta release. On
Arnold the other hand, if the entropy were collected separately,
Arnold disk activity entropy would completely rekey the PRNG
Arnold whenever enough accumulated, regardless of network
Arnold manipulation. Similarly, in a system with a hardware entropy
Arnold source, adding disk entropy in a mixing mode would serve
Arnold little purpose, but if the pools were kept separate, disk
Arnold entropy would be a valuable backup in case the hardware
Arnold source failed or were compromised.
I think this makes sense only if the "entropy source" under
consideration isn't actually any good. If if is reasonably sound (and
in particular, its entropy amount estimated conservatively) then there
isn't a problem. For example, if an attacker floods with network
messages, and you use network timing as an entropy source, the design
job was to pick a conservative lower bound of entropy per arrival
given that the arrivals may all be controlled by an attacker. If
you've done that, then the attack doesn't hurt.
Arnold 2. It seems clear that the best solution combines strong
Arnold crypto primitives with entropy collection. I wonder how much
Arnold of the resistance expressed in this thread by has to do with
Arnold concerns about performance. For this reason, I think RC4
Arnold deserves further consideration. It is very fast and has a
Arnold natural entropy pool built in. With some care, I believe RC4
Arnold can be used in such a way that attacks on the PRNG can be
Arnold equated to an attacks on RC4 as a cipher. The cryproanalytic
Arnold significance of RC4's imperfect whiteness is questionable and
Arnold can be addressed in a number of ways, if needed. I have some
Arnold thoughts on a fairly simple and efficient multi-pool PRNG
Arnold design based on RC4, if anyone is interested.
Well, yes, but /dev/{u,}random already does use strong crypto (a
strong cryptographic hash, to be precise). I expect RC4 could do the
job but is there any reason to replace what's there now (MD5 and
SHA-1) with RC4 or anything else?
Arnold 3. With regard to diskless nodes, I suggest that the
Arnold cryptographic community should push back by saying that some
Arnold entropy source is a requirement and come up with a
Arnold specification (minimum bit rate, maximum acceptable color,
Arnold testability, open design, etc.). An entropy source spec would
Arnold reward Intel for doing the right thing and encourage other
Arnold processor manufacturers to follow their lead.
Obviously an entropy source is required, but I'm not prepared to
translate that into a requirement for dedicated hardware. I still
believe (based on experiments -- though not on PC hardware) that
network arrival timing done with low order bits from a CPU cycle
counter supply non-zero entropy.
Arnold A hardware RNG can also be added at the board level. This
Arnold takes careful engineering, but is not that expensive. The
Arnold review of the Pentium III RNG on www.cryptography.com seems
Arnold to imply that Intel is only claiming patent protection on its
Arnold whitening circuit, which is superfluous, if not harmful. If
Arnold so, their RNG design could be copied.
There are probably plenty of designs; at the block diagram level they
are pretty simple and pretty obvious. The devil is in the details.
By the way, various crypto accelerator chips now come with an RNG
built-in. Some may be subject to export control, which would make
them unuseable in a Linux contents, but perhaps not all of them.
paul
Re: Summary re: /dev/random
Date: Sat, 07 Aug 1999 22:44:35 -0500 From: John Kelsey [EMAIL PROTECTED] Now, I haven't looked closely at the design of /dev/random, so I may be missing something. Is there something that would protect it from this class of attack, if it were overestimating the entropy collected by a, say, a factor of two or three? So if I understand your reasoning, your attack posits that you start at the very beginning, where the pool has only (say) 50 bits of entropy, but the pool *thinks* it has a few hundred bits of entropy. Basically, the idea is you assume the pool's starting state, and can try all 2**50 possible inputs that might have been mixed into the pool, and try to match it with the output to /dev/random, right? One of the things which makes this difficult is that as soon as the machine boots, every single disk access will be result in timing access data which gets mixed into the pool. The timing is done using the pentium cycle clock, so we get a fairly high resolution timing, which will be affected by the pattern of disk access, the layout of files accessed by the boot scripts on the disk, chaotic air turbulence in the drive (which is admittedly very small), delay caused by interrupts being blocked by the kernel, etc. So having the outside attacker model the system is actually fairly difficult, and I believe would require detailed knowledge of the configuration, setup, and filesystem layout of the system. Next, one of the other hurdles an attacker has to surmount is the mixing of data from a previous boot. During the shutdown process, the /etc/rc.d scripts ask /dev/urandom to generate a block of random data equal to the size of the entropy pool, and this is stored in a file readable only by root, typically /var/run/random-seed. During the boot sequence, the contents of that file is mixed into the entropy pool. *However*, the entropy count is not credited in this operation. This is merely done to try to deny attackers a stable starting point to begin the attack, assuming they can't gain physical access to the machine and read the random-seed file before the machine boots. Of course, immediately after that file is mixed into the entropy pool, the file is cleared out by asking the /dev/urandom device to generate a block of random data which is used to over-write the file. (This also guarantees that the system won't start with the same random seed file even if the system crashes without executing its shutdown scripts.) The random-seed file doesn't protect you from the very first time that you boot the machine, but usually the first time when you boot the machine is when you're installing the beast, and so usually there's at least some (if not quite a bit) keyboard activity during the initial system setup phase which typically happens before any services become available that might leak the outputs of /dev/random. And of course, the time at which /dev/random is read from is also mixed into the pool (altough again no entropy is credited to this operation). It does mean that the attacker has to not only gain access to the output of /dev/random, but also no exactly when the reads on /dev/random happened, down to the pentium clock cycle, in order to be able to carry out the interative guessing attack forward. I'll also note that in order for the interative guessing attack to work, the attacker has to be able to see sufficient numbers of the output of /dev/random to know that he/she is on track. This is one of the reasons why I didn't recommend that IPSEC cookie generation be done using /dev/random; first of all, it doesn't need that level of security in terms of random generation, and secondly it is sent in the clear. If you use /dev/random just to generate session keys, or to rekey secondary PRNG, then the attacker never gets to see anything direct from the output of /dev/random. It looks to me like /dev/random, and the PGP and Cryptlib PRNGs are all kind-of built on the assumption that there will probably be enough entropy to generate all the output bits we need (and we'll be able to tell if there is that much or not), and if not, these PRNGs are designed to hopefully give good pseudorandom outputs. That's fair. Because of the position of /dev/random in the kernel, it is in the position to grab a large quantity of timing data which will contain at least *some* entropy. It's such that the pool fills relatively quickly, and certainly once the pool is full, any overestimation of the entropy count becomes corrected, since the entropy estimate is capped by the size of the pool, but new values harvested from the system continue to get mixed into the pool. So yes, part of the design assumption is that /dev/random that it gets a very large number of events whose timings can be measured and distilled for entropy. - Ted
Re: Summary re: /dev/random
-BEGIN PGP SIGNED MESSAGE- Date: Mon, 2 Aug 1999 18:14:30 -0400 To: [EMAIL PROTECTED] Subject: Re: Summary re: /dev/random From: [EMAIL PROTECTED] [ Much deleted ] Yarrow is different. It uses a 160 bit pool, and as such is much more dependent on the strength of the cryptographic function. Hence, the two stage design is much more important. It also doesn't use a block cipher, BTW. It just uses a an interated hash function such as SHA, at least the last time I looked at the Counterpane paper. The next version (called Yarrow-160) will use a block cipher for output generation, and a hash function for entropy collection. We have a draft paper up on the website, and I'm giving a talk on it at SAC in a couple days. Before, we were relying upon an ad-hoc design based on SHA1 for output generation, for exportability reasons; we moved to 3DES because we basically wanted to settle any arguments about the security of the generating function. As such, I don't really believe the second stage design part of Yarrow is really necessary for /dev/random. Does it add something to the security? Yes, but at the cost of relying more on the crypto hash, and less on the entropy collection aspects of /dev/random, which is as far as I'm concerned much more important anyway. I guess I'd evaluate this a little differently. I think generating good random-looking outputs, once we have 100 or so bits of entropy, is easy. On the other hand, I think correctly estimating the entropy you're collecting in your pool is quite hard. It looks to me like /dev/random's design makes the opposite set of assumptions: I can get plenty of entropy, and correctly estimate how much I have got. But I don't know how to do cryptographic pseudorandom number generation. Now, here's the problem: I look at cryptographic primitives for generating pseudorandom bit sequences from short keys or seeds, and I see lots of solid-looking proposals. I see algorithms that people are already building systems around, and that years of cryptanalysis have failed to dent. I feel like the problem is pretty well understood, and that, in engineering terms, it's more-or-less solved. We can argue about whether we want to use 3DES-OFB, 3DES-counter, RC4, SHA1-counter, that weird SHA1-OFB-ish mode we used for the current version of Yarrow, or whatever else, but I don't have any doubts that we can do this. I am comfortable relying on these primitives. Then I look at estimating the entropy from each of the possible sources on a PC running Windows or Linux. I can find some tools to do this, but I don't have a lot of confidence I'm not missing something. I have to worry about all kinds of weird special cases--diskless workstations, PCs with no user at them, fresh out of the box system configurations, etc. I don't see this as a solved engineering problem, I see it as an interesting research problem. *That* is the set of beliefs that led to the Yarrow design. Let's talk about iterative guessing attacks. Everyone seems to assume they can only happen if an attacker can either get physical access to the box, or can get root. The best way to implement the iterative guessing attack is at the very beginning, when the pool has only (say) 50 bits of entropy, but the software *thinks* it has a few hundred bits of entropy. If the PRNG starts outputting bytes at this point, and an attacker is able to record the outputs from this box, the attacker can spend some time to break the initial state of the PRNG at the time of the first output. He can then carry on the iterative guessing attack forward, for as long as he has outputs being spun out faster than entropy is coming in. Now, something like /dev/random makes an entropy estimate of how fast entropy is coming in, and at least tries to limit its outputs. But it's easy for an estimate of this kind to be too high--entropy estimation is hard to do well in all cases. My claim is that if a generator like /dev/random falls behind early enough for the initial state to be guessed, and outputs keep being used quickly, then the generator never recovers. Now, I haven't looked closely at the design of /dev/random, so I may be missing something. Is there something that would protect it from this class of attack, if it were overestimating the entropy collected by a, say, a factor of two or three? If Free S/WAN really wants the second stage design, I will observe that the second stage can be done entirely in user space. Just use /dev/random or /dev/urandom as the first stage, and then simply use an iterated SHA (or AES candidate in MAC mode --- it really doesn't matter) as your second stage, periodically doing the catastrophic reseed by grabbing more data from /dev/random. This gives you all of the benefits (speed of key generation, no worry about DOS attacks by depleting entropy --- by mostly ignoring the problem) and drawbacks (over-dependence on the crypto function) of Yarrow. True. This isn't hard at all. Wait
Re: linux-ipsec: Re: Summary re: /dev/random
"Theodore Y. Ts'o" wrote: I'd certainly agree that having a standard user-space library would be a Good Thing. The real question in my mind is should the code live in user space or in kernel space. Definitely kernel space. Precisely because a good source of entropy is: * not computable, you need to get it from a device * essential for assorted security applications it needs to be in kernel space, where it can talk to raw devices, and be protected from corruption spoofing. Crispin - Crispin Cowan, Research Assistant Professor of Computer Science, OGI NEW: Protect Your Linux Host with StackGuard'd Programs :FREE http://www.cse.ogi.edu/DISC/projects/immunix/StackGuard/
Re: linux-ipsec: Re: Summary re: /dev/random
On Tue, 3 Aug 1999, bram wrote: The goal is to make it so that any time someone wants random numbers they can go to /dev/random, with no required studying of entropy and threat models and all that yadda yadda yadda which most developers will rightfully recoil from getting into when all they want is a few random bytes. That, surely, is what /dev/urandom is for. (Maybe /dev/random ought to be mode rw---, so that only root applications can use it?) Henry Spencer [EMAIL PROTECTED] ([EMAIL PROTECTED])
Re: Summary re: /dev/random
On Mon, 2 Aug 1999 [EMAIL PROTECTED] wrote: Linux's /dev/random uses a very different design, in that it uses a large pool to store the entropy. As long as you have enough entropy (i.e., you don't overdraw on the pool's entropy), /dev/random isn't relying on the cryptographic properties as much as Yarrow does. The problem is that the one bit of entropy for one bit of output rule creates the potential for lots of denial of service attacks where the entropy gets used up. There is no application which needs that amount of entropy. John Kelsey put it pretty well earlier this thread: Suppose God, in a fit of budget-consciouness, decides to get rid of all this wasteful hardware for generating random numbers that are necessary for quantum mechanics, and instead replaces them with a PRNG with a 256-bit seed. In this case, all hardware noise sources are ultimately tapping into this same seed and PRNG. How will you, or anyone, tell the difference? Most people don't know the fine-grained distinction between /dev/random and /dev/urandom. In fact, I'll bet most developers don't even know that /dev/urandom exists. As a result, lots of programs which require very large amounts of random numbers suck data out of /dev/random, creating a very large potential for unknown numbers of present and future problems. This entire class of problems can be eliminated completely by altering /dev/random to only block at bootup until it has enough entropy (or not at all if there was some stored on disk) and thereafter to spit out data as soon as it's requested. The complete threat model for RNG's, admittedly, has a number of attacks which seem very impractical under current circumstances, but since those attacks can be completely eliminated now prudence indicates doing so. That way, when circumstances arise in which one of those attacks is practical, we can make a little academic note which nobody cares about for it, rather than having to deal with a disaster. The other reason for changing the way /dev/random currently works is that the long output version of RIPEMD160 would make it just plain faster, since it would halve the amount of hashing done per byte of output. The goal is to make it so that any time someone wants random numbers they can go to /dev/random, with no required studying of entropy and threat models and all that yadda yadda yadda which most developers will rightfully recoil from getting into when all they want is a few random bytes. -Bram
Re: linux-ipsec: Re: Summary re: /dev/random
"Osma" == Osma Ahvenlampi [EMAIL PROTECTED] writes: Osma Looking at this discussing going round and round, I'm very Osma inclined to fetch the latest freeswan-snapshot, grep for Osma /dev/random, and replace all reads with a routine that has it's Osma own internal Yarrow-like SHA mixer that gets reseeded from Osma /dev/random at semi-frequent intervals, and in the meantime Osma returns random numbers from the current SHA value. That's how I Osma believe /dev/random was intended to be used, anyway... No, that's how /dev/urandom was intended to be used. What you describe duplicates the functionality of /dev/urandom. Why do it? I agree with Ted that there may well be people that misuse /dev/random. If so, the obvious comment is RT*M. Perhaps the documentation may want to emphasize the intended use of /dev/random more strongly. (Come to think of it, it's not clear to me especially after reading the Yarrow paper that there really *are* cases where the use of /dev/random rather than /dev/urandom is actually warranted.) Re Henry Spencer's comment: On Tue, 3 Aug 1999, bram wrote: The goal is to make it so that any time someone wants random numbers they can go to /dev/random, with no required studying of entropy and threat models and all that yadda yadda yadda which most developers will rightfully recoil from getting into when all they want is a few random bytes. That, surely, is what /dev/urandom is for. (Maybe /dev/random ought to be mode rw---, so that only root applications can use it?) That may reduce the number of applications that blindly use /dev/random without knowing why this isn't the right thing to do. On the other hand, it won't prevent applications that read /dev/urandom from causing those that use /dev/random to block (so long as both continue to use the same pool. Then again, if the valid uses of /dev/random are somewhere between rare and non-existent, which seems to be the case, this is a non-issue. Finally, from Bram: 5) a (very small) amount of persistent memory to keep pool state in (or at least periodically put some random bytes in to put in the pool at next reboot.) It would have to be plugged into a trusted piece of hardware to give it real randomness at least once, of course, but that wouldn't be a big deal. That doesn't solve the issue of entropy sources on diskless UI-less systems. All it does is let you carry whatever you got across reboots. If you have none to carry, you still have an issue. I do agree that using any available NV memory for keeping pool state across reboots is a good thing. paul
Re: Summary re: /dev/random
Date: Sun, 01 Aug 1999 17:04:14 + From: Sandy Harris [EMAIL PROTECTED] More analysis is needed, especially in the area of how to estimate input entropy. True. I actually don't believe perfection is at all possible. There are things which could probably do a better job, such as trying to run gzip -9 over the entropy stream and then using the size of the compressed stream (minus the dictionary) as the entropy. This is neither fast nor practical to do in the kernel, though. Yarrow's two-stage design, where the output from hashing the pool seeds a pseudo-random number generator based on a strong block cipher, offers significant advantages over the one-stage design in /dev/random which delivers hash results as output. In particular, it makes the hash harder to attack since its outputs are never directly seen, makes denial-of-service attacks based on depleting the generator nearly impossible, and "catastrophic reseeding" prevents iterative guessing attacks on generator internal state. Yarrow is different. It uses a 160 bit pool, and as such is much more dependent on the strength of the cryptographic function. Hence, the two stage design is much more important. It also doesn't use a block cipher, BTW. It just uses a an interated hash function such as SHA, at least the last time I looked at the Counterpane paper. Linux's /dev/random uses a very different design, in that it uses a large pool to store the entropy. As long as you have enough entropy (i.e., you don't overdraw on the pool's entropy), /dev/random isn't relying on the cryptographic properties as much as Yarrow does. Consider that if you only withdraw 160 bits of randomness out of a 32k bit pool, even if you can completely reverse the SHA function, you can't possibly determine more than 0.3% of the pool. As such, I don't really believe the second stage design part of Yarrow is really necessary for /dev/random. Does it add something to the security? Yes, but at the cost of relying more on the crypto hash, and less on the entropy collection aspects of /dev/random, which is as far as I'm concerned much more important anyway. If Free S/WAN really wants the second stage design, I will observe that the second stage can be done entirely in user space. Just use /dev/random or /dev/urandom as the first stage, and then simply use an iterated SHA (or AES candidate in MAC mode --- it really doesn't matter) as your second stage, periodically doing the catastrophic reseed by grabbing more data from /dev/random. This gives you all of the benefits (speed of key generation, no worry about DOS attacks by depleting entropy --- by mostly ignoring the problem) and drawbacks (over-dependence on the crypto function) of Yarrow. - Ted P.S. PGP's random number generator is similar to Linux's, and is similarly quite different from Yarrow. Probably the best thing to say is that philosophically quite different. I don't really believe we have enough analysis tools to say which one is "better".
Re: linux-ipsec: Re: Summary re: /dev/random
"Paul" == Paul Koning [EMAIL PROTECTED] writes: Paul 2. Pool size. /dev/random has a fairly small pool normally but Paul can be made to use a bigger one. Yarrow argues that it makes Paul no sense to use a pool larger than N bits if an N bit mixing Paul function is used, so it uses a 160 bit pool given that it uses Paul SHA-1. I can see that this argument makes sense. (That Paul suggests that the notion of increasing the /dev/random pool Paul size is not really useful.) Correction... I reread the Yarrow paper, and it seems I misquoted it. Yarrow uses the SHA-1 context (5 word hash accumulator) as its "pool" so it certainly has a 160 bit entropy limit. But /dev/random uses a much larger pool, which is in effect the input to a SHA-1 or MD5 hash, the output of which is (a) fed back into the pool to change its state, and (b) after some further munging becomes the output bitstream. In that case, the possible entropy should be as high as the bit count of the pool, not the length of the hash, so cancel my comment #2... paul
Re: Summary re: /dev/random
On Mon, 2 Aug 1999, Anonymous wrote: Disagree. /dev/random in cryptographic mode should be adequate as long as the machine is secured. If the machine is attacked to grab PRNG state the attacker can probably weaken the code. No, /dev/random's propensity to block can be unacceptable, especially for machines which don't have a source of entropy available. If the gateway machine is vulnerable to attacks which get root access, that is a serious weakness, but no work on the RNG can fix it. If not, then any decent cryptographically strong PRNG is fully adequate. No one has shown any value whatsoever for large entropy pools in this circumstance. Right now, everything which collects entropy has to be run as root or in the kernal, which is uncomfortable from a security standpoint. I disagree that bad entropy attacks are unrealistic - if a machine is running several different sources of entropy, getting information from god knows what source, it's quite possible one of them could be made by external forces to start spewing controlled data into the pool, and if you have a machine which, for example, is running a web server which isn't being hit by anyone but the attacker, and that web server is the only thing reading data out of /dev/random, suddenly an attack looks quite possible. This is especially true for possible future sources of entropy where, for example, some sysadmin might figure 'I'll just spew the traffic logs into /dev/random, it's the only source of randomness I have, and it's pretty random.' As things stand, that would leave the system much more wide-open than it would have to be. Yarrow does not use a block cipher. In PRNG mode, it is simply an iterated SHA-1 hash, with the hash output provided as the RNG output. It hashes a 20-byte seed, then hashes the previous 20 bytes of output to get the new 20 bytes of output. Every so often it updates the seed to be a new hash output value. That isn't quite accurate, but the basic point is that Yarrow is based on a hash algorithm as a primitive, and any hash algorithm could be substituted in there. Further work on figuring out what core trickery should be at the heart of the randomness source is unnecessary, especially since other work on the same problem has come up with essentially the same algorithm. Continue discussions on cryptography list, focussing on the hardest problem: acquiring and estimating entropy. This may be the hardest problem, but it is not the most important one, especially not for FreeS/WAN use. Mis-estimates of entropy are not crucial for this purpose. FreeS/WAN does not need "true" entropy and the current design of /dev/random does a soft fallback from true RNG to pseudo RNG, which is perfect for FreeS/WAN. No, this is actually the biggest gaping hole in the entire system - if the randomness source starts spewing after only getting 40 bits of entropy then it's wide open to attack, regardless of how much whitening it does on the output. The iterative guessing attack is being overstated here in terms of its practical significance. The root privileges which are necessary to snoop the RNG state will also allow for more malicious actions that completely compromise security. The way to diddle with RNG state is to mess with it's sources, not by directly looking inside the state. Attacks of that form, even if they aren't 'practical' now, could easily become practical in the future. -Bram
Re: Summary re: /dev/random
Sandy Harris writes: Conclusions I've reached that I hope there's agreement on: More analysis is needed, especially in the area of how to estimate input entropy. (Yarrow does this quite differently than /dev/random. I'm not convinced either is right, but I've nothing else to propose. This is clearly a hard problem.) It's really impossible to do it in general. What you can do is to come up with a model for a particular entropy source, such as mouse movements or disk timings, assuming the details are unknown to an attacker. But there is no feasible algorithm which can be given a block of data and say how much entropy is in it. There could be a serious weakness on a gateway machine. At a minimum, such machines should use the largest possible entropy pool (2K 32-bit words for current /dev/random) and enable all entropy sources. Disagree. /dev/random in cryptographic mode should be adequate as long as the machine is secured. If the machine is attacked to grab PRNG state the attacker can probably weaken the code. If the gateway machine is vulnerable to attacks which get root access, that is a serious weakness, but no work on the RNG can fix it. If not, then any decent cryptographically strong PRNG is fully adequate. No one has shown any value whatsoever for large entropy pools in this circumstance. Yarrow's two-stage design, where the output from hashing the pool seeds a pseudo-random number generator based on a strong block cipher, offers significant advantages over the one-stage design in /dev/random which delivers hash results as output. In particular, it makes the hash harder to attack since its outputs are never directly seen, makes denial-of-service attacks based on depleting the generator nearly impossible, and "catastrophic reseeding" prevents iterative guessing attacks on generator internal state. Yarrow does not use a block cipher. In PRNG mode, it is simply an iterated SHA-1 hash, with the hash output provided as the RNG output. It hashes a 20-byte seed, then hashes the previous 20 bytes of output to get the new 20 bytes of output. Every so often it updates the seed to be a new hash output value. So possible actions are: Continue discussions on cryptography list, focussing on the hardest problem: acquiring and estimating entropy. This may be the hardest problem, but it is not the most important one, especially not for FreeS/WAN use. Mis-estimates of entropy are not crucial for this purpose. FreeS/WAN does not need "true" entropy and the current design of /dev/random does a soft fallback from true RNG to pseudo RNG, which is perfect for FreeS/WAN. FreeS/WAN project should take steps in docs or scripts to ensure /dev/random is appropriately compiled on gateway systems. Yes, but more to the point, it should not run if /dev/random does not exist. In that case it would certainly be convenient to inform the user of any potential problems at install time. /dev/random should become two-stage, preferably using an AES candidate cipher with 256-bit key, 128-bit block and reseeding operations which change at least 128 bits at a time. The two-stage design, which is really just a matter of having a separate entropy buffer so it doesn't come in too slowly, is designed to protect against an attack where the PRNG state is snooped. No one has shown a practical method for doing so which could not be easily extended to weaken the RNG code. The iterative guessing attack is being overstated here in terms of its practical significance. The root privileges which are necessary to snoop the RNG state will also allow for more malicious actions that completely compromise security. Here is an alternative proposed set of actions. Emphasize the need to make gateway machines secure. These machines have sensitive keys and other data in addition to RNG state. If an attacker can get root privileges on your gateway, you have no security. This is the most crucial element in the whole security setup. Make sure the RNG in /dev/random is strong as a pseudo RNG, even with no entropy being brought in. Most gateway machinse will be stand-alone boxes without many events other than network events themselves, which cannot be assumed to be unknown to an attacker. Entropy is likely to be scarce in normal operation and the machine must run well without it. Hence the PRNG behavior of the system (without entropy addition) is the most crucial element for the analysis of its security. Having settled both of those problems, then you can add an input entropy buffer for the PRNG. Just bring input entropy into a hash context (doesn't even need to be cryptographically strong), and dump that into the entropy pool using the existing mechanisms when you have "enough". It's probably less than 50 lines of code to add this, so you might as well do it. But this is not a major addition to the security of your system. The other elements above are far more important.
