Randomness and the CRC


Path: news.io.com!news.eden.com!mr.net!news.maxwell.syr.edu!nntp.uio.no!mn5.swip.net!news
From: bo.doemstedt@mbox200.swipnet.se (Bo Dömstedt)
Newsgroups: sci.crypt
Subject: Re: Non-deterministic random generator for the PC
Date: Thu, 30 Oct 1997 11:25:53 GMT
Organization: Protego Information AB
Lines: 56
Message-ID: <345868af.706133259@nntpserver.swip.net>
References: <19971012014201.VAA24799@ladder01.news.aol.com> <19971014114700.HAA03888@ladder02.news.aol.com> <34438fd1.501392634@ntserv02> <344427C8.E85EBD4A@flash.net> <344BA33C.5795@helsbreth.org> <34576f4a.84848645@ntserv02>
Reply-To: bo.doemstedt@mbox200.swipnet.se

wayne@hoxnet.com (Wayne D. Hoxsie Jr.) wrote:
>>Much better is to take _all_ the data, even the most significant bits,
>>and distill them with a hashing function like CRC32 or MD5.
>
>
>This seems to be a decent proposal.  I've tried the Von Neumann
>approach and it seemed to produce decent results (flat distribution,
>no apparent patterns), but chi-square tests showed non-random
>tendencies.  I later added an option to use a 4:1 MD5 hash to the
>incoming data (512 bits in -> 128 bits out) and this method has passed
>every randomness test I've thrown at it.
>
>Its interesting to note that a 1:1 MD5 had the same results, but it
>seemed to me that if the Von Neumann method distilled the raw data
>down by about 3:1 that there must be some deterministic infomation
>getting through the MD5 hash.  I settled on the 4:1 MD5 hash as a
>guess.
>
>Any comments?

Extracting the information from the output sequence is no
real problem, as evident from previous postings. Note
that "the hash method" is much superior to the
"von Neumann approach", but I would rise questions if
CRC32 or MD5 (MD4, etc.) is really suitable for this
work. For the SG100 hardware random number generator
we use a special hash-function that has been designed
especially for this task.

The main problem, in designing a hardware random number
generator and making it work, is not any of the academic
issues mentioned so far. It took about 20 times more effort
and programming making the serial port driver working,
as compared to any cryptographic-math stuff.

For the hobbyist PC-cryptographer, who want to make some
simple (and cheap!) hardware for himself, make sure to
take the issue of shielding seriously. In fact, our first
SG100 prototype, had to have no less than three levels of
filters to remove RF-signals from the power lines.

I would strongly recommend a battery powered generator
with a IR diode (light) output, all mounted in a metal box.
The battery consumption is definitively cheaper than
the approach of using excessive shielding, or the
method we use in the SG100.

The SG100 generator
http://www.protego.se/sg100_en.htm

Bo Dömstedt
Cryptographer
Protego Information AB
Malmoe,Sweden
http://www.protego.se


From: ritter@io.com (Terry Ritter) Newsgroups: sci.crypt Subject: Re: Non-deterministic random generator for the PC Date: Thu, 30 Oct 1997 16:49:31 GMT Lines: 28 Message-ID: <3458b9d4.1062007@news.io.com> References: <19971012014201.VAA24799@ladder01.news.aol.com> <19971014114700.HAA03888@ladder02.news.aol.com> <34438fd1.501392634@ntserv02> <344427C8.E85EBD4A@flash.net> <344BA33C.5795@helsbreth.org> <34576f4a.84848645@ntserv02> <345868af.706133259@nntpserver.swip.net> NNTP-Posting-Host: as4-dialup-44.wc-aus.io.com On Thu, 30 Oct 1997 11:25:53 GMT, in <345868af.706133259@nntpserver.swip.net> in sci.crypt bo.doemstedt@mbox200.swipnet.se (Bo Dömstedt) wrote: >[...] >Extracting the information from the output sequence is no >real problem, as evident from previous postings. Note >that "the hash method" is much superior to the >"von Neumann approach", but I would rise questions if >CRC32 or MD5 (MD4, etc.) is really suitable for this >work. For the SG100 hardware random number generator >we use a special hash-function that has been designed >especially for this task. I'd be interested in hearing more about this special hash function. What do you see as the requirements which separate this hashing task from others? I have often argued that a CRC is ideal in this work. It is fast, has a strong mathematical basis, and if it really is collecting physical randomness, there is no need for strength. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ The Crypto Glossary: http://www.io.com/~ritter/GLOSSARY.HTM
Path: news.io.com!insync!news-feed.inet.tele.dk!news.maxwell.syr.edu!howland.erols.net!ix.netcom.com!news From: rcktexas@ix.netcom.com (R. Knauer-AIMNET) Newsgroups: sci.crypt Subject: Re: Non-deterministic random generator for the PC Date: Thu, 30 Oct 1997 20:12:43 GMT Organization: Netcom Lines: 11 Message-ID: <3458e9fe.2203398@nntp.ix.netcom.com> References: <19971012014201.VAA24799@ladder01.news.aol.com> <19971014114700.HAA03888@ladder02.news.aol.com> <34438fd1.501392634@ntserv02> <344427C8.E85EBD4A@flash.net> <344BA33C.5795@helsbreth.org> <34576f4a.84848645@ntserv02> <345868af.706133259@nntpserver.swip.net> <3458b9d4.1062007@news.io.com> Reply-To: rcktexas@ix.netcom.com On Thu, 30 Oct 1997 16:49:31 GMT, ritter@io.com (Terry Ritter) wrote: >I have often argued that a CRC is ideal in this work. Would the CRC-16 suffice for cryptographically secure hashing, in your opinion? Bob Knauer "Without Censorship, Things Can Get Terribly Confused In The Public Mind." - General William Westmoreland
From: ritter@io.com (Terry Ritter) Newsgroups: sci.crypt Subject: Re: Non-deterministic random generator for the PC Date: Thu, 30 Oct 1997 22:35:32 GMT Lines: 27 Message-ID: <34590ab6.889036@news.io.com> References: <19971012014201.VAA24799@ladder01.news.aol.com> <19971014114700.HAA03888@ladder02.news.aol.com> <34438fd1.501392634@ntserv02> <344427C8.E85EBD4A@flash.net> <344BA33C.5795@helsbreth.org> <34576f4a.84848645@ntserv02> <345868af.706133259@nntpserver.swip.net> <3458b9d4.1062007@news.io.com> <3458e9fe.2203398@nntp.ix.netcom.com> On Thu, 30 Oct 1997 20:12:43 GMT, in <3458e9fe.2203398@nntp.ix.netcom.com> in sci.crypt rcktexas@ix.netcom.com (R. Knauer-AIMNET) wrote: >On Thu, 30 Oct 1997 16:49:31 GMT, ritter@io.com (Terry Ritter) wrote: > >>I have often argued that a CRC is ideal in this work. > >Would the CRC-16 suffice for cryptographically secure hashing, in your >opinion? No, no, no! All CRC's are linear operations. They essentially have no strength at all! But in many applications -- even in cryptography -- no strength is needed. One example is the hashing of variable-length user key phrases into the fixed-length arbitrary values needed to key a random number generator. See, for example: http://www.io.com/~ritter/KEYSHUF.HTM --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ The Crypto Glossary: http://www.io.com/~ritter/GLOSSARY.HTM
From: kelsey@plnet.net Subject: Re: Non-deterministic random generator for the PC Date: Mon, 03 Nov 1997 11:11:39 -0600 Message-ID: <878576604.1048@dejanews.com> Newsgroups: sci.crypt Organization: Deja News Posting Service Path: news.io.com!globeset.com!news.eden.com!uunet!in1.uu.net!pressimage!news1.isdnet.net!newsfeed.nacamar.de!dispose.news.demon.net!demon!news.idt.net!ais.net!news-out.internetmci.com!newsfeed.internetmci.com!204.238.120.130!jump.net!grunt.dejanews.com!not-for-mail Lines: 41 -----BEGIN PGP SIGNED MESSAGE----- >Subject: Re: Non-deterministic random generator for the PC >From: ritter@io.com (Terry Ritter) >Date: 1997/10/30 >I have often argued that a CRC is ideal in this work. It is >fast, has a strong mathematical basis, and if it really is >collecting physical randomness, there is no need for >strength. I mostly agree with this statement. The CRC is great, if you know that your opponent can't control your inputs. If he can control all your inputs, he can precisely control the input to your PRNG. If he can't see the intermediate CRC values that you're using to collect inputs, though, he loses control as more unknown-to-him bits appear in the input. (That is, if he knows all but one bit of the input, then he can guess that bit, choose the remaining inputs, and end up with a 0.5 chance of ending up with a desired final CRC value. If the starting state of the CRC is unknown to the attacker, then all this kind of attacks fail.) >Terry Ritter ritter@io.com http://www.io.com/~ritter/ >The Crypto Glossary: http://www.io.com/~ritter/GLOSSARY.HTM --John Kelsey, Counterpane Systems, kelsey@counterpane.com PGP 2.6 fingerprint = 4FE2 F421 100F BB0A 03D1 FE06 A435 7E36 -----BEGIN PGP SIGNATURE----- Version: 2.6.2 iQCVAwUBNF1aP0Hx57Ag8goBAQEKkQQA1vUvE37vJiEjJet65JS2jOC7PVirPRQ2 FrXcj5dlkLQZiNOEu7REb1/bM8ZGzbVtFaVAPw/R71ACKOJMHI0nSIJk2PHDu+oW tUggFgZDhuytJtbG4dweQm2NC7LsNZLOTe/1sRep2Nobeur6xAcFN5v9VrbWzAtM ox4754cavL4= =/7J2 -----END PGP SIGNATURE----- -------------------==== Posted via Deja News ====----------------------- http://www.dejanews.com/ Search, Read, Post to Usenet

Terry Ritter, his current address, and his top page.

Last updated: 1998-01-16