A long answer to the simple question, "Is TLS provably secure?"

On Tuesday afternoon Tom Shrimpton gave a talk on the security of TLS [video]. This was of particular interest to me because it was a protocol I had spent some time studying during my PhD. TLS or Transport Layer Security is the most widely used security protocol on the Web; most famously being used to secure on-line credit card purchases.

In the first part of the talk Tom presented some joint work with Kenny Paterson and Tom Ristenpart which was published at Asiacrypt last year [pdf]. He started by posing the question: "Is TLS provable secure?". The answer to this was yes but with three caveats: 1) w.r.t the right model, 2) with some correctly chosen parameters, and 3) sometimes this isn't the correct question to ask.

The TLS record layer is responsible for ensuring the confidentiality and integrity of messages being sent. It follows a MAC-then-encode-then encrypt (MEE) structure. What is meant by this is that first a MAC is calculated on the message and then appended. Next this concatenated message is encoded by adding some additional padding bytes. Finally the message is encrypted; the recommended encryption scheme is CBC mode. Previous attacks on MEE type schemes have shown vulnerabilities in the composition especially when CBC mode is the preferred choice of encryption scheme. In particular the padding oracle attack of Vaudenay [ps] and its later extension in the attack on TLS by Canvel et al. [ps] exploit the timing difference between padding errors and MAC errors in order to recover plaintext. Tom showed that in TLS whenever the combined size of a message and tag is less than n-8 (when the block-size is n) with variable length padding we can always perform a distinguishing attack in an Authenticated-Encryption (AE) security model where the adversary is given access to a left-or-right (LOR) encryption oracle.

Previous work has been performed on examining the security of TLS by Krawczyk [pdf] and, Maurer and Tackmann [pdf] but it is not clear exactly how these results apply to TLS in practice. Krawczyk's analysis fails to consider padding and Maurer and Tackmann's work provides security based on a "secure" channels notion but only when minimal padding is used. The new security model presented in the talk was for Length-Hiding Authenticated Encryption (LHAE) thus allowing the study of variable-length padding. In this model the adversary now no longer needs to send two messages of equal length to the LOR encryption oracle as is the case in the normal model. Furthermore the following relationship can easily be proved (this is an extension of the standard relationship for IND-CCA security proved by Bellare and Namprempre [pdf]):

LHAE <=> LH-IND-CPA + INT-CTXT

Now to prove the security of TLS:

• The IND-CPA of CBC implies the LH-IND-CPA of TLS.
• We also know that any MAC-then-Encrypt scheme is INT-PTXT secure by the results of Bellare and Namprempre but this does not imply INT-CTXT.
• It therefore remained to find what the missing notion was that would give INT-CTXT security.

This missing notion was Collision Resistant Decryption (CRD). The theorem presented states that if

• the block cipher is a prp with block size n,
• the MAC is a prf with tag size t, and
• for all messages M we have |M|+t ≥ n.

then MEE using the TLS pad and CBC mode is CRD-secure (with a birthday type bound).

Putting all this together proves that TLS is LHAE secure.

In the second part of his talk Tom presented some work of an even more applied nature. Here he described joint work with Dyer, Coull and Ristenpart, entitled "Peek-a-Boo, I Still See You: Why Traffic Analysis Countermeasures Fail". The scenario here is that a user wants to hide which websites he visits by using a proxy. A provably secure AE scheme (such as TLS) is used to create a secure connection between the user and the proxy and the hope is that an adversary will not be able to determine the websites visited by eavesdropping on the traffic sent between the user and the proxy. In practice however, this is very hard to achieve. In 2006 Liberatore and Levine [pdf] showed that it was possible to correctly identify packets based on their size alone with 68% accuracy. In the new work presented by Tom they show that it is very easy for an adversary to identify which websites the user is visiting in the above scenario. In fact even with the current countermeasures websites can still be identified easily. With the obvious countermeasure of fixing the size of each packet to be equal this reduced the attackers accuracy to 6% but introduced a 365% overhead. This renders this countermeasure completely useless in practice. To prevent this type of traffic analysis it would be necessary to hide three things: download time, bandwidth and bursts of packets. The current countermeasures preventing analysis of these are all highly inefficient.