A New Vulnerability In RSA Cryptography

http://it.slashdot.org/article.pl?sid=06/11/18/2030247

A New Vulnerability In RSA Cryptography

    Posted by kdawson on Saturday November 18, 04:45PM
    from the predictions-of-trouble dept.

    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 [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, 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." [2]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 [3]ePrint abstract.

   1. http://eprint.iacr.or
g/2006/351
   2. 
http://www.lemond
e.fr/web/article/0,1-02-651865,36-83594451-835781,0.html
   3. http://eprint.iacr.or
g/2006/351


-- 
((Udhay Shankar N)) ((udhay  pobox.com))
((www.digeratus.com))

------------------------------------------------------------
---------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography"
to majordomometzdowd.com

Udhay Shankar N <udhaypobox.com> writes:

>However, 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,
>successfully bypasses the OpenSSL protections, and
should prove harder to
>avoid without a very large execution penalty."

That's not quite accurate.  What it did was succeed against
a an old version
of OpenSSL that (a) didn't have the protections present yet
and (b) had been
specially modified to make it vulnerable to the attack. 
It's a nice attack,
but based on what's been published so far the claims of
RSA's demise are
considerably exaggerated.

What it does is rely on the fact that on a HT P4, if you
saturate the branch
target buffer (BTB) from a second thread running in the same
pipeline (i.e. on
the same HT CPU), you can see when BTB misses occur in the
RSA thread and
therefore observe whether it's branching on a one or zero
bit.

To do this, they had to use (as mentioned above) a rather
old version of
OpenSSL that doesn't employ any protection against this type
of attack.  In
addition they reduced the modexp window size from 5 to 1 (to
make sure you get
a branch for each bit, with the standard window size 5 the
branches are
replaced by a table lookup), and they disabled the CRT code
(to force use of
the textbook-mode RSA operation that, in practice, no
software implementation
ever uses).

This isn't to say that the paper doesn't point out a
potential vulnerability.
However, saying "we broke RSA" or "we broke
OpenSSL" is pushing things a bit.

Peter.

------------------------------------------------------------
---------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography"
to majordomometzdowd.com