Fw: PRNGs

["Marcel Popescu" <marcel@aiurea.com>]

It seems that this never got delivered...

----- Original Message -----
From: Marcel Popescu <marcel@aiurea.com>
To: <cypherpunks@openpgp.net>
Sent: Wednesday, March 08, 2000 10:24 AM
Subject: PRNGs


> Hi! I hope someone on this list can help me - I am not allowed to
subscribe
> to coderpunks (don't know why), and I haven't received any answer from
Bruce
> Schneier either.
>
> I am trying to implement the Yarrow PRNG (in Delphi, but it doesn't
> matter) - it is described somewhere inside www.counterpane.com - and I
have
> found something weird. Bear with me, this might be long.
>
> The structure of Yarrow, as I understand it, is this:
>
> - a counter (32 bits; if this is wrong, I can easily change it to 64 bits)
> - a key
> - an encryption function E with a key of k bits and a block of n bits
> (Twofish [k=256, n=128] and Blowfish [k=448, n=64] instead of 3DES - I
don't
> have a 3DES implementation - but I don't see how this could affect the
> result below)
> - a one-way function with m bits of output (SHA-1, m=160)
>
> To generate the next n bits of output,
>
> counter <- counter + 1 mod 2^n
> output <- Ek (counter)
>
> Everything up to here is ok. If I test this with DIEHARD, it passes all
> tests. The problem I have is caused by an indication in the Yarrow paper:
> the key should be "refreshed" from the output stream:
>
> after Pg <= 2^(n / 3) cycles, k <- k bits of output
>
> The paper recommends that Pg to be made very small - suggested value: 10.
> And if I do this, the PRNG *horribly* flunks several of the DIEHARD tests!
>
> If I increase Pg, this effect is diminished, up to the point that Pg = 512
> passes all the tests again.
>
> Now, can anybody explain me what did I do wrong? Or is the suggestion
> mistaken? [Note: I understand that a counter smaller than n bits will
reset
> sooner than expected; but it does whether Pg = 10 or 512, and there's no
> apparent problem with the latter value.]
>
> Thanks,
> Mark
>
> -----
> All inventions or works of authorship original to me, herein and past,
> are placed irrevocably in the public domain, and may be used or modified
> for any purpose, without permission, attribution, or notification.
>
>
>