Re: [TLS] Encrypt-then-MAC again (was Re: padding bug)

["Paterson, Kenny" <[e-mail]>]

Hi Nikos, all,

I've been following this discussion with great interest, but keeping
rather quiet since my last contribution because I've been a bit busy with
other work, and because I was told that I was contorting reality last time
I tried to make a contribution...which left me somewhat disenchanted with
the tenor of the debate.

On 30/11/2013 15:50, "Nikos Mavrogiannopoulos" <[e-mail]> wrote:

>On Fri, 2013-11-29 at 17:23 -0800, Watson Ladd wrote:
>
>> > Contrary to popular opinion on this list AtE is a standard way of
>> > operation with no flaws known unless used with an unauthenticated pad
>> > (as in TLS). When SSL 3.0 was designed AtE was believed to be the
>> > conservative approach comparing to EtA.
>> The passive voice is doing a lot of work here. Bellare and Namparah
>> showed that EtA is generically secure,
>> AtE isn't. Rogaway sent out an email in 1995 pleading for EtA in TLS.
>> "no flaws known"!="proved to be secure"
>
>Proven to be secure doesn't mean that attacks don't exist. The TLS
>padding scheme was proven to be secure prior to be broken; ironically by
>the same person who made the proof. Attacks work by playing outside the
>requirements of the proof.

I assume here that you're referring to my "Tag size matters" paper with
Ristenpart and Shrimpton, and then to the Lucky 13 paper here. OK, with
some of my TLS credentials established for those who don't know me, here
are the key points that I take away from the TLS proof (from that paper)
versus the Lucky 13 attack:

The proof for MAC-then-Pad-then-Encrypt in TLS was extremely delicate and
difficult to produce. Indeed, in generating it, we came up with another
new attack on "TLS with short MACs" that excludes certain parameters from
ever being secure. We then had to make an assumption for the proof to go
through: that the decryption process does not leak the source of
decryption failure (sanity check failure, bad pad, or bad MAC), or any of
the timing involved in decryption.

What the Lucky 13 attack showed is that achieving this "uniformity of
errors" is very difficult for TLS's MAC-then-Pad-then-Encrypt construction.

And this is why MAC-then-Encrypt - and its real world variants - are being
given such a hard time on this list by some, including me: our bitter
experience is that implementing it securely is just much too hard. Witness
Adam Langley's 500 line patch for OpenSSL and NSS to get this (finally)
right. (Side note - Adam deserves credit for independently discovering the
same attack vector that we used in Lucky 13.)

To add a bit more detail: during the Lucky 13 disclosure process, I worked
with many vendors to help them get their patches ready. Very few of them
were actually able to completely eliminate timing side channels completely
in their implementations, and all that I know of (except for Adam) settled
for a "good enough" approach. Of course, that pragmatic approach is quite
justifiable. But it may still leave open small windows of opportunity for
future attack.

Bottom line: none of the many issues that MAC-then-Pad-then-Encrypt has
had in TLS should *ever* arise for Encrypt-then-MAC, unless the
implementer was extremely ill-educated.

To me, the perceived dangers of exposing the MAC - dangers which neither I
(nor any serious cryptographer I know) accept as being real - are far
outweighed by the simplicity and robustness provided by an
Encrypt-then-MAC approach.

>Nevertheless, there is much more recent work on EtA vs AtE, that
>actually proves AtE secure (not "generically" as you pose, you just need
>a decent cipher). You may check "The order of encryption and
>authentication for protecting communications (or: How secure is SSL?)".
>There are even newer papers than that, it is just this that came to
>mind.

This is too simplistic an interpretation of that paper by Hugo Krawczyk,
I'm afraid. It's an excellent piece of work, and quite ahead of its time
in trying to apply provable security techniques to a real protocol. But it
has two major shortcomings if you try to apply it to CBC-mode encryption
as used in TLS:

1. It does not consider TLS padding whatsoever - but instead assumes data
is all block-aligned. As soon as you introduce padding in-between the MAC
and the encryption, i.e. as in TLS's actual construction, you run into
lots of trouble - Vaudenay, Bodo Moeller's observations, Lucky 13 and all.

2. It assumes the MAC output size is the same as the block cipher's block
size. Out of all mainstream TLS ciphersuites that I know, this is true
only for HMAC-MD5 with AES. And I think we all agree we'd like to avoid
MD5 now!

On the plus side, and perhaps this is what you were referring to, Hugo's
analysis works just fine for stream-cipher based ciphersuites (as long as
the stream cipher is good - so not RC4 then!). The Asiacrypt 2011 paper
can be seen as extending his analysis to handle the actual construction
used in TLS's CBC-mode ciphersuites, but with the important, necessary,
and difficult-to-achieve proviso concerning uniformity of errors.

Also on the plus side, Hugo's analysis can be fairly easily extended to
cover the Pad-then-MAC-then-Encrypt construction for CBC-mode encryption
that you, and others, have been arguing for (still under the assumption
concerning the size of the MAC tags and the block size, though it might be
that this assumption can be removed with more work). So there is indeed
theoretical support for this kind of construction. And maybe it can even
be implemented securely, too.

But, at the risk of repeating myself, I very much prefer the simplicity
and robustness of an Encrypt-then-MAC construction.

Of course, this is just another opinion, like many others that have been
expressed on this list recently, and I cannot hope it will be the last
word on the subject. But I can hope that it's accepted as an opinion born
from significant experience in analysing TLS security, from a variety of
perspectives (theoretical, implementation, attacks).

Best wishes,

Kenny