Bluetooth based Pseudorandom Number Generation

[MS3FGX] has done an interesting study about using Bluetooth adapters as a source for Pseudorandom Number Generation (PRNG). As it turns out, the Bluez package has a function that calls a remote Bluetooth adapter to return a random number. He picked up 10 compatible adapters for about $30 from DealExtreme and set about assembling some numbers to see how this compares to an OS-based PRNG.

Because millions of samples are needed for an accurate comparison, time became a problem. The adapters are a little bit slow responding to a request, sending just 4800 numbers in the first 30-second test. This can be overcome with multiple adapters being accessed by multiple computers for hours at a time. What can this be used for? Your guess is as good as ours, but [MS3FGX] has done a great job of writing up his tests. He’s also made a set of 20.7 million randomly generated values available if you want to generate your own statistical analysis.

Comments

  1. toodlestech says:

    This title is misleading. It’s just a random number generator written in assembly. I thought this was going to be something cool creating a number generator from the bluetooth frequencies, or data “sniffed” over bluetooth or something.

  2. jimmys says:

    MS3FGX-
    nice work!

  3. Matt says:

    Wouldn’t truely random numbers be more useful?

  4. MS3FGX says:

    Real random data would be a lot more useful, but it is also extremely difficult to get real random data without an exotic source like ionizing radiation.

    The idea here is that by using a bunch of very cheap PRNGs clustered together, the average output should be better than the operating system’s internal PRNG, which has a very limited pool of entropy.

    Unfortunately, it is much much slower than I would have liked. On the plus side though, the data coming out of it looks very good so far.

  5. kikkoman says:

    pseudo. the word is PSEUDO.

  6. laube says:

    I still dont get why using PRNGs connected over bluetooth is any better than just coupling multiple software PRNGs running on the same machine..
    @toodlestech:
    thats exactly what i thought

  7. Noobixide says:

    “This title is misleading. It’s just a random number generator written in assembly. I thought this was going to be something cool creating a number generator from the bluetooth frequencies, or data “sniffed” over bluetooth or something.”

    Exactly what I thought as well.

  8. MS3FGX says:

    @laube
    The theory is that by pushing the calculation of random numbers out into cheap external devices, you would be less likely to be effected by a local software exploit or attack on the internal PRNG. These cheap adapters all put out the same quality of numbers and can’t be influenced by anything running on the machine. Plus they are so cheap that if one of them was showing a strong bias or had been physically damaged, you could swap it out like a lightbulb.

    But the idea here is not that this is a better way of generating random numbers (though it does look a little less predictable than the Linux kernel PRNG), but mainly an experiment to see if it could be done in the first place. I am certainly not suggesting anyone start doing this on their production servers.

    At the same time, I am working on a few true RNG projects, and this served mainly as a dry run for a lot of the concepts I will be working with. For instance I wrote up a little app (Spectra) that visualizes random ASCII files in an attempt to identify bias or repeating patterns.

  9. amk says:

    MS3FGX, I’m interested to know more about these “true RNG” projects, and what your definition of that is. I would think that true RNG is impossible as long as the data is generated algorithmically. To extend that further, even very random naturally occurring data can’t be truly random. It’s also generated algorithmically according to the laws of physics.

  10. MS3FGX says:

    That is absolutely true, anything goverened by Newtonian physics can, by definition, not be truely random. Which is why real random data can only be generated by occurrences governed by quantum physics.

    These events are generally much more difficult to observe and measure, but I am steadily working on a few promising leads that should make things much easier, at least in the context of random number generation.

    I am still in the early stages so I don’t have anything to show right now, but it should go without saying that once they are in a workable state they will be fully documented (and hopefully gracing these fine pages).

  11. SimonCooper says:

    @MS3FGX. The biases in the distribution of your random digits is “self-imposed”.

    You are printing out an integer (0-65535) and then analyzing the individual digits.

    If you were printing 00000 – 99999 each time then you would see an even distribution. But since the numbers you print only go up to 65535 and you don’t print leading zeros you would expect to see a much smaller number of 0, 7, 8 and 9 digits. The expected probability of getting a number in the 60000-65536 range is going to be about half that of the range 50000-59999, so the expected probability of seeing a 6 will be midway between the 1-5 and 0,7-9 probabilities.
    (This is precisely what you see in your results)

    If you took the 16 bit value and printed it as 4 hex digits and then did a statistical analysis on 0-F you’d probably get pretty good results.

    The biases in your Interpreted Binary mode are also caused by this skewed distribution.

    If you still wanted to use decimal, then you should truncate the numbers from 0000 – 9999 (and print leading zeros!). If the number you get back from the device is >60000 throw it away, otherwise reduce it modulo 10000. Do not be tempted to just do modulo 10000 and use that number — you’ll just introduce bias back into your results… see the following as to why,

    0 – 9999 -> 0000-9999 equally distributed
    10000 – 19999 -> 0000-9999 equally distributed
    20000 – 29999 -> 0000-9999 equally distributed
    30000 – 39999 -> 0000-9999 equally distributed
    40000 – 49999 -> 0000-9999 equally distributed
    50000 – 59999 -> 0000-9999 equally distributed
    60000 – 65535 -> 0000-5535 un-evenly distributed

    Also check out the analysis done on LavaRND

    http://www.lavarnd.com/what/nist-test.html

    (disclaimer – I am a co-Inventor of LavaRND)

  12. shitehawk says:

    wouldn’t something based on chua’s chaos circuit be more suitable? link:http://en.wikipedia.org/wiki/Chua%27s_circuit

  13. kikko says:

    Another truly useless project which just proves how bored people can get. Want random numbers? use GetTickCount() …

  14. TehRabbitt says:

    Great project MS3FGX… I have a couple bluetooth adapters i think I told you about that you might wanna try for your testing… might work better than the DX ones

  15. SimonCooper says:

    @ds :-)

    As compared to the probabilities of hex digits…

    $ perl -e ‘for ($i=0;$i<65536;$i++) { $a=sprintf "%04x", $i; for $j (split (//,$a)) { $x{$j}++ }} for $i (sort keys %x) { print "$i $x{$i}\n" }'

    And the evenly distributed way of using digits from a decimal expansion….

    $ perl -e 'for ($i=0;$i 59999); $a=sprintf “%04d”, ($i%10000); for $j (split (//,$a)) { $x{$j}++ }} for $i (sort keys %x) { print “$i $x{$i}\n” }’

  16. SimonCooper says:

    Posting code in comments doesn’t seem to work all that well. And the evenly distributed way of using digits from a decimal expansion…

    #!/usr/bin/perl
    for ($i=0;$i 59999);
    $a=sprintf “%04d”, ($i%10000);
    for $j (split (//,$a)) { $x{$j}++ }
    }
    for $i (sort keys %x) { print “$i $x{$i}\n” }’

  17. SimonCooper says:

    wordpress == fail. It cannot handle code posted into comments!

    The processing of < and > is borked!

    #!/usr/bin/perl
    for ($i=0;$i<65536;$i++) {
    next if ($i > 59999);
    $a=sprintf “%04d”, ($i%10000);
    for $j (split (//,$a)) { $x{$j}++ }
    }
    for $i (sort keys %x) { print “$i $x{$i}\n” }’

  18. Erik says:

    Or you could buy an entropy key, which is a pretty nice hack imho.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 96,441 other followers