Yeah, this has actually been a known thing for a while. The government has been sneakily getting their hand into NIST standards and trying to ensure they have back doors in the commonly used “best practices”.
So as a result for instance, encryption based on pseudo random numbers generated with hashing algorithms are actually safer that these theoretically “actually random” numbers generated in dedicated security modules in hardware.
I’ve never fully understood the issue with pseudo-random numbers… but I do know there’s an issue. I know, for example, bad random number generators have been the surface area of attack for recovering HDD crypto wallets with old bitcoin balances on them.
Would you care to help me understand something, though?
I think a fair framing here is that pseudo-random numbers generators need a random “seed” (starting value) to produce the resulting random number. So if someone knows the initial seed, they can rerun the algorithm to reproduce the original “random” number.
I think what follows is that good pseudo-random number generators introduce complexity and obfuscation in how the seed is created. Perhaps they use current time, speaker input, mouse input, and some other seemingly “random” data source.
Given enough dimensions (sources) in the source material for the seed, surly it would create an intractable number of permutations such that the seed can not be reliably reproduced — right?
Like, let’s say you know a 10 minute interval where the seed was created — and the tool uses millisecond granularity. That’s 1000 (mili) * 60 (sec) * 10 (min) total possible values. If it’s also collecting mouse movement in a screen, that’s a huge number of possibilities with each given interval of movement. Adding more sources (dimensions) increases the number of possibilities exponentially.
So how are people reverse engineering seeds? This seems secure to me, for the same reason cryptographic keys using giant prime numbers is secure… there are just too many possibilities, and it would take eons to brute force the right one.
How are they doing it faster with seeds? Shitty algorithms not using enough data sources?
The issue is not usually with the seed (although being able to determine the seed used for a PRNG completely defeat its purpose). The biggest issue (aside from deterministic seed) is that not all (P)RNG are created equal. Some have seemingly infinitely long, non repeating sequences, that varies greatly for a minuscule change in the seed (the good ones). Some have relatively short, repeating sequences. Some are so badly implemented that actually seeing a few numbers of the sequence allows reverse-engineering their internal state, so you can get the next numbers for free afterward. If you don’t use a big function with an impossible to probe initial state (like any good cryptographic hash function), you could even go backward in the sequence, finding previously generated secrets.
There’s plenty of attack surface on bad implementation of a (P)RNG. And the hardware ones combines “nuh-uh, we won’t tell you the seed” with “nuh-uh, you’ll have to trust our implementation”. That’s why, as far as I know, hardware RNG is usually used as one of the source for the seed of a PRNG.
For example, although it was deemed a bug, some AMD processor, for a while, failed to generate actual randomness under some circumstances. That’s a problem if you only rely on them. That’s why dumping that in a tumbler of other sources is a good idea. (sorry for the reddit link: https://old.reddit.com/r/AMDHelp/comments/itfgf4/cpu_random_generator_seem_to_be_failing/ )
The way you get your seed also matter. Time-based seed, if you have a vague idea of when it was acquired, is easy to check. Sure, there might be a window of a few hundred of thousands of milliseconds, but that’s nothing too hard to check if you’re sure this would yield you a secure key you really need. Multiplying the source, from sources that seemingly can’t be under the control of an attacker is important, but you have to be careful. An anecdote I was told at a conference was about using the system’s delay on read. Since reading happened at seemingly random (with a busy system), on a HDD, where the head have to actually move and the platters have to spin, it might be a good idea. When people moved to SSD, the reading delay became almost constant. Not such a good source now.
An example of failure on properly seeding your PRNG would be the random SSH keys generated by Debian (a long time ago).
The random generation of keys moved from almost the full space of possibility to around 32.000 keys. That’s low enough that those keys are actually listed and banned from being used by some systems.
More info about that here: https://www.hezmatt.org/~mpalmer/blog/2024/04/09/how-i-tripped-over-the-debian-weak-keys-vuln.html
If your PRNG is implemented correctly, with proper impossible (well, extremely hard) to reverse functions, and a really good seed that can’t be exfiltrated, periodically augmented (and not replaced!) with many source of seemingly out of control randomness, there’s little to do against that beyond just dumping memory beforehand and taking it out the hard way. Unfortunately, a lot of people think “outside the box” and wants to reimplement their own. Or rely on faulty hardware. Or rely on tampered hardware. And so on.
Yeah, this has actually been a known thing for a while. The government has been sneakily getting their hand into NIST standards and trying to ensure they have back doors in the commonly used “best practices”.
So as a result for instance, encryption based on pseudo random numbers generated with hashing algorithms are actually safer that these theoretically “actually random” numbers generated in dedicated security modules in hardware.
I’ve never fully understood the issue with pseudo-random numbers… but I do know there’s an issue. I know, for example, bad random number generators have been the surface area of attack for recovering HDD crypto wallets with old bitcoin balances on them.
Would you care to help me understand something, though?
I think a fair framing here is that pseudo-random numbers generators need a random “seed” (starting value) to produce the resulting random number. So if someone knows the initial seed, they can rerun the algorithm to reproduce the original “random” number.
I think what follows is that good pseudo-random number generators introduce complexity and obfuscation in how the seed is created. Perhaps they use current time, speaker input, mouse input, and some other seemingly “random” data source.
Given enough dimensions (sources) in the source material for the seed, surly it would create an intractable number of permutations such that the seed can not be reliably reproduced — right?
Like, let’s say you know a 10 minute interval where the seed was created — and the tool uses millisecond granularity. That’s 1000 (mili) * 60 (sec) * 10 (min) total possible values. If it’s also collecting mouse movement in a screen, that’s a huge number of possibilities with each given interval of movement. Adding more sources (dimensions) increases the number of possibilities exponentially.
So how are people reverse engineering seeds? This seems secure to me, for the same reason cryptographic keys using giant prime numbers is secure… there are just too many possibilities, and it would take eons to brute force the right one.
How are they doing it faster with seeds? Shitty algorithms not using enough data sources?
The issue is not usually with the seed (although being able to determine the seed used for a PRNG completely defeat its purpose). The biggest issue (aside from deterministic seed) is that not all (P)RNG are created equal. Some have seemingly infinitely long, non repeating sequences, that varies greatly for a minuscule change in the seed (the good ones). Some have relatively short, repeating sequences. Some are so badly implemented that actually seeing a few numbers of the sequence allows reverse-engineering their internal state, so you can get the next numbers for free afterward. If you don’t use a big function with an impossible to probe initial state (like any good cryptographic hash function), you could even go backward in the sequence, finding previously generated secrets.
There’s plenty of attack surface on bad implementation of a (P)RNG. And the hardware ones combines “nuh-uh, we won’t tell you the seed” with “nuh-uh, you’ll have to trust our implementation”. That’s why, as far as I know, hardware RNG is usually used as one of the source for the seed of a PRNG.
For example, although it was deemed a bug, some AMD processor, for a while, failed to generate actual randomness under some circumstances. That’s a problem if you only rely on them. That’s why dumping that in a tumbler of other sources is a good idea. (sorry for the reddit link: https://old.reddit.com/r/AMDHelp/comments/itfgf4/cpu_random_generator_seem_to_be_failing/ )
The way you get your seed also matter. Time-based seed, if you have a vague idea of when it was acquired, is easy to check. Sure, there might be a window of a few hundred of thousands of milliseconds, but that’s nothing too hard to check if you’re sure this would yield you a secure key you really need. Multiplying the source, from sources that seemingly can’t be under the control of an attacker is important, but you have to be careful. An anecdote I was told at a conference was about using the system’s delay on read. Since reading happened at seemingly random (with a busy system), on a HDD, where the head have to actually move and the platters have to spin, it might be a good idea. When people moved to SSD, the reading delay became almost constant. Not such a good source now.
An example of failure on properly seeding your PRNG would be the random SSH keys generated by Debian (a long time ago). The random generation of keys moved from almost the full space of possibility to around 32.000 keys. That’s low enough that those keys are actually listed and banned from being used by some systems. More info about that here: https://www.hezmatt.org/~mpalmer/blog/2024/04/09/how-i-tripped-over-the-debian-weak-keys-vuln.html
If your PRNG is implemented correctly, with proper impossible (well, extremely hard) to reverse functions, and a really good seed that can’t be exfiltrated, periodically augmented (and not replaced!) with many source of seemingly out of control randomness, there’s little to do against that beyond just dumping memory beforehand and taking it out the hard way. Unfortunately, a lot of people think “outside the box” and wants to reimplement their own. Or rely on faulty hardware. Or rely on tampered hardware. And so on.