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"

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

At 09:12 PM 8/5/98 -0400, mgraffam@mhv.net wrote:
...
>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
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!