Subject: Re: [TLS] Fixing CBC Mode I: GenericBlockCipher construction

From: Bill Frantz <[email-masked]>
Date: Sun, 5 Jan 2014 22:37:25 -0800

[Getting caught up on mail after vacation.]

On 12/29/13 at 3:15 PM, [email-masked] (Eric Rescorla) wrote:

> We have seen two major proposals for fixing the GenericBlockCipher
> construction:
> 
> - Encrypt-then-MAC
> - Pad-MAC-Encrypt

Given the better robustness shown by Encrypt-then-MAC, I prefer it. Its weakness seem to be:

  * If the MAC leaks MAC key bits and the MAC key generation from
  the initial master secret can be reversed, an attacker can
  recover the session encryption key. I don't think this attack
  is likely.

  * If the MAC is weak enough that an attacker can create valid
  MACs for messages, a message injection attack or a replay
  attack may be possible. I think the proven properties of HMAC
  make this attack unlikely.
  
Cheers - Bill

-------------------------------------------------------------------------
Bill Frantz        | The first thing you need when  | Periwinkle
(408)356-8506      | using a perimeter defense is a | 16345 Englewood Ave
www.pwpconsult.com | perimeter.                     | Los Gatos, CA 95032

---

From: [email-masked] (Martin Rex)
Date: Fri, 10 Jan 2014 06:53:12 +0100 (CET)

Eric Rescorla wrote:
> The sense of the chairs is that the Encrypt-then-MAC construction
> has greater support (see, for instance, the thread started by
> http://www.ietf.org/mail-archive/web/tls/current/msg10584.html)
> but we would like to confirm that impression.
> 
> If you have a comment to make about this, please do so by
> January 10, 2014.

It seems to me that both of these approaches, when applied to the
SSLv3/TLSv1.0 GenericBlockCipher PDU with "running IV", will pull
the rug from underneath the 1/(n-1) record splitting workaround
that has been widely adopted as countermeasure to the Rizzo/Duong
BEAST attack, because the first block is going to be filled with
only deterministic block cipher padding following the one byte of
application data rather than an unpredictable (H)MAC output.

I therefore firmly believe that the fix should use one common
GenericBlockCipher PDU with an explicit IV for SSLv3 and TLSv1.0
as well.

A month ago I indicated that I would write and submit an I-D for
Pad-MAC-Encrypt.  I'm sorry I have not yet succeeded (I am still actively
working on it).  Aside of family/vacation and duties of my regular job,
I've been busy trying to figure out the historic events and coming
up with a rationale for the Pad-MAC-Encrypt approach that I prefer.
(and I since realized that history was somewhat different to what I
 had thought...).

Before X-Mas I did a proof-of-concept implementation for myself
(based on openssl-1.0.1e) in order to get an idea about implementation
complexity, LoC ballpark and potential pitfalls.

In the last paragraph of Section 7, the LuckyThirteen paper writes
about the OpenSSL patch to make the original Decrypt-unpad-MACverify
processing execute in (near) constant time:

  The OpenSSL patch addressing the attacks in this paper provides
  an exemplar of how to do this. The complexity of the OpenSSL patch
  is notable, with around 500 lines of new 'C' code being required.
  For further discussion and explanation,
  see http://www.imperialviolet.org/2013/02/04/luckythirteen.html

My private OpenSSL PoC included an SCSV for client->server signaling,
a ServerHelloExtension for server->client signaling and covered
TLSv1.0,v1.1&v1.2 and used an explicit IV for TLSv1.0 and amounted
to ~200 LoC, but I continued to call tls1_cbc_remove_padding()
to remove the padding.  (Covering DTLS and SSLv3 should be 
less than 100 additional LoC).

Implementing this took me 2 hours.  Determining that the tunneling
of the padding length back through rr->type was causing me interop
problems took me 10 minutes once I stepped through the code in
the debugger.  (but I spend 4 hours trying to understand the
interop problem only by source code review before I decided to recompile
in debug mode and step through the code in the debugger...).

-Martin

---

From: Adam Langley <[email-masked]>
Date: Fri, 10 Jan 2014 10:54:29 -0500

> the rug from underneath the 1/(n-1) record splitting workaround

Yes, if the MAC isn't going to end up as the IV for the next block
then 1/n-1 record splitting doesn't work.

So unless this extension also enables an explicit IV then it's limited
to >= TLS 1.1.

That wouldn't be too much of a concern, except for version fallback.
/Hopefully/ version fallback will be solved[1] soon.

[1] https://tools.ietf.org/html/draft-bmoeller-tls-downgrade-scsv-01

> processing execute in (near) constant time:

I believe the patch achieves actual constant time processing. (And I
measured that with cycle counters.) Although note that upstream
OpenSSL reenabled the stitched AES-SHA code and that's not
constant-time.

> less than 100 additional LoC).

Certainly, almost anything is better than trying to implement the
current CBC modes in constant-time.

Cheers

AGL

---

From: Watson Ladd <[email-masked]>
Date: Fri, 10 Jan 2014 08:15:46 -0800

> So unless this extension also enables an explicit IV then it's limited

I'm very surprised at the both of you. Because we will have ciphertext
integrity,
CBC decryption oracles aren't a consideration. The remaining attack on
deterministic IVs is guessing
low entropy blocks by injecting cleverly chosen blocks. But 1/(n-1)
record splitting will prevent this attack
by restricting the control over the next IV to be negligible.

Sincerely,
Watson Ladd

>
> <snip>
>
>
> Cheers
>
> AGL
> _______________________________________________
> TLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tls

-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin

---

From: Adam Langley <[email-masked]>
Date: Fri, 10 Jan 2014 11:57:20 -0500

On Fri, Jan 10, 2014 at 11:15 AM, Watson Ladd <[email-masked]> wrote:
> CBC decryption oracles aren't a consideration.

Sure, but 1/n-1 was never about decryption oracles.

> The remaining attack on

This is using 1/n-1 record splitting in a different way and you appear
to be confident that it's safe. It's certainly not as obviously safe
as using a random IV for CBC mode.

I agree that it's not obvious that anything bad can be done because
the attacker doesn't have enough control over the contents of the
first block. But we know that CBC mode *should* have random IVs and,
if we're changing code anyway, I think you're being much too accepting
of throwing together a new construction rather than doing it right. It
would make me sad if we're not going to say that the extension
negotiates explicit IVs *and* not say that it needs TLS 1.1. TLS 1.1
just isn't that hard to implement and we might be able to securely
negotiate it soon.

Cheers

AGL

---

From: Eric Rescorla <[email-masked]>
Date: Fri, 10 Jan 2014 09:07:00 -0800

On Fri, Jan 10, 2014 at 8:57 AM, Adam Langley <[email-masked]> wrote:
> It

Yes, that seems likely.

Indeed, unless I'm missing something, the same draft that we need to
negotiate TLS 1.1 securely is also what we need to negotiate
this draft securely.

-Ekr

---

From: [email-masked] (Martin Rex)
Date: Fri, 10 Jan 2014 23:02:39 +0100 (CET)

Watson Ladd wrote:
> Adam Langley <[email-masked]> wrote:
>>
>> Martin Rex <[email-masked]> wrote:
>>>

Ooops, I'm sorry.  You're correct in that 1/(n-1) record splitting
will continue to prevent the original attack.  I was confused.

In its original characterization [1] the weakness has two prerequisites
to work (1) the IV must be known prior to the submission of the plaintext
and (2) it must be possible to specify most (or all) of the plaintext
block that gets encrypted with that IV.

The CBC residue that is IV for the next record in SSLv3/TLSv1.0 becomes known
to the attacker prior to submission of the next plaintext, but it
still has the "strong random" property.  The attacker can not force a
specific IV.  With 1/(n-1) splitting, the attacker has control over just
a single octet of the next plaintext block.  Whether the remaining
plaintext is strong random (e.g. encrypted HMAC) or whether it is
known fixed padding is actually not relevant here.

What happens is that the (len=1) record gets XOR-ed with a strong random
(but pre-known) IV and is then AES-encrypted.  The resulting ciphertext
is again strong random / non-predictable (in the sense that you don't
know it before you see it), so that the (n-1) block, where the attacker
has full control over all plaintext bytes, the IV will be unknown at
the time when the plaintext is submitted.

I'm sorry for the confusion.

-Martin

---

From: [email-masked] (Martin Rex)
Date: Fri, 10 Jan 2014 23:18:13 +0100 (CET)

Adam Langley wrote:
> Watson Ladd <[email-masked]> wrote:
>>

I'm perfectly fine with implementations supporting and using protocol
features and semantics of TLSv1.1 and TLSv1.2.

I am just violently opposed to requiring implementations having to send
"ClientHello.client_version" = { 0x03,0x02 } or { 0x03, 0x03 } prior
to using TLSv1.1 or TLSv1.2 protocol features or semantics.
because we know that this causes interop problems with parts of
the installed base and requires the complex, inefficient and
dangerous reconnect fallbacks.

>From a protocol perspective, it is completely irrelevant how both
communication peers negotiate the use of specific protocol features,
and it is more important that we devise a scheme that interops
nicely with the installed base, than maintaining the illusion
of a "clean specification", where in reality implementations will need
complex, inefficient and dangerous reconnect fallback hacks for interop.

-Martin

---

From: [email-masked] (Martin Rex)
Date: Fri, 10 Jan 2014 23:26:31 +0100 (CET)

Sorry, I forgot the reference to the "original characterization[1]" of
the weakness.

-Martin

 [1] Bodo Moeller quoting his 2002 Email response to Wei Dai in
     http://www.openssl.org/~bodo/tls-cbc.txt

    >> Phil Rogaway observed that CBC mode is not secure against chosen-
    >> plaintext attack if the IV is known or can be predicted by the attacker
    >> before he choses his plaintext.

    in which Wei Dai refers to an I-D formatted comment
    of Phil Rogaway on IPSEC from 1995
    http://www.cs.ucdavis.edu/~rogaway/papers/draft-rogaway-ipsec-comments-00.txt