3 ms·

I'm confused; if you can predict the output, then isn't it by definition not secure? Or is the seed so hard to brute force that it's equivalent to breaking the

I'm confused; if you can predict the output, then isn't it by definition not secure? Or is the seed so hard to brute force that it's equivalent to breaking the underlying cryptography.

hinkley 3y ago
Guessing the seed is impossible using current knowledge of information theory and predictable breakthroughs in new computer hardware. That may or may not include quantum. Entropy sources in for instance Linux constantly receive new data, but there are CSPRNGs that only receive truly random data at construction time, and you can intentionally expose that data in your testing code. Or to be precise, since this is security we are talking about: You can set your bootstrapping code to take a seed as input, and your tests can generate and log that seed, while the real code picks its own (secret) value and keeps it safely away from storage. I don't know how Java works now but it worked this way about ten years ago. It takes a lot of work to get people to use randomized testing properly. Seed reproduction is table stakes IMO and yet I've had to introduce it a couple of times because it was missing. Getting people to look at test failures instead of clicking 'run again' is a whole psycho-social tarpit. In fact I suspect whoever invented Property Based Testing was trying to route around this tarpit - do random tests, then provide concrete repro steps, so people can't ignore them and hope.
tptacek 3y ago
People talking about seedable CSPRNGs for Monte Carlo work are proposing that you use CSPRNG algorithms, but in userland, as a library; instead of periodically rekeying them with unpredictable data collected from timing and hardware, you'd key it just once, with a known key, and thus generate a predictable sequence of "random" bits for your simulation.
espadrine 3y ago
If you have the key to a ciphertext, you can decrypt it, but that doesn't make the cipher insecure. It is the same principle for the seed of a CSPRNG. In fact, a common cipher construction (ChaCha20, for instance) relies on a random stream seeded by the key, generated by the sender to encrypt data, which the recipient re-generates from that same key to decrypt the data.
jmprspret 3y ago
There is no such thing as a true random generator when we are talking about software - hence the P in PRNG. The seed value to any of these algorithms is meant to be the "true" random part - or as close to that as it can be. The idea here is that given a truely random seed, the algorithm should subsequently generate random bits that aren't predicable from its last output. So given the first 128 bits of output you shouldn't be able to predict the next bit for example. Given the same seed a PRNG, and a CSPRNG will always output the same bits. Hopefully that explains it?
Klaus23 3y ago
As hinkley said, it is basically impossible to get the seed from the output of the generator without breaking the algorithm itself. CSPRNG can also be used as the basis for a stream cipher. The output must be the same for the receiver of the message to be able to decrypt it. Being able to extract the seed would be problematic because an attacker could know some part of the message being sent, calculate the CSPRNG output from it and get the seed, thus being able to read all the messages. CSPRNG are specifically designed to be a one-way function. Calculating the output from the seed should be easy, but calculating the seed from any output must be impossible.
SonOfLilit 3y ago
CSPRNG means "if the seed were secure, it would be secure", i.e. "the mixing is so good we don't even know how to undo it"

I'm confused; if you can predict the output, then isn't it by definition not secure? Or is the seed so hard to brute force that it's equivalent to breaking the underlying cryptography.

hinkley 3y ago

Guessing the seed is impossible using current knowledge of information theory and predictable breakthroughs in new computer hardware. That may or may not include quantum. Entropy sources in for instance Linux constantly receive new data, but there are CSPRNGs that only receive truly random data at construction time, and you can intentionally expose that data in your testing code. Or to be precise, since this is security we are talking about: You can set your bootstrapping code to take a seed as input, and your tests can generate and log that seed, while the real code picks its own (secret) value and keeps it safely away from storage. I don't know how Java works now but it worked this way about ten years ago. It takes a lot of work to get people to use randomized testing properly. Seed reproduction is table stakes IMO and yet I've had to introduce it a couple of times because it was missing. Getting people to look at test failures instead of clicking 'run again' is a whole psycho-social tarpit. In fact I suspect whoever invented Property Based Testing was trying to route around this tarpit - do random tests, then provide concrete repro steps, so people can't ignore them and hope.

tptacek 3y ago

People talking about seedable CSPRNGs for Monte Carlo work are proposing that you use CSPRNG algorithms, but in userland, as a library; instead of periodically rekeying them with unpredictable data collected from timing and hardware, you'd key it just once, with a known key, and thus generate a predictable sequence of "random" bits for your simulation.

espadrine 3y ago

If you have the key to a ciphertext, you can decrypt it, but that doesn't make the cipher insecure. It is the same principle for the seed of a CSPRNG. In fact, a common cipher construction (ChaCha20, for instance) relies on a random stream seeded by the key, generated by the sender to encrypt data, which the recipient re-generates from that same key to decrypt the data.

jmprspret 3y ago

There is no such thing as a true random generator when we are talking about software - hence the P in PRNG. The seed value to any of these algorithms is meant to be the "true" random part - or as close to that as it can be. The idea here is that given a truely random seed, the algorithm should subsequently generate random bits that aren't predicable from its last output. So given the first 128 bits of output you shouldn't be able to predict the next bit for example. Given the same seed a PRNG, and a CSPRNG will always output the same bits. Hopefully that explains it?

Klaus23 3y ago

As hinkley said, it is basically impossible to get the seed from the output of the generator without breaking the algorithm itself. CSPRNG can also be used as the basis for a stream cipher. The output must be the same for the receiver of the message to be able to decrypt it. Being able to extract the seed would be problematic because an attacker could know some part of the message being sent, calculate the CSPRNG output from it and get the seed, thus being able to read all the messages. CSPRNG are specifically designed to be a one-way function. Calculating the output from the seed should be easy, but calculating the seed from any output must be impossible.

SonOfLilit 3y ago

CSPRNG means "if the seed were secure, it would be secure", i.e. "the mixing is so good we don't even know how to undo it"