This serves as your daily reminder that modern CSPRNG designs don't rely on a single entropy source, but rather mix many sources with hashes or block ciphers into entropy pools.
It would indeed have been bad if Linux (insanely) had converted to relying entirely on RDRAND as a replacement for the devrandom kernel CSPRNG. But no OS I know has done anything like that.
Even at 32 bits of entropy (which is an extremely unlikely conspiracy theory, as Schneier says), mixing the output of RDRAND into the rest of the entropy available to a kernel would still be a marginal improvement. For instance, it would mitigate some concerns about cold-start entropy for solid-state machines without real entropy sources.
The fact that OS CSPRNGs were unlikely ever to have trusted RDRAND directly (even if wasn't backdoored, what if someone screwed up? That too is somewhat unlikely, given that Paul Kocher's Cryptography Research reviewed the Intel HWRNG. But still...), and the fact that it's such a high-profile place to put a hardware backdoor, leads me to conclude that this is an unlikely vector for hardware backdoors.
Note that there are tests that would catch this, but Intel specifically chooses not to test the hardware RNG using them, according to the paper. (This is ostensibly to guard against attacks on the RNG using scan mode. That could very well be true; I don't have enough domain knowledge in designing secure hardware to know whether this is a common practice or not.)
Detecting stuck-at faults is one of the main applications of scan testing[1]. Generally coverage isn't perfect, but by spending more time and making particular implementation decisions one can make coverage pretty close to arbitrarily good.
Moreover, I can always choose to randomize my scan chains if I think this is a threat, and then an attacker will have to assume that he's only allowed to modify gates that can't be covered by any possible scan chain. Remember, the attacker has to modify the mask, so that means I'm making a large number of chips that all have the same flaw. So if I detect stuck-at faults using randomized scan chains on any wafer in a lot and I'm paranoid, I can re-run the failing scan chain on other chips from the same lot to determine whether it's systematic or random failure.
Lest you think this is an inconvenient test to perform, almost all digital chips are scanned because it's one of the fastest ways to detect manufacturing defects. Unlike rewiring a chip, generating stuck-at faults is a really bad way of being sneaky if the target circuit is being scanned, because as I said above that's a type of error against which scan is quite good.
This happens to be my area of expertise and is exactly true. Basic DFT would prevent this from happening without a customer knowing. Also, anything below 65nm and the chip is almost certain to have stuck@ scan testing at the minimum. The chip would be marked bad during production and tossed out. The only way in todays market this could get through is if the design was intentionally done this way, otherwise the test vectors would not match the silicon. EDIT: After reading more about their decision to use LBIST for this logic I could see a possible back door, but it does up the complexity of this hack. In my opinion this is a very low probability attack vector. It would be much easier to just pay off a disgruntled designer.
The designers of the Z-80 did the same thing (modifying dopant levels so transistors would look like normal transistors but function differently) in order to avoid competitors from cloning the chip.
Faggin (Zilog CEO): "Yes, we were concerned about others copying the Z80. So I was trying to figure what we could
do that that would be effective, and thatβs when I came across an idea that if we use the depletion load
the mask that doesnβt leave any trace, then I could create depletion load devices that look like
enhancement mode devices. And by doing that we could trick the customer into believing that a certain
logic was implemented, when it was not."
Shima (Z-80 designer): "I placed six traps for stopping the copy of the layout
by the copy maker. And one transistor was added to existing enhancement transistors. And I added a
transistor looks like an enhancement transistor. But if transistors are set to be always on state by the ion
implantations, it has a drastic effect"
I think you could detect dopant tampering (and these traps) with scanning capacitance microscopy, but I don't have any actual experience with that.
I remember seeing the original journal article a while ago on Slashdot (somehow it never made it to the front page on HN). It's really ingenious - even inspection under a microscope can't spot the difference between the tampered hardware RNG and a honest implementation, it passes all the tests, and yet it actually has so little entropy that essentially anyone can break otherwise-secure crypto that uses it.
Possibly, if you know what you're doing, but as someone in the comments at Bruce Schneier's blog points out the changes are small enough that it's feasible to only backdoor selected batches of chips (for example, just the ones shipped to countries of interest to the US or companies like Google).
In fact, it can also be designed as a marginal circuit so that a small fraction of the chips fail due to manufacturing variance. You can test for the weakness and ship the bad chips to people whose privacy you don't respect.
The circuit in question could also be enabled or disabled by using a high-energy laser pulse to blow out a tiny fuse on the ICs as they sit on the wafer, before sending the wafer out to be cut into individual ICs which are then subsequently packaged into the seemingly ordinary chips that we are all familiar with.
I don't understand how an RNG can be compromised to the point that it's got very little entropy, yet still be able to pass randomness tests. Can anyone explain?
Randomness tests mean extremely little for cryptographic PRNGs [1]. Passing a statistical test basically just means that your RNG isn't horribly, awfully broken. Such tests mean almost nothing in terms of cryptographic security.
A statistical test just determines if the output of a PRNG "looks random" from a very, very narrow point of view, typically not algorithm-specific and often predefined ahead of time. Cryptographic security, on the other hand, requires defending against an intelligent adversary who actively seeks to subjugate and compromise the unpredictability of the specific PRNG in question.
As an example, the Mersenne Twister passes many of the popular statistical tests with flying colors, but learning 624 consecutive values from it allows an attacker to reconstruct its internal state and predict all future values. (That is, it's totally worthless when it comes to cryptographic security.)
The output of every block cipher in the world would be expected to pass randomness tests. The output of a specific block cipher with a hard-coded publicly known key will obviously not provide any cryptographic security to uits users.
The RNG in question is deliberately designed to use AES as a way of stretching out a limited amount of hardware entropy into a much larger amount of output entropy. Because of the way AES works, unless you know the encryption key it's essentially impossible to distinguish the output from truely random data.
Can modern crypto systems conveniently support manual, verifiable entropy?
What I mean - even if I don't trust any of the computers RNG's, if I want, I can generate a 2048 bit random key manually with a piece of paper and a few somewhat fair dice. Sure, it'll take time, but it's feasible.
To generate a secure 2048 bit RSA key (or ElGamal or whatever) you do not need 2048 bit truly random data.
RSA keys are generated like this: 1) Choose 1024 random bits. 2) Set the first and last bit to "1". 3) Check if the generated number is prime (this is probabilistic and also needs random numbers!). 4) Repeat until you have two primes, generate public key by multiplying the two primes and generate private key using the factorization.
So if you really want to use true randomness for every random bit in the key generation then you need a lot more than 2048 random bits.
What you actually want to do is generate 256 bit of randomness and use that to seed a good cryptographically secure pseudo random number generator (AES Counter Mode, Salsa, Fortuna) to generate the necessary random bits. For 256 bit of randomness you need about a hundred D6 die rolls, probably a little bit more, as your dice are probably not perfect. The easiest way would be to feed the result string ("6216543155314"...) into a hash fuction like sha256 and use the output as a key for the ciphers mentioned above (Fortuna is not a cipher, I know).
But honestly, that is really a bit too paranoid (and impractical). It's much faster and probably equally secure to take 256 bit of randomness from /dev/random, concatenate that with the output of one minute of keyboard smashing and feed the result to sha256 to generate your PRNG seed. (I propose the use of both randomness sources because taking bits from /dev/random is so easy and it can only increase randomness)
Keyboard smashing is surprisingly predictable by the views of what I smash when a program ask for entropy. You have the center row over represented with a lot of asd clustered (old gamer hehe)
Keyboard smashing can be made quite unpredictable if implemented correctly. The randomness should come from time difference between keystrokes, not from the key values.
I have used the Unix signal(3), using SIGINFO, in conjunction with a tight CPU loop to generate random numbers for e.g. WiFi passwords. The technique is something like this:
Before running this program I use
stty -kerninfo
to avoid seeing CPU statistics.
Then every time I press ^T I display a new random number displayed based on the LSBs of the count. E.g. to simulate a die roll I print count%6.
This technique is good for not just a few bits of randomness per ^T, it is good for over 20 bits. That's because when I examine the timing of the inner loop generated I find it taking about 2 or 3 CPU cycles per increment (depending on compiler). So on a 2 GHz machine the counter is incremented at a 1 GHz rate. That's about 30 binary bits, the least significant of which are the most unpredictable. Assuming you press ^T at about a 3 Hz rate, you're probably getting over 20 bits (more or less) of randomness each time you do so.
The above only works if your system supports a decent SIGINFO setup (works fine on OpenBSD and OS X, I don't know about Linux). It probably has serious problems in a virtual machine, I use a real keyboard that has its own independently clocked CPU.
This is rearranging deck chairs on the titanic though. If you don't trust the physical hardware you're running on, it's already game over.
I mean why stop at the RNG? For the effort and expense of compromising the RNG, why not do other things as well? Why not rig the NIC chips to respond to a special packet and start leaking the RAM or just keypresses as bad parity in the packetstream?
But then, why bother with something no one ever updates once they have it, when you can just go after something people do - why not tamper with BIOS updates (the "evil maid" attack) or get involved patching the Linux drivers for really specific firmware (Stuxnet was a triumph).
That really is so. Anyways, what is the solution then?
Pen&paper encryption like the cold war spies?
Dedicated hardware (calculator form factor) that allows to write emails and encrypts them before they leave devices?
I've learned something new. So, dice is the plural of die exactly like mice is of... err... Anyway, I really didn't know about "die" and dice as singular and plural, thanks! I've had to check the Oxford's dictionary.
Yeah, or d20 400 times or a d100 300 times or some combinations. Anyway, takes some time but if you generate your key once, then it's doable; if you need a one-time pad, then not.
Any modern ASIC being built would be tested using Automatic Test Pattern Generation. This involves connecting all the registers in the chip into a chain and feeding patterns in and out of the chains and stimulating the logic between registers in a defined manner. These tests will at one level be looking for Stuck and 0 and Stuck at 1 faults and typically nobody would tape out a chip without >99% coverage. It would be very difficult to fiddle with individual gates as the author describes without this being detected with an ATPG test.
It would indeed have been bad if Linux (insanely) had converted to relying entirely on RDRAND as a replacement for the devrandom kernel CSPRNG. But no OS I know has done anything like that.
Even at 32 bits of entropy (which is an extremely unlikely conspiracy theory, as Schneier says), mixing the output of RDRAND into the rest of the entropy available to a kernel would still be a marginal improvement. For instance, it would mitigate some concerns about cold-start entropy for solid-state machines without real entropy sources.
The fact that OS CSPRNGs were unlikely ever to have trusted RDRAND directly (even if wasn't backdoored, what if someone screwed up? That too is somewhat unlikely, given that Paul Kocher's Cryptography Research reviewed the Intel HWRNG. But still...), and the fact that it's such a high-profile place to put a hardware backdoor, leads me to conclude that this is an unlikely vector for hardware backdoors.