A New Vulnerability In RSA Cryptography

[Peter Gutmann]

Udhay Shankar N <udhay at pobox.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 majordomo at metzdowd.com