As the number of digital transactions increases explosively each year, more and more people place their trust in the security that underlies e-commerce. As we have seen before, only years of study can ensure that the underlying cryptography is strong. However, even trusted protocols such as SSL can have weaknesses that are exposed after many years of use.

Czech cryptographers Klima, Pokorny and Rosa have discoverd such an attack on the RSA-based SSL/TLS protocol and made it publicly available March 14, 2003 on the International Association of Cryptologic Research ePrint server. (http://eprint.iacr.org/2003/052/)

In fact, practical tests showed that two-thirds of randomly chosen SSL/TLS web servers were vulnerable.

Summary of the Attack

The attack extends a famous attack of Bleichenbacher from the Advances in Cryptology 1998 conference. Bleichenbacher’s attack exploits features in PKCS #1 version 1.5 padding used for RSA encryption, and in particular how this PKCS #1 version 1.5 padding was used in the SSL/TLS protocol.
Klima, Pokorny and Rosa’s attack is more specific to SSL/TLS protocol than Bleichenbacher’s attack, but similar in its underlying mathematics. It exploits alert messages sent during the SSL/TLS protocol resulting from incorrect lengths of the plaintext or from incorrect SSL/TLS version numbers contained in the plaintext.

Each such alert message can be used to leak, according to Klima, Pokorny and Rosa, a small amount of information about the master key used for a previous SSL/TLS. Eventually this leaked information, the authors claim, can be accumulated together and the master key of a previous SSL/TLS session can be recovered, allowing the adversary to decrypt all the messages protected during that session.

Klima, Pokorny and Rosa examined several SSL/TLS servers for potential vulnerability to their attack by examining the frequency with which the dangerous alerts were issued. They found that several servers with OpenSSL, which is used in approximately 50% of all e-commerce web servers, issued leaky alerts at considerable rates. From these rates, the authors estimated that if their attack was implemented, it could compromise a previous SSL/TLS session by bombarding an SSL/TLS server with specially
chosen RSA ciphertexts for 56 hours continuously.

Assessment of the Attack

The damage of the attack is specific to the RSA algorithm, and the PKCS #1 version 1.5 padding in particular. Furthermore, it is limited to the SSL/TLS protocol, unlike Bleichenbacher’s original attack that affected more general uses of RSA with PKCS #1 version 1.5 padding.

The viability of the attack is limited by the need to bombard an SSL/TLS server with copious amounts of invalid RSA ciphertexts. In practice, an SSL/TLS server might not allow such a large amount of invalid ciphertexts. Nevertheless, such limitations are inappropriate countermeasures for such an attack because of their lack of cryptographic robustness.

Despite the limitations above, the sheer ubiquity of SSL/TLS using RSA with PKCS #1 version 1.5 compensates to make the impact of the Klima, Pokorny and Rosa attack potentially very harmful. As well, Klima, Pokorny and Rosa’s attack might extend to other forms of RSA padding, such as OAEP (Optimal Asymmetric Encryption Padding), by analogy to Manger’s extension of Bleichenbacher’s attack.

Interestingly, Klima, Pokorny and Rosa’s attack does not apply to SSL/TLS using ECC because it uses key agreement rather than key transport to transmit the “pre-master secret”. In particular, this means that the pre-master secret is not conveyed in a plaintext, but rather more indirectly by calculations done on both the client side and the server side. As a result, there is no plaintext used to transmit the pre-master secret, which is the crux of the Klima, Pokorny and Rosa attack. Therefore, no version number and no length in the plaintext need checking so the problematic alert messages used by the attack are not generated when using ECC.

Reactions to the Attack

Klima, Pokorny and Rosa suggest a countermeasure that they deem optimal. In their countermeasure, a SSL/TLS server, instead of issuing an alert immediately upon discovery of an invalid length or version, replaces the offending pre-master secret by a random one, and proceeds as though everything was fine.
The OpenSSL group issued a patch that aimed to prevent Klima, Pokorny and Rosa’s attack. The patch essentially implemented the countermeasure recommended by Klima, Pokorny and Rosa.
Only time will tell if this change prevents exposing the protocol to yet other attacks, such as those based on timing analysis.



Find a copy of Klima, Pokorny and Rosa’s paper
Attacking RSA-based Sessions in SSL/TLS at
http://eprint.iacr.org/2003/052/