Slashdot Mirror
A New Vulnerability In RSA Cryptography
romiz writes, "Branch Prediction Analysis is a recent attack vector against RSA public-key cryptography on personal computers that relies on timing measurements to get information on the bits in the private key. However, the method is not very practical because it requires many attempts to obtain meaningful information, and the current OpenSSL implementation now includes protections against those attacks. However, German cryptographer Jean-Pierre Seifert has announced a new method called Simple Branch Prediction Analysis that is at the same time much more efficient that the previous ones, only needs a single attempt, successfully bypasses the OpenSSL protections, and should prove harder to avoid without a very large execution penalty." From the article: "The successful extraction of almost all secret key bits by our SBPA attack against an openSSL RSA implementation proves that the often recommended blinding or so called randomization techniques to protect RSA against side-channel attacks are, in the context of SBPA attacks, totally useless." Le Monde interviewed Seifert (in French, but Babelfish works well) and claims that the details of the SBPA attack are being withheld; however, a PDF of the paper is linked from the ePrint abstract.
Just in case it gets Slashdotted.
PDF file
Knowledge is how to play a game, intelligence is how to win, wisdom is knowing what game to play.
This is not a vulnerability in RSA per se, but rather in the implementation of RSA on modern CPUs. It is possible to run a "spy" process along side cryptographic application, which would "sniff" out private keys. It can do this by making note of how its own instructions are executed and thus predicting what instructions are executed for other processes. I think the important thing is that this type of attack requires local execution of code for this to work.
I would think this can be circumvented by alternative implementation of the RSA encoding algorithm. Maybe by inserting "noise" instructions into the execution flow.
You just keep on using RSA of course. As the article says: it is possible for a spy application running on your machine to get vital information about an RSA enryption process with OpenSSL. So, as long as you make sure your machine is secure there is nothing to worry about.
Most of the time when you hear an encryption scheme is cracked or successfully attacked they mean that it has gotten easier to crack, not that the encryption is totally worthless. Which of course doesn't mean that countermeasures should not be taken, but it also doesn't mean that you have to throw out RSA.
Reminds me a lecture I attended last year where Adi Shamir talked about one of his latest AES attacks.
Basically it uses information about the state of the CPU's memory cache and thus attacks processes on the same computer too.
Here's the paper.
On a multi-user system, someone may well have the right to run arbitrary code on the same processor, but not to access your data.
The Tao of math: The numbers you can count are not the real numbers.
that's what they refer to with "blinding techniques". and as they said, it doesn't protect against this attack
``If you have a Trojan on your computer you are going to lose your secrets anyway,''
Whose secrets? Multiple people use my computers. If there's a trojan on the system, it can't necessarily access all these people's data.
``your private key is probably stored on the disk drive,''
Password-protected, thank you very much.
``and you use the keyboard to type passwords''
I don't use a keyboard with most computers I use; I communicate with them over SSH. Of course, I use a keyboard on _some_ machine, so if that machine has a keylogger running on my account (or root's), that would be a problem.
``Could someone explain how a local attack can be big news ?''
I haven't RTFA yet, but local attacks are often problematic for systems used by multiple people, especially if not all people know good security practices (or are even completely clueless - you get many of such people when you operate shared web hosts).
Please correct me if I got my facts wrong.
For unmasking the sensationalist headline. This attack only works if you are already logged in to the box and able to run processes on it. Yet from reading the article summary, it looked like I would have to fear for my online banking SSL connections and SSH sessions.
RSA isn't the problem. The implementation of RSA on a modern processor is the problem. Moving to another algorithm wouldn't guarantee a lack of side channels. One way around this would be to specialise the algorithm with your own private key. This would unroll all of the loops, and decide the branches statically. If you assume that the machine is not compromised, then this executable could be stored as read-only for your account. If the machine is compromised enough for a non-priviledged process to read your private data then you don't need SBPA - you're toast.
Slashdot: where don knuth is an idiot because he cant grasp the awesome power of php
Aciicmez et al are extending an attack they published a few months ago. It's real, but:
It targets RSA implementations, not the algorithm, which is fine
Attackers need to be on the same host as the victim
This specific attack is tuned to the Pentium 4 architecture
This paper doesn't break SSL.
We wrote about the attack two months ago. A quick, dumbed-down recap:
The CPU aggressively caches aspects of what programs do. It doesn't make an exception for RSA. You obviously can't just read key bits out of the cache.
But caches are finite, and way, way too small to accomodate everything every program does. So operations from one program are constantly evicting cached values from other programs. This makes the other program imperceptably but measurably slower. By writing a program that constantly and carefully measures those time differences, you can watch an RSA operation from another program leave footprints through the cache.
There are years-old attacks like this against the L1 and L2 caches, and extensions that use hyperthreading to improve the resolution. Some variants, which measure timing differences but don't track cache footprints, are remote attacks. These aren't. You run a "spy" process on the machine; it repeatedly executes a series of operations and measures timing differences. Aciicmez found an overlooked cache which makes Pentium branch prediction work (the BTB). They published back in August.
From what I can tell, this paper extends the attack; they figured out that the Pentium 4 architecture has two BTB caches, and their original attack wasn't hitting both of them. Their new attack does, and that creates much bigger timing differences, making RSA's footprints much easier to see.
This is really cool stuff, but from where I stand, they hit game-over back in August with the original BTB attack. This paper reads like a refined exploit for the same vulnerability.
Since this is localhost-only, and (unlike Bernstein's and Boneh's attacks) can't be extended remote, it's not going to impact SSL or (single-user) SSH. The classic victim of timing attacks is smart cards. For these attacks, another interesting possibility is DRM; these attacks say you can't trust crypto running on the same Pentium 4+ as an attacker.
Run all of your RSA operations in secure, dedicated HW devices (crypto co-processors such as smart-cards, IBM 4758s, nCipher, etc).
Better than BabelFish I hope.. human made, so prone to errors ;)
====
The confidence users have in Internet and in the capacity of the system to secure data has always been relative. And it could collapse if the microprocessor manufacturers and cryptography software editors were to be unable to cope against a new type of attack, fearsomely efficient, discovered by the team directed by the German cryptographer Jean-Pierre Seifert (universities of Haifa and Innsbruck). Electronic commerce could be threatened, but also, more broadly, everything that enables the dematerialization of exchanges, which rely on asymmetrical cryptography applications, would it be ciphers, digital signatures or message integrity checks.
In the still confidential article, the researcher and his colleagues describe the procedure they used to, gather a nearly entire cipher key of 512 bits (a series of as many of 0s and 1s) in a single attempt, that's to say in a few milliseconds. For comparison, the greatest public key that has been broken so far is 640 bits long, and as announced in November 2005, the process involved the usage of 80 microprocessors running at 2.2 Ghz for 3 months.
Since the announcement made this summer, on the International Association of Cryptology Research (IACR), that such an attack was theoretically feasible, microprocessors producers were on their nerves: the chips of nearly all of the computers, world wide, are vulnerable. So much that the head of Intel security, the number 1 microprocessor manufacturer, when confronted with the issue declared that he would be "unavailable for a few weeks". This is because the usual fix against classical attacks on public key cryptography - to increase the size of the keys - will not work this time.
Jean-Pierre Seifert was in fact able to affect the systems from the ground up. As most of the security relies on the incapacity to mathematically deduce the private key, kept secret, from the public one, he chose to study how the microprocessors was reading these confidential data.
He found out that the mode of operation or the chip itself, optimized for calculation speed, was making it vulnerable. "Security was sacrificed for the sake of performance", estimated the researcher.
The attack principle can be summed up as such: to go faster and faster, the microprocessor parallelizes operations and uses a branch prediction system to predict the result of the current operation. If the prediction is good, the computation time is greatly decreased. If not, the processor must go back and start again the elementary operation. It is "sufficient" to measure the computation time when the processor goes through the line of 0s and 1s that constitute the cipher key to able able to deduce it.
This threat, called "Branch Prediction Analysis" (BPA) was already known. It was thought a lot of attempts was necessary to statistically deduce the cipher key, thus making the attack not-practicable. The technique discovered by Jean-Pierre Seifert make it possible to break the key in a single attempt. It relies on the fact that the prediction process, essential to increase the processor speed, is not protected.
A spyware could then be made to listen to the chip discreetly, and send back the key to hackers, foreign intelligence services or competitors.
"A MATTER OF WEEKS"
We are not yet there though. "We have not made a turn key application that would be available online" argues Jean-Pierre Seifert. But he estimates that once the method is made public, in early 2007 during the next RSA conference - RSA, being one of the most popular ciphers -, the making of such software would be "a matter of weeks".
Cryptography specialists confirm that the threat is serious. One of the best world wide public key experts anonymously sums up the situation: "The real solution is to review the conception of the microprocessors itself - a long and difficult process. A short term solution would be to forbid normal applications to run in para
That's exactly why "Hyper-Threading Technology" is disabled by default on FreeBSD, and probably other systems.
- 05:09.htt.asc
It's a know issue:
http://security.freebsd.org/advisories/FreeBSD-SA
http://kerneltrap.org/node/5103
Cheers.
STOP SHOUTING!
Guess why I used a loop instead of a single increment instruction in my example code? Exactly: Because it's a bigint!
I've used x86 assembly as example because there you can see exactly where a branch occurs. I could also have written some generic C code to do the same which could have been in a bigint library (OTOH I can imagine a bigint library using assembler as well, just in order to speed things up).
What about actually reading the article? They explicitly don't target the multiplication algorithm, but the branch in the SM loop itself.
Again, RTFA. Their attack specifically works in multitasking OSs running on multiple execution pipeline processors (such as Intel's Hyperthreading). It won't work on multicore processors with only one pipeline per core, however.
The Tao of math: The numbers you can count are not the real numbers.