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
Cicero (cicero@redneck.efga.org)
14 Jul 1998 03:54:16 -0000
On 13 Jul 1998, Bram wrote:
>On 13 Jul 1998, Cicero wrote:
>> Bram wrote:
>> >
>> >xor the resust with the contents of the pool, then hash the result to get
>> >the new contents of the pool.
>>
>> I think you can make this good method better by removing the second
>> hash.
>>
>> Am I missing some attack you are protecting against, or other
>> advantage you get, by the second hash?
>
>There's an attack I'm worried about.
>
>If an attacker finds out the internal state and can control the inputs to
>the PRNG, then by pelting it with a whole bunch of bitstrings to
>incorporate between requests for output he can cause the output to cycle.
>An obscure attack requiring several breaches to already have taken place,
>but since it's possible to stop it easily might as well.
One of us is still confused. It could be me; I don't find your
argument above convincing, though.
Recall that your iteration step was:
>A good way of getting random numbers out of the pool is to compute the
>hash of it's negation and use that as the random output, then hash it's
>non-negated value to get the new value for the pool.
For the record, I was not suggesting that you didn't need to hash
twice when iterating.
If you do my proposed simplification, and if you reseed twice with the
identical seed, without doing any output between reseedings, then the
seeds will cancel, and it will be as if you did not reseed at all.
There is an attack if the attacker can always add a cancelling seed
paired with your good seed. This would be a denial-of-reseeding, I
admit, but there would not be cycling.
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.
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.
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.
If the original state were leaked, but at least one reseeding had
sufficient entropy, output subsequent to that reseeding would be
secure.
With the current state of technology, sufficient entropy would be 80
to 160 bits, depending on the threat model.
Cicero
The following archive was created by hippie-mail 7.98617-22 on Fri Aug 21 1998 - 17:20:20 ADT