Re: linux-ipsec: Re: Summary re: /dev/random
> From: "Arnold G. Reinhold" <[EMAIL PROTECTED]> > [...] > 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. http://www.nshore.com/atom_age.htm Jim
Re: linux-ipsec: Re: Summary re: /dev/random
John Denker: >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. 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...) One can show that in Champernowne's number each digit of the base, and each block of digits of any length, occurs with equal asymptotic frequency. One can define, if not successfully run, an actual universal test for any preparation process simulable by a Turing machine: search the space of all possible possible ways the string could have been prepared on a Turing machine, i.e. all the possible programs shorter than the string. (The lengths of programs specified in different Turing complete languages are equivalent up to a constant). The entropy (Kolmogorov complexity) of the string is the length of the shortest program (to within that constant). It's not too hard to see that that (a) this search procedure is uncomputable, and (b) there is no more comprehensive statistical test possible on a Turing machine (i.e., the test defined above really is universal for Turing machines). One could restrict the search to programs polynomially bounded in time and space, so that the test is computable, but then one would still expend at least as much effort to generate random numbers as the cryptanalyst would need to break them. The standard reference is Li and Vitanyi, _An Introduction to Kolmogorov Complexity and its Applications_. Online start at http://www.cwi.nl/~paulv/kolmogorov.html. [EMAIL PROTECTED] http://www.best.com/~szabo/ PGP D4B9 8A17 9B90 BDFF 9699 500F 1068 E27F 6E49 C4A2
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
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
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: 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
- 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=WGRD&d=3m). Enzo
Re: linux-ipsec: Re: Summary re: /dev/random
At 1:22 PM -0700 8/13/99, David Honig wrote: >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... 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. We should proceed from the assumption that unless it is specifically forbidden, it is permitted. For example, since strong authentication (without privacy) is permitted, we should export it. Yes, it can be perverted into providing privacy, but so can CPUs. At 9:25 AM -0700 8/11/99, Theodore Y. Ts'o wrote: >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 FIPS-140 tests are a good start for checking that the hardware is still working. Arnold Reinhold pointed out that sound cards are quite available and easy to use as a source of entropy. I particularly like using the differences between stereo microphones because it eliminates a lot of common-mode interference. The big problem with sound cards and microphones is that a Trojan horse could use them to listen in on conversations in the room. I expect that there isn't much of interest to listen to in the typical server room. People should probably avoid speaking passwords though. - Bill Frantz | The availability and use of secure encryption may | Periwinkle | offer an opportunity to reclaim some portion of | Consulting | the privacy we have lost. - B. FLETCHER, Circuit Judge|
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: 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
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
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: 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
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
Henry Spencer wrote: > 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.) My information (from Intel insiders) says that this has already happened: the hardware RNG has been moved from the CPU to the chip set. It seems to be a topic of debate whether that is good or bad news. At least one poster claimed it was good, because the Intel chipset was likely to be more pervasive than the new high-end CPUs. 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 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: 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.
linux-ipsec: Re: Summary re: /dev/random
Ted Ts'o writes: >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. 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. It is true that Intel has not yet released the specs for accessing the chip, but software which uses it should start being available soon, and it will not take long to discover the interface by analyzing the software. Concern about scarce randomness will be largely obsolete within a couple of years. The world is full of randomness, it's just that there has been no significant market for it until recently. Now that Intel has shown the way, other manufacturers will follow suit. Within the next few years, any system configured as a crypto server or gateway will have built in hardware RNGs provided by the manufacturer. These will provide ample randomness for cryptographic purposes.
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: linux-ipsec: Re: Summary re: /dev/random
At 9:02 AM +0300 8/11/99, Osma Ahvenlampi wrote: >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's the general idea. The details of "adding them" need to be discussed. >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. Maybe you'd need a killobyte all together? That seems quite wieldy to me. Random number generation is one of the major vulnerabilities of modern cryptographic systems, maybe the biggest. One KB is a very cheap price to pay for a significant improvement in RNG security. >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. That idea won't fly, I'm afraid. We're talking about waiting until you accumulate, say, 128 bits of entropy (some might prefer 256 bits), not raw data bits. Arnold Reinhold
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
At 11:38 AM -0400 8/10/99, Paul Koning replied:
> > "Arnold" == Arnold G Reinhold <[EMAIL PROTECTED]> writes:
> Arnold> ...
> 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> ...
>
>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.
This is where I disagree most strongly and the reasons are somewhat a
mater of philosophy. It is relatively easy to design crypto systems
that protect against attacks you know. It is harder to defend against
unanticipated attacks. Maybe some future server box will have the
network controller integrated with the CPU and running off the same
clock so that all your sub-millisecond entropy goes bye-bye. Maybe
someone more clever than I will figure out how to goose the network
just so and get things to sync up a la V.90. I would be a whole lot
happier having the entropy come from two or more independent sources
and having it accumulated independently. If all it takes is a little
software, why not do that?
>
> Arnold> ... I think RC4 deserves further consideration. ...
>
>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?
I like RC4 for this application 'cause its fast and simple, but it's
a side issue. If you are satisfied with performance, there is no
reason to change.
>
> 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.
IPsec is going to spawn a whole industry and represents an
opportunity to get things done right. The software you are designing
today may be used unchanged for decades in very sensitive
applications. (The Y2K report for the Seabrook nuclear plant lists a
critical database running on a PDP-11). Maybe one compromise is to
define a set of quality levels for random number generation, say:
A = hardware RNG + ad hoc backup
B = hardware RNG alone
C = two or more ad hoc sources, e.g. disk and network,
independently collected
D = single ad hoc source
Then market pressure would drive vendors to level A.
Arnold
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: 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
> "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: 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: 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: linux-ipsec: Re: Summary re: /dev/random
I get the feeling from the discussion on /dev/random vs. alternatives (in particular, Yarrow) that not all the commenters have looked at the code for /dev/random. Let's see... 1. Estimating entropy. Yes, that's the hard one. It's orthogonal from everything else. /dev/random has a fairly simple approach; Yarrow is more complex. It's not clear which is better. If there's reason to worry about the one in /dev/random, a good solution would be to include the one from Yarrow and use the smaller of the two answers. 2. Pool size. /dev/random has a fairly small pool normally but can be made to use a bigger one. Yarrow argues that it makes no sense to use a pool larger than N bits if an N bit mixing function is used, so it uses a 160 bit pool given that it uses SHA-1. I can see that this argument makes sense. (That suggests that the notion of increasing the /dev/random pool size is not really useful.) 3. /dev/random blocks after delivering as many bits of output as its current entropy estimate. Right. But /dev/urandom does not, and neither does Yarrow. In other words, Yarrow is like /dev/urandom in that respect; if people feel Yarrow is an example of a good generator, they can't very well use the blocking behavior of /dev/random as additional ammo! Conversely, if you believe some applications really require that blocking behavior, it follows you would not want to use Yarrow in its current form. Incidentally, if you adopt Scheier's comment that the entropy pool size should be bounded by the hash value length, the blocking behavior of /dev/random doesn't make much sense anymore. Also, Scheier argues that a conservative upper bound on how many bits to extract before reseeding is 2^(n/3), i.e., 2^53 bits in the SHA-1 case... although he doesn't prevent you from using smaller numbers. 4. Questions/concerns about the cryptographic primitives used. This is where I wonder what people have looked at... Yarrow uses SHA-1 as a mixing function. /dev/random uses either SHA-1 or MD5 as a mixing function. What's the issue again? Note also that /dev/random doesn't give you the current hash state as its output; instead it "folds" it (high half xor low half) on the ultra-conservative principle that knowing a particular 160-bit SHA-1 output value might maybe give you some insight in what subsequent iterations of SHA-1 would produce. I don't believe that's currently thought to be the case, but even if it were, /dev/random doesn't suffer from it. I don't remember what Yarrow does in this area. 5. "Catastrophic reseeding" to recover from state compromise. It's been argued that this is a rather extravagant concern. I agree to a point... if someone can read kernel memory, you probably have other more immediate concerns. On the other hand, it's a really good idea to have the property that compromise at time T doesn't give the attacker a way in for time > T+n for suitable (reasonably small) n. Also, note that the state compromise is a passive attack, it may go unnoticed more readily than, say, a trojan horse patch to the kernel. So while this attack is a bit of a stretch, defending against it is really easy. It's worth doing. 6. Inadequate entropy sources for certain classes of box. This is common to both. On diskless UI-less boxes, neither Yarrow nor /dev/random currently have any entropy inputs. We've discussed this before; I've recommended adding fine grained (CPU clock cycle few low order bits) network packet timing as a source. There's been some scepticism expressed, rightly so; I've done comparable things in the past and feel comfortable that this one will work out, but I would definitely expect others to want to do their own analysis. Having a Yarrow-style entropy analyzer might help here. In summary: I think (6) is the biggest issue. Items (1) and (5) suggests pieces that could be adopted from Yarrow and put into /dev/random. I see no valid argument that there is anything major wrong with the current generator, nor that replacing it with Yarrow would be a good thing at all. In particular, I disagree with Sandy's comment that "Yarrow's two-stage design... offers significant advantages over the one-stage design in /dev/random". Apart from the long shot (iterative guessing attack) and possibly some nuances relating to entropy estimates, I don't see any significant difference in strength between the two. paul
Re: linux-ipsec: Re: Summary re: /dev/random
On Sun, 1 Aug 1999, bram wrote: > 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. Which is why /dev/urandom is provided. The newer random drivers also offer an entropy count (accessible through /proc). This is a policy decision - do we want a failure mode where the software shuts down (entropy exhaustion on /dev/random) or continues operating with reduced security (/dev/urandom). > > 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. It currently has to be in the kernel. IIRC bytes written to /dev/random are hashed into the entropy pool but not credited to the entropy count. I have asked for a means to say "please add these bytes to the pool and increment the entropy counter", but have received not response. > 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. There attacks require the attacker to either know the current state of the pool or to reverse SHA1. > 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. There is still the entropy from things like disk interrupt timings, as well as the state collected during boot. > > 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. The random driver already uses SHA1, but it doesn't do the bulk reseeding that Yarrow does. > > > 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. Good point - it makes sense to modify the random driver to not output until a lower bound of entropy has been collected. Regards, Damien Miller -- | "Bombay is 250ms from New York in the new world order" - Alan Cox | Damien Miller - http://www.ilogic.com.au/~dmiller | Email: [EMAIL PROTECTED] (home) -or- [EMAIL PROTECTED] (work)
