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.'"

Original article

[sk19842]

TFA is just a summary of an article yesterday in the NYT: http://www.nytimes.com/2007/11/17/technology/17code.html?ref=technology [nytimes.com]

Re:how many encryption schemes us floating point?

[EvanED]

What?

The point the OP was trying to say was that if the error is in the FPU, that isn't used for integer calculations at all, and so wouldn't be exercised by security code. I don't know if this is true, but for instance RSA in theory is all integers.

Re:Original article

[RuBLed]

Yup and TFA really had nothing much to do or even related with NSA's officially sanction random number generator. Mr. Shamir is talking about math error in our processor's ever increasing complexities, much like what happened in Intel back then.

There are no terrorist mentioned!! Sensationalist networkworld...

Pentium FDIV Bug

[rubicon7]

Remember the Intel blunder of 1996?

Don't you mean 1994 [wikipedia.org]?

Re:how many encryption schemes us floating point?

[Kuciwalker]

Compared to cryptographic algorithms, floating point math isn't that much more complex then integer math.

Yet the claim is that an actual error in the implementation of elementary amthematical operations on the processor could weaken a cryptographic algorithm run on that processor, even if the algorithm itself is implemented flawlessly in source. Therefore the relevant question remains "where are processor bugs most likely to occur?"

Also, floating point math is exact since floating points representations (like IEEE 754) are eventually all calculations and representations in bits which are always exactly reproducible. Also irrelevant - most applications of floating point rely on the fact that floating point numbers are sufficiently precise approximations of the reals, therefore they base their algorithms on real-number math (with hedges built in to protect against numerical instability) and are satisfied with inexact answers. Encryption algorithms depend the exact answers produced, and would therefore have to be based on the specific IEEE-specified behavior of a specific precision of floating point number. While such an encryption scheme is possible, it strikes me as unlikely and unnecessarily complex.

Re:how many encryption schemes us floating point?

[evanbd]

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.

Re:Random Numbers in .NET and in General

[DrJokepu]

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.

Comment removed

[account_deleted]

Comment removed based on user account deletion

Re:first post. TFA = WTF?

[NoTheory]

What are you talking about? How is this hard to understand? This is one of the grand daddies of practical encryption stating that a huge freaking security hole could be opened if encryption is performed on faulty hardware. If a piece of hardware with such a fault was in wide spread use, then a large number of people would be susceptible to exploits which would be able to defeat public key encryption (e.g. HTTPS, ssh, etc).

Re:Random Numbers in .NET and in General

[evanbd]

It doesn't have to be a geiger counter. There is plenty of randomness to be had in the exact timing of key presses, exact behavior of rotating media, incoming network information, etc etc. It can be harder to make use of (poor or unknown distribution, patterns that you might not know about), and it might be insecure (especially if it came from the network card), but there are plenty of physically derived things a modern computer can measure and generate randomness from with enough processing of the raw data.

Re:NSA "Suite A" is the real problem.

[0xygen]

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 [intel.com], 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.