[TLS] Encrypt-then-HMAC is the only credible choice. Here's why:

Marsh Ray <maray@microsoft.com> Thu, 14 November 2013 21:00 UTC

Return-Path: <maray@microsoft.com>
X-Original-To: tls@ietfa.amsl.com
Delivered-To: tls@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 2343911E8162 for <tls@ietfa.amsl.com>; Thu, 14 Nov 2013 13:00:38 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.398
X-Spam-Level:
X-Spam-Status: No, score=-2.398 tagged_above=-999 required=5 tests=[BAYES_00=-2.599, HTML_MESSAGE=0.001, J_CHICKENPOX_36=0.6, J_CHICKENPOX_46=0.6, RCVD_IN_DNSWL_LOW=-1]
Received: from mail.ietf.org ([12.22.58.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id Is2paLao5Bun for <tls@ietfa.amsl.com>; Thu, 14 Nov 2013 13:00:32 -0800 (PST)
Received: from na01-by2-obe.outbound.protection.outlook.com (mail-by2lp0241.outbound.protection.outlook.com [207.46.163.241]) by ietfa.amsl.com (Postfix) with ESMTP id 4562011E80FA for <tls@ietf.org>; Thu, 14 Nov 2013 13:00:28 -0800 (PST)
Received: from BY2PR03MB074.namprd03.prod.outlook.com (10.255.241.154) by BY2PR03MB075.namprd03.prod.outlook.com (10.255.241.155) with Microsoft SMTP Server (TLS) id 15.0.820.5; Thu, 14 Nov 2013 21:00:25 +0000
Received: from BY2PR03MB074.namprd03.prod.outlook.com ([169.254.12.17]) by BY2PR03MB074.namprd03.prod.outlook.com ([169.254.12.17]) with mapi id 15.00.0820.005; Thu, 14 Nov 2013 21:00:25 +0000
From: Marsh Ray <maray@microsoft.com>
To: "tls@ietf.org" <tls@ietf.org>
Thread-Topic: Encrypt-then-HMAC is the only credible choice. Here's why:
Thread-Index: Ac7he9XegiaaCPP0QGGxMFjRjJVXTg==
Date: Thu, 14 Nov 2013 21:00:25 +0000
Message-ID: <c8943847aecd44c29540bd198794746b@BY2PR03MB074.namprd03.prod.outlook.com>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
x-originating-ip: [2001:4898:80e8:ee31::2]
x-forefront-prvs: 0030839EEE
x-forefront-antispam-report: SFV:NSPM; SFS:(52604005)(199002)(189002)(81342001)(2656002)(51856001)(87936001)(33646001)(87266001)(81542001)(74706001)(59766001)(74876001)(19580395003)(83322001)(54356001)(80976001)(53806001)(77982001)(19609705001)(15202345003)(85306002)(15975445006)(65816001)(76482001)(49866001)(63696002)(80022001)(83072001)(47446002)(79102001)(16236675002)(19300405004)(56776001)(74366001)(81816001)(31966008)(74502001)(4396001)(81686001)(47976001)(47736001)(74662001)(76176001)(69226001)(50986001)(54316002)(46102001)(77096001)(56816003)(76796001)(76786001)(76576001)(74316001)(3826001)(24736002); DIR:OUT; SFP:; SCL:1; SRVR:BY2PR03MB075; H:BY2PR03MB074.namprd03.prod.outlook.com; CLIP:2001:4898:80e8:ee31::2; FPR:; RD:InfoNoRecords; A:1; MX:1; LANG:en;
Content-Type: multipart/alternative; boundary="_000_c8943847aecd44c29540bd198794746bBY2PR03MB074namprd03pro_"
MIME-Version: 1.0
X-OriginatorOrg: microsoft.com
Subject: [TLS] Encrypt-then-HMAC is the only credible choice. Here's why:
X-BeenThere: tls@ietf.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: "This is the mailing list for the Transport Layer Security working group of the IETF." <tls.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/tls>, <mailto:tls-request@ietf.org?subject=unsubscribe>
List-Archive: <http://www.ietf.org/mail-archive/web/tls>
List-Post: <mailto:tls@ietf.org>
List-Help: <mailto:tls-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/tls>, <mailto:tls-request@ietf.org?subject=subscribe>
X-List-Received-Date: Thu, 14 Nov 2013 21:00:38 -0000

Our knowledge of generic hashing constructions has evolved:

A.      Standard constructions

B.      Length extension attacks

C.      Joux multicollisions/"2nd preimages for less work"

D.      Chosen-Target Forced-Prefix (Nostradamus, RapidSSL, Flame)

E.       Sponge constructions

Attacks against specific hashes (MD4, MD5, SHA-0, SHA-1, SHA-2) tend to unfold in sequence:

1.       Reduced round collisions demonstrated (depends on reduction)

2.       Absurdly impractical multicollision and/or collision weakness theorized

3.       Plausible multicollision and/or collision weakness theorized

4.       Full collision demonstrated

5.       CTFP demonstrated

6.       2nd preimage theorized

7.       2nd preimage attack demonstrated

8.       Primary preimage attacks demonstrated

The last I heard:
MD4 is at stage 6
MD5 is at stage 5
SHA-0 was withdrawn at stage 3 or 4
SHA-1 is at stage 3
SHA-2 is at stage 2

Now let's talk about HMAC.

HMAC uses a double invocation of the full hash function each of which is initialized with a secret key. There's some pretty well respected proven properties on the security of HMAC. For example, assuming the key is actually secret from the attacker, you generally don't need to worry about collision attacks. The resulting MAC value or tag can be truncated and yet it still retains min(secret key bits, tag bits) security.

In TLS, the secret key is generated by the TLS PRF. The TLS PRF is one of the most conservative parts of the design of TLS. It itself uses HMAC recursively. IIRC, to produce one block of PRF output takes something like 4 invocations of the underlying hash's block function. It functions much like a slow, conservative block cipher with 512+160 bits of key and secret plaintext input (512+1024 for SHA-2-384 and -512).

So the concern (C) has been raised that an attacker who may know some plaintext, and sees one or more samples of ciphertext, and the non-truncated MAC tag around this ciphertext, may then be able to "reach back through" the HMAC to obtain the MAC key. This would enable him to forge ciphertext, which would enable him to and flip various bits decrypted plaintext bits. (Of course the current design allows anyone to do this today it's just that the later MAC will detect it so it becomes a game of oracle testing).

Additionally, the concern (D) is raised that an attacker who completely succeeds with (C) may then be able to "reach back through" several additional layers of HMAC in the TLS PRF in order to derive one or both of the cipher keys allowing full decryption of the protocol stream.

To be clear, I say "reach back through" because I don't think there is actually a name for this attack model. Even if we were just talking about a hash function instead of HMAC, this is an attack capability *beyond* primary preimage. Primary preimage is "given h(M), find M' such that h(M') = h(M)", whereas this attack is: "given h(M), find M"!

In other words, the attacker doesn't get to control the message input. Such a feat has never been openly proposed in the literature (that I've seen on hash functions), not even theorized, not even for MD4.

But again, our scenario (C) is not the use of plain hash functions. We're talking about attacking the use of HMAC<Hfn>(k, msg) to recover the secret key bits of input. This is yet another step removed from "unthinkable".

In the case where that the secret key length is the same as the MAC length, there's even about a coin toss chance there will be two or more keys that yield the target hash MAC. When the MAC is truncated, there are exponentially more.

But again, for the concern (D), we're talking about accomplishing (C) and then continuing on to attack the TLS PRF through several cascaded HMAC<Hfn>(k, msg) to recover the secret key bits of input. This is yet another step removed from "unthinkable".

My conclusion is that for any reasonable choice of hash function, the TLS PRF is noninvertible. To put this another way, if this feat were demonstrated even using the horribly broken MD5 it would be earth-shattering in its crypto impact. It is secure forever, unless there are seriously fundamental advances in complexity-theoretic cryptanalysis. And if that day comes, *it will be your fast ciphers that you'll worry about*. The TLS PRF is by far the slowest, most conservatively designed stream cipher in common use.

I would never say something is "impossible" in cryptanalysis. We should always be vigilant and paranoid. But the key to being *constructively paranoid* is to worry about the *right* thing. The security of HMAC<modern hash>(secret k, message) is *not* the right to worry about.

The thing to worry about is block cipher modes' propensity to turn into plaintext oracles. This has been demonstrated as a practical attack on over and over again.

*** RECOMMENDATIONS ***

* Put TLS PRF and HMAC security way, way down if not last on the list of things likely to negatively affect security.

For all future TLS cipher suites and TLS 1.3 in general is:

* Use encrypt-then-HMAC. Seriously. Yes really. No other choice is defensible in this age. If you think "oh but GCM" look more closely into its design.

* Use the NIST-specified truncation SHA-2-512/256 for the HMAC hash function.
* Don't truncate the TLS record MAC in an attempt to protect the master secret (as in the Finished message). Even if such an attack were practical, the attacker sees many samples of the MAC any way.

* Do truncate the TLS record MAC to 128 bits because anything more is an indefensible waste of bandwidth.

* Don't panic.

Thanks for reading this far. I'm fallible. TIA for details, factual corrections, and flames. These are my own personal opinions and not necessarily those of my employer.


-          Marsh