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

From: [email-masked] (Martin Rex)
Date: Tue, 3 Dec 2013 00:07:58 +0100 (CET)

Nikos Mavrogiannopoulos 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.
> 
> 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.

Very important observation.

Peter's proposal changes AtE to EtA, but does not currently address
the predictable IV for SSLv3 & TLSv1.0.  As it turns out, EtA will
not protect from BEAST, because it is "generically" secure only against
decryption oracles.  BEAST was exploiting an _encryption_ oracle.

:-)

-Martin

---

From: Wan-Teh Chang <[email-masked]>
Date: Mon, 2 Dec 2013 19:58:17 -0800

I am a programmer working on the NSS crypto libraries. Here are my
thoughts on this issue.

1. Since TLS 1.0 is widely deployed, we don't need to fix this issue
for SSL 3.0. This will avoid the need to add another SCSV.

2. I prefer a TLS extension that changes how CBC block ciphers work,
rather than adding new AEAD ciphers based on CBC-HMAC. (We already
have too many cipher suites.) In addition, CBC block ciphers should
work in this new way by default in TLS 1.3.

An argument for adding new AEAD ciphers based on CBC-HMAC is that it
simplifies testing. The extension-based solution essentially forks
every TLS version and increases the number of combinations that need
to be tested.

3. I took a look at the TLS/SSL implementation in NSS. I believe that
the EtA and pad-MAC-Encrypt proposals should require similar amount of
change to the NSS source code.

Ignoring the details of padding, It boils down to reordering the
operations this way:
    MAC-pad-Encrypt => pad-MAC-Encrypt
vs. reordering the operations this way:
    MAC-pad-Encrypt => pad-Encrypt-MAC

So the assertion that pad-MAC-Encrypt requires a smaller patch doesn't
seem to be true for NSS. Caveat: it's possible that the arguments
passed to the three operations need more adjustments when the
operations are reordered in one way. I didn't look into that.

4. The TLS/SSL implementation in NSS performs the padding itself
rather than letting the underlying encryption function do the padding.
This means the pad-MAC-Encrypt proposal won't make things more
difficult for NSS in this aspect.

Wan-Teh Chang

---

From: Nikos Mavrogiannopoulos <[email-masked]>
Date: Wed, 04 Dec 2013 09:11:35 +0100

On Sat, 2013-11-30 at 17:29 +0000, Paterson, Kenny wrote:

> 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.

Hello Kenny,
 Indeed, this is the paper I was referring to. Note however, that my
main point was not about any issue with the proof instead, but how
crypto proofs should be interpreted by non-hardcore-crypto experts. As
we are now, a proof in a cryptography field is not equivalent to a
proof, for example, in the language of mathematics, which is typically
accepted as a universal truth. 

> 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.

Indeed, and the paper contributes a lot to our knowledge of the AtE
mode.

> 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.

That's why I don't like this kind of fixes (having 500 or 1000 lines to
remove the CBC padding is unacceptable to me). Thus I find it natural
for an implementer to avoid such a fix, as he may accidentally introduce
more bugs than the one it solves.  This is the reason I would like to
see a proper fix in the protocol.

> 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.

Indeed, but I believe the same point applies for AtE if AtE is seen as
Pad-then-MAC-then-Encrypt (thanks to your attacks and papers, this is
the only reasonable interpretation of AtE today).

> 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.

I agree that if TLS would be redesigned today, that could be a very good
point. However, this is not the case. The issue at hand is a fix in the
CBC ciphersuites and I find it quite drastic change (*) to switch the
order of encryption and authentication in all ciphersuites just because
of an issue in the CBC ones. That's why I'd prefer a simple fix for the
issue at hand that is _known_ to be as secure as EtA for the ciphers we
use.

(*). drastic but acceptable for me though - see my previous posts.

> 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.

This is true, but it is part of my argumentation as I consider AtE to be
pad-then-MAC-then-encrypt, can be seen as no padding whatsoever, the AtE
proof applies directly.

> 2. It assumes the MAC output size is the same as the block cipher's block
> size.

That I hadn't notice, and if it is not fixable, it is indeed a strong
counter-argument against pad-mac-then-encrypt.

> 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.

So as I understand your proof fixes the point (2), that you mentioned
above?

> 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).

I believe your opinion is greatly appreciated on this list (and of
course by me), so thanks for taking the time of expressing it. It is
nice to discuss with solid arguments.

best regards,
Nikos

---

From: "Paterson, Kenny" <[email-masked]>
Date: Wed, 4 Dec 2013 09:20:42 +0000

Nikos,

On 04/12/2013 08:11, "Nikos Mavrogiannopoulos" <[email-masked]> wrote:

<snippage>

>So as I understand your proof fixes the point (2), that you mentioned

It should. But, to our continuing embarrassment, the proof is not yet in
the public domain - the published version of the paper does not include
it, because of page limits, and we never got the full version into a shape
that we are happy with. We have more motivation than ever to finish it.

I also believe the Phil Rogaway and co-authors have been examining MtE
versus EtM recently, and should have some new results that give additional
support to MtE provided the encryption scheme satisfies certain natural
properties. I'll see if I can get Phil or his co-authors to post a summary
here, but if you want an advance preview, there's this:

http://2013.diac.cr.yp.to/slides/rogaway.pdf

particularly slides 7 and 8 (but notice the conditions on the encryption
scheme on slide 8).

Cheers

Kenny