[1858] in cryptography@c2.net mail archive
Re: testing your RNG
daemon@ATHENA.MIT.EDU (stewarts@ix.netcom.com)
Tue Nov 18 15:36:58 1997
From: stewarts@ix.netcom.com
Date: Tue, 18 Nov 1997 01:45:59 -0800
To: Zooko Journeyman <zooko@xs4all.nl>, cryptography@c2.net
Original-From: Bill Stewart <stewarts@ix.netcom.com>
In-Reply-To: <199711171646.RAA27841@xs1.xs4all.nl>
At 05:46 PM 11/17/1997 +0100, Zooko Journeyman wrote:
>Any suggestions on statistical methods for testing (P)RNG's?
>I know Knuth has lots of relevant ideas, which I am about to
>study up on, but I thought I would ask some practical
>cryptographers if there are any particularly insidious broken
>(P)RNG problems which can appear normal under automated
>inspection, and how to improve the automated, perhaps
>human-assisted inspection.
Well, as a cryptographer, I'd ask "what's your threat model?".
Are you looking for badly skewed data,
or subtle but patterned data that could be abused,
or patterns that will disrupt your Monte Carlo simulation accuracy,
or ways to detect a trapdoor hidden in an algorithm,
or ways to detect a trapdoor hidden in a string of random numbers?
The former's pretty easy to catch, the latter's probably impossible,
and the fourth one requires careful analysis.
Consider the series of numbers Hash( Key, i, Key), for i=0..N.
It should look extremely random if the hash is good,
and it's entirely predictable if you know the key.
Or 3DES(data=i,Key=K), i=0..N, if you prefer reversibility.
Some of these may interact with your block chaining methods
if you're not careful.
Thanks!
Bill
Bill Stewart, stewarts@ix.netcom.com
Regular Key PGP Fingerprint D454 E202 CBC8 40BF 3C85 B884 0ABE 4639
