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.'"
The problem with backdoors, is that noone can guarantee who uses them. While it allows for (possibly) justified surveillance by our government, it also allows for it by others.
The United States, or the NSA, doesn't have all the world's best cryptographers. Russia, China, etc, other nations have excellent skill in these endeavors. Ironically, by trying to protect the nation, the NSA runs the risk of opening us up to foreign espionage.
Isn't this exactly what the terrorists want? Our own government to become to oppressive that our country changes into the government of 1984?
http://it.slashdot.org/article.pl?sid=07/11/15/184204
So, if a security bug is present an exploit could happen...?
TFA is just a summary of an article yesterday in the NYT: http://www.nytimes.com/2007/11/17/technology/17code.html?ref=technology
Hey! What if terrorists were to discover TIME TRAVEL and went back to prevent us from getting our independence from England! I think I'll hold off on worrying about math-genius terrorists figuring out bugs in encryption hardware until there's some actual evidence of it, thank you.
It seems to me that the most likely source of a math error is in the floating point unit, since floating point math is far more complex than integer math. I've always understood that most crypto is based on integer math, both because it's based on number theory and because floating point math isn't exact. Doesn't that make this sort of exploit extremely unlikely?
Wouldn't pulling off something like this require a level of knowledge and togetherness more in line with a government agency, rather than a "terrorist" group? The results would also be more in line with what a government agency would want ("we have your secrets, ha!"), rather than what a terrorist would want ("Maybe I can't blow up a bridge / poison your water supply / whatever. But then maybe I can. So while you're deciding whether to go do things or hide under your bed all day, I have a question for you: do you feel lucky?").
Why does everything have to come back to terrorists? They kill a small number of people and people go nuts about them. Hunger, disease, motor cars, lightning, ... All these things have killed far more people than terrorists and they don't get brought up at every *FUCKING* opportunity. Yeah. I'm pissed off. If the terrorism obsessed turned on their brains for a picosecond they might realise that they have caused far more damage than any terrorist has.
The math errors tend to be in obscure and complex operations - store long double, divide double, etc.
Important cryptographic stuff tends to use extremely primitive operations, often just shifts, adds, xors, and indirection.
I'm not sure how Mr. Shamir envisions a simple "math error" causing a problem. A buffer overflow exploit, perhaps, but not a math error... A user on a flawed but protected computer receives a "poisoned" encrypted message, opens it... And what happens? The math error, say, elicits some aspects of the user's private key in the decoded message; but how does the attacker then obtain that information without already having access to the machine? Further outgoing messages wouldn't have any usable information, no modern cryptosystem allows a received message from affecting any such message; a code exploit might affect the system's PRNG, but a math error shouldn't feed back to the PRNG unless it was horribly implemented. Without something affecting the user's machine's code execution, I can't see any way for an attacker to utilize a math error in a decryption function.
Is this chip / software used in any slot / video poker games?
how to cause the blue screen of death to happen simultaneously across all computers...
Terrorists want us to stop screwing around in the Middle East and Central Asia -- specifically they want us to stop supporting Israel and to stop propping up various dictatorships in countries where there'd be a good chance of overthrowing the government and creating a theocracy.
They don't give a flying f--- about "our freedoms" except where they think that shows we are "morally corrupt." Islamic militants are under no illusions that they're going to change our culture any time soon, though. They've got bigger fish to fry back home trying to establish a power block.
How we govern ourselves beyond our foreign policy is utterly unimportant to their larger goals.
If it's for-profit but free, you're not the customer -- you're the product (e.g., the Slashdot Beta's "audience").
I had a computer arch prof who used to refer to self-tests in digital logic as the ability for circuits and chips to test for their own sanity. As the implementaiton gets smaller, the ability to test for sanity could get more difficult. For example, some of the experimenetal nano-media are prone to faults and its only in the massive redundncy, that they are usefull. I wonder about the ability of an attacker in the future to manipulate the fault level of digitial logic/memory, or the self-tests of digital logic. Could the attacker able to introduce this fault manipulate a higher order operation like a math op and therefore gain access to some variation of Shamir's attack.
Sorry, I was looking at this the wrong way. The "math error" Mr. Shamir must be talking about, with regard to "chips", must be an error in the logic system in an arithmetic logic unit. An error that might, for instance, cause one or more bits in a register to stick in one state or another, would indeed affect future messages, disrupting PRNG (both encryption algorithms and one-way) and public-key computations. I doubt a system so badly affected could continue to operate for very long, but an attacker who monitors outgoing messages after sending that "poisoned" message to trigger such an error would learn valuable clues to the machine's cryptosystem and keys, perhaps enough to trivialize breaking its keys.
Depending on what sort of application the user's machine performs, I can think of a few ways, offhand, to help guard against this sort of attack. A simple self-test prior to encrypting each message might work but might be onerous with a heavily-utilized system. Reducing the number of registers used for encryption might help, surprisingly, because any error would tend to cascade more quickly, reducing the output to a complete mess rather than something analyzable. Also, where practical, decrypting part of the message after encryption would work as a fast check for this sort of corruption.
*scottish accent* NO! I warned em about tha' Pinnacle Chip! I told them it had a' flaw where if you logged onto the internet then entered in *@[=g3,8d]\&fbb=-q]/hk%fg it would suck you into the internets and make you some sort of a' freakazoid!
Where has the time gone? Anyway as I recall that error only really affected the low megahertz pentiums and were fixed extremely early. I think that is probably because with millions of chips sooner or later someone is going to notice their code not executing correctly on brand X chip while working just fine on brand Y.
Let's say that this error does get out somehow though. Lets assume that the error only creeps in when a freakishly rare set of instructions is executed. It seems the companies upgrade their designs every couple of years. So I doubt that the problem would affect all intel super duo core whatever processors. Likely it would be all chips made between this date and that date and of this specific model.
So hackers would likely not know ahead of time which servers are affected so they would likely have to try to send the signal to as many servers as possible hoping that some would be affected.
Are you going to tell me that no one is going to notice that hackers are trying a specific exploit on so many machines?
And if there did exist such a problem in hardware how would it be that much worse or different than finding a big bug in software. In the end people would be forced to replace their chips or get a software patch. The company would get a big black eye and life would move on.
Yes there could be such exploits out there right now that we don't know about. But there are also many many more software exploits out there that we don't know about. How is the hardware problem worse or even much different?
Just wondering?
In my experience, the slightest error will render the whole cypher text unreadable, so it won't take long for people to complain that all HTTPS shopping sites don't work with a specific computer system and then that system will end up in land fills really quickly.
Excuse me, but please get off my Pennisetum Clandestinum, eh!
Want the citizens to give up some freedom/pay some new tax/whatever? Easy! Play the terrorism trump card.
Without some Evil Empire force (that the US plays so well), it is very hard for terrorists to get the emotions going either. Terrorists & empire building governments need each other.
Engineering is the art of compromise.
--- We are not in the 8th dimension. We are over New Jersey.
The flaw seems too obvious to really have been something illicit. If it was an attempt at a backdoor, it was pretty stupid. And it was a weird/improbable way to create a backdoor -- it was PRNG, not really a cryptographic function per se, and while knowing its output could help you break a system, it wouldn't guarantee it. The people at the NSA had to know it would be combed over.
But the fact that it seems to be incompetence rather than malice doesn't make me feel a whole lot better. There are still a bunch of secret-algorithm ciphers around and in use (and which the government, in its infinite wisdom, treats as more secure than the openly-reviewed ones), that the NSA is basically the only organization that has any access to. If they could miss such a trivial flaw in a PRNG that they knew was going to go out for public scrutiny, what could they have let slip by in a cryptographic function that was supposed to be a state secret?
"Ladies and gentlemen, my killbot features Lotus Notes and a machine gun. It is the finest available."
ao0o0o0f0d sgjfd ahgfd-00--000-0 gsdfa ghif hgfui9u808-00-0- gf0g fo tsrhksngfaj hgajkhH LH JKLhger hnm,mhm/t./m.tmm up90u9mp()U)U()MUhfd, shaskfsdtGFTFT eweqewf d hnjhHJHJHiuo 903u3u u90u3p1q u4r91p-4u932pu j;kds;aj;j;;j;j;je89i yi obvious obvious obvious
Yeah know, I've noticed this problem on a series of processors at my college. I had to write a basic key based cryptography program in C#. Well I created the system with no problem. But if you ran the program in a certain lab where all the computer are identical (hardware and software) I could generate the same 4 key sets each time. My solution was just to use and external DLL with my own generator from another language.
My point for this example is that I don't believe its the processors fault. If the software engineer can't write a decent algorithm to generate random numbers then it the engineer at blame, not the processor. I wrote great random number generator back on the Apple IIe years ago. Why can't people do the same now?
You say things that offend me and I can deal with it. Can you?
I'd think it more likely that a bug in a popular encryption related software package/library would lead to more exploits than a hardware bug. My guess is this would be true for both open and closed source projects. While open source projects can have 'many eyes' looking for bugs, my guess is that more bugs are found when trying to port to multiple architectures than by people casually glancing at the core (the OpenBSD developers maintain ports to multiple architectures for precisely that reason).
I misuse like misuse cheese misuse,,,, mñññññññññññññ!
Trust em with our secrets, the lottery, property, health care, transportation, science, entertainment, trust em to tell us when its safe to go outside, who can have a radio station, a tv station, a gun, a drink, a smoke, trust them to watch us in traffic, out of traffic, on the internet, trust them to read our email, trust them to take our money, trust them and don't ask for proof, evidence, accountability, or transparency! That's something they can't trust us with!
So you have a myriad of operating systems, daemons, arrays "security software." And every single combination can be disabled by a single magic spell that lets someone take over the computer directly through a flaw the chip. Right.
So, because they don't like US foreign policy, they think it's alright to kill, and it's the fault of the US?
What the flying fuck planet of twisted "logic" are you living on? You're blaming the victims of murder for the acts of the murderers.
If someone doesn't like people who paint their houses pink and purple and then goes and kills anyone living in such houses, the people who painted their houses in garish colors are not the ones at fault.
And it's not "US foreign policy" that's fueling terrorist rage.
It's Islam. Plain and simple.
Specifically, the concepts of dar al-Harb and dar al-Islam. In the case of Israel, the utter insult it is to Islam to have that part of dar al-Islam revert back to dar al-Harb.
The mere existence of Israel is an affront to fundamentalist Islam.
And if the jihadis manage to "wipe Israel off the map" (gee, they wouldn't ever slip up and actually say that, now would they?), then those other areas of the world that were once part of dar al-Islam but reverted to dar al-Harb will be returned to the ummah. Say, like the Balkans, or Spain, er, I mean ar-Andalus.
And if any kaffirs get in the way, too bad. They're subhumans, anyway.
Maybe you'll get your head out of your ass before the jihadis lop it off - as their holy book directs...
I bet you are not counting the many acts of terrorism in Iraq and (depending on your political stance) Ceylon and Israel during the last few years.
Baring the use of a nuclear weapon, a well placed chemical weapon, or a good biological weapon with a poor response, I think it will be a long time before September 11th is topped.
Consider low-level handshake protocols. There is, for example, an attack on SSL that allows recovering private RSA key by measuring response delays of a victim. These responses are mandated by a protocol, so they are (in a way) solicited.
3.243F6A8885A308D313
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).
There are lives at stake here!
What sort of cowardly and spineless politician will say that terrorism is not a top 100 killer of Americans. To say otherwise is to say that the deaths of the people in New York on that September day are insignificant.
No electable politician would say such a thinghttp://www.911familiesforamerica.org/?cat=42
You're attacking a straw man. I never once said that in my post that the terrorists were justified by these beliefs and goals. I merely stated that "destroying our freedoms" is not anything close to what they actually care about. Big logical leap there.
If it's for-profit but free, you're not the customer -- you're the product (e.g., the Slashdot Beta's "audience").
I've read the summary twice and it's like the plot of a Bruce Willis movie.
Will this affect me in any way besides exposing my PizzaHut.com orders, and the fact I bid on any auction that includes ceramic cats?
There, see? The truth will set you free.
Comment removed based on user account deletion
So the "expert" is making a fuss over an issue which is possible in ALL existing processors, and making a hype over a theory?
It's like saying: "If a terrorist organization was able to construct portals, they'd be able to attack and vanish!"
Mod points are a dangerous tool. Abuse them wisely.
Heh heh... backdoors, shmackdoors. Private/public key pairs are used only on the faith that it is mathematically impossible to figure out one given the other. Supposedly, if some wise mathematician someday figures out a theorem that allows you to do that, all the public/private key pair encryption systems in use today become WORTHLESS. Luckily that hasn't happened yet. Or has it? Well I happen to know just that... a secret math theorem that makes it possible to generate a private key given a public one. It goes like this: Let A equal Alice's private key, and let B equal Bob's public key. Divide A by B and let Q equal the quotient and let R equal the remainder. My top secret theorem, which is known to NOBODY except ME, is that all I have to do to obtain Alice's private key is multiply B by Q and add R. Heh heh heh... It never fails. We are 1337z h4x0rz d00dz, bwaaaaahaaahaaahaahaahaahaahahahahahahahahahaha!!!
Step 1: The attacker an SSL session with a web server
...
Step 2: Generate the "poisoned" SSL session shared key K1, and encrypt it with the server's public RSA key
Step 3: The server decrypts the poisoned SSL session shared key K1 with its private key and obtains a value K2, which is
different than the original poisoned shared key K1. If the shared key K1 was not poisoned, K2 would be equal to K1,
but the attacker is exploiting an error in the CPU implementation that causes K2 != K1.
Step 4: All the AES-encrypted messages from the server will now be transformed with the poisoned K2, which the attacker does not know yet.
Step 6: Carefully select the messages that you send to the server, so that when you get the AES-encrypted with K2 replies to these messages, you
can use them to infer K2.
Step 7: Use K2 to infer the server's private RSA key
And that's the way you do it
This is a chosen ciphertext attack, which does not exploits weaknesses of the RSA scheme, but instead exploits the faulty
hardware.
That basically means sending the target the secret message: "Would you kindly....?"
All I see is whitespace.
... but for a second I could swear that I saw "Math Coprocessor Error: N$A"
Do it yourself, because no one else will do it yourself. [beta blockade 10-17 Feb]
..but who will we direct our hatred towards? Heretic doesn't work anymore, nor does witch, n$gga, joo or anarchist or communist. Nazi doesn't work either, to be perfectly honest. It's all just worn out sticking tape. And it's boring to hate politicians. Terrorists are the new black!
I mean, you can't expect people just to go around not hating anyone!
The first thing that went through my head as I read the story was:
"Mr. Potatohead! Mr. Potatohead! Backdoors are not secrets!
Ronald said nothing. He flung himself from the room, flung himself upon his horse, and rode madly off in all directions.
People generally evaluate risk on largely emotional terms. For this reason, we frequently make gross errors in risk assessment.
1) When we think there's somebody out to get us, we evaluate that risk very highly, even when there are more immediate but "random" risks clearly at hand. For example, a "terrorist" is a bogey-man, it's somebody out to get you. But hunger has no bad guy, and neither do disease, auto accidents, and lightning.
2) We evaluate as "risky" situations where we are not in immediate control, even if they are carefully situated to protect us. For example, riding a horse is far more risky than flying, even in the most dangerous category of flying, single-engine piston planes. Yet people routinely are more concerned about the "motor stalling" in a carefully watched and maintained airplane than they are about their kids riding around without protection on a champion racing horse.
3) Because of our intense pattern-matching, our ability to relate to other people, and our social nature, we routinely underrate risks that are impersonal - the flip-side of #1 above. For example, auto accidents are seen as a "way of life" and "can't be changed" by most, but freak out when the local high-school is held up for a few hours when some teenie gets involved in a love triangle and holds a SINGLE person "hostage" with a pocket knife. Look at the dichotomy - people who don't attend school drive right by a smashed up car on the way to work, tisking as they go, but sit glued to the telly when something happens at the High School.
It's reality. Get used to it. And no, it doesn't make sense.
I have no problem with your religion until you decide it's reason to deprive others of the truth.
So one of the great granddaddy's of practical encryption is saying that "if a machine has faults, then bad stuff can happen" ? I've always wondered why Adi was considered such a heavyweight when, aside from the fact that he's a math guru, he's such a dumbfuck. That's the differnce between him and Bruce, Bruce isn't a hysterical idiot constantly trying to associate himself with as much controversy as possible.
Most chips have flaws of one kind or another. Most of these are trivial and can be worked around in microcode. The article mentions the Pentium floating point bug. This caused the original Pentium to return the wrong result for some calculations. In theory, it would be possible to produce a cyphertext that would generate this error if the key contained one of the two values that you needed to generate the error. This then lets you dramatically reduce the key search space.
Other CPU flaws are more serious. There are a few in the Core 2 which allow a process to violate the page protection mechanism, for example. If an attacker found one that caused the program counter to be modified as a side effect of an arithmetic operation then they could create a cyphertext which contained a program at the end and some data at the beginning that caused execution to jump into the exploit code. This is much easier for cypertexts than arbitrary data because the attacker has can make some good guesses about how a cyphertext will be processed.
It seems like this is a very theoretical category of vulnerability to use for anything more than a DoS. On the other hand, as Theo de Raadt says, the only difference between a bug and a vulnerability is the intelligence of your attacker.
I am TheRaven on Soylent News
Just use a lava lamp or a camera with the lens cap on.
Pavlov wouldn't be so famous if he'd used a can opener instead of a bell.
In that case, the benefit of open review (that, just possibly, someone in the small pool of non-spook cryptographers who know what they're doing might find a flaw) is far less than the downside (that your opponents get to see what a modern code system looks like). The lowdown on a modern close-world cipher system would reveal attacks they are defending against, give a good impression of their real capabilities and so on. Yes, in a real shooting war, the spooks have to allow for their crypto systems falling into the wrong hands. But in the current climate, the tactical stuff will be exposed, but the strategic stuff can be closed algorithms and closed keys: what's not to like?
This reminds us all of the S Box hoo-hah, where elaborate theories were put forward by open community `experts' about the `flaws' in the S Boxes in DES. It turned out, of course, that they were optimal against an attack that wasn't even public, and close to optimal against other attacks that (allegedly) weren't known to anyone. I'd take a cipher system that the NSA or GCHQ approves for government use over anything advocated outside the wire., simply because the chances of an intentional weakness in the former are far smaller than the chances of an accidental weakness in the latter.
We went through all this is the discussion about the S Boxes
If a guy like Shamir says this, I'd say it's full-red-alert for all those manufacturing this sort of chip. We are just doing asymetric crypto in Math 1 (Bachelor CompSci) and my brain goes into overload-error every 5 minutes or so as soon as the professor starts talking about it. Someone like Shamir (the "S" in "RSA" btw.) who can come up with this sort of thing should be considered 'God' in the field of cryptography and his call upon action should be noted duely.
We suffer more in our imagination than in reality. - Seneca
The "math attack" presupposes that an attacker knows of a flaw
in the integer multiply unit that no one else knows about.
Perhaps it was engineered to have such a flaw; it would be
almost impossible to find. This flaw can be exploited by
sending cleverly constructed ciphertext to the decryption
unit.
However, many implementations of RSA already have protection
against this attack: they either "blind" the computation
(by multiplying by a random quantity before encryption, and
dividing by its decryption afterwards), or by verifying that
the encryption of the alleged decryption result is correct.
In any case, it is easy to protect against this attack (once
you know it exists).
I'm sure Intel test their chips very carefully now, to avoid further embarrassment, but even for the average user it wouldn't be hard to do. A program that tests all mathematical functions of a CPU over the entire range of 8, 16, 32 and 64 bit numbers (both float and integer) for errors would be fairly easy to craft. Might take a while but would only need to be done once per revision of CPU.
const int one = 65536; (Silvermoon, Texture.cs)
SJW, n: "Someone I don't like, and by the way I'm a fuckwit" - AC
I would make it so when people eventually found it, which they would, the code could be spun as an accident. This way you can always deny it was planned. If the backdoor is too complex it will appear obvious someone planned it.
Chances are it was an accident or just some small group of executive idiots.
Because, rarely is breaking encryption as worthy a goal as simply spying on the person. Want their password or secret documents ? Just spy on them, it's much faster and more accurate to catch them in the act. Plus since their are many choices in encrupted, what is the chance they will have this one.
So, it makes more sense that this is an accident OR it's a targeted hack toward a certain group they knew would be using this encrupted, such as a government agency or corporation. Otherwise, it makes little sense. You know their is a high chance of the flaw being found AND you know criminals can use a host of other 'unbreakable' encryptions.
AS this guy suggests, make the backdoor in the CPU or else you can ONLY look into one encryption of hundreds and for the NSA that's mostly useless. What's the chance the one file they need is acutally encrypted in their breakable encryption ?
Certainly it would be a grave mistake to make a backdoor so easy to find. Either they didn't plan it, or they planned it to happen to specific groups. Letting a flaw like this potentially encrypted important data could be economic disaster. I don't think the NSA would have done that as a goup, though individuals can be convinved to do almost anything. The NSA still has a lot of respect, they did turn in the wiretapping program to the public. I think we have some good guys left there, but yea bad ones too.
I have thought about this a lot. Perhaps mathematicians should be locked up as terrorists. They would not be able to get out unless the can factor rsa120 in their head. Clearly math is a subversive activity. It leads to all sorts of hack attacks on computers and computer communications. It leads to dangerous things like atomic bombs and bridges that collapse under heavy winds. It leads to wet naked men running down the street yelling Eureka. (A small city in California - how did he know about Eureka? Was he a mole planted by the Romans?)
and also if you look at the number of blades in a shaving razor, it has been increasing geometrically over the last couple of years. It is equally clear that all those HUGE number of future deaths will be caused by terrorists weilding razors with HUGE number of blades.
Most politicians worth a damn have enough skill with rhetoric to be able to make a decent speech with the general meaning of "the best way to honour your deceased loved ones is to not give the scum who killed them the pleasure of living the rest of your life in fear and anger". And I bet a good enough politician would make a damned good speech out of it. Nobody wants to take that chance though.
Protocols like SSL (TLS Handshake) can make others send you feedback according to your input.
So...there could be a hardware hole on top of numerous software holes that would let an attacking stream of bits take control of a target machine?
Golly!
(-1: Post disagrees with my already-settled worldview) is not a valid mod option.
Some older CPUs and apparently, Via's C7 and some AMD chips, had True Random Number Generators built into the chip.
Why were the circuits dropped? It's not as if there was no demand for the feature. If nothing else, Internet shopping relies on solid crypto which as the article illustrates, crypto relies on good random number sources.
I hate to sound paranoid but (sounding paranoid) I'm wondering if the NSA got the chip companies to remove the functionality.
If you could break the PKI(Public key infrastructure) would you ..
(a) publish a paper on it .. get famous .. and close down the RSA?
or
(b) quietely snoop over the world's conversations .. and possibly break banks' security systems to make billions?
If (a) is not the chosen option .. why would anyone publish such a result, even if they found one?
Maybe, but in the minds of govt. agencies, and/or paranoid terrorist-threat-obsessed nutjobs, the safest thing to do seems to be assuming that every enemy was personally instructed by Einstein himself...
Go figure.
Wouldn't any error even in a complete instruction set architecture lead to portability problems? For instance, even if the entire Intel/AMD instruction set had some math flaw, I would expect problems. In particular, if someone ran the app on PowerPC, PA-RISC, SPARC or (perhaps more likely, given wide use in cell phones, PDAs, etc) on ARM or MIPS, that they would either find messages unintelligible, or send out messages (properly encrypted) that would be unintelligible on the desktop.
Perhaps these guys thing a flaw would be found that would cause weakness with a few *particular* keys..