r/cryptography • u/neuralbeans • 9d ago
Why cryptographically secure random number generation must be difficult to reverse
CSPRNG algorithms like Blum Blum Shub make use of one way functions to transform one PRNG state into the next. For example, modular squaring of the state (modular square root requires factoring) or modular exponentiation (discrete logarithms are computationally hard).
It seems that the reasoning is, if the random state is compromised (state compromise extension attack), then the attacker would be able to know what the future random numbers will be but not what the previously generated random numbers were. I am not finding any information on why this particular requirement is important. How is it useful to be able to keep past generated random numbers secret when future ones are compromised?
5
u/doggydestroyer 9d ago
Let's suppose you generate ssl keys and random primes for that... Let's suppose for RSA... Then getting prior state of RNG will compromise previous keys...
1
u/neuralbeans 8d ago
Shouldn't you be using non deterministic true random numbers for those?
3
u/doggydestroyer 8d ago
Typically the rate of RNG must be very high especially for servers... AES-CTR for example mode is a very high quality RNG that can produce GB/s... Also debiasing true random observation needs some kind of hash function as well... So pipeline is unpredictable data -> hash conditioner -> AES-CTR mode...
1
u/neuralbeans 8d ago
CSPRNGs are slow as well, no?
2
u/atoponce 8d ago edited 8d ago
They don't have to be, no. A simple CSPRNG is AES in fast-key-erasure mode. If you have AES-NI, then you can produce an extremely fast random bitstream. On the order of gigabits per second.
On my Intel Core i7-8650U CPU @ 1.90GHz, I get just shy of 800 MBps with a 16-byte block and 6 GBps with a 16k byte block with AES-128-ECB:
$ openssl speed -evp aes-128-ecb ...(snip)... type 16 bytes 64 bytes 256 bytes 1024 bytes 8192 bytes 16384 bytes AES-128-ECB 792189.37k 3070270.93k 5008869.29k 5758503.59k 6132162.56k 6176565.93kCompared to ChaCha20, which is not hardware accelerated, it's about half as good:
$ openssl speed -evp chacha20 ...(snip)... type 16 bytes 64 bytes 256 bytes 1024 bytes 8192 bytes 16384 bytes ChaCha20 342175.45k 711233.66k 1477347.32k 3090790.74k 3314854.57k 3210231.81kSure, there will be some overhead for the re-keying logic, but not enough to significantly impact the performance of the CSPRNG. It's one call of the primitive, the rest is insignificant overhead. It is still considerably faster than any off-the-shelf HWRNG, even those from ID Quantique.
Edit: typo
3
u/WE_THINK_IS_COOL 9d ago edited 9d ago
Suppose you compromise a web server that generates its API authentication tokens using a CSPRNG and stores their hashes for validation. If you could run that web server's CSPRNG backwards, you could recover all of the previously-emitted authentication tokens, whereas if you can't, you're stuck trying to crack the hashes.
Or perhaps a web server and client use a CSPRNG to generate their TLS session keys in modes with forward secrecy. If you could run their CSPRNGs backwards in time, you could get those keys and decrypt past TLS sessions.
A reversible CSPRNG's outputs are vulnerable to theft from a compromise occurring indefinitely in the future. So making the CSPRNG non-reversible limits the window of exposure of outputs that are generated but not stored on the system (since if they were stored, the attacker could just get them from wherever they were stored instead of running the CSPRNG backwards).
You also want to make sure it's impossible to recover the CSPRNG's state from the outputs, which is another reason one-way functions are used. And continually injecting randomness or re-seeding prevents an attacker from learning future outputs as well (e.g. if their attack was limited to just being able to make a copy of the system's state, like they can't persist malware on the machine or whatever).
1
u/neuralbeans 8d ago
I guess my question is why use a deterministic CSPRNG that would compromise future generated numbers when you can use a non-deterministic true RNG that would keep both past and future generated numbers secret.
3
u/WE_THINK_IS_COOL 8d ago
Mainly for speed. True hardware RNGs can only produce bits at a limited rate, and the application might need more bits per second than the hardware can produce, so in practice (e.g. in the Linux kernel's /dev/urandom) a CSPRNG is used for generating the output, which periodically has true randomness from the hardware RNG injected into its state to prevent forward/backward-looking attacks.
Older CPUs also do not have a hardware RNG built in, so in that case the OS is limited to collecting "true" randomness from the precise timing of interrupts, network and disk I/O, and so forth, which is extremely slow at gathering entropy.
In that case the entropy needs to be estimated and "pooled" to be injected all at once in large batches, using the CSPRNG for generating output in between. If small amounts of entropy were just injected immediately instead of in large batches, then an application could continually read the CSPRNG's output and brute-force each injected value "Hollywood style", i.e. brute-forcing the 10 unknown bits of the precise timing 100 times (100 * 2^10 operations) by asking for the next CSPRNG output after each 10-bit injection, instead of having to brute-force the whole batch of entropy (2^(10 * 100) operations) when it's pooled and injected all at once.
3
u/Honest-Finish3596 8d ago
Knowing any part of the plaintext of a stream cipher gives you knowledge of the keystream at that point automatically, then you can just rewind to get the rest of it. For this reason it should not only not be possible to reverse, but also impossible to predict forwards.
Known plaintext attacks are always a concern because the attacker can always guess parts of your plaintext, unless you are encrypting uniformly random numbers.
Blum blum shub is insecure for all practical parameter sizes and you should use a symmetric key stream cipher instead.
2
u/Intelligent_Law_5614 9d ago
Consider a system in which a server is using such a generator to create cryptographic keys or nonces, which it uses to create encrypted session connections with a bunch of different clients.
Consider what would happen if one client of such a server was a bad actor.
If it could ask the server to create an encrypted connection, and could use the key it negotiated with the server to discover the RNG's internal state and reverse-compute the earlier states, it would then be able to deduce the session keys which the server had generated previously for other connections. If it has been able to eavesdrop on the earlier connections it could then decrypt the content of those connections. This is one instance of a "record now, decrypt later" attack.
Because this is s reverse attack, the server could not mitigate it after the fact by discarding and renewing the internal state of the RNG using fresh entropy, even if it did this immediately after giving a key to the bad actor.
2
u/dittybopper_05H 5d ago
How is it useful to be able to keep past generated random numbers secret when future ones are compromised?
This should be obvious, but to keep your past traffic secure.
If you're using encryption it's because you want to keep the information being exchanged a secret. You can learn a lot about current events by reading past traffic. This is why signals intelligence organizations keep traffic that they can't break pretty much indefinitely, because they might one day be able to actually break it.
1
u/esteindividu0 9d ago
any inversion algorithm gives immediately a distinguisher from random: to distinguish you can just check if the inverter succeeded.
1
u/neuralbeans 8d ago
If you can predict future numbers then you can still confirm that they are not true random, no?
2
u/esteindividu0 8d ago
yes, that is the idea. a successful inverter can be used to predict accurately, whereas no true random string allows it.
16
u/atoponce 9d ago
Imagine just encrypting a counter. If the state is compromised, then the attacker knows the current value of that counter. Run the counter in reverse, and you can calculate prior states of the generator. With that, you could discover previously generated secrets.