Other Directory Sites: SeekWonder | Directory Owners Forum
The following archive was created by hippie-mail 7.98617-22 on Fri Aug 21 1998 - 17:20:20 ADT
bram (bram@gawth.com)
Tue, 14 Jul 1998 00:30:31 -0700 (PDT)
On 14 Jul 1998, Cicero wrote:
> If the attacker resubmits seeds later that are identical to earlier
> ones (whether either his or yours), but after an output has occurred,
> then I do not see how cycling can be induced. The reason being that
> the state has been hashed.
The attack I'm worried about is one where the attacker has already
completely cracked everything in the system (knows internal state,
controls inputs, knows when outputs happen) and is now attempting to
induce statistical bias in it's output. Clearly some statistical bias will
be easy to induce, it's a matter of how much. Granted, this is sort of
like worrying how far apart your body parts will land after a really bad
auto accident.
Now that I've phrased it that way, it's clear a better way of fixing that
problem is to xor all outputs with a statistically good if
cryptographically unsound PRNG. So I guess you're right about the extra
hash being unnecessary. Does anybody have any thoughts as to when (or
whether) xoring with a weaker PRNG is worthwile?
(I didn't realize how weak my attack is before really thinking it through
- similar techniques are much more powerful against only slightly
different PRNG algorithms.)
Without the extra hash, the PRNG works as follows:
To incorporate new data, hash the data and xor the result into the pool.
To produce an output, first compute the hash of the negation of the
internal state, this will be the result. Then replace the pool with it's
own hash and return the result.
> Note that we are both assuming the hash we are using has the property
> that if an attacker is given hash( ~state ), it is computationally
> infeasible to derive any information about hash( state ). This sounds
> reasonable to me. I use ~ to denote your negation.
Good point. A hash constructed by xoring the some strong hash function of
x with the same function of ~x is trivially weak in that way.
> Here is another proposal for how to state the property:
>
> A cryptographically strong reseedable PRNG must have the property that
> if all output preceding and following the bit in question is known,
> and all reseeding data is known, but the original state is secret,
> there is no compromise (ability to predict the bit in question),
> assuming that the original state had sufficient entropy.
It also must be able to withstand an attacker who can feed in inputs
adaptively.
> With the current state of technology, sufficient entropy would be 80
> to 160 bits, depending on the threat model.
When is it either one? If an application is getting fed strings which only
contain small amounts of entropy, it's necessary to set up two PRNGs, the
first one of which simply acts as a collection area for entropy, it's
output being fed into the 'main' PRNG which is used for output. How much
new entropy should one wait to be put into the collection area before
using it to reseed main, 80 or 160 bits?
I think it's possible to streamline the two PRNGs together, but haven't
given any thought as to how yet.
-Bram
The following archive was created by hippie-mail 7.98617-22 on Fri Aug 21 1998 - 17:20:20 ADT