[19379] in cryptography@c2.net mail archive
Re: RNG quality verification
daemon@ATHENA.MIT.EDU (Philipp =?iso-8859-1?q?G=FChring?=)
Fri Dec 23 01:29:52 2005
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
From: Philipp =?iso-8859-1?q?G=FChring?= <pg@futureware.at>
To: "Travis H." <solinym@gmail.com>, cryptography@metzdowd.com
Date: Thu, 22 Dec 2005 21:35:50 +0100
In-Reply-To: <d4f1333a0512221024o25908a20h8f41f5a6f6e8bd88@mail.gmail.com>
X-MDaemon-Deliver-To: cryptography@metzdowd.com
Hi Travis,
> The only thing is, you cannot test in randomness,=20
That=B4s true, but I can test non-randomness. And if I don=B4t detect=20
non-randomness, I can assume randomness to a certain extent.
> and it is an abuse=20
> of statistics to make predictions about individual events --=20
Wasn=B4t that one of the reasons, why statistic was invented?
> they=20
> describe populations. The best thing you could do is combine them
> with a truly random source that you control. =20
I don=B4t control the software everyone is using on this world.
> Of course then your=20
> users may not trust you, so you have to do a cryptographically strong
> combination such that control of one of the inputs doesn't translate
> into control of the outputs. For example, you cannot simply XOR them
> or you could force the key to be anything of the same length by
> choosing an appropriate stream. Also, you could not do this with
> small input spaces or else exhaustive search is trivial (try every
> input until the output is what you want).
The problem is that I have to live with COTS (Common-off-the-shelf) softwar=
e=20
out there, that is generating the certificate requests. The only thing I ca=
n=20
do is create a blacklist or a whitelist of known bad or known good software=
,=20
to tell the users: Use this software, or don=B4t use that software.
> The best you could do is examine (reverse engineer) the RNGs in the
> products, and whatever seeds them, and then create tests for their
> nonrandom properties, and then see if the tests work. This would,
> however, not tell you anything you didn't already know once you had
> examined the internals. =20
Has anyone done this yet?
> You might be able to find structure in their=20
> outputs through blind application of general-purpose statistics, but
> it will likely take a great deal more output, even with supposedly
> sensitive statistics like double-sided Kolmogorov-Smirnof.
Hmm, every key should deliver about 1000 bits of randomness, I guess. How m=
any=20
bits should I collect for the tests in your opinion?
> As a pathological example, my RNG may output the text of the King
> James Bible, encrypted with AES-CBC using a counter as the key, and
> uniquified across instances by using a processor serial number or
> licence number as an IV. Unless you knew this, you would be
> hard-pressed to tell they were not random and in fact totally
> predictable to anyone who knows the "secret". If a general statistic
> could distinguish this from a random stream, I think it would imply a
> weakness in AES-CBC. The tests would likely fail until enough output
> was generated that it started to repeat itself. On the other hand, I
> could decrypt it with a counter and see what pops out, and all I'd
> have to do is distringuish the KJV from a random stream.
I guess someone would have noticed already, if Microsoft, Mozilla or OpenSS=
L=20
had done that.
Wait. How many LOC(lines of code) does the King James Bible have? Mozilla h=
ad=20
something like 13 Mio. LOC as far as I remember ... perhaps they really hid=
=20
the KJ Bible in it! ;-)
> I'd look at seeding techniques first, as that's an easy win.
> Predictable seed -> predictable output. If that bootstrap is wrong,
> you can treat everything else as an oracle and still get a good
> distinguisher.
Contrary to the normal challenge of developing a new random number generato=
r,=20
I don=B4t have the possibility to change the existing software, I just have=
to=20
evaluate them, and find out, whether it=B4s ok or not.
I first thought about a black-box test, by simply tracing in the operating=
=20
system where the software gets its numbers from. A open("/dev/random")=20
systemcall at the time of key generation might be a good hint for good rand=
om=20
numbers. But as Netscape proofed some years ago, you can=20
ch=3Dread(stream,&ch,1) one perfectly random number, and overwrite it with =
the=20
value 1 (which is not soo random anymore) in one single line of error, and=
=20
invisibly to the operating system failing to use the random numbers given.
So since the random numbers might be modified between gathering and using f=
or=20
the keypair, I thought that I need to evaluate the quality at the end of th=
e=20
keypair generation.
Best regards,
Philipp G=FChring
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
