4 ms·

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_s

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?

lxgr 3y ago
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.
er4hn 3y ago
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.SP.800-90Ar1.pdf 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.
- kloch 3y ago
  Analysis of PRNG's is difficult and very important: https://www.pcg-random.org/posts/does-it-beat-the-minimal-standard.html https://www.pcg-random.org/posts/does-it-beat-the-minimal-st...
  - tptacek 3y ago
    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.
- eternityforest 3y ago
  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!
  - stcredzero 3y ago
    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_generator https://en.wikipedia.org/wiki/Hardware_random_number_generat... Nothing is perfect, it turns out.
    - eternityforest 3y ago
      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.
aljarry 3y ago
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#BSI_evaluation_criteria https://en.wikipedia.org/wiki/Pseudorandom_number_generator#... where first two are interesting for a non-cryptographic PRNG.
Verdex 3y ago
IIRC there's a PRNG talk for videogames where they mention your method: https://www.youtube.com/watch?v=LWFzPP8ZbdU&t=4s 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.

lxgr 3y ago

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.

er4hn 3y ago

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.SP.800-90Ar1.pdf 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.

kloch 3y ago
Analysis of PRNG's is difficult and very important: https://www.pcg-random.org/posts/does-it-beat-the-minimal-standard.html https://www.pcg-random.org/posts/does-it-beat-the-minimal-st...
- tptacek 3y ago
  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.
eternityforest 3y ago
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!
- stcredzero 3y ago
  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_generator https://en.wikipedia.org/wiki/Hardware_random_number_generat... Nothing is perfect, it turns out.
  - eternityforest 3y ago
    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.

aljarry 3y ago

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#BSI_evaluation_criteria https://en.wikipedia.org/wiki/Pseudorandom_number_generator#... where first two are interesting for a non-cryptographic PRNG.

Verdex 3y ago

IIRC there's a PRNG talk for videogames where they mention your method: https://www.youtube.com/watch?v=LWFzPP8ZbdU&t=4s 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.