Noise source processing
Hello all.. After a little bit of work I have put together a white noise source (hacked FM reciever, heavily shielded to reduce local EMR bias) and have it jacked into a mic port on one of my machines. I would like to develop of bit of code (oh, horror :) to take bits from the sound card, and bits from /dev/random, and mix them together to get a random number stream. The noise coming off of the sound card is more beige than white though.. Does anyone know of any papers, articles or whatever on good techniques to remove bias from the audio source? My initial thoughts are along the lines of just hashing everything, but this will be slow, and I'd like to see what other ideas are out there. Michael J. Graffam (mgraffam@mhv.net) http://www.mhv.net/~mgraffam -- Philosophy, Religion, Computers, Crypto, etc "Let your life be a counter-friction to stop the machine." Henry David Thoreau "Civil Disobedience"
After a little bit of work I have put together a white noise source (hacked FM reciever, heavily shielded to reduce local EMR bias) and have it jacked into a mic port on one of my machines. I would like to develop of bit of code (oh, horror :) to take bits from the sound card, and bits from /dev/random, and mix them together to get a random number stream.
The noise coming off of the sound card is more beige than white though..
Does anyone know of any papers, articles or whatever on good techniques to remove bias from the audio source? ... If I were doing it, I would probably feed the raw bytes into a stream cipher with feedback, like Sapphire II, and then select every nth byte from
At 09:12 PM 8/5/98 -0400, mgraffam@mhv.net wrote: ... the output stream (just to match the output bit rate to the estimated actual entropy in a conservative fashion and improve the effective avalanche performance of that particular algorithm). This would be faster than a hash like SHA-1. Indeed, you could just use a good mixer, like a CRC or non-cryptographic hash to whiten the noise if speed is an issue. As long as you restrict the output bit rate to less than the actual estimated entropy of the source, you should be alright, provided that your noise source is as random as you think it is. Then again, the truly paranoid may beg to differ. _______ Michael Paul Johnson mpj@ebible.org http://ebible.org http://cryptography.org PO BOX 1151, Longmont CO 80502-1151, USA Jesus Christ is Lord!
On Wed, 5 Aug 1998 mgraffam@mhv.net wrote: [...]
The noise coming off of the sound card is more beige than white though..
Does anyone know of any papers, articles or whatever on good techniques to remove bias from the audio source?
See the RFC 1750, Randomness Recommendations for Security. D. Eastlake, 3rd, S. Crocker & J. Schiller. December 1994. (Format: TXT=73842 bytes) A sample from the table of contents gives: [...] 5. Hardware for Randomness............................... 10 5.1 Volume Required...................................... 10 5.2 Sensitivity to Skew.................................. 10 5.2.1 Using Stream Parity to De-Skew..................... 11 5.2.2 Using Transition Mappings to De-Skew............... 12 5.2.3 Using FFT to De-Skew............................... 13 5.2.4 Using Compression to De-Skew....................... 13 5.3 Existing Hardware Can Be Used For Randomness......... 14 5.3.1 Using Existing Sound/Video Input................... 14 5.3.2 Using Existing Disk Drives......................... 14 6. Recommended Non-Hardware Strategy..................... 14 6.1 Mixing Functions..................................... 15 6.1.1 A Trivial Mixing Function.......................... 15 6.1.2 Stronger Mixing Functions.......................... 16 6.1.3 Diff-Hellman as a Mixing Function.................. 17 6.1.4 Using a Mixing Function to Stretch Random Bits..... 17 6.1.5 Other Factors in Choosing a Mixing Function........ 18 6.2 Non-Hardware Sources of Randomness................... 19 6.3 Cryptographically Strong Sequences................... 19 [...] Berke Durak - berke@gsu.linux.org.tr - http://gsu.linux.org.tr/kripto-tr/ PGP bits/keyID: 2047/F203A409 fingerprint: 44780515D0DC5FF1:BBE6C2EE0D1F56A1
At 09:12 PM 8/5/98 -0400, mgraffam@mhv.net wrote:
Hello all..
After a little bit of work I have put together a white noise source (hacked FM reciever, heavily shielded to reduce local EMR bias) and have it jacked into a mic port on one of my machines. I would like to develop of bit of code (oh, horror :) to take bits from the sound card, and bits from /dev/random, and mix them together to get a random number stream.
The noise coming off of the sound card is more beige than white though..
Does anyone know of any papers, articles or whatever on good techniques to remove bias from the audio source?
Let me save you the trouble. First, RFC 1750 gives some background including the info-theory behind bit 'distillation'. I have digitized FM radio hiss using a $10 transistor radio feeding into the LINE in of my soundcard. The spectrum looks poisson with prominant, periodically spaced noise spikes. It does not pass Diehard. But if you take the PARITY of 8 bits to get one bit, then assemble bytes out of these bits, the results pass Diehard. This works with 44Khz, 16 bit sampling, with full-volume hiss feeding the soundcard. I have yet to try this with a video adc sampling snow. 1. There are some nice spectrogramming shareware programs out there. 2. Diehard is invaluable. 3. Language is so vague. Don't export this filter: /* Alemb.c Alembic bit distiller Takes 8 bytes, computes the parity of each, composes a byte from the bits. 2 Aug Ported from Alembic.java which I had prototyped earlier 3 Aug modified to be faster */ #include <stdio.h> /* return parity of byte input */ int parity(int c) { int i,p=0; for (i=0; i<8; i++) { p ^= c & 1; c >>= 1; } return p; } main(int argc, char **argv) { int c=0, p, n, i; int count=0, accum=0; int ones=0, zeroes=0; unsigned char parlut[256]; unsigned char buff[8]; FILE *fptr, *of; char *infname="test.wav"; char *outfname="test.bin"; int hist[256], max; if (argc>1) infname=argv[1]; if (argc>2) outfname=argv[2]; fprintf(stderr,"Alembic C 4 in=%s out=%s\n", infname, outfname); fptr = fopen(infname, "rb"); of = fopen(outfname, "wb"); for (p=0; p<256; p++) { parlut[p]=parity(p); /* initialize parity table */ hist[p]=0; } n=8; while (n==8) { n=fread(buff, 1,8, fptr); count += n; if (n==8) { for (i=0; i<8; i++) { p = parlut[ buff[i] ] ; accum <<= 1; accum |= p; /* measure */ if (p==1) ones++; else zeroes++; } fwrite(&accum,1,1,of); hist[accum]++; accum=0; } } printf("In: %0d bytes\n", count); printf("Out: %0d bytes\n", count/8); printf("output: 1's=%0d %0f% \n", ones, 100.0*ones/(ones+zeroes)); printf("output: 0's=%0d %0f% \n", zeroes, 100.0*zeroes/(ones+zeroes)); max=0; for (i=0; i<256; i++) {if (max<hist[i]) max=hist[i];} for (i=0; i<256; i++) { printf("%0d %0d %lf\n", i, hist[i], 100.0*hist[i]/max); } } honig@alum.mit.edu
On Thu, 6 Aug 1998, David Honig wrote:
I have digitized FM radio hiss using a $10 transistor radio feeding into the LINE in of my soundcard. The spectrum looks poisson with prominant, periodically spaced noise spikes. It does not pass Diehard.
Yeah, I ran Diehard on it .. and that is why I wanted to find some references on removing bias.
But if you take the PARITY of 8 bits to get one bit, then assemble bytes out of these bits, the results pass Diehard.
This is a neat idea. I smiled when I read this in RFC1750
1. There are some nice spectrogramming shareware programs out there.
I haven't been able to find any for UNIX/X .. any recommendations for Win31 (I'll try it with Wabi ;) software? [source clipped] :) Sweet. Thanks. Michael J. Graffam (mgraffam@mhv.net) http://www.mhv.net/~mgraffam -- Philosophy, Religion, Computers, Crypto, etc "Two things fill the mind with ever new and increasing admiration and awe the more often and steadily we reflect upon them: the starry heavens above and the moral law within me. I do not seek or conjecture either of them as if they were veiled obscurities or extravagances beyond the horizon of my vision; I see them before me and connect them immediately with the consciousness of my existence." - Immanuel Kant "Critique of Practical Reason"
At 10:31 AM 8/6/98 -0400, mgraffam@mhv.net wrote:
On Thu, 6 Aug 1998, David Honig wrote:
I have digitized FM radio hiss using a $10 transistor radio feeding into the LINE in of my soundcard. The spectrum looks poisson with prominant, periodically spaced noise spikes. It does not pass Diehard.
Yeah, I ran Diehard on it .. and that is why I wanted to find some references on removing bias.
But if you take the PARITY of 8 bits to get one bit, then assemble bytes out of these bits, the results pass Diehard.
This is a neat idea. I smiled when I read this in RFC1750
1. There are some nice spectrogramming shareware programs out there.
I haven't been able to find any for UNIX/X .. any recommendations for Win31 (I'll try it with Wabi ;) software?
You should probably look for native freeware, no? Otherwise look in various win archives. I have not yet done systematic experiments looking at, e.g., entropy in less-than full-amplitude noise, or intentionally filtering out various pieces of spectrum. The tables in RFC 1750 show that 8 bits is reasonable. Interestingly, the parity of a $10 10year old Radio shack monophonic FM radio, UNSHIELDED, in a digitally-noisy environment, sampled at 44Khz and 16 bits, passed Diehard. NB: Consumer computainment devices will include FM/TV receivers very shortly. Less of a rat's nest in back of the machine. I always thought listening to static was a suspicious activity. A CDROM burner is $350. "Entropy. Its not just for ambassadors anymore." honig@alum.mit.edu
On Thu, 6 Aug 1998, David Honig wrote:
I have not yet done systematic experiments looking at, e.g., entropy in less-than full-amplitude noise, or intentionally filtering out various pieces of spectrum.
After I get the software end sorted out, I'm going to start stripping the signal down and take look at some of this stuff too..
Interestingly, the parity of a $10 10year old Radio shack monophonic FM radio, UNSHIELDED, in a digitally-noisy environment, sampled at 44Khz and 16 bits, passed Diehard.
Yeah, that is pretty neat .. maybe I'll tear the shielding off of my source and see what sort of results I get. Maybe the shielding I put in place is unnecessary. Michael J. Graffam (mgraffam@mhv.net) http://www.mhv.net/~mgraffam -- Philosophy, Religion, Computers, Crypto, etc "If you die, you win.." John Landry, statistics professor discussing life insurance and probability
At 02:24 PM 8/6/98 -0400, Dave Emery wrote:
This is expected of hard limiters below threshold (such as in a reasonable FM IF system fed Johnson noise). The spikes occur on phase discontinuities in the limiter output - what you are seeing is the input Johnson noise intermittantly inducing phase jumps in the output of the ringing IF filters shock excited by the broadband input noise. The IF filters tend to ring somewhat coherently until hit by another burst of noise which sets them off on another phase. Each phase jump shows up as a spike on the discriminator output. The narrower the bandwidth of the filters, the longer the spike and interspike intervals. Thus one needs an IF bandwidth considerably wider than the sample rate.
Given that the cheapo radio was 10 cm from a 21" monitor, I don't think you need to invoke noise-driven resonances in the humble radio. I was/am interested in robust methods that don't depend on exquisite analog equalization, etc. Zero crossings are analogs (pun intended) of RFC1750's #2 method (via Shannon): map 01 -> 1 map 10 -> 0 00, 11 are no-ops. Note that for a digital signal you are detecting level-changes. (Vdd/2 changes?) Waiting for zero crossing will give you perfect 0:1 ratio, but you may have to wait arbitrarily long (but will almost certainly not, in the formal sense ---there's a decaying exponential in there).
On Thu, 6 Aug 1998, David Honig wrote:
Zero crossings are analogs (pun intended) of RFC1750's #2 method (via Shannon):
map 01 -> 1 map 10 -> 0 00, 11 are no-ops.
RFC1750 attributes this to von Neumann. Michael J. Graffam (mgraffam@mhv.net) http://www.mhv.net/~mgraffam -- Philosophy, Religion, Computers, Crypto, etc They (who) seek to establish systems of government based on the regimentation of all human beings by a handful of individual rulers.. call this a new order. It is not new, and it is not order." - Franklin Delano Roosevelt
On Thu, Aug 06, 1998 at 10:31:20AM -0700, David Honig wrote:
At 10:31 AM 8/6/98 -0400, mgraffam@mhv.net wrote:
On Thu, 6 Aug 1998, David Honig wrote:
I have digitized FM radio hiss using a $10 transistor radio feeding into the LINE in of my soundcard. The spectrum looks poisson with prominant, periodically spaced noise spikes. It does not pass
This is expected of hard limiters below threshold (such as in a reasonable FM IF system fed Johnson noise). The spikes occur on phase discontinuities in the limiter output - what you are seeing is the input Johnson noise intermittantly inducing phase jumps in the output of the ringing IF filters shock excited by the broadband input noise. The IF filters tend to ring somewhat coherently until hit by another burst of noise which sets them off on another phase. Each phase jump shows up as a spike on the discriminator output. The narrower the bandwidth of the filters, the longer the spike and interspike intervals. Thus one needs an IF bandwidth considerably wider than the sample rate. Your parity scheme is pretty good, but simple zero crosses (or crossings of the long term mean value of the waveform) aren't bad either. Many years ago I suggested, half seriously, that simply taking a suitable cheap Radio Shack audio transformer and stepping the speaker output of a cheap FM radio tuned between stations to around 15 volts and shoving it directly into the CD or DSR input of a standard PC serial port would work as a quicky hardware noise source (this was before the near universality of soundcards on PCs). The serial port pins incorperate a threshold comparitor in the RS-232/423 receiver chips which would act to convert the noise to a string of 1s and 0s that could be sampled by reading the DSR value occasionally. Or one could use the DSR interrupt and record the time the zero crossing occurred and use this time stamp as a random (poisson distributed) value.
I always thought listening to static was a suspicious activity.
My wife thinks so... -- Dave Emery N1PRE, die@die.com DIE Consulting, Weston, Mass. PGP fingerprint = 2047/4D7B08D1 DE 6E E1 CC 1F 1D 96 E2 5D 27 BD B0 24 88 C3 18
participants (5)
-
Berke Durak -
Dave Emery -
David Honig -
mgraffam＠mhv.net -
Michael Paul Johnson