Slashdot Mirror
Cryptography Expert Sounds Alarm At Possible Math Hack
netbuzz writes "First we learn from Bruce Schneier that the NSA may have left itself a secret back door in an officially sanctioned cryptographic random-number generator. Now Adi Shamir is warning that a math error unknown to a chip makers but discovered by a tech-savvy terrorist could lead to serious consequences, too. Remember the Intel blunder of 1996? 'Mr. Shamir wrote that if an intelligence organization discovered a math error in a widely used chip, then security software on a PC with that chip could be "trivially broken with a single chosen message." Executing the attack would require only knowledge of the math flaw and the ability to send a "poisoned" encrypted message to a protected computer, he wrote. It would then be possible to compute the value of the secret key used by the targeted system.'"
TFA is just a summary of an article yesterday in the NYT: http://www.nytimes.com/2007/11/17/technology/17code.html?ref=technology
In the past there have existed implementations of integer math that used the floating point unit. The only one I know of off hand is the Prime95 Mersenne prime search program. I imagine there are others, though. The reason for this is simply that the floating point units were faster -- more bits per operation. The x87 FPU instructions operate on 80 bit floating point numbers, compared to 32 bit integers (the floating point numbers can't use the exponent bits, but it's still more than 32 by a lot). If your code is sufficiently parallel, and you put forth the effort, there was a performance gain to be had. I don't know if this is still the case in modern CPUs (especially 64 bit ones), but it's entirely possible to do high-performance integer math on the floating point unit.
You are aware that computers can only generate pseudo-random numbers, right? The random number generator in C# actually doesn't generate random numbers but numbers that look random. These numbers are generated by a 'seed'. If you give the same seed to the computer, it will generate the same set of numbers. The C# implementation (if you don't supply a seed yourself) uses the system clock as seed, hence if you start your random-number-generation session in the same millisecond on same computers, they will generate the same numbers! The rest of the hardware & software is irrelevant here. If you need a REAL random number generator, you should connect your computer to something naturally random, e.g. a Geiger device, because your external DLL from an other language just uses a different model to generate the default seed but it is still predetermined.
1) is a serious problem though. We can never PROVE it is backdoored unless someone steps forward with those numbers. We can NEVER prove it is NOT backdoored, as we cannot PROVE that no-one has the numbers, so are compelled to treat it as backdoored.
2) is about specific cases where particular categories of mathematical failures actually lead to the compromising of the private key, which is significantly more dangerous. It is not about utilitising typical exploits like buffer overflows to take over and kind of security software. For example, once they private key is known, it may allow the third party to fake messages appearing to originate from the target of the attack.
3) indeed, the problem here is typically relating to very specific edge conditions, eg overflows, underflows, carries which are handled incorrectly, and have been known to go undetected for years. If you do not believe there are issues in the microcode, take a quick look at the current errata list for the Core2Duo, showing many unfixed bugs (and many of them unimportant due to the impossibility of them occurring in modern operating systems).
As for "installing bad microcode", the microcode is something done purely from the software each time the OS boots into volatile memory on the cpu, and so is reset back to the original shipping microcode each time the machine is power-cycled.
If an adversary has access to the booting OS to update the microcode, the adversary already has access to superuser priveleges on your system anyway, so I feel it is irrelevant.