1024 bit RSA cracked?

[James Muir]

>> "The RSA algorithm gives security under the assumption that as long as
>> the private key is private, you can't break in unless you guess it.
>> We've shown that that's not true," said Valeria Bertacco, an associate
>> professor in the Department of Electrical Engineering and Computer
>> Science, in a statement.
> 
> They're not the first ones to show that!  Side-channel attacks have been
> around for a while now.  It's not just the algorithms, but the machine
> executing them and its physical characteristics that matter.

I agree. I think the paper overstates its novelty and implications.  It
seems to be an experimental implementation of a fault attack presented
by Boneh, DeMillo and Lipton (i.e. where it is assumed that single bit
errors affect the private exponent).  They target _some_ crypto
application** that uses the openssl library running on an fpga board.
Getting the attack to work in real life is no small feat, so they
deserve props for that, but they make a few questionable claims -- e.g.
they seem to state that the left-to-right fixed-window exponentiation
algorithm was thought to be immune to fault attacks.  In fact, adapting
the BDL attack, which was presented against a right-to-left algorithm,
to work against a left-to-right algorithm is straightforward, and so the
susceptibility of the left-to-right FWE algorithm has been known for
some time.

What I find much more strange about the paper is that the authors make
no mention of message blinding.  I could be wrong, but message blinding
would defeat their attack.  By default, an openssl server utilizes
message blinding in its private key operations, so there attack wouldn't
apply...

** I just had the following realization:  I had assumed that the authors
were attacking an openssl *server* running on the fpga board, but
perhaps that is not so.  They don't seem to make that specific claim.
They claim only to be attacking an "unmodified version of the OpenSSL
library".  It is possible that they only created a toy RSA application
that generates signatures using the openssl library (i.e. by making
calls to specific openssl functions).  This would explain why they don't
discuss message blinding -- because they didn't enable it in their toy
application!  I suspect that's what they did.  In that case, their
experimental results say very little about the susceptibility of an
openssl server to fault attacks.  Wow... if I'm correct, then the
authors really need to be more clear about exactly what they did.

-James

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 189 bytes
Desc: OpenPGP digital signature
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20100317/f12842f0/attachment.pgp>