December 27, 2011 by bodangly On the projects section, a hardware random number generator project is mentioned, but there is no link. I assume this means its still being worked on.I am just wondering how to pick up on noise in the voltage to use it as a source of randomness. I'm a programmer so I am not worried about how to write the code but just am not sure on how to pick up on the noise to use it in my algorithm. Thanks! @bodangly The first thing that came to my mind was using the "tempsensor" project. The ADC readings can be summed up and hashed any number of different ways. Good luck! @pcbolt I thought of that as well, but I'm not sure sampling the air temperature is acceptable in a secure application when any device in theory can sample that same air using an LM34. The thing is, it looked to me when doing that project that the lower bits appeared more random than the higher bits. I'd consistently get a reading of say 70 degrees, but the fractional part would vary more randomly. Will the noise in the ADC reading be secure enough? Maybe I can strip out the higher order bits and gather a pool of entropy from the lower bits? I'm trying to come up with a device that can function as source of entropy for a cryptographically secure RNG, feeding results via USB to a PC; possibly as a source of a additional entropy to /dev/random . It would make for an interesting experiment. Take the smallest bit in each reading say 1024 times to generate a number. You could vary the sampling intervals and maybe even the reference voltage to distinguish it from an identical LM34 sensor. You would have to have a pretty secure USB connection since that can be hijacked with software and/or hardware. Pretty cool concept tho. Hi bodangly, That sounds like a really cool project you have in mind. Taking the lower order bits of an adc conversion is probably an o.k. source to use as a seed, but as you mentioned the higher order bits are going to be pretty consistent from reading to reading, and across several sensors next to each other. Even if they are not the same from one reading to the other, they are certainly correlated to what the last sample was. What I would probably do is to rely on only the lowest order single bit of your ADC reading. Given the noise in the system, I'm willing to say that that last bit is pretty randomly 1 or 0 (you should probably run a few tests to convince yourself of that). You can then take 8 successive readings and have 8 random bits. Humberto It seems this is a very viable source of randomness, with a little work. There is an inherent bias to the readings when they are taken close together, there will be long sequences of identical bits for example if you just do a simple for loop to gather 8 bits then return that byte, ad infinitum. But by taking many successive readings XOR'd together and then using the simple von Neumann algorithm (take two bits, if they are equal discard, if the pair is (1,0) return a 1, if its (0,1) return 0) I was able to whiten the bits and achieve what seems to be highly random output, but I still need to write some code to test it and verify. I'm just piping the output from USB into a file and I'm putting together some Tcl code to test the randomness of that stream, but my initial results look like I may not even need a hashing function to distill the entropy further. Next I'd like to AES encrypt the USB output to protect the stream from malicious software. However, this whole process is already a little taxing on the chip, I'm only getting a few bytes a second. I was looking at the Atmel site and it looks like the xmega line has a hardware AES module. They also look to have USB pins. I'd need to put together my own equivalent to uart.c (though in the case of one of the chips with USB pins I guess it would be usb.c) and lcd.c for my chip but they look pretty easy to port. If I purchased my own programmer, would I need the NerdKits bootloader for anything at that point to use the chip? What kind of sucks is the smallest one I can find appears to have 44 pins in a square configuration. Is there a way to make that work with a breadboard? (either the supplied nerdkits one or another) And lastly, I understand these will have their own registers and pinouts, but aside from that is there something I'm missing that would make using these substantially harder than what I've described? Thanks for all the help! Buying the NerdKit was one of the best choices I've made with money in a while =D Er let me clarify, I know the NerdKits bootloader probably won't just run on one of these chips since they have different pinouts and registers, what I meant was would I need to port anything from the NerdKits bootloader. Thanks again If you were able to get you hands on a ATxmega32A4U-AU, those would from the factory have a bootloader already installed. From what I can see though they are pretty new and not readily available at this time. However, they use Atmel's FLIP software for loading programs onto the device via USB. Those devices are USB native and as such would not require a USB serial cable. However, keep in mind, as you have already noticed they are all SMD. The device I listed above is a TQFP 44 package. These aren't too bad to solder to adapter boards that can break out the pins for breadboarding. You would need to build the USB side circuit to allow it to communicate properly to your computer (I haven't looked but most likely it would consist of a couple of resistors and maybe some diodes) Once that was done, you could write the program and compile it then use FLIP to transfer it over. It would be some extra steps to what is done with the nerdkit but would be a fun project if you need encryption. Now if you want to have these devices act as a serial device to a PC, you would have to program them to be USB-Serial devices. This is similar to what the arduino folks do with their newer arduino's. They went with a second microcontroller (an atmega16u2 on the newer boards) that is programmed to be a serial port when connected to a computer. The other xmega's would be more difficult to setup out of the box as they require a jtag programmer. You can install serial bootloaders into them but you would have to buy a jtag programmer to send it over to the chip. There are some development boards out there that have pre-installed bootloaders and those would most likely be the easiest starting point if you wanted to get into the xmega series chips. One last note, I just checked the avr-gcc website and it doesn't appear that the newer usb based xmegas are supported yet. Just a little more food for thought. Rick I think I found the chip at mouser.com: http://www.mouser.com/ProductDetail/Atmel/ATXMEGA32A4U-AU/?qs=HbI%2fMOA3e14zr9I2HFi4TQ%3d%3d Unfortunately it doesn't look like they'll be in stock until the end of January - early February; but that's not too far off at least. So it sounds like my biggest hurdles will be building the side-circuit and then building the serial support. I see the code for how arduino does it looks to be in their source under hardware/firmwares/arduino-usbserial, according to their readme they base it off of LUFA's UsbToSerial (http://www.fourwalledcubicle.com/LUFA.php) project, so at least there is something for me to work off of. Of course with no avr-gcc support I am pretty SoL as far as using anything from that LUFA project. Maybe I'll put the encryption side of this project on the shelf for 6 months and let the support around those chips mature. I also am ahead of myself as far as my EE knowledge goes, I doubt I'd be able to figure out the USB side-circuit on my own at this point. The good news is that the raw bits ALMOST pass Maurer's statistical test, I'm getting a value of L=7.1755384 when I should be getting 7.1836656. Pretty sure if I hash the pool on the PC side I'll have a really nice source of entropy, maybe I'll use the NIST test suite to check since Maurer isn't really the be all end all. Amazing how simple it really is just using this sensor to get a source of entropy. I'm thinking if I used two sensor's and XOR'd their output I may be able to pass Maurer without a hashing function. Would that be as simple as using pins 21,22, and 24, so I am using pin PC1(ADC1) on the second sensor? bodangly would you please define: a source of entropy My definition does not fit with how you are using the term "entropy". Some of the viewers of your post (like myself) are of limited knowledge and probable could not help you with your question directly but we use these postings to learn. Thanks, Ralph @Ralph, Sure thing, I'm very new when it comes to the electrical engineering aspect of all this myself so I could not at all explain WHY this is a source of entropy beyond the fact that there is a certain degree of noise in the voltage which manifests itself in the ADC reading. As for what entropy is, I am not referring to entropy as a thermodynamics term, but rather as it relates to information theory. You may have heard entropy defined as the amount of chaos in a system. This is what we are talking about here. When I grab the lowest bit of an ADC conversion, which I do as ``````uint_fast8_t result = ADCL & 0x01; `````` if this was a perfect source of entropy, then whether that bit is a 1 or 0 is entirely random. This would mean each bit has an entropy of 1. If there is a bias the entropy may be lower. Having a source of highly random bits is important for things like generating keys for cryptography, passwords, lotteries or gambling involving real money, etc. The statistical test I was referring to purports (I say that because its really not a perfect test and there are more stringent tests such as the NIST tests http://csrc.nist.gov/groups/ST/toolkit/rng/index.html) to measure the entropy of a block, in this case 8 bits (1 byte). I do a little bit more than simply grab the bits off of the conversion and use them directly to try and "whiten" any bias in them. I'm happy to comment my code and post it if you are interested to see what I do. The circuit is identical to the tempsensor though I removed the LCD as I do not use it as I just output directly to USB. The tempsensor project uses averaging doesn't this reduce the noise? Isn't that what the averaging is there to do? I think of "entropy as a thermodynamics term" so whenever someone uses it in place of "noise" I pull a blank. This isn't the first time I have had to ask for clarification about the use of "entropy" hopefully it will sink in, but I do suffer from the AGE virus. Ralph Hopefully my code will help clarify some of what I was talking about. As you'll see I don't average the bits but I do use successive readings to affect the last. If you set your board up for the tempsensor project you can compile and download this right to your chip. I also have my board wired to use the USB for power which is described in the Appendix of the nerdkits guide. Since I am not outputting to use the LCD you must access your USB serial port on your PC, or you can put back in the statement to include lcd.h and write last_byte to your LCD. This will SEVERELY slow down the generation of bits but its useful to test at a glance that random bytes are being generated. Otherwise, if you are on linux you can simply type "cat /dev/ttyUSB0 > results" and let that run awhile to generate a file filled with random data. You can then open that file up in a hex editor to see for yourself. If you aren't using linux (it may work the same way in Mac OSX too but not sure) you can use Hyperterminal to read the data off your USB serial device and then save it into a file. Once you have a file filled with the random data you can use the data from that file to generate random numbers in a range, or you can read however many bits you need to create a specific crypto key, one-time pad, etc. ``````// entropypool.c // for NerdKits with ATmega168 // based on tempsensor by mrobbins@mit.edu // bodangly@gmail.com #define F_CPU 14745600 #include #include #include #include #include #include #include "../libnerdkits/delay.h" #include "../libnerdkits/uart.h" // PIN DEFINITIONS: // // PC0 -- temperature sensor analog input void adc_init() { ADMUX = 0; ADCSRA = (1 << ADEN) | (1<