Re: why compression doesn't perfectly even out entropy

>Is it possible to find a percentage of the key space to eliminate that
>will optimize security assuming that the attacker will try the easy
>stuff first (and is it possible to quantify "easy stuff")?

If you eliminate all repeating byte sequences, such as 00 00 or 7F 7F, you
will reduce your possible entropy by .07058% (7.99435 bits per byte), and
eliminate the (astronomically remote) possibility of Hamlet or some other
English text popping out of your RNG/PRNG.  As long as your key is long
enough to withstand this slight entropy reduction, you are still OK.

JonWienke@aol.com writes:
> >Is it possible to find a percentage of the key space to eliminate that
> >will optimize security assuming that the attacker will try the easy
> >stuff first (and is it possible to quantify "easy stuff")?
> 
> If you eliminate all repeating byte sequences, such as 00 00 or 7F 7F, you
> will reduce your possible entropy by .07058% (7.99435 bits per byte), and
> eliminate the (astronomically remote) possibility of Hamlet or some other
> English text popping out of your RNG/PRNG.  As long as your key is long
> enough to withstand this slight entropy reduction, you are still OK.

Before making pronouncements like "You are still OK" you ought to
learn a bit more about cryptanalysis. Its tiny little statistical
toeholds like that which permit breaks. I don't know for sure, but my
intuition says that there may very well be instances in which a couple
of little nicks like that into the entropy of a key are sufficient to
radically lower the time to crack something. Since there are far
better techniques available (hash distillation, for instance) for
assuring the quality of a random stream, Jon's suggested techniques
should be regarded as unnecessary and dangerous.

PUBLIC SERVICE ANNOUNCEMENT:

For the benefit of everyone reading, I've become increasingly
convinced that Jon really doesn't understand the topic he's working on
well enough to trust, and he doesn't have the sense to know that he
doesn't understand it well enough. I know enough to know that I'm
extremely ignorant -- he's ignorant enough to think that he knows more
than he does. I don't mean to insult Jon -- I'm sure that in his own
field whatever it is he's a smart enough guy, and he seems like a nice
enough fellow -- but cryptography is a dangerous business -- bad
technique KILLS, literally. Until Mr. Wienke loses his bad case of
hubris I would suggest not taking his technical suggestions.

Perry

In article <199604181352.JAA08215@jekyll.piermont.com>,
Perry E. Metzger <perry@piermont.com> wrote:
> > If you eliminate all repeating byte sequences, such as 00 00 or 7F 7F, you
> > will reduce your possible entropy by .07058% (7.99435 bits per byte), and
> > eliminate the (astronomically remote) possibility of Hamlet or some other
> > English text popping out of your RNG/PRNG. [...]
> 
> Before making pronouncements like "You are still OK" you ought to
> learn a bit more about cryptanalysis. [...]

Then I propose the following scheme.  (I've proposed it before.)

My entropy cruncher takes in random noise from a number of diverse
sources (some possibly of dubious quality).  I take *all* the noise
and run it through a hash function to distill entropy.

Now I need to have some method to estimate when I have enough entropy
in the random noise I'm crunching.  First rule: be conservative.
One can never have too much entropy in the input to the hash function.

Therefore, I suggest making a *copy* of the input noise stream,
running it through Jon Wienke's "this shouldn't happen" filter, and
feeding the result to some entropy estimator.  When the entropy
estimator says "I've got 1000 bits of entropy", I stop crunching.

This is conservative design, folks.  Using Wienke's filter in this manner
can't be any weaker than not using it at all. (agreed?)

Now, you can go argue whether the extra design complexity is worth it,
if you like. <shrug>


P.S.  To forestall confusion, let me be explicit about what I'm *not*
proposing: I *don't* want you to apply Wienke's filter to the input or
output of the hash function.

Applying Wienke's filter to the random noise stream, to the input to
the hash function, or to the output to the hash function, is clearly
a bad idea.
(The mathematician says "clearly", knowing full well that, unfortunately,
some small part of the audience probably doesn't get it... <sigh>)

This is what the "POTP" snake oil folks were proposing-- they had
some "quality control" process they applied to the one-time pads
they generated.  I think they said they regularly eliminated 70%
of the pads as "defective".  This was supposed to be encouraging :-)

If you don't understand why the POTP "quality control" process was
laughable, let someone else design the entropy cruncher!!!

David Wagner writes:
> Therefore, I suggest making a *copy* of the input noise stream,
> running it through Jon Wienke's "this shouldn't happen" filter, and
> feeding the result to some entropy estimator.  When the entropy
> estimator says "I've got 1000 bits of entropy", I stop crunching.
> 
> This is conservative design, folks.  Using Wienke's filter in this manner
> can't be any weaker than not using it at all. (agreed?)

Unfortunately, I think his filter puts too high a bound on the
entropy. Put it this way: I think he's only giving you an upper
bound. Furthermore, he's using his technique because he's using
spinners as RNGs, which I have a substantial fear of.

However, you are correct that this mechanism is no worse than not
using it at all. However, it doesn't substitute for doing a thorough
systems analysis to try to figure out how much entropy there actually
is in your source.

Thus, to summarize, yes, I agree with your strict statement that using
the filter this way is not weaker than not using it at all, but I'm
not sure it is worthwhile in this case because it isn't sufficient.

> Applying Wienke's filter to the random noise stream, to the input to
> the hash function, or to the output to the hash function, is clearly
> a bad idea.

Agreed.

> (The mathematician says "clearly", knowing full well that, unfortunately,
> some small part of the audience probably doesn't get it... <sigh>)

Sad but true.

Perry