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

21–30 of 42 posts

Re: Convert standard Geiger counter to RNG

#21

Post by tptacek »

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…

I don't understand what you mean by "leak" here. You can definitely make a secure random bit generator with a stream cipher. Once it's fully initialized/seeded, it's practically never going to run out of random bits.

Re: Convert standard Geiger counter to RNG

#22

Post by tptacek »

lxgr wrote: post #15
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.

I mean this is true, but it's also true that every cipher can be trivially broken if its key leaks. Yes: you want to rekey regularly (and that's not complicated). But whatever circumstance allowed your state to leak in the first place is most probably repeatable by an attacker, so you likely have much bigger problems than PRNG design.

If you want to snipe at people for freelancing their own CSPRNGs, the better point to make is that people should be relying on the OS's secure random generator to the exclusion of everything else; there are systems security reasons to avoid userland CSPRNGs.

But I think for the most part these are just people enjoying working out how a CSPRNG works. Which, mazel tov!

Re: Convert standard Geiger counter to RNG

#23

Post by eternityforest »

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…

Is there actually a limit to how much data you can output? Modern state sizes are so big you'll never get a repeat in billions of years.

We also mix entropy in continually. Even if your sources only give you 1 bit per minute, within a few hours you'll have way too much entropy for attackers to decode anything before that window.

Plus, if you're using hashing, you can't figure out previous states from the current state.

Then on top of it people generally also use hardware RNGs built into all modern chips. On Linux I believe they don't trust it by itself but mix it with other sources.

Actually building a PRNG yourself would still be hard though!

It would be cool if modern devices had a solid state radiation detector for this purpose. Not so much because they actually need it, but anything security related often sells well, and it might let them put radiation sensing in consumer devices. I wonder how much stuff people would find!

Re: Convert standard Geiger counter to RNG

#24

Post by stcredzero »

tptacek wrote: post #21
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…

I don't understand what you mean by "leak" here. You can definitely make a secure random bit generator with a stream cipher. Once it's fully initialized/seeded, it's practically never going to run out of random bits.

I don't understand what you mean by "leak" here.

Again, not a crypto expert, but my understanding is that all stream ciphers leak some bits of the key with enough output. This is why differential cryptanalysis is possible against them. This is also why RC4 could be broken.

EDIT: Perhaps a better algorithm: Accumulate 128 bits of entropy and use that to key Salsa20. Then, whenever another 128 bits are accumulated, simply re-key the stream cipher.

Re: Convert standard Geiger counter to RNG

#25

Post by stcredzero »

lxgr wrote: post #15
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.

Certainly, but your proposed scheme does not feed entropy back into the stream cipher, it just offsets its output.

Which effectively introduces entropy into the output, as well as to the internal state of the stream cipher.

This can be trivially broken if the stream cipher key ever leaks.

This is a trivial restatement of how symmetric ciphers are supposed to work.

Re: Convert standard Geiger counter to RNG

#26

Post by stcredzero »

eternityforest wrote: post #23
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…

Is there actually a limit to how much data you can output? Modern state sizes are so big you'll never get a repeat in billions of years. We also mix entropy in continually. Even if your sources only give you 1 bit per minute, within a few hours you'll have way too much entropy for attackers to decode anything before that window. Plus, if you're using hashing, you can't figure out previous states from the current stat…

Actually building a PRNG yourself would still be hard though!

Well, coming up with a crappy one isn't hard. Coming up with a new good one, with good efficiency is hard, though.

It would be cool if modern devices had a solid state radiation detector for this purpose.

Don't current chips already do this with noise from a diode? Quick google: Yes. There are quite a number of these sorts of methods: https://en.wikipedia.org/wiki/Hardware_random_number_generat...

Nothing is perfect, it turns out.

Re: Convert standard Geiger counter to RNG

#27

Post by eternityforest »

stcredzero wrote: post #26
eternityforest wrote: post #23

Earlier quoted context omitted.

Is there actually a limit to how much data you can output? Modern state sizes are so big you'll never get a repeat in billions of years. We also mix entropy in continually. Even if your sources only give you 1 bit per minute, within a few hours you'll have way too much entropy for attackers to decode anything before that window. Plus, if you're using hashing, you can't figure out previous states from the current stat…

Actually building a PRNG yourself would still be hard though! Well, coming up with a crappy one isn't hard. Coming up with a new good one, with good efficiency is hard, though. It would be cool if modern devices had a solid state radiation detector for this purpose. Don't current chips already do this with noise from a diode? Quick google: Yes. There are quite a number of these sorts of methods: https://en.wikipedia.…

They do, but a regular diode noise source can't double as an actual radiation detector. I was thinking something like a SPAD diode or something, so everyone could have background radiation monitoring at all times and get an alert if someone mixed a cobalt source in the scrap metal used to make their furniture or whatever, or the nearby coal plant was puffing out radiation or something.

Re: Convert standard Geiger counter to RNG

#28

Post by tptacek »

stcredzero wrote: post #24
tptacek wrote: post #21

Earlier quoted context omitted.

I don't understand what you mean by "leak" here. You can definitely make a secure random bit generator with a stream cipher. Once it's fully initialized/seeded, it's practically never going to run out of random bits.

I don't understand what you mean by "leak" here. Again, not a crypto expert, but my understanding is that all stream ciphers leak some bits of the key with enough output. This is why differential cryptanalysis is possible against them. This is also why RC4 could be broken. EDIT: Perhaps a better algorithm: Accumulate 128 bits of entropy and use that to key Salsa20. Then, whenever another 128 bits are accumulated, sim…

It’s why RC4 is broken, not a thing we accept from ciphers that aren’t comically broken.

Re: Convert standard Geiger counter to RNG

#29

Post by adrian_b »

stcredzero wrote: post #24
tptacek wrote: post #21

Earlier quoted context omitted.

I don't understand what you mean by "leak" here. You can definitely make a secure random bit generator with a stream cipher. Once it's fully initialized/seeded, it's practically never going to run out of random bits.

I don't understand what you mean by "leak" here. Again, not a crypto expert, but my understanding is that all stream ciphers leak some bits of the key with enough output. This is why differential cryptanalysis is possible against them. This is also why RC4 could be broken. EDIT: Perhaps a better algorithm: Accumulate 128 bits of entropy and use that to key Salsa20. Then, whenever another 128 bits are accumulated, sim…

The term "stream cipher" is much more general than how you understand it.

There is a huge number of stream ciphers that have never been broken.

There is also a great number of stream ciphers that have been broken, but almost all of them belong to a class of ciphers that deserves the name "cheap stream ciphers".

Such "cheap stream ciphers" have been designed so that they can have a much cheaper implementation than the ciphers that are based on pseudorandom functions similar in complexity to DES and its successors, with the hope that despite being cheaper they will still be hard enough to break.

In most cases, sooner or later these hopes have been shown to be unfounded.

The term "stream cipher" just means that it encrypts a stream of plaintext symbols by combining a stream of encryption mask symbols with them.

There are many kinds of stream ciphers based on how the stream of encryption mask symbols are generated and based on the methods used to combine them with the plaintext.

Even if more general combination functions are possible when the only condition is to be able to decrypt the ciphertext, when an additional condition is imposed, that the statistical properties of the plaintext must not leak into the ciphertext, then the encryption mask symbols must be combined with the plaintext symbols using a quasigroup operation (a.k.a. a Latin square operation).

Most frequently, it is preferred that the quasigroup operation is a group operation, because this makes it simpler to implement. Moreover, usually it is preferred that the group operation is an additive group operation, to have an even cheaper implementation. Such stream ciphers are called additive stream ciphers.

When implemented in software, there are many additive group operations with equal complexity. However, when the encryption is implemented in hardware, addition modulo 2 is the cheapest so it is preferred.

The use of addition modulo 2 as a combination method has been invented by Gilbert S. Vernam in 1918. The term "binary additive stream cipher" should have been synonymous with "Vernam cipher". Unfortunately, in another example of mistaken historical attribution, the term "Vernam cipher" is used to mean any stream cipher where the encryption mask stream is truly random, which is a different invention, first described by Frank Miller in 1882 and rediscovered and popularized by Joseph Mauborgne, a user of Vernam machines.

Based on how the encryption mask stream is generated, there are many kinds of stream ciphers, but most of the practical stream ciphers are either synchronous stream ciphers, where the initial state and the transition function and the output function of the automaton that generates the encryption mask symbols do not depend on the plaintext or on the ciphertext, and self-synchronizing stream ciphers, where the encryption mask symbols are generated either as a pseudorandom function of the ciphertext symbols (these are a.k.a. ciphertext autokey stream ciphers) or as a pseudorandom function of the plaintext symbols (these are a.k.a. plaintext autokey stream ciphers; they have been abandoned a long time ago, because they are less secure). The two kinds of self-synchronizing stream ciphers are dual, i.e. starting from one such cipher a dual cipher is obtained by using the encryption algorithm for decryption and the decryption algorithm for encryption.

The stream ciphers that are most frequently used nowadays are binary additive synchronous stream ciphers, but there is a great variety of possible structures for the automaton that generates the encryption mask symbols. When implemented in software on a modern CPU, the simplest such automaton is made by using AES in counter mode (CTR mode).

Re: Convert standard Geiger counter to RNG

#30

Post by mike_hock »

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.…

How about this?

Preparation: Pick some measurement interval in which you'd expect a bunch of clicks, e.g. a minute. Count how many clicks you get in that interval. Then take 138% of that time and divide it by the number of clicks you counted. That will be the interval for your timer.

RNG: Tune the counter so it rolls over approximately once per time interval you've computed above. We'll take two measurements per interval, b0 and b1. Every time the counter rolls over, reset b0 and b1 to zero. When a click occurs, set b0 to one if the counter is less than half its maximum value, otherwise set b1 to one (if multiple clicks occur, the respective bit just stays at 1). When the counter rolls over, check b0 and b1. If they're equal, do nothing (discard the measurement). If they're different, take b0 as a random bit that you've just created (discard b1, and then reset b0 and b1 for the next round). You can then combine multiple successive bits into random numbers of the width that you want.

Post reply on HN