6 ms·
Show HN: True-Random – Generate “truly” random numbers
- DanielStraight 10y agoIt seems a bit ambitious to call this true random without any analysis of randomness quality or predictability. I find it very unlikely this will be shown to be better than existing RNG solutions. It's clever, but clever in the way that sleep sort is clever, at least until proven to be of actual benefit.
- kazinator 10y agoIt's expensive; it spins for a millisecond to obtain one bit. Suppose this is running on a quiescent system with no interrupts or other tasks running. I can see it degenerating into deterministic behavior. Suppose the RTC counter and the CPU clock are from the same master clock, and the code is executing cleanly to the clock from on-chip caches. Ultimately, the question is: is there really one bit of entropy from each call to get_bit(), and under what conditions?
- dragontamer 10y agoIt spins for a millisecond to have a chance of obtaining half a bit actually. It takes two clock calls to create a chance of getting a bit, and only if the bit pattern changed during that period.
- infogulch 10y agoIt can create a whole bit per spin, but my guess is that the output was predictable enough for the author to notice, so they added a single round of the most basic random scrubber. 'Hey it looks random now, ship it!'
- dragontamer 10y agoFrom that perspective, I think we can use the methodology in this code as an input into SHA3 / Keccak or Skein (A SHA3 finalist). I dunno Keccak, so I'll talk from a Skein perspective. If every millisecond you added the "nanoseconds" field with the Skein cryptofunction salt = mix(nanoseconds + salt + current seed + other Skein stuff), it'd be pretty darn random. (Apparently Keccak can 'sponge up' entropy somehow, but I don't know the mechanism that it does it with) The output would at least be a crypto-secure PRNG. All that needs to be proven after that fact is whether or not enough entropy was being gathered from the real time clock.
- mindslight 10y agoAnalysis of the output can only disprove randomness. For example, not knowing the key it is impossible to condemn the deterministic output of AES-CTR (assuming the properties of AES hold). The author really needs to cut back the grandiose claims. Projects like this are more part of the learning process, than something useful to others.
- highCs 10y agoYou have to ship the hardware with it.
- gjmulhol 10y agoThis is almost certainly not more random than this: http://www.fourmilab.ch/hotbits/ http://www.fourmilab.ch/hotbits/ It is a cool idea.
- saganus 10y agoOr than https://www.random.org/ https://www.random.org/ Which even includes real-time statistics on the quality of the numbers.
- woliveirajr 10y agoOr https://qrng.anu.edu.au/ https://qrng.anu.edu.au/ That takes his number from random fluctuations from quantic processes.
- Grue3 10y agoWhat if get_bit happens to be deterministic on a particular machine? Then get_fair_bit would be stuck in an infinite loop. This can potentially happen when CPU is so overloaded that executing the bit-flipping instruction takes longer than a millisecond.
- valarauca1 10y agoHow does checking `get_fair_bit(0)' that the next bit isn't the same as the current help fairness?
- micaeked 10y agoThis is a known method for a simple way of getting an unbiased bit from a series of (possibly biased) coin flips. Stated another way, the algorithm for getting an unbiased bit from a biased coin is: 1. Flip the coin twice. 2. If it's both heads or both tails, discard result and go back to 1. 3. If it's heads then tails, result = 0 4. If it's tails then heads, result = 1
- infogulch 10y agoThis assumes the bias can't change over time. This works for a coin because you're using the same coin for all flips, you just don't know the bias. This falls apart in this library because in the computer the source can be affected differently over time -- an attacker can effectively switch out your coin on every flip, rendering this whole process useless.
- micaeked 10y agoYep, I agree. I do think the claims made in the readme are way too strong for what they are. This is only an explanation for what that small part of it does. EDIT: And you're right about the bias changing making this useless. I hadn't thought of that.
- dakami 10y agoI'm not convinced Von Neumann debiasing is vulnerable like you think. You're dropping runs (00's and 11's) so you don't care if it's 90% 0 or 90% 1, you care if there's an even number of a run or an odd number of a run. In other words: 0000000000000001 000000001 001 ...are all interchangeable. So biases can change all day. There are _other_ issues I've seen in real world data, but not this one.
- 10y ago
- caffeinewriter 10y agoI'm really hesitant to even consider this without it being run through the Diehard Tests[0], since from my understanding, "True Randomness" should be cryptographically secure should this be used in a CSPRNG. [0]: https://en.wikipedia.org/wiki/Diehard_tests https://en.wikipedia.org/wiki/Diehard_tests
- daveguy 10y agoA reference from the diehard tests page. The dieharder tests: http://www.phy.duke.edu/~rgb/General/dieharder.php http://www.phy.duke.edu/~rgb/General/dieharder.php A relatively recent (2013) library implementation of the diehard tests plus additional tests. Some things to note: The OP implementation is going to be VERY dependent on OS/language/etc. For example even if it works in C it won't necessarily work in JVM. It probably will not work on a microcontroller.
- Freaky 10y agorng-tools includes a command for testing random number generator output. I tried this with a FreeBSD port from https://github.com/waitman/rngtest https://github.com/waitman/rngtest Results aren't great: rngtest: bits received from input: 300032 rngtest: FIPS 140-2 successes: 0 rngtest: FIPS 140-2 failures: 15 rngtest: FIPS 140-2(2001-10-10) Monobit: 15 rngtest: FIPS 140-2(2001-10-10) Poker: 15 rngtest: FIPS 140-2(2001-10-10) Runs: 15 rngtest: FIPS 140-2(2001-10-10) Long run: 0 rngtest: FIPS 140-2(2001-10-10) Continuous run: 0 rngtest: input channel speed: (min=236.690; avg=245.396; max=251.742)bits/s
- Freaky 10y agoAnd with more data: After nearly 8 hours: rngtest: bits received from input: 6762248 rngtest: FIPS 140-2 successes: 156 rngtest: FIPS 140-2 failures: 182 rngtest: FIPS 140-2(2001-10-10) Monobit: 182 rngtest: FIPS 140-2(2001-10-10) Poker: 174 rngtest: FIPS 140-2(2001-10-10) Runs: 160 rngtest: FIPS 140-2(2001-10-10) Long run: 0 rngtest: FIPS 140-2(2001-10-10) Continuous run: 0
- 10y ago
- egoegoego 10y agoEgo has infected this thread. We can't just say that this project is interesting. We have to talk about "expensive" computation. Why? What does "ambition" have to do with computer science?
- jsprogrammer 10y agoYou are ego. The comment you replied to stated only a fact.
- deleted 10y ago[deleted]
- dang 10y agoWe detached this subthread from https://news.ycombinator.com/item?id=11669106 https://news.ycombinator.com/item?id=11669106 and marked it off-topic.
- jsonninja 10y ago'fuck, not again' - said the cryptographer. The title of the project is potentially very misleading. I know most of you take this stuff seriously in your codes and rely on the well know cryptographically secure random number generators: https://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator https://en.wikipedia.org/wiki/Cryptographically_secure_pseud...
- geofft 10y agoCSPRNGs require random seeds. They're the obvious right thing when you can generate 256 (or whatever your security level is) bits that are truly unpredictable, independent, and of equal probability 0 and 1, but when generating significantly more is hard. If you can't generate 256 truly unpredictable bits, the CSPRNG doesn't help you much. And if you can generate an unbounded number of them, it's not clear that there's a downside to just using the TRNG data (but there's certainly the argument that it's better-studied and more robust to use a CSPRNG anyway). Whether this particular method of random bit generation is in fact sound is a different question entirely (and worth asking of all ways to generate those seeds, including the Linux kernel's entropy divination code).
- geofft 10y agoThis looks to be the same technique as Dan Kaminsky's DakaRand, including the debiasing: https://dankaminsky.com/2012/08/15/dakarand/ https://dankaminsky.com/2012/08/15/dakarand/ See also Kaminsky's implementation of the same approach in pure JS: https://gist.github.com/PaulCapestany/6148566 https://gist.github.com/PaulCapestany/6148566 and Ryan Finnie's implementation in Perl: http://www.finnie.org/2012/08/14/twuewand-2-0-released/ http://www.finnie.org/2012/08/14/twuewand-2-0-released/ The big concern I have is how reliable this is on virtual machines. Just about all physical machines I'd want to use have high-quality, trustworthy-within-my-threat-model (i.e., "if the NSA wanted to attack my silicon, there's easier silicon for them to attack") hardware random number generators, and all physical machines I'd want to use pick up sufficient randomness from the kernel's entropy magic thing. But virtual machines often don't have access to the hardware RNG, and they don't have access to enough other hardware to populate entropy. It seems like this technique would be particularly risky there ... although I don't think anyone's published an attack on DakaRand yet, so maybe it's fine!
- Natanael_L 10y agoThe answer for VMs is guest OS drivers that taps into the host's system RNG (with support for doing so in the VM software).
- nickpsecurity 10y agoExactly. Having a root, high-quality RNG whose output can be input into other systems directly or seeding a CRNG is a classic, design pattern of mine. It can be used for dedicated, simple machines too predictable for TRNG (eg RTOS's), virtual machines, and probably other things I haven't thought of.
- geofft 10y agoDo the common VM hosting services (AWS, DigitalOcean, etc.) offer such a thing? Unfortunately, a superstitious RNG is more useful to a production service than a theoretical one.
- dakami 10y agoIt's definitely based on my approach, but it's missing the concept a bit. The only way this approach gets entropy is if you cross two clocks at very different speeds, and get randomness from the mismatched tolerances. For example, using a computer's microsecond accurate clock to measure a human's 100 millisecond scale behavior yields bits, because we can't be microsecond accurate even if we try. The bitflipping I was exploring involved matching the CPU clock (nanosecond scale) with the real time clock (millisecond scale). This of course has some risk because the OS can easily implement the latter with the former. And in fact, in this implementation, that's actually what happens -- he's measuring the number of bit flips at nanosecond accuracy. Output is distinguishable from PRNG, as seen elsewhere. If I remember right somebody did break my "Defcon Challenge" with Firefox.
- balls187 10y ago> Since the number of times it would be able to flip the bit changes due to random fluctuations in time due to context switching of processes, this generates an arguably truly random bit (I would love to see a PoC that shows otherwise, however). This wouldn't be true random. It's just using the time jitter introduced by context switching to introduce entropy. Similar to many other pRNGs that use system entropy, mouse movements, etc in order to seed the pRNG. A pRNG is 'p' because if you know the conditions used, you can deterministically predict the outcome. The difficulty of recreating those conditions has nothing to do with being truly random.
- szc 10y agoThe periodic interrupt frequency of the system this is run on will have an impact on the numbers produced.
- anishathalye 10y agoThis post reminded me of this other project: https://github.com/dasmithii/RCRand https://github.com/dasmithii/RCRand (a similarly silly but fun race condition based RNG)
- jamesbowman 10y agoThe debiasing idea is due to von Neumann himself: https://en.wikipedia.org/wiki/Fair_coin https://en.wikipedia.org/wiki/Fair_coin
- arno1 10y agougly tests 1. ("true"-random) 10 iterations; 32 random bytes | Result Avg Entropy: 4.82 $ echo $(echo -n "("; for i in $(seq 1 10); do echo -n $(./generate_constant_stream |head -c 32 |ent |head -1 |awk '{print $3}')"+"; done; echo -n "0)/10") |bc -l 4.81945500000000000000 2. ("true"-random) 100 iterations; 32 random bytes | Result Avg Entropy: 4.37 $ echo $(echo -n "("; for i in $(seq 1 100); do echo -n $(./generate_constant_stream |head -c 32 |ent |head -1 |awk '{print $3}')"+"; done; echo -n "0)/100") |bc -l 4.37395291000000000000 3. ("true"-random) 200 iterations; 32 random bytes | Result Avg Entropy: 4.35 $ echo $(echo -n "("; for i in $(seq 1 200); do echo -n $(./generate_constant_stream |head -c 32 |ent |head -1 |awk '{print $3}')"+"; done; echo -n "0)/200") |bc -l 4.34563333000000000000 1. (openssl) 10 iterations; 32 random bytes | Result Avg Entropy: 4.88 $ echo $(echo -n "("; for i in $(seq 1 10); do echo -n $(openssl rand 32 |ent |head -1 |awk '{print $3}')"+"; done; echo -n "0)/10") |bc -l 4.88125000000000000000 2. (openssl) 100 iterations; 32 random bytes | Result Avg Entropy: 4.87 $ echo $(echo -n "("; for i in $(seq 1 100); do echo -n $(openssl rand 32 |ent |head -1 |awk '{print $3}')"+"; done; echo -n "0)/100") |bc -l 4.87404420000000000000 3. (openssl) 200 iterations; 32 random bytes | Result Avg Entropy: 4.88 $ echo $(echo -n "("; for i in $(seq 1 200); do echo -n $(openssl rand 32 |ent |head -1 |awk '{print $3}')"+"; done; echo -n "0)/200") |bc -l 4.87885575000000000000 1. (/dev/urandom) 10 iterations; 32 random bytes | Result Avg Entropy: 4.82 $ echo $(echo -n "("; for i in $(seq 1 10); do echo -n $(head -c32 < /dev/urandom |ent |head -1 |awk '{print $3}')"+"; done; echo -n "0)/10") |bc -l 4.82264100000000000000 2. (/dev/urandom) 100 iterations; 32 random bytes | Result Avg Entropy: 4.89 $ echo $(echo -n "("; for i in $(seq 1 100); do echo -n $(head -c32 < /dev/urandom |ent |head -1 |awk '{print $3}')"+"; done; echo -n "0)/100") |bc -l 4.88655640000000000000 3. (/dev/urandom) 200 iterations; 32 random bytes | Result Avg Entropy: 4.88 $ echo $(echo -n "("; for i in $(seq 1 200); do echo -n $(head -c32 < /dev/urandom |ent |head -1 |awk '{print $3}')"+"; done; echo -n "0)/200") |bc -l 4.88061280000000000000
- wyager 10y agoThe only thing in the world that might be classified as truly random is wavefunction collapse under observation, and even then we're not sure.
- cyphar 10y agoOr radiation.
- TickleSteve 10y agothis is not random.... it is deterministic. typical round-robin times are on the order of 10ms, so you would have a significant amount of non-context-switched 'random' numbers, which when combined with analysis using the cycle counter.... namely a counter running at the clock-speed of your processor would yield a very non-random value.
- coldcode 10y agoCould you not build a "truly" random number generator using a quantum computer?
- spamfilter247 10y agoWouldn't an example of a truly random number generator be to open up a pseudo random webpage (say something like www.engadget.com/page/<pseudo_random_number>) and do a modulo count of the number of whitespace separated words/tokens?