Some security experts are counseling a bit of caution about the recent reports of a potential math error in a commercial microprocessor that could lead to mass compromises. The possible computational error–which is only a theoretical problem at this point–was raised by noted cryptographer Adi Shamir in a note circulated recently in the cryptography community. In short, Shamir, one of the co-authors of the RSA algorithm, posits that there could be an undiscovered mathematical mistake in any one of the microprocessors on the market which could enable skilled attackers to compromise any crypto key on a machine running the flawed processor.
“In this note we show that if some intelligence organization discovers (or secretly plants) even one pair of integers a and b whose product is computed incorrectly (even in a single low order bit) by a popular microprocessor, then ANY key in ANY RSA-based security program running on ANY one of the millions of PC’s that contain this microprocessor can be trivially broken with a single chosen message,” Shamir wrote in his note.
However, as it turns out, many, if not most, of the popular cryptographic libraries in use today already protect against this kind of attack.
“This is a neat extension to an existing attack and a good reason not to implement your own public key crypto, but if you use a mainstream library, you’re already protected,” said Nate Lawson of Root Labs. “It depends on there being a bug in the multiplier section of the CPU and using a poorly implemented crypto library. Luckily all crypto libraries I know of (OpenSSL, crypto++, etc.) guard against this kind of error by checking the signature before outputting it. Also, hardware multipliers are less likely to have bugs than dividers due to the increase in logic complexity for the latter, although I certainly wouldn’t claim they would be bug-free.”
This by no means discounts the seriousness of what Shamir proposed. The fact is, chip designers, like everyone else, make mistakes and those mistakes can lead to major problems. But thankfully, someone else has anticipated those mistakes and taken precautions against them. Shamir makes another point in his note that’s worth mentioning as well. He talks about the increased complexity of the multiplication units in CPUs being the root of these possible attacks. It’s often said that complexity is the enemy of security, and this is yet another example of this maxim.