6 ms·

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

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

lxgr 3y ago
> 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.
- tptacek 3y ago
  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!
- stcredzero 3y ago
  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.
tptacek 3y ago
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.
- stcredzero 3y ago
  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.
  - tptacek 3y ago
    It’s why RC4 is broken, not a thing we accept from ciphers that aren’t comically broken.
    - stcredzero 3y ago
      Isn't that a matter of degree? RC4 leaks a lot. "Acceptable" ciphers leak so little, it's still not feasible to break the full version. But apparently this scales with increasing or reducing rounds. So it seems unlikely it ever goes to zero. It just gets near enough to zero, that there are no feasible attacks for some length of message.
      - tptacek 3y ago
        No, it's not. A reasonable cryptanalytical model of a modern stream cipher (AED in a stream mode, or Salsa20, or whatever) is that --- within the birthday bounds of the underlying cipher (exabytes? you'd look it up, whatever you're using), and, in the case of something like an AEAD (or maybe just in the idiosyncratic case of GCM), the bounds of your nonce width --- they're not leaking _anything_. "Comical" really is the right word to use with respect to what RC4 did. It is kind of amazing that a cipher that broken remained in common use for as long as it did.

lxgr 3y ago

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

tptacek 3y ago
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!
stcredzero 3y ago
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.

tptacek 3y ago

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.

stcredzero 3y ago
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.
- tptacek 3y ago
  It’s why RC4 is broken, not a thing we accept from ciphers that aren’t comically broken.
  - stcredzero 3y ago
    Isn't that a matter of degree? RC4 leaks a lot. "Acceptable" ciphers leak so little, it's still not feasible to break the full version. But apparently this scales with increasing or reducing rounds. So it seems unlikely it ever goes to zero. It just gets near enough to zero, that there are no feasible attacks for some length of message.
    - tptacek 3y ago
      No, it's not. A reasonable cryptanalytical model of a modern stream cipher (AED in a stream mode, or Salsa20, or whatever) is that --- within the birthday bounds of the underlying cipher (exabytes? you'd look it up, whatever you're using), and, in the case of something like an AEAD (or maybe just in the idiosyncratic case of GCM), the bounds of your nonce width --- they're not leaking _anything_. "Comical" really is the right word to use with respect to what RC4 did. It is kind of amazing that a cipher that broken remained in common use for as long as it did.