Eliezer will be better understood if he uses the standard term in the standard way.
Agreed.
A computer scientist would not describe the “omega” case as random—if the input is correlated with the random number source in a way that is detectable by the algorithm, they’re by definition not random.
Right. But I want to repeat the objection here that we often use pseudorandomness instead of actual randomness, and then the real worst case is that we’ve gotten a cursed seed. Somewhat less practically, in situations where a real adversary may have access to our hardware, we may have to assume that they can read (or write to!) our RNG.
Somewhat less practically, in situations where a real adversary may have access to our hardware, we may have to assume that they can read (or write to!) our RNG.
I think this is a practical scenario in cryptography where your threat model is state-level actors.
They may only be able to access your hardware in limited ways. For example, if a hardware “RNG” actually outputs 1,2,3,… encrypted with some key known only to the NSA, that’s essentially totally undetectable. But if instead they have the hardware send out extra information over the internet, sooner or later someone will notice and the game will be up.
They don’t need to sync for it to be a serious weakness in a cryptosystem. If a system using Khoth’s PRNG sends out a billion encrypted messages in its lifetime, then an attacker with the PRNG key needs less than 2^30 tries to decrypt a message sent at an unknown point in that sequence—a large number, but more than manageable when you consider that a PRNG with a period of 2^80 would be considered weak in the crypto world.
If your adversary can read or write bits in your hardware, then what is the purpose of using cryptography?
Side channel attacks on hardware are not rare. For example, an adversary might have a way of measuring the power consumption of your CPU as it does RNG calculations. This is not quite the ability to “read or write bits in… hardware”, but it is a viable attack to gain information about your, ahem, random numbers.
Agreed.
Right. But I want to repeat the objection here that we often use pseudorandomness instead of actual randomness, and then the real worst case is that we’ve gotten a cursed seed. Somewhat less practically, in situations where a real adversary may have access to our hardware, we may have to assume that they can read (or write to!) our RNG.
I think this is a practical scenario in cryptography where your threat model is state-level actors.
If your adversary can read or write bits in your hardware, then what is the purpose of using cryptography?
They may only be able to access your hardware in limited ways. For example, if a hardware “RNG” actually outputs 1,2,3,… encrypted with some key known only to the NSA, that’s essentially totally undetectable. But if instead they have the hardware send out extra information over the internet, sooner or later someone will notice and the game will be up.
How does the NSA synchs with your “RNG” is no information is exchanged?
But anyway, if you reasonably believe that your RNG may have been compromised, then you just don’t use it.
They don’t need to sync for it to be a serious weakness in a cryptosystem. If a system using Khoth’s PRNG sends out a billion encrypted messages in its lifetime, then an attacker with the PRNG key needs less than 2^30 tries to decrypt a message sent at an unknown point in that sequence—a large number, but more than manageable when you consider that a PRNG with a period of 2^80 would be considered weak in the crypto world.
Agreed.
Side channel attacks on hardware are not rare. For example, an adversary might have a way of measuring the power consumption of your CPU as it does RNG calculations. This is not quite the ability to “read or write bits in… hardware”, but it is a viable attack to gain information about your, ahem, random numbers.
Sure, but at this point they can also gain information on your keys or the data you wish to encrypt.
Not necessarily. Think wider, not only PCs use encrypted communications. Consider a router, for example, or a remote sensor.
Still, if they can compromise the RNG state in the router/sensor/whatever, they could probably compromise its CPU and/or RAM.
That’s not self-evident to me. Passively observing power consumption is much easier than, say, getting inside a SOC in tamper-resistant packaging.