Re: entropy depletion
On Tue, Jan 11, 2005 at 03:48:32PM -0500, William Allen Simpson wrote: 2. set the contract in the read() call such that the bits returned may be internally entangled, but must not be entangled with any other read(). This can trivially be met by locking the device for single read access, and resetting the pool after every read. Slow, but it's what the caller wanted! Better variants can be experimented on... Now I don't remember anybody suggesting that before! Perfect, except that an attacker knows when to begin watching, and is assured that anything before s/he began watching was tossed. The point is interesting and well made, but I'm not sure it was intended as a concrete implementation proposal. Still, as long as it's floating by.. Rather than locking out other readers from the device (potential denial-of-service, worse than can be done now by drawing down the entropy estimator?), consider an implementation that made random a cloning device. Each open would create its own distinct instance, with unique state history. One might initialise the clone with a zero (fully decoupled, but potentially weak as noted above) state, or with a copy of the base system device state at the time of cloning, but with a zero'd estimator. From there, you allow it to accumulate events until the estimator is ready again. Perhaps you clone with a copy of the state, and allow an ioctl to zero the private copy.. perhaps you only allow a clone open to complete once the base generator has been clocked a few times with new events since the last clone.. many other ideas. Most implementations allow data to be written into the random device, too, so a process with a cloner open could add some of its own 'entropy' to the mix for its private pool, if it wanted additional seeding (usually, such writes are not counted by the estimator). The base system device accumulates events while no cloners are open. You'd need some mechanism to distribute these events amongst accumulating clones such that they'd remain decoupled. It's an interesting thought diversion, at least - but it seems to have as many potential ways to hurt as to help, especially if you're short of good entropy events in the first place. Like smb, frankly I'm more interested in first establishing good behaviour when there's little or no good-quality input available, for whatever reason. -- Dan. pgpiBemAGKvdQ.pgp Description: PGP signature
Re: entropy depletion
Let me raise a different issue: a PRNG might be better *in practice* because of higher assurance that it's actually working as designed at any given time. Hardware random number generators are subject to all sorts of environmental issues, including stuck bits, independent oscillators that aren't independent, contamination by power line frequency noise, etc. By contrast, a correct implementation of a cryptographic algorithm will always function correctly. (Yes, there could be an undetected hardware fault. Run it three times, on different chips) To me, the interesting question about, say, Yarrow is not how well it mixes in entropy, but how well it performs when there's essentially no new entropy added. Clearly, we need something to see a PRNG, but what are the guarantees we have against what sorts of threats if there are never any new true-random inputs? (Remember the purported escrow key generation algorithm for Clipper? See http://www.eff.org/Privacy/Newin/Cypherpunks/930419.denning.protocol for details. The algorithm was later disavowed, but I've never been convinced that the disavowal was genuine.) --Prof. Steven M. Bellovin, http://www.cs.columbia.edu/~smb - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: entropy depletion
Ben Laurie wrote: William Allen Simpson wrote: Why then restrict it to non-communications usages? Because we are starting from the postulate that observation of the output could (however remotely) give away information about the underlying state of the entropy generator(s). Surely observation of /dev/urandom's output also gives away information? Right. So what we are looking at here is a requirement such that we don't leak any internal state. Traditionally, the Unix people would do this by a) limiting access to the resource to root and b) auditing the user of the resource carefully. But that's a bit OTT, IMHO. Another way of doing this is to put in a requirement that each read is separate and unlinked. That is, if you do a read of 1024 bits for some key operation, the contract with the random device is that entropy might be mixed between those bits, *but* it isn't mixed with any other read that might be done. Trivially, this could be met by throwing away all existing entropy, locking the entropy for syncronised read, and waiting until enough fresh stuff was built up. That might take a while, but hey, that's the contract that the coder asked for. And there are plenty of variants imaginable. Either way, it seems that restriction is not the only way to deal with the leakage problem, once we understand that avoiding the leakage is the requirement. -- News and views on what matters in finance+crypto: http://financialcryptography.com/ - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: entropy depletion
Ben Laurie wrote: William Allen Simpson wrote: Why then restrict it to non-communications usages? Because we are starting from the postulate that observation of the output could (however remotely) give away information about the underlying state of the entropy generator(s). Surely observation of /dev/urandom's output also gives away information? Right. I'd suggest the original statement of the issue at hand might be better rephrased as: The *requirement* is that the generator not leak information. This requirement applies equally well to an entropy collector as to a PRNG. For an entropy collector there are a number of ways of meeting the requirement. 1. Constrain access to the device and audit all users of the device. 2. set the contract in the read() call such that the bits returned may be internally entangled, but must not be entangled with any other read(). This can trivially be met by locking the device for single read access, and resetting the pool after every read. Slow, but it's what the caller wanted! Better variants can be experimented on... We are still left with the notion as Bill suggested that no entropy collector is truly clean, in that the bits collected will have some small element of leakage across the bits. But I suggest we just cop that one on the chin, and stick in the random(5) page the description of how reliable the device meets the requirement. (This might be a resend, my net was dropping all sorts of stuff today and I lost the original.) iang -- News and views on what matters in finance+crypto: http://financialcryptography.com/ - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: entropy depletion
Ian G wrote: The *requirement* is that the generator not leak information. This requirement applies equally well to an entropy collector as to a PRNG. Now here we disagree. It was long my understanding that the reason the entropy device (/dev/random) could be used for both output and input, and blocked awaiting more entropy collection, was the desire to be able to quantify the result. Otherwise, there's no need to block. For an entropy collector there are a number of ways of meeting the requirement. 1. Constrain access to the device and audit all users of the device. 2. set the contract in the read() call such that the bits returned may be internally entangled, but must not be entangled with any other read(). This can trivially be met by locking the device for single read access, and resetting the pool after every read. Slow, but it's what the caller wanted! Better variants can be experimented on... Now I don't remember anybody suggesting that before! Perfect, except that an attacker knows when to begin watching, and is assured that anything before s/he began watching was tossed. In my various key generation designs using MD5, I've always used MD-strengthening to minimize the entanglement between keys. There was MD5 code floating around for many many years that I wrote with a NULL argument to force the MD-strengthening phase between uses. I never liked designs with bits for multiple keys extracted from the same digest iteration output. And of course, my IPsec authentication RFCs all did the same. See my IP-MAC design at RFC-1852 and RFC-2841. We are still left with the notion as Bill suggested that no entropy collector is truly clean, in that the bits collected will have some small element of leakage across the bits. But I suggest we just cop that one on the chin, and stick in the random(5) page the description of how reliable the device meets the requirement. (This might be a resend, my net was dropping all sorts of stuff today and I lost the original.) That's OK, the writing was clearer the second time around. -- William Allen Simpson Key fingerprint = 17 40 5E 67 15 6F 31 26 DD 0D B9 9B 6A 15 2C 32 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: entropy depletion
William Allen Simpson wrote: Ben Laurie wrote: William Allen Simpson wrote: Why then restrict it to non-communications usages? Because we are starting from the postulate that observation of the output could (however remotely) give away information about the underlying state of the entropy generator(s). Surely observation of /dev/urandom's output also gives away information? ummm, no, not by definition. /dev/random blocks on insufficient estimate of stored entropy useful for indirect measurement of system characteristics (assumes no PRNG) /dev/urandom blocks only when insufficient entropy for initialization of state computationally infeasible to determine underlying state (assumes robust PRNG) These are the definitions we've been using around here for many years. It does help when everybody is talking about the same things. Around where? I've never heard of a /dev/random that doesn't include a PRNG. But I'll admit its entirely possible I just haven't been paying attention. Can you give examples? In any case, if the postulate is that observing the output could give away information about the underlying state, then I cannot see how /dev/urandom gets around this problem. Cheers, Ben. -- http://www.apache-ssl.org/ben.html http://www.thebunker.net/ There is no limit to what a man can do or how far he can go if he doesn't mind who gets the credit. - Robert Woodruff - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: entropy depletion
William Allen Simpson wrote: Ian G wrote: The *requirement* is that the generator not leak information. This requirement applies equally well to an entropy collector as to a PRNG. Now here we disagree. It was long my understanding that the reason the entropy device (/dev/random) could be used for both output and input, and blocked awaiting more entropy collection, was the desire to be able to quantify the result. Otherwise, there's no need to block. I'm sorry, I don't see the relationship between the requirement to not leak, and the requirement to deliver a quantifiable result. For an entropy collector there are a number of ways of meeting the requirement. 1. Constrain access to the device and audit all users of the device. 2. set the contract in the read() call such that the bits returned may be internally entangled, but must not be entangled with any other read(). This can trivially be met by locking the device for single read access, and resetting the pool after every read. Slow, but it's what the caller wanted! Better variants can be experimented on... Now I don't remember anybody suggesting that before! Perfect, except that an attacker knows when to begin watching, and is assured that anything before s/he began watching was tossed. That seems to address the trivial implementation rather than the requirement? (In practice, I'd be inclined to not so much reset the pool after every read, but flush or discard a certain amount that is calculated to reduce any cross read leakage. But yes, the requirement may prove to present some interesting challenges to the implementor.) In my various key generation designs using MD5, I've always used MD-strengthening to minimize the entanglement between keys. There was MD5 code floating around for many many years that I wrote with a NULL argument to force the MD-strengthening phase between uses. I never liked designs with bits for multiple keys extracted from the same digest iteration output. And of course, my IPsec authentication RFCs all did the same. See my IP-MAC design at RFC-1852 and RFC-2841. Zooko and I struck this issue in our recent SDP1. As a datagram secret key layout, it uses a lot of secret keying material. The way we resolved it was to set a requirement for quality in the key exchange phase, which derived from a requirement to reduce the complexities of the datagram encryption phase (for programming reasons, not crypto reasons); in effect we punted the problem upstairs and put all the load on the key exchange phase. iang -- News and views on what matters in finance+crypto: http://financialcryptography.com/ - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: entropy depletion (was: SSL/TLS passive sniffing)
William Allen Simpson wrote:
There are already other worthy comments in the thread(s).
This is a great post. One can't stress enough
that programmers need programming guidance,
not arcane information theoretic concepts.
We are using
computational devices, and therefore computational infeasibility is the
standard that we must meet. We _NEED_ unpredictability rather than
pure entropy.
By this, do you mean that /dev/*random should deliver
unpredictability, and /dev/entropy should deliver ...
pure entropy?
So, here are my handy practical guidelines:
(1) As Metzger so wisely points out, the implementations of /dev/random,
/dev/urandom, etc. require careful auditing. Folks have a tendency to
improve things over time, without a firm understanding of the
underlying requirements.
Right, but in the big picture, this is one of those
frequently omitted steps. Why? Coders don't have
time to acquire the knowledge or to incorporate
all the theory of RNG in, and as much of today's
software is based on open source, it is becoming the
baseline that no theoretical foundation is required
in order to do that work. Whereas before, companies
c/would make a pretence at such a foundation, today,
it is acceptable to say that you've read the Yarrow
paper and are therefore qualified.
I don't think this is a bad thing, I'd rather have a
crappy /dev/random than none at all. But if we
are to improve the auditing, etc, what we would
need is information on just _what that means_.
E.g., a sort of webtrust-CA list of steps to take
in checking that the implementation meets the
desiderata.
(2) The non-blocking nature of /dev/urandom is misunderstood. In fact,
/dev/urandom should block while it doesn't have enough entropy to reach
its secure state. Once it reaches that state, there is no future need
to block.
If that's the definition that we like then we should
create that definition, get it written in stone, and
start clubbing people with it (*).
(2A) Of course, periodically refreshing the secure state is a good
thing, to overcome any possible deficiencies or cycles in the PRNG.
As long as this doesn't effect definition (2) then it
matters not. At the level of the definition, that is,
and this note belongs in the implementation notes
as do (2B), (2C).
(2B) I like Yarrow. I was lucky enough to be there when it was first
presented. I'm biased, as I'd come to many of the same conclusions,
and the strong rationale confirmed my own earlier ad hoc designs.
(2C) Unfortunately, Ted Ts'o basically announced to this list and
others that he didn't like Yarrow (Sun, 15 Aug 1999 23:46:19 -0400). Of
course, since Ted was also a proponent of 40-bit DES keying, that depth
of analysis leads me to distrust anything else he does. I don't know
whether the Linux implementation of /dev/{u}random was ever fixed.
( LOL... Being a proponent of 40-bit myself, I wouldn't
be so distrusting. I'd hope he was just pointing out
that 40-bits is way stronger than the vast majority
of traffic out there; that which we talked about here
is buried in the noise level when it comes to real effects
on security simply because it's so rare. )
(3) User programs (and virtually all system programs) should use
/dev/urandom, or its various equivalents.
(4) Communications programs should NEVER access /dev/random. Leaking
known bits from /dev/random might compromise other internal state.
Indeed, /dev/random should probably have been named /dev/entropy in the
first place, and never used other than by entropy analysis programs in
a research context.
I certainly agree that overloading the term 'random'
has caused a lot of confusion. And, I think it's an
excellent idea to abandon hope in that area, and
concentrate on terms that are useful.
If we can define an entropy device and present
that definition, then there is a chance that the
implementors of devices in Unixen will follow that
lead. But entropy needs to be strongly defined in
practical programming terms, along with random
and potentially urandom, with care to eliminate
such crypto academic notions as information
theoretic arguments and entropy reduction.
(4A) Programs must be audited to ensure that they do not use
/dev/random improperly.
(4B) Accesses to /dev/random should be logged.
I'm confused by this aggresive containment of the
entropy/random device. I'm assuming here that
/dev/random is the entropy device (better renamed
as /dev/entropy) and Urandom is the real good PRNG
which doesn't block post-good-state.
If I take out 1000 bits from the *entropy* device, what
difference does it make to the state? It has no state,
other than a collection of unused entropy bits, which
aren't really state, because there is no relationship
from one bit to any other bit. By definition. They get
depleted, and more gets collected, which by definition
are unrelated.
Why then restrict it to non-communications usages?
What does it matter if an SSH daemon leaks bits used
in its *own* key generation if those bits can never be
Re: entropy depletion (was: SSL/TLS passive sniffing)
On Sat, Jan 08, 2005 at 10:46:17AM +0800, Enzo Michelangeli wrote: But that was precisely my initial position: that the insight on the internal state (which I saw, by definition, as the loss of entropy by the generator) that we gain from one bit of output is much smaller than one full bit. I think this last bit is untrue. You will find that the expected number of states of the PRNG after extracting one bit of randomness is half of the number of states you had before, thus resulting in one bit of entropy loss. -- Taral [EMAIL PROTECTED] This message is digitally signed. Please PGP encrypt mail to me. A: Because it fouls the order in which people normally read text. Q: Why is top-posting such a bad thing? A: Top-posting. Q: What is the most annoying thing on usenet and in e-mail? pgpEGgoI4O221.pgp Description: PGP signature
Re: entropy depletion
Ian G wrote: (4A) Programs must be audited to ensure that they do not use /dev/random improperly. (4B) Accesses to /dev/random should be logged. I'm confused by this aggresive containment of the entropy/random device. I'm assuming here that /dev/random is the entropy device (better renamed as /dev/entropy) and Urandom is the real good PRNG which doesn't block post-good-state. Yes, that's my assumption (and practice for many years). If I take out 1000 bits from the *entropy* device, what difference does it make to the state? It has no state, other than a collection of unused entropy bits, which aren't really state, because there is no relationship from one bit to any other bit. By definition. They get depleted, and more gets collected, which by definition are unrelated. If we could actually get such devices, that would be good. In the real world, /dev/random is an emulated entropy device. It hopes to pick up bits and pieces of entropy and mashes them together. In common implementations, it fakes a guess of the current level of entropy accumulated, and blocks when depleted. If there really were no relation to the previous output -- that is, a _perfect_ lack of information about the underlying mechanism, such as the argument that Hawking radiation conveys no information out of black holes -- then it would never need to block, and there would never have been a need for /dev/urandom! (Much smarter people than I have been arguing about the information theoretic principles of entropy in areas of physics and mathematics for a very long time.) All I know is that it's really hard to get non-externally-observable sources of entropy in embedded systems such as routers, my long-time area of endeavor. I'm happy to add in externally observable sources such as communications checksums and timing, as long as they can be mixed in unpredictable ways with the internal sources, to produce the emulated entropy device. Because it blocks, it is a critical resource, and should be logged. After all, a malicious user might be grabbing all the entropy as a denial of service attack. Also, a malicious user might be monitoring the resource, looking for cases where the output isn't actually very random. In my experience, rather a lot of supposed sources of entropy aren't very good. Why then restrict it to non-communications usages? Because we are starting from the postulate that observation of the output could (however remotely) give away information about the underlying state of the entropy generator(s). What does it matter if an SSH daemon leaks bits used in its *own* key generation if those bits can never be used for any other purpose? I was thinking about cookies and magic numbers, generally transmitted verbatum. However, since we have a ready source of non-blocking keying material in /dev/urandom, it seems to be better to use that instead of the blocking critical resource -- William Allen Simpson Key fingerprint = 17 40 5E 67 15 6F 31 26 DD 0D B9 9B 6A 15 2C 32 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: entropy depletion (was: SSL/TLS passive sniffing)
- Original Message - From: [EMAIL PROTECTED] To: cryptography@metzdowd.com Sent: Friday, January 07, 2005 9:30 AM Subject: Re: entropy depletion (was: SSL/TLS passive sniffing) From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Enzo Michelangeli Sent: Tuesday, January 04, 2005 7:50 PM This entropy depletion issue keeps coming up every now and then, but I still don't understand how it is supposed to happen. If the PRNG uses a really non-invertible algorithm (or one invertible only with intractable complexity), its output gives no insight whatsoever on its internal state. I see much misunderstanding of entropy depletion and many misstatements because of it. It is true you don't know what the internal state is but the number of possible internal states tends to reduce with every update of the internal state. See Random Mapping Statistics by Philippe Flajolet and Andrew M. Odlyzko (Proceedings of the workshop on the theory and application of cryptographic techniques on Advances in cryptology, Houthalen, Belgium, Pages: 329 - 354, year 1990) for a thorough discussion. [...] In the real world, our PRNG state update functions are complex enough that we don't know if they are well behaved. Nobody knows how many cycles exist in a PRNG state update function using, for example, SHA-1. You run your PRNG long enough and you may actually hit a state that, when updated, maps onto itself. When this occurs your PRNG will start producing the same bits over and over again. It would be worse if you hit a cycle of 10,000 or so because you may never realize it. I don't know of any work on how not-so well behaved PRNG state update function lose entropy. But that was precisely my initial position: that the insight on the internal state (which I saw, by definition, as the loss of entropy by the generator) that we gain from one bit of output is much smaller than one full bit. However, I've been convinced by the argument broght by John and others - thanks guys - that we should not mix the concept of entropy with issues of computational hardness. That said, however, I wonder if we shouldn't focus more, for practical purposes, on the replacement concept offered by John of usable randomness, with a formal definition allowing its calculation in concrete cases (so that we may assess the risk deriving from using a seeded PRNG rather than a pure RNG in a more quantitative way). The paper you mention appears to go in that direction. Enzo - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: entropy depletion
Zooko O'Whielacronx wrote: I would love to have an information-theoretic argument for the security of my PRNG, but that's not what we have, Yes, and I'd like my goldfish to ride a bicycle, but he can't. The P in PRNG is for Pseudo, and means the PRNG is relying on computational intractability, not entropy. and I don't think reducing the entropy_count by one bit per output bit gets us any closer to such an argument. For PRNGs that's true ... which is why I have introduced the terminology of SRNG, meaning Stretched RNG, which is a hermaphrodite, being partly PRNG and partly HESG. Linux /dev/urandom is an early and less-than-satisfactory attempt at a SRNG. Yarrow is vastly better. For starters, the entropy_count value before you output the bit is obviously not a measure of the real information-theoretic entropy in the PRNG's state. It is a guess implemented by a simple algorithm (the entropy estimator). So if we set the resulting entropy_count after outputting one bit to be equal to the previous entropy_count - 1, we really have no justification for thinking that the resulting entropy_count is any closer to the true information-theoretic entropy than if you had set it equal to the previous entropy_count - 2. On the other hand, I've haven't heard an information-theoretic argument that the output bit contains a whole bit of entropy. Well, that depends on details. Suppose you seed your PRNG with 1000 bits of entropy, and then put out 50,000 bits of output. For one typical class of PRNGs, which includes linux /dev/urandom and excludes yarrow, the first 1000 bits of output will use up all the entropy, in the sense that the mapping from seeds to output-strings will be very nearly one-to-one. To say the same thing another way, the adversaries are trying to find the seed by brute-force search of seed-space, if they've guessed the wrong seed they'll know it with very high probability after seeing the first 1000 bits of output. (They could also wait and know the same thing from the second 1000 bits of output, so we can have metaphysical arguments about just where the entropy resides ... but since the adversaries get to see the output stream in order, our minimax strategy is to assume they are not stupid and have used the first 1000 bits to reduce *their* entropy. The number that I'm decrementing by one bit per bit is my minimax estimate of the adversaries' entropy. If you have some other number that you would like to decrement by some other rule, that's fine ... but I think I'm doing the right thing with my number.) Yarrow, in contrast, might well be configured to use only 100 bits of entropy for the first 50,000 bits of output, and then reseed itself with another 100 bits for the second 50,000 bits of output. This leads to a notion of average entropy density of the output, which is greater than zero but less than 100%. There is a nice practical-cryptography argument that an observer gains a whole bit of information from seeing that output bit, but in pure information-theoretic terms an observer gains less than one bit of information from seeing that output. So perhaps when you output a bit from /dev/random you ought to decrement entropy_count by 0.9 instead? That is not minimax, as explained above. In general, I've heard no persuasive information-theoretic argument to justify the practice of decrementing the entropy_count by 1 bit per bit. See above. If that practice does indeed ever protect someone from a cryptanalytic attack on their PRNG, it will not be because the practice is Information Theoretically Correct, but because the entropy_count-bits-added-per-input-bit minus the entropy_count-bits-subtracted-per-output-bit were an engineering fudge factor that was turned up high enough to drown out the cryptanalytic weakness in the PRNG. I'm not sure I would have said it that way, but I might agree with the sentiment. If the PRNG were secure against cryptanalysis, including practical cryptanalysis such as peeking at the state vector, then you wouldn't need more than an infinitesimal entropy density. Of course using such a fudge factor has some other costs, including the cost of introducing new security risks. I estimate that the chance of a successful attack due to timing attacks, induced failure, taking advantage of accidental failure, social engineering, etc. outweighs the chance of a successful attack due to cryptanalysis of the PRNG, which is why I use /dev/urandom exclusively [*, **]. You may weigh those trade-offs differently, but you shouldn't think that by decrementing entropy_count you are achieving information-theoretic security. [*] Of course I have to be aware of the regrettable possibility that /dev/urandom has *never* been properly seeded and protect against that in user space. [**] ... and the possibility that the operating system is re-using stored random state which it already used just before an unclean shutdown. Meanwhile, implementing a High
Re: entropy depletion (was: SSL/TLS passive sniffing)
From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Enzo Michelangeli Sent: Tuesday, January 04, 2005 7:50 PM This entropy depletion issue keeps coming up every now and then, but I still don't understand how it is supposed to happen. If the PRNG uses a really non-invertible algorithm (or one invertible only with intractable complexity), its output gives no insight whatsoever on its internal state. I see much misunderstanding of entropy depletion and many misstatements because of it. It is true you don't know what the internal state is but the number of possible internal states tends to reduce with every update of the internal state. See Random Mapping Statistics by Philippe Flajolet and Andrew M. Odlyzko (Proceedings of the workshop on the theory and application of cryptographic techniques on Advances in cryptology, Houthalen, Belgium, Pages: 329 - 354, year 1990) for a thorough discussion. The jist is that a well behaved state update function for a PRNG will have one very long cycle. This cycle will be shorter than the number of possible values that the state can hold. States not on the cycle are on branches of states that eventually land on the cycle. Flajolet and Odlyzko go on to show that the expected cycle length for a 1000 bit state will be around 2^500 iterations. So, you start your PRNG by filling the state with 1000 bits of real entropy. You have 2^1000 possible states. You use your PRNG and update the state. Now, there are a certain number of states that the PRNG cannot be in. After one state update, the PRNG cannot be in the states at the ends of the chains of states branched off from the aforementioned cycle. This means that, after one state update, you have slightly less than 1000 bits of entropy. When you update the state again, you now have more states that the PRNG cannot be in, thus reducing your entropy again. Every time you use your PRNG, you reduce your entropy in this way and you keep on doing so in an asymptotic way until, after many many iterations, you are close enough to 500 bits that you don't care anymore. In the real world, our PRNG state update functions are complex enough that we don't know if they are well behaved. Nobody knows how many cycles exist in a PRNG state update function using, for example, SHA-1. You run your PRNG long enough and you may actually hit a state that, when updated, maps onto itself. When this occurs your PRNG will start producing the same bits over and over again. It would be worse if you hit a cycle of 10,000 or so because you may never realize it. I don't know of any work on how not-so well behaved PRNG state update function lose entropy. I figure the state update functions we as a community use in what we consider to be well designed PRNGs probably have multiple long cycles and maybe a few scary short cycles that are so unlikely that nobody has hit them. I don't even know what multiple cycles means for entropy. Because of the lack of knowledge, cryptographic PRNGs have more state than they probably need just to assure enough entropy - at least that is one thing I look for when looking at cryptographic PRNGs. -Michael Heyman - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: entropy depletion (was: SSL/TLS passive sniffing)
On Thu, Jan 06, 2005 at 04:35:05PM +0800, Enzo Michelangeli wrote: By how much exactly? I'd say, _under the hypothesis that the one-way function can't be broken and other attacks fail_, exactly zero; in the real world, maybe a little more. Unfortunately for your analysis, *entropy* assumes that there is infinite compute capacity. From an information-theoretic point of view, there is NO SUCH THING as a perfect one-way function. -- Taral [EMAIL PROTECTED] This message is digitally signed. Please PGP encrypt mail to me. A: Because it fouls the order in which people normally read text. Q: Why is top-posting such a bad thing? A: Top-posting. Q: What is the most annoying thing on usenet and in e-mail? pgpRflyK9JPXi.pgp Description: PGP signature
Re: entropy depletion (was: SSL/TLS passive sniffing)
| You're letting your intuition about usable randomness run roughshod
| over the formal definition of entropy. Taking bits out of the PRNG
| *does* reduce its entropy.
|
| By how much exactly? I'd say, _under the hypothesis that the one-way
| function can't be broken and other attacks fail_, exactly zero; in the
| real world, maybe a little more. But in
| /usr/src/linux/drivers/char/random.c I see that the extract_entropy()
| function, directly called by the exported kernel interface
| get_random_bytes(), states:
|
| if (r-entropy_count / 8 = nbytes)
| r-entropy_count -= nbytes*8;
| else
| r-entropy_count = 0;
|
| ...which appears to assume that the pool's entropy (the upper bound of
| which is POOLBITS, defined equal to 4096) drops by a figure equal to the
| number of bits that are extracted (nbytes*8). This would only make sense
| if those bits weren't passed through one-way hashing.
The argument you are making is that because the one-way function isn't
reversible, generating values from the pool using it doesn't decrease its
computational entropy. (Its mathematical entropy is certainly depleted,
since that doesn't involve computational difficulty. But we'll grant that
that doesn't matter.)
The problem with this argument is that it gives you no information about the
unpredictablity of the random numbers generated. Here's an algorithm based
on your argument:
Pool: bits[512]
initializePool()
{ Fill Pool with 512 random bits; }
getRandom() : bits[160]
{ return(SHA(bits));
}
By your argument, seeing the result of a call to getRandom() does not reduce
the effective entropy of the pool at all; it remains random. We certainly
believe that applying SHA to a random collection of bits produces a random
value. So, indeed, the result of getRandom() is ... random. It's also
constant.
Granted, no one would implement a random number generator this way. But
*why*? What is it you have to change to make this correct? Why? Can you
prove it? Just saying you have to change the pool after every call
won't work:
getRandom() : bits[160]
{ Rotate bits left by 1 bit;
return(SHA(bits));
}
This (seems to) generated 512 random values, then repeats. Just what *is*
good enough?
-- Jerry
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: entropy depletion
Jerrold Leichter asked: random number generator this way. Just what *is* good enough? That's a good question. I think there is a good answer. It sheds light on the distinction of pseudorandomness versus entropy: A long string produced by a good PRNG is conditionally compressible in the sense that we know there exists a shorter representation, but at the same time we believe it to be conditionally incompressible in the sense that the adversaries have no feasible way of finding a shorter representation. In contrast, A long string produced by a HESG is unconditionally, absolutely incompressible. There does not exist a shorter representation. There cannot possibly exist a shorter representation. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: entropy depletion
| | random number generator this way. Just what *is* | good enough? | | That's a good question. I think there is a good answer. It | sheds light on the distinction of pseudorandomness versus | entropy: | | A long string produced by a good PRNG is conditionally | compressible in the sense that we know there exists a shorter | representation, but at the same time we believe it to be | conditionally incompressible in the sense that the adversaries | have no feasible way of finding a shorter representation. | | In contrast, | | A long string produced by a HESG is unconditionally, absolutely | incompressible. There does not exist a shorter representation. | There cannot possibly exist a shorter representation. You're using Kolgomorv/Chaitin complexity here, but unfortunately that's a bit hard to apply. *Any* string has a shorter representation - if I get to specify the model *after* you choose the string. K/C complexity is robust when you talk about sets of possible strings, because playing around with the machine can only shorten a fixed number of them. Turning that into a notion useful for cryptography is a bit tougher - and in any case, if you want to get at PRNG's, you need to get at K/C complexity with trapdoor information: The bit stream may *look* uncompressible, but given the internal state, it is easily produced. More generally: We're talking about stretching entropy here. There are certainly theoretical results in that direction, the one usually mentioned being the BBS bit generator, which takes k bits of entropy and gives you p(k) (for some polynomial p) bits that are polynomially-indistinguishable from random bits. But you (a) need some significant work to set this up and prove it; (b) BBS generators are slow. A simpler approach that does work (in some sense) is: Choose a random starting value R, and a number k. Compute SHA^i(R) for i from 0 to k. Emit these values *backwards*. Then given the first k-1 outputs, an attacker cannot determine the next one (under the standard hypotheses about SHA). Unfortunately, this is useless as, say, a key generator: If you send me the k-1'st output for use as a key, I can't determine what your *next* key will be - but I can trivially read your preceding k-2 sessions. The idea that revealing just the hash of random bits doesn't reduce the effective entropy sounds great, but it's naive. It's like the argument that if H is a good hash function, then H(K || message) is a good MAC. Not quite. -- Jerry - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: entropy depletion (was: SSL/TLS passive sniffing)
From: John Denker [EMAIL PROTECTED] Sent: Jan 5, 2005 2:06 PM To: Enzo Michelangeli [EMAIL PROTECTED] Cc: cryptography@metzdowd.com Subject: Re: entropy depletion (was: SSL/TLS passive sniffing) ... You're letting your intuition about usable randomness run roughshod over the formal definition of entropy. Taking bits out of the PRNG *does* reduce its entropy. This may not (and in many applications does not) reduce its ability to produce useful randomness. Right. The critical question is whether the PRNG part gets to a secure state, which basically means a state the attacker can't guess in the amount of work he's able to do. If the PRNG gets to a secure state before generating any output, then assuming the PRNG algorithm is secure, the outputs are indistinguishable from random. The discussion of how much fresh entropy is coming in is sometimes a bit misleading. If you shove 64 bits of entropy in, then generate a 128-bit output, then shove another 64 bits of entropy in, you don't end up in a secure state, because an attacker can guess your first 64 bits of entropy from your first output. What matters is how much entropy is shoved in between the time when the PRNG is in a known state, and the time when it's used to generate an output. --John Kelsey - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: entropy depletion
I wrote: A long string produced by a good PRNG is conditionally compressible in the sense that we know there exists a shorter representation, but at the same time we believe it to be conditionally incompressible in the sense that the adversaries have no feasible way of finding a shorter representation. In contrast, A long string produced by a HESG is unconditionally, absolutely incompressible. There does not exist a shorter representation. There cannot possibly exist a shorter representation. Jerrold Leichter wrote: You're using Kolgomorv/Chaitin complexity here, but unfortunately that's a bit hard to apply. It works for me. It is in principle hard to apply exactly, but in practice it's easy to apply to a good-enough approximation. In particular, for any given PRNG I can readily exhibit the compressed representation of its output, namely the PRNG itself along with the initial internal state. K/C complexity is robust when you talk about sets of possible strings, because playing around with the machine can only shorten a fixed number of them. Yes, I stand corrected. I sloppily wrote string when I should have written strings. Specifically, the set of strings collectively cannot be compressed at all. As for each string individually, it is not compressible either, except possibly for trivially rare cases and/or trivial amounts of compression. *Any* string has a shorter representation - if I get to specify the model *after* you choose the string. Yes, for one particular string, or very small set of strings. You get to choose the model, but you only get to choose once. So you can only compress a trivially small subset of all the output strings, unless we're talking about a trivial degree of compression. In any case, you derive no cryptanalytic advantage from compression based on an ad-hoc model, so you might as well not bother, and just stick to some convenient standard model. Turning that into a notion useful for cryptography is a bit tougher - and in any case, if you want to get at PRNG's, you need to get at K/C complexity with trapdoor information: The bit stream may *look* uncompressible, but given the internal state, it is easily produced. Isn't that what I said, as quoted above? I said it was conditionally compressible. It should go without saying that knowing the trapdoor information, i.e. the internal state, is the sufficient condition for feasible compressibility. More generally: We're talking about stretching entropy here. Well, I can agree that that's what we _should_ be talking about. I like to speak of an SRNG (stretched random number generator) as having a nonzero lower bound on the entropy density of the output, as opposed to a traditional PRNG where the entropy density is asymptotically zero. There are certainly theoretical results in that direction, the one usually mentioned being the BBS bit generator, which takes k bits of entropy and gives you p(k) (for some polynomial p) bits that are polynomially-indistinguishable from random bits. But you (a) need some significant work to set this up and prove it; (b) BBS generators are slow. A simpler approach that does work (in some sense) is: Choose a random starting value R, and a number k. Compute SHA^i(R) for i from 0 to k. Emit these values *backwards*. Then given the first k-1 outputs, an attacker cannot determine the next one (under the standard hypotheses about SHA). Unfortunately, this is useless as, say, a key generator: If you send me the k-1'st output for use as a key, I can't determine what your *next* key will be - but I can trivially read your preceding k-2 sessions. When I wanted to stretch entropy, I implemented the Yarrow approach, i.e. encrypted counter plus systematic reseeding: http://www.av8n.com/turbid/paper/turbid.htm#sec-srandom It's not slow, and appears incomparably stronger than the SHA^i example. Indeed it does not have any serious weaknesses that I know of. If anybody knows of any flaws, please explain! The idea that revealing just the hash of random bits doesn't reduce the effective entropy sounds great, but it's naive. We agree it's naive. Indeed it's just wrong, as I've said N times over the last couple of days. And please let's not talk about effective entropy. I have no idea what ineffective entropy is supposed to be, and I can't imagine any way that makes sense to distinguish effective entropy from plain old entropy. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: entropy depletion (was: SSL/TLS passive sniffing)
- Original Message - From: John Denker [EMAIL PROTECTED] Sent: Thursday, January 06, 2005 3:06 AM Enzo Michelangeli wrote: [...] If the PRNG uses a really non-invertible algorithm (or one invertible only with intractable complexity), its output gives no insight whatsoever on its internal state. That is an invalid argument. The output is not the only source of insight as to the internal state. As discussed at http://www.av8n.com/turbid/paper/turbid.htm#sec-prng-attack attacks against PRNGs can be classified as follows: 1. Improper seeding, i.e. internal state never properly initialized. 2. Leakage of the internal state over time. This rarely involves direct cryptanalytic attack on the one-way function, leading to leakage through the PRNGs output channel. More commonly it involves side-channels. 3. Improper stretching of limited entropy supplies, i.e. improper reseeding of the PRNG, and other re-use of things that ought not be re-used. 4. Bad side effects. There is a long record of successful attacks against PRNGs (op cit.). Yes, but those are implementation flaws. Also a true RNG could present weaknesses and be attacked (e.g., with strong EM fields overcoming the noise of its sound card; not to mention vulnerabilities induced by the quirks you discuss at http://www.av8n.com/turbid/paper/turbid.htm#sec-quirks). Anyway, I was not saying RNG's are useless because PRNG's are more than enough: the scope of my question was much narrower, and concerned the concept of entropy depletion. I'm not saying that the problems cannot be overcome, but the cost and bother of overcoming them may be such that you decide it's easier (and better!) to implement an industrial-strength high-entropy symbol generator. Sure, I don't disagree with that. As entropy is a measure of the information we don't have about the internal state of a system, That is the correct definition of entropy ... but it must be correctly interpreted and correctly applied; see below. it seems to me that in a good PRNGD its value cannot be reduced just by extracting output bits. If there is an entropy estimator based on the number of bits extracted, that estimator must be flawed. You're letting your intuition about usable randomness run roughshod over the formal definition of entropy. Taking bits out of the PRNG *does* reduce its entropy. By how much exactly? I'd say, _under the hypothesis that the one-way function can't be broken and other attacks fail_, exactly zero; in the real world, maybe a little more. But in /usr/src/linux/drivers/char/random.c I see that the extract_entropy() function, directly called by the exported kernel interface get_random_bytes(), states: if (r-entropy_count / 8 = nbytes) r-entropy_count -= nbytes*8; else r-entropy_count = 0; ...which appears to assume that the pool's entropy (the upper bound of which is POOLBITS, defined equal to 4096) drops by a figure equal to the number of bits that are extracted (nbytes*8). This would only make sense if those bits weren't passed through one-way hashing. Perhaps, a great deal of blockage problems when using /dev/random would go away with a more realistic estimate. Enzo - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: entropy depletion
I wrote: Taking bits out of the PRNG *does* reduce its entropy. Enzo Michelangeli wrote: By how much exactly? By one bit per bit. I'd say, _under the hypothesis that the one-way function can't be broken and other attacks fail_, exactly zero; in the real world, maybe a little more. If you said that, you'd be wrong. This is getting repetitious. As I said before, this is an abuse of the terminology. If you want to quantify the goodness of your PRNG, go right ahead, but please don't apply the word entropy to it. The word is already taken. It means something very specific. But in /usr/src/linux/drivers/char/random.c I see that the extract_entropy() function, directly called by the exported kernel interface get_random_bytes(), states: if (r-entropy_count / 8 = nbytes) r-entropy_count -= nbytes*8; else r-entropy_count = 0; ...which appears to assume that the pool's entropy (the upper bound of which is POOLBITS, defined equal to 4096) drops by a figure equal to the number of bits that are extracted (nbytes*8). This would only make sense if those bits weren't passed through one-way hashing. The linux /dev/random driver has lots of problems, but that's not one of them. That makes perfect sense. Anything else would not make sense. That's what entropy is. If you're not interested in entropy, then go measure whatever you are interested in, but don't call it entropy. Perhaps, a great deal of blockage problems when using /dev/random would go away with a more realistic estimate. 100% of the blocking problems go away if you use /dev/urandom to the exclusion of /dev/random. For the Nth time: a) Most of modern cryptography is based on notions of computational intractability. I'm not saying that's good or bad; it is what it is. b) My point is that there is an entirely different set of notions, including the notion of entropy and the related of unicity distance, which have got *nothing* to do with computational intractability. You can study (a) if you like, or (b) if you like, or both. Maybe (a) is best suited to your application, or maybe (b). But whatever you do, please don't mistake one for the other. Lots of things have large amounts of usable randomness, with little or no entropy. Please don't mistake one for the other. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
