Surreptitiously Tampering with Computer Chips
schneier.com
schneier.com
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.
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.
See the very interesting interview about the Z-80 (page 13): http://archive.computerhistory.org/resources/text/Oral_Histo...
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.
Isn't this a testable thing?
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.
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.
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 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:
volatile int signal_info = 0;
void sighdlr(int sig)
{ signal_info = 1; }
int main(...) {...
unsigned count = 0;
signal(SIGINFO, sighdlr);
...
for(;;) {
count++;
if (signal_info) {
signal_info = 0;
...
}
}
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.
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).