4 ms·
Any hardware RNG that is included in a CPU or any other complex integrated circuit cannot be trusted, because it is impossible to verify that it is truly a RNG
by adrian_b 4y ago
Any hardware RNG that is included in a CPU or any other complex integrated circuit cannot be trusted, because it is impossible to verify that it is truly a RNG and not a pseudo-RNG that implements backdoors.
The only hardware RNGs that can be trusted are those that use an analog-digital converter (e.g. one of the ADCs included in any microcontroller, or the audio microphone input of a computer) and a discrete analog noise source, e.g. a diode or a resistor, because their components can be tested separately, to verify that they do what they claim to do.
Nevertheless, the output of the hardware RNGs provided by the Intel or AMD CPUs can be used in a reasonably secure way if the supposedly random values are never used directly, but they are passed through a cryptographic hash, e.g. SHA-256. Even SHA-1 is completely adequate for this special purpose, where collision-resistance does not matter (and it is faster than any other secure hashes in the ARM, AMD or Intel CPUs with SHA-1 instructions).
Even better, the supposedly random value could be hashed together with the timestamp read from the TSC, or just with the value of a counter incremented after generating a random number, for additional unpredictability. One can add to the hash a unique computer identifier, e.g. the MAC address of the first Ethernet interface. In this case, distinct sequences of uniformly-distributed pseudo-random numbers will continue to be produced even in computers where the hardware RNG remains stuck to a constant value, as it happened in some buggy AMD Zen models.
The hashing (with a secure hash algorithm) of the RNG output destroys any hidden structure that might have been exploitable by the designers of the hardware RNG, while preserving the uniform distribution of the random numbers.
- eternityforest 4y agoI don't think straight hashing is enough. Suppose the internal RNG is just AES in counter mode(Assume somehow they can persist state internally) They then know the full list of numbers it will ever make. They also know the full list of hashed numbers it will ever make, if they know the hashed block size, which they do if they know what software you are using. Now when you make a private key they just try all trillion possible offsets into the list of numbers it could likely be, hash those 32 bytes or whatever the block size is, and see if that's your key. But I am not the paranoid type nor do I currently have things to hide from anyone with access to Intel backdoors, so I'm not too worried. I think Linux has it pretty well figured out mixing in other sources just to be sure.
- adrian_b 4y agoIt is completely impractical to store a table of hash values that is large enough to be able to reverse the hash. No HDD will be big enough. Moreover, as I have already written, this possibility is easily circumvented by also hashing a time-varying value and a value unique to each computer, not only the RNG output.
- eternityforest 4y agoIf the unique value is secret, yes. Otherwise there is no need to store a table of values. If a home type PC is used for a year, there will be a finite amount of randomness used from the HW generator in total. Probably under a terabyte I would guess. Maybe under a gigabyte. If you are doing something like looking for an encryption key, you know it's somewhere in that terabyte, which you can generate too, then put every possible block through your hash, and try it. You don't even need to store anything, you can just generate them since they're deterministic. And if the backdoor is based on a block cipher in in counter mode or something like that, you can do it all in parallel on FPGAs in seconds if you're a billionaire.
- bscphil 4y ago> Nevertheless, the output of the hardware RNGs provided by the Intel or AMD CPUs can be used in a reasonably secure way if the supposedly random values are never used directly, but they are passed through a cryptographic hash, e.g. SHA-256. Even SHA-1 is completely adequate for this special purpose Why would you go to any of this trouble and not just XOR the output of RDRAND into the starting seed (based on hardware entropy) for your PRNG (/dev/urandom)? Even if it turns out that Intel is providing a single static value (like all zeros) to every device ever, that's not going to help them figure out the starting seed if the rest of the entropy is from a sufficiently secure source.
- moonchild 4y agoSufficiently adversarial rdrand could snoop the rest of your seed and choose its result appropriately. But sha256 is not reversible.
- dragontamer 4y agoA sufficiently adversarial CPU could detect the sha256 hash you're using as a random number generator (and no other sha256 hash) and set its result to a known value as well. At some point, you gotta just trust the hardware.
- KerrAvon 4y agoThis sounds excessively paranoid to me. If you’re worried about backdoors and the threat model includes the ability to compromise the CPU, you probably need to back up a few steps and figure out how the CPU got compromised? What am I missing?
- adrian_b 4y agoAny CPU can be compromised by its designers, and the owner cannot verify whether this is true or not. All Intel and AMD CPUs are compromised from a security POV by features much more dangerous than the hardware RNG, i.e. by the existence of the System Management Mode and of the extra processors included in the CPU package, which can do absolutely anything in a manner that cannot be detected by the owner of the computer. As long as Intel and AMD do not publish a complete documentation of how their remote management features work and as long as they do not allow the owners of the computers to control them, it can only be assumed that they can be backdoored. Whatever documentation exists for those features, it appears to be provided only under NDA, presumably only to the companies which write remote management applications for large corporations. Nevertheless, like for the hardware RNG, there are workarounds that can make very unlikely the exploitation of any hardware backdoor. For example, if a computer with an Intel CPU is used in a router/firewall exposed to the Internet, it is prudent to not use any Intel Ethernet interface for the Internet interface. If there are only Intel Ethernet interfaces, an USB to Ethernet adapter can be used. This will prevent the use of the remote management by an attacker. The same applies for the WiFi, for a secure router/firewall, any Intel WiFi must be disabled (e.g. by disconnecting the antennas) and replaced by a WiFi dongle.
- dragontamer 4y ago> Any hardware RNG that is included in a CPU or any other complex integrated circuit cannot be trusted, because it is impossible to verify that it is truly a RNG and not a pseudo-RNG that implements backdoors. If the opponent has enough control of your CPU to rewrite your assembly instructions to do nefarious things, you have more than just RDSEED to worry about.
- adrian_b 4y agoFor the RNG to be backdoored there is no need for something as unlikely as "rewriting assembly instructions". It is enough for the supposedly random numbers to be non-random, i.e. deterministic, according to a function known only by the designers of the hardware RNG. It is impossible to distinguish by testing a true RNG from a good pseudo-RNG. Designing a hardware pseudo-RNG instead of the claimed true RNG is a trivial task. Succeeding to exploit it to decrypt something, e.g. some HTTPS traffic, is however not very likely, because it is easy to avoid this by combining the output of RDSEED with other sources of random numbers and by processing it, e.g. by hashing. So it can be hoped that the designers of a hardware RNG do not attempt to backdoor it, because the chances of that being used successfully are low and the penalty if that would ever be discovered is high.