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 (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
Re: entropy depletion (was: SSL/TLS passive sniffing)
Wondering how in the world we got into this endless debate, I went back
and re-read the entire thread(s). I think that early comments were
predictive, where Ian Grigg wrote:
... Crypto is
such a small part of security that most all crypto people
move across to general security once they realise there
isn't much work around for a pure crypto person. Which is
good, because only in the general security field can one
really make a difference, IMHO, because that's when starts
to understand what is needed, as opposed to what's cool.
It was Denker that jumped off into the realm of entropy density (again)
(Message-ID: <[EMAIL PROTECTED]>), recommending that nobody use
/dev/urandom. He's right about entropy in the strict theoretical sense,
but wrong about our _need_ for practical security.
As David Wagner wrote with regard to another such claim:
(That poster wants you to believe that, since /dev/urandom uses a
cryptographic-strength pseudorandom number generator rather than a
true entropy source, it is useless. Don't believe it. The poster is
confused and his claims are wrong.)
And John Kelsey recently wrote:
... 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.
There are already other worthy comments in the thread(s). We are using
computational devices, and therefore computational infeasibility is the
standard that we must meet. We _NEED_ "unpredictability" rather than
"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.
(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.
(2A) Of course, periodically refreshing the secure state is a good
thing, to overcome any possible deficiencies or cycles in the PRNG.
(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.
(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.
(4A) Programs must be audited to ensure that they do not use
/dev/random improperly.
(4B) Accesses to /dev/random should be logged.
--
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: 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 (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 (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 (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)
> 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)
- 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 PRNG’s 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 (was: SSL/TLS passive sniffing)
Enzo Michelangeli wrote: > > This "entropy depletion" issue keeps coming up every now and then, but I > still don't understand how it is supposed to happen. Then you're not paying attention. > 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 PRNG’s 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.). 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. > 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. This may not (and in many applications does not) reduce its ability to produce useful randomness. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
