A New Vulnerability In RSA Cryptography 108
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.
I got a question... (Score:4, Interesting)
What is to be done? (Score:2)
Get rid of the spyware, perhaps?
Multi-site servers at risk? (Score:5, Insightful)
Re: (Score:2)
Re: (Score:3, Informative)
Re:I got a question... (Score:5, Interesting)
The following loop (adapted from fig. 3 in the paper) should IMHO work as well (although less efficiently):The only branch here is in the for loop, and that's independent of the key. Unless there are exploitable branches in the multiplication routine, of course.
Great idea! (Score:5, Interesting)
A slight improvement to your idea might be to balance the loop anyway, using D = 1 - di, etc., essentially a vectorized version of figure 4. This would slow it down by a factor of two but it would make it resistant to conventional timing attacks.
I was wrong about the speed (Score:2)
Balancing may not be needed at all with the vectorized version. Certainly the same top level calls are made each time through the loop regardless of the bits in the private key so the need to balance is totally dependent on the impleme
Re: (Score:2)
branching. Or did you just think they magically happen?
Re: (Score:2)
Re: (Score:3, Interesting)
The question is if they have exploitable branching. For example, the only + in that algorithm is the C=C+1, and that can clearly be done without exploitable branching, e.g. with the following x86 assembler code (assuming lsb-first storage, as usual for x86):
Re: (Score:2)
are specifically designed to handle bigint numbers that 100+ digits long. that is the
branching they are talking about in the article nothing else.
That said, temporal and power cryptography has been known for at least 15 years now. this article
is yesterdays news. the people writing this stuff are for all intents and purposes burnouts from
the 90s.
In short such attack don't work will in multitasking OSs running on multiple
Re: (Score:3, Informative)
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).
Re: (Score:2)
C = di
C = C * A
C = C + 1
if di was 1, then C - M, but if di was 0, the C - 0
If C - 0, you get the wrong answer.
Re: (Score:1)
Re: (Score:2)
For di=0:For di=1:
Re: (Score:1)
S = M
for i from 1 to n-1 do
S = S * S (mod N)
C = (M & di) + (1 & not di)
S = S * C (mod N)
return S
Re: (Score:1)
Re: (Score:3, Interesting)
Re: (Score:2)
Re: (Score:3, Informative)
I would think this can be circumvented by alternat
Re:I got a question... (Score:5, Informative)
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.
Re:I got a question... (Score:5, Informative)
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
1. Use a most recent Via CPUs (the ones released this year). The C7 has the time consuming parts of RSA accelerated on the CPU which makes this attack considerably less feasible. This is possibly the only cost effective method for limited budget cases where high speed is required. A full motherboard with CPU, SATA and all bells and whistles is around 150 pounds and IIRC is supported by OpenSSL 0.9.8 (and backport patches).
2. Use (to the full) TPM on your machine (if present
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
Or keep the system so heavily loaded that the spy process can't tell whether it's sharing a BTB with the RSA computation or with one of the other N threads.
Or use a thread scheduler that assigns separate CPUs to crypto threads and to spyware threads
Re: (Score:2, Informative)
Maybe, maybe not (Score:2)
Second, these are timing-based attacks that perform branch prediction. This requires no changes to OpenSSL or any other source to completely mask. You first mix the optimization me
Let me be the first to say.. (Score:1, Funny)
Not so bad... (Score:5, Insightful)
So it requires a spy proccess to be running on the same processor as the server....
--jeffk++
Re: (Score:1)
Re: (Score:2, Informative)
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. [weizmann.ac.il]
Re: (Score:2)
You can also attack the algorithm by measuring current draw on the cpu, or you can attack it by measuring RF radiation from the system too.
In order to avoid these attacks, the cpu's ALU's etc need to be designed with complementary logic gates such that no matter what signal is changing, there is always a paired signal changing the other way - so there are always the same number of data and clock transitions of every type on every clock cycle, giving you constant power usage.
--jeffk++
Re: (Score:1)
There's a *real* problem with this. Constant power output means *maximum* power output, 100% of the time.
Think about it...
Re: (Score:2)
I wonder if the 'Trusted Computing' chips do this - If they don't then this could be researched as a work-around for them.
--jeffk++
mod parent up (Score:1, Informative)
Re:Not so bad... (Score:5, Interesting)
Essentially they took a very impractical attack with an unlikely scenario, and created a somewhat practical attack with an unlikely scenario. Avoid the problem scenario which was raised in the prior work last year, and you are still golden.
Re: (Score:2, Informative)
It's a know issue:
http://security.freebsd.org/advisories/FreeBSD-SA
http://kerneltrap.org/node/5103 [kerneltrap.org]
Cheers.
Re: (Score:1, Insightful)
Re: (Score:3, Interesting)
The problem is that theoretically the attacker could use javascript or any other locally interpreted language or an ActiveX control under Inter
Re: (Score:1)
Re: (Score:2)
Not necessarily. Javascript or any other interpreted language could probably perform this attack and would run as the victim user, but since it's sandboxed the attack couldn't get at the keys directly.
Re: (Score:1)
Re: (Score:2)
OK, so obviously the attack can be thwarted by preventing a crypto thread from sharing a core with any untrusted th
Re:Not so bad... (Score:4, Insightful)
Re: (Score:1)
Corel Cache (Score:5, Informative)
PDF file [nyud.net]
Unsecure computer - no secrets. Big deal ! (Score:1)
Re: (Score:3, Informative)
Re: (Score:1)
Re: (Score:1, Insightful)
"Moreover, despite sophisticated hardware-assisted partitioning methods such as memory protection, sandboxing or even virtualization, SBPA attacks empower an unprivileged process to successfully attack other processes running in parallel on the same processor."
Re: (Score:2)
Re:Unsecure computer - no secrets. Big deal ! (Score:4, Interesting)
Virtualization (Score:2)
Re:Unsecure computer - no secrets. Big deal ! (Score:4, Informative)
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).
Re:Unsecure computer - no secrets. Big deal ! (Score:4, Insightful)
And perhaps more signifigantly, it is problematic for idiots who think the definition of "secure/security" is using some DRM scheme hoping to "secure" a computer against its owner.
The owner of a computer can use the technique in this article to keep an eye on his own computer and track what his computer is doing for him, and to record the DRM-keys being used to "secure" his own data against him.
-
Re: (Score:2)
For this special attack, I don't think it would matter too much if the users know good security practices. If you start up SSL, it probably start off with a sequence that can be easily detected (e.g. by simply watching what's running on a machine). Then the spy application would kick in. It's something to be solved by the software implementors more than
Re: (Score:2)
VMS (Score:3, Interesting)
I started working on VAX/VMS systems in 1986. I changed jobs to another DEC site after nine months or so. I got an account, put my username in at the appropriate prompt, hit return and then immediately knew that I had entered my old username, not the new one.
I had to think for a bit before I knew the reason: VMS searched SYSUAF.DAT for my username before I entered the password. If it found the username it would stop searching. Later versions did the search after the password had been entered and one type of attack became less likely.
I suppose something like this could be done so that timing can't be used to debug the process runing the algorithm but another way of viewing it is that it is like getting the key from a chip by measuring the amount of power it uses or something. There may be limits to who far protection can go if you have the hardware or are on the same (virtual) machine.
Re: (Score:1)
Re: (Score:2)
Branch predictor as a covert channel (Score:5, Interesting)
This class of problems is only going to grow as CPUs become less and less deterministic.
Solution to: Branch predictor as a covert channel (Score:4, Interesting)
R0 = 1; R1 = M
for i from 0 to n-1 do
if d[i] then
R1 = R0 * R1 mod N
R0 = R0 * R0 mod N
else
R0 = R0 * R1 mod N
R1 = R1 * R1 mod N
return R0
The key-dependent if statement is the key here, if we can remove all such branches, then there's no Branch Target Buffer entry that depends on it, and no timing channel attack either:
R0 = 1; R1 = M;
for (i = 0; i < n; i++) {
mask = 0 - d[i];
nmask = mask ^ -1;
T0 = R0 & mask;
T0 += R1 & nmask;
T1 = R0 * R1 mod N;
T0 = T0 * T0 mod N;
R1 = T1 & mask;
R0 = T0 & mask;
R0 += T1 & nmask;
R1 += T0 & nmask;
}
return R0;
There are at least three interesting issues here:
a) Most modern cpus have hw support for conditional operations, on x86 this is in the form of CMOVcc which is a (constant-time!) conditional move into a register, but as shown above, it really isn't needed here.
b) The perforance impact of the above branch removal can be negative!
On a P4 a branch miss costs about 20 clock cycles, and since a key-dependent branch will miss 50% of the time, the average cost is 10 cycles. My replacement code above takes around 5 cycles or less on any current cpu.
c) A final possible timing-channel attack would be due to the memory alignment of the R0 and R1 values:
By allocating them at the same address modulo the cpu page size, i.e. at 4 KB offset, the cache lines hit will be the same for both.
When I worked on the asm version of DFC, one of the AES also-rans, I removed a similar timing attack from a core 128-bit modular multiplication operation, using very similar techniques.
Terje
MOD PARENT UP (Score:2)
RSA Isn't Broken, And This Is Localhost Only (Score:5, Informative)
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 [matasano.com]. 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.
Re: DRM? (Score:2)
DRMs! yep yep!...
I would love to see Vista DRMs cracked before the OS even make it to the market...
ok.. i'm probably dreaming, but still it feels good.
Re: (Score:3, Interesting)
No no no! I hate when researchers do that!
Not long ago someone published a way to load unsigned kernal drivers in Vista (Vista's DRM mechanisms criticially rely on owners being strictly forbidden to do that). So what happened? Microsoft patched Vista to prevent that mechanism from working... before the OS even made it to market. So the discovery and all that work went entirely to waste.
No, when someone finds an anti-DRM met
Re: (Score:1, Offtopic)
Virtually every academic paper ever published will match some statement of the form "a refined X for a known Y". That's what academic papers do. Papers which break new ground come around about once every few decades; most significant developments are actually a sequence of very small steps that the press ignores because it doesn't sound very impressive that way.
Academic papers are almost never newsworthy. They are for academics to read. If y
Re: (Score:3, Insightful)
Re: (Score:1)
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.
What's more, they didn't break OpenSSL even on the same machine. To quote from the paper:
Closed and open. (Score:1)
This really hits the mark. What if OpenSSL, an arguably widely-used crypto layer, were closed instead of open? According to what I hear on Slashdot, we would have no idea if "ClosedSSL" would have protection against this kind of thing, but because OpenSSL is, uh, open, we can verify that these kinds of attacks are indeed mitigated.
Re: (Score:2)
In fact, if I understood the article correctly, this particular attack is NOT mitigated by the protections that were implemented in OpenSSL.
Re: (Score:1)
Translation of the article published by Le Monde (Score:5, Informative)
====
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
It All Depends On Simple Branch Prediction (Score:1)
Run it on the GPU (Score:2, Interesting)
Re: (Score:2)
No, if you're doing a lot of SSL work and are worried about this, take a look at SSL accelerator cards. They range from $100 to $1000, and seem quite useful for website hosting that will be doing a lot of encrypted traffic.
What about virtualization? (Score:1)
It only needs the public key (Score:1)
PGP / GPG: It only needs the public key! (Score:1)
here's how it works (from the paper) (Score:3, Informative)
Redundant ? (Score:3, Interesting)
The whole thing - as critical as it is - spies on the processes running on the machine. It is an indirect attack, checking on the resources used while performing some not broken algorithmic calculations.
When you disable pipelining and cache while doing the calculations, there is not much to spy on and nothing to gain. Just prevent the wanna-be intruder from seeing cache, pipelines, CPU from working makes you safe.
The problem is, that this isn't very practical.
I wished the editors used less misleading headlines. There is no vulnerability in RSA cryptography per se. It is rather that you observe Men At Work and from what you see you can guess what the're doing.
And in principle this applies to any other cryptography just as well. Inclusive DRM (which makes me giggle).
Nobody uses binary exponentiation (Score:2, Interesting)
predication is your friend (Score:1)
Multi-Processors (Score:1)
I can't login to my Slashdot account! (Score:1, Funny)
Peter Gutmann on the Seifert Paper (Score:1)
Widely-respected Australian cryptographer Peter Gutmann offered a concise analysis of the Seifert's achievement on the Cryptography Mailing List yesterday. It offers both detail and useful perspective.
Udhay Shankar N had just summarized the scary rumors about the Seifert's attack:
"... German cryptographer Jean-Pierre Seifert has announced [1]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, successful
Re: Peter Gutmann on the Seifert Paper (Score:1)