Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Convert standard Geiger counter to RNG

github.com

Post reply on HN
Print view View original

11–20 of 42 posts

Re: Convert standard Geiger counter to RNG

#11

Post by stcredzero »

Not a crypto expert, but here's my understanding of the problem. The system just has to gain bits of entropy from the physical randomness source faster than the hardware and software leaks them. So one could feed the entropy into a stream cipher with the right characteristics.

What if one just counted the number of clicks, modulo 2? Then one could take the output of ChaCha20 or Salsa20 stream ciphers and every N outputs of the stream cipher, increment the stream cipher's counter bits 0 or 1 times. One would also have to re-key the stream cipher periodically. (Maybe after gathering 128 bits of output from the Geiger counter in another register, then using that.)

Re: Convert standard Geiger counter to RNG

#12

Post by ashleyn »

gus_massa wrote: post #2

Have you tested how good the random numbers are? I think they should be good, if the interval between clicks is much larger than the interval for the counter, but I may be missing something. Also, some source emit two particles and I don't know if there are interesting cascades of decompositions. If two consecutive clicks are close enought, I expect an uneven distribution on increasing secuances like 13478AC023489BC.…

I'm assuming the source is just ordinary background radiation. I'm wondering if, at such low levels, the geiger counter can accurately determine it enough to get a truly random output (as opposed to, some internal squelch on the unit creating predictable patterns). You probably would get far better randomisation ripping out americium from an old smoke detector and putting it by the geiger counter. (Just take note that residue on your hands from handling it may be toxic if ingested.)

Re: Convert standard Geiger counter to RNG

#13

Post by lxgr »

LeoPanthera wrote: post #10

I'm not a math or a CS expert, but I naively "designed" a PRNG which was simply repeatedly doing hash(random_seed+counter). Obviously you have to keep random_seed secure, and use a hashing algorithm that does not have easy collisions, but other than that, is there any actual downside to this method?

One important thing this does not achieve is forward and backward secrecy.

A proper PRNG periodically irreversibly mutates its internal state (which gives you the property of not being able to retrieve past outputs in case of a point-in-time system compromise) and also incorporates additional entropy into its internal state whenever it becomes available (which makes it impossible to predict all future outputs after a point-in-time compromise).

Backward secrecy can be achieved by completely replacing your current state with some hash function of it, i.e. completely deterministically; forward secrecy needs additional entropy, so it's not always feasible.

Re: Convert standard Geiger counter to RNG

#14

Post by er4hn »

LeoPanthera wrote: post #10

I'm not a math or a CS expert, but I naively "designed" a PRNG which was simply repeatedly doing hash(random_seed+counter). Obviously you have to keep random_seed secure, and use a hashing algorithm that does not have easy collisions, but other than that, is there any actual downside to this method?

You do have a few details to worry about such as the size of the random_seed, and how much you can output before you need to get a new seed. There's also a problem that if the state of the rng is exposed at any point, all past generated values can be determined (oh, it's currently on {random_seed="foobar", ctr=5}, I can predict the prior values.)

But it is very close to the US Fed approved HASH_DRBG, under NIST SP 800-90A, section 10.1.1 here: https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.S... .

The big problem with PRNG algorithms is that, imo, determining how good they are feels like a bit of a black art. You can have things that measure as having high entropy very easily that have very predictable inputs or can be easily broken. It's always been a nit of mine when trying to analyze how good a PRNG is.

Re: Convert standard Geiger counter to RNG

#15

Post by lxgr »

stcredzero wrote: post #11

Not a crypto expert, but here's my understanding of the problem. The system just has to gain bits of entropy from the physical randomness source faster than the hardware and software leaks them. So one could feed the entropy into a stream cipher with the right characteristics. What if one just counted the number of clicks, modulo 2? Then one could take the output of ChaCha20 or Salsa20 stream ciphers and every N outp…

> So one could feed the entropy into a stream cipher with the right characteristics.

Certainly, but your proposed scheme does not feed entropy back into the stream cipher, it just offsets its output. This can be trivially broken if the stream cipher key ever leaks.

A better solution would combine (ideally securely hash) the stream cipher key with a relatively large (i.e. on the order of > 100 bits) number of bits.

Re: Convert standard Geiger counter to RNG

#16

Post by aljarry »

LeoPanthera wrote: post #10

I'm not a math or a CS expert, but I naively "designed" a PRNG which was simply repeatedly doing hash(random_seed+counter). Obviously you have to keep random_seed secure, and use a hashing algorithm that does not have easy collisions, but other than that, is there any actual downside to this method?

Depends on the usage. Commonly available "legit" PRNGs have uniform distribution, even over long range of numbers.

Wikipedia has a list of interesting tests you could do to confirm you PRNG: https://en.wikipedia.org/wiki/Pseudorandom_number_generator#... where first two are interesting for a non-cryptographic PRNG.

Re: Convert standard Geiger counter to RNG

#17

Post by kloch »

er4hn wrote: post #14
LeoPanthera wrote: post #10

I'm not a math or a CS expert, but I naively "designed" a PRNG which was simply repeatedly doing hash(random_seed+counter). Obviously you have to keep random_seed secure, and use a hashing algorithm that does not have easy collisions, but other than that, is there any actual downside to this method?

You do have a few details to worry about such as the size of the random_seed, and how much you can output before you need to get a new seed. There's also a problem that if the state of the rng is exposed at any point, all past generated values can be determined (oh, it's currently on {random_seed="foobar", ctr=5}, I can predict the prior values.) But it is very close to the US Fed approved HASH_DRBG, under NIST SP 80…

Analysis of PRNG's is difficult and very important:

https://www.pcg-random.org/posts/does-it-beat-the-minimal-st...

Re: Convert standard Geiger counter to RNG

#18

Post by Verdex »

LeoPanthera wrote: post #10

I'm not a math or a CS expert, but I naively "designed" a PRNG which was simply repeatedly doing hash(random_seed+counter). Obviously you have to keep random_seed secure, and use a hashing algorithm that does not have easy collisions, but other than that, is there any actual downside to this method?

IIRC there's a PRNG talk for videogames where they mention your method:

https://www.youtube.com/watch?v=LWFzPP8ZbdU&t=4s

There are downsides, but for videogames, the speaker decided that this wasn't that bad of an idea.

Re: Convert standard Geiger counter to RNG

#20

Post by tptacek »

kloch wrote: post #17
er4hn wrote: post #14

Earlier quoted context omitted.

You do have a few details to worry about such as the size of the random_seed, and how much you can output before you need to get a new seed. There's also a problem that if the state of the rng is exposed at any point, all past generated values can be determined (oh, it's currently on {random_seed="foobar", ctr=5}, I can predict the prior values.) But it is very close to the US Fed approved HASH_DRBG, under NIST SP 80…

Analysis of PRNG's is difficult and very important: https://www.pcg-random.org/posts/does-it-beat-the-minimal-st...

This isn't a security analysis, and PCG isn't a secure random number generator, but it is the case that you can fashion a crude secure random number generator out of a sufficiently large state and a cryptographic hash.
Post reply on HN