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

From: Marsh Ray <[email-masked]>
Date: Thu, 14 Nov 2013 21:00:25 +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

---

From: "Paterson, Kenny" <[email-masked]>
Date: Thu, 14 Nov 2013 23:07:04 +0000

+1 to almost everything in this post.

Let's now move on to discussing the substantive issues, keeping in the
forefront of our minds Marsh's wonderful phrasing:

"We should always be vigilant and paranoid. But the key to being
*constructively paranoid* is to worry about the *right* thing."

Kenny

On 14/11/2013 21:00, "Marsh Ray" <[email-masked]> wrote:

>A.     
>Standard constructions
>C.     
>Joux multicollisions/²2nd preimages for less work²
>D.     
>Chosen-Target Forced-Prefix (Nostradamus, RapidSSL, Flame)
>E.      
>Sponge constructions
> 
>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.      
>5.      
>CTFP demonstrated
>6.      
>2nd preimage theorized
>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.
> 
>* 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.
> 
>* 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.
> 
>* 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
> 
>

---

From: "Blumenthal, Uri - 0558 - MITLL" <[email-masked]>
Date: Thu, 14 Nov 2013 18:18:23 -0500

+1

--
Regards,
Uri Blumenthal                            Voice: (781) 981-1638
Cyber Systems and Technology   Fax:   (781) 981-0186
MIT Lincoln Laboratory                Cell:  (339) 223-5363
244 Wood Street                        Email: <[email-masked]>
Lexington, MA  02420-9185       

Web:  http://www.ll.mit.edu/CST/

MIT LL Root CA: 

 <https://www.ll.mit.edu/labcertificateauthority.html>

DSN:   478-5980 ask Lincoln ext.1638

----- Original Message -----
From: Paterson, Kenny [mailto:[email-masked]]
Sent: Thursday, November 14, 2013 06:07 PM
To: Marsh Ray <[email-masked]>; [email-masked] <[email-masked]>
Subject: Re: [TLS] Encrypt-then-HMAC is the only credible choice. Here's why:

Kenny

>corrections, and flames. These are my own personal opinions and not

_______________________________________________
TLS mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/tls

---

From: Tom Ritter <[email-masked]>
Date: Fri, 15 Nov 2013 09:11:54 -0500

+1

-tom

---

From: Nikos Mavrogiannopoulos <[email-masked]>
Date: Fri, 15 Nov 2013 16:24:21 +0100

> Our knowledge of generic hashing constructions has evolved:
[...]
> 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.

Hello,
 These are interesting facts and I don't think anyone denied them in
this list. The fact however that EtA is ok, doesn't imply that AtE is
not ok. The only stream cipher in TLS had never issues due to the mode
of encryption (AtE). Why switch it to EtA when we know the issue and
can fix (fix and not hack) the currently used mode?

In any case that is argumentation for the sake of argumentation. Now
we are full of hacks solving the issue and what we need is some action
on this topic.

regards,
Nikos

---

From: Robert Ransom <[email-masked]>
Date: Fri, 15 Nov 2013 11:42:51 -0800

On 11/14/13, Marsh Ray <[email-masked]> wrote:

> initialized with a secret key. There's some pretty well respected proven
> properties on the security of HMAC.

Are these properties proved for all iterative hash functions, or only
for hash functions with the same general structure (block cipher in
feedforward mode) as MD5 and the pre-SHA-3 NSA hash functions?

> 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"!

I call that a “preimage recovery attack”.  I don't think that name is
standard, but it is an accurate description of the attack.

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

This is the most important point, and it's already being ignored (again).

> defensible in this age. If you think "oh but GCM" look more closely into its
> design.

There are plenty of other defensible choices for a MAC.

GCM has some bad design features, but its MAC is the good part (at
least for implementations with hardware support for multiplication in
GF(2)[X]).

Poly1305 (as used in draft-agl-chacha20-poly1305-03) is faster than
HMAC, and almost as secure.

SipHash is faster than Poly1305, and as secure as an HMAC truncated to
64 bits.  I don't expect it to be used in TLS, but it's certainly good
enough for voice communication protocols over UDP.

With a good hash function (one which does not permit the
length-extension attack), such as any of the SHA-3 finalists, H(k, m)
is a good MAC.

Robert Ransom

---

From: Marsh Ray <[email-masked]>
Date: Fri, 15 Nov 2013 22:44:21 +0000

From: Robert Ransom [mailto:[email-masked]]
Sent: Friday, November 15, 2013 11:43 AM
> > 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.
> 
> Are these properties proved for all iterative hash functions, or only for hash
> functions with the same general structure (block cipher in feedforward
> mode) as MD5 and the pre-SHA-3 NSA hash functions?

One would certainly hope the properties would still hold when used with actual hash functions which differ from an ideal hash function in a subset of ways.

ISTR one of the original NIST requirements for SHA-3 was that it be compatible with existing constructions like HMAC. On the other hand, NIST seemed to feel that some of the other original requirements were still negotiable (e.g., preimage resistance of two times collision resistance).

NIST suggests they will standardize a specific MAC mode for SHA-3. I haven't heard anything to suggest this provides any security advantage over HMAC, just a little more performance for short messages.

> I call that a “preimage recovery attack”.  I don't think that name is standard,
> but it is an accurate description of the attack.

Intuitively that makes sense as a descriptive term.

But I find for myself that having such an attractive term around is a dangerous temptation!

My search engine turns up only one hit for the term:
http://crypto.stackexchange.com/questions/5589/speeding-up-partially-known-plaintext-preimage-recovery-attack-on-md5

I think it's a reasonable question and the asker gets a good answer, but I would much rather see it defined a bit more formally. It probably has been somewhere.

> There are plenty of other defensible choices for a MAC.

Yeah, I didn't mean to imply so much that HMAC is the One True MAC or that integrated AE modes can never be defensible. Just that MAC-(then|and)-Encrypt are broken while Encrypt-then-HMAC is a very conservative design which has stood the test of time and emerged victorious.

See: https://twitter.com/elwoz/status/401135814307889152
Figure 2 from http://eprint.iacr.org/2000/025

> GCM has some bad design features, but its MAC is the good part (at least for
> implementations with hardware support for multiplication in GF(2)[X]).

What *doesn't* look good if we restrict our discussion to configurations which have explicit hardware support?

Wait...I'll answer that: RC4 :-)
 
> With a good hash function (one which does not permit the length-extension
> attack), such as any of the SHA-3 finalists, H(k, m) is a good MAC.

What if (as in the TLS handshake) m itself was used to negotiate the length of k?

- Marsh
Usual disclaimers apply.

---

From: Bodo Moeller <[email-masked]>
Date: Mon, 18 Nov 2013 18:08:22 +0100

>
> Yeah, I didn't mean to imply so much that HMAC is the One True MAC or that
> integrated AE modes can never be defensible. Just that
> MAC-(then|and)-Encrypt are broken while Encrypt-then-HMAC is a very
> conservative design which has stood the test of time and emerged victorious.

> Figure 2 from http://eprint.iacr.org/2000/025
While you are right, http://eprint.iacr.org/2000/025 alone isn't why MtE is
broken (and https://twitter.com/marshray/status/401147046767239169/photo/1thus
is a gross over-simplification -- not that there's anything wrong with
that, per se ...).

That Bellare/Namprempre paper did show that MtE is not *generically*
secure.  However, there's also http://eprint.iacr.org/2001/045 =
http://www.iacr.org/archive/crypto2001/21390309.pdf, showing (sort of) that
MtE *is* secure if E specifically is, for example, CBC encryption.  Well,
we all know how well *that* went [*][**] ... but the various problems with
CBC ciphersuites are not implied by the Bellare/Namprempre paper.

[*] See Paterson/Watson, "Authenticated-Encryption with Padding: A Formal
Security Treatment", 2011, for a more complete truth.  That article is
behind a paywall, but Kenny conveniently provided this pointer to Gaven's
thesis: http://www.isg.rhul.ac.uk/~kp/theses/GWthesis.pdf

[**] I must have my hand-written slides somewhere ...
http://www.iacr.org/conferences/crypto2002/rump-prog.html

Bodo

---

From: Marsh Ray <[email-masked]>
Date: Tue, 19 Nov 2013 05:15:14 +0000

From: Bodo Moeller
> 
> While you are right, http://eprint.iacr.org/2000/025 alone
> isn't why MtE is broken (and https://twitter.com/marshray/status/401147046767239169/photo/1
> thus is a gross over-simplification -- not that there's anything
> wrong with that, per se ...).

Gross over-simplification tends to be what Twitter's best at.

AES-GCM good! RC4 bad! :-)

> That Bellare/Namprempre paper did show that MtE is not
> *generically* secure.  However, there's also
> http://eprint.iacr.org/2001/045 =
> http://www.iacr.org/archive/crypto2001/21390309.pdf , showing
> (sort of) that MtE *is* secure if E specifically is, for example,
> CBC encryption.  Well, we all know how well *that* went [*][**]
> ... but the various problems with CBC ciphersuites are not implied
> by the Bellare/Namprempre paper.

I feel the world of end users, admins, and other RPs shaking their
collective heads in wonder at these security proofs when they see
a giant flame-shooting robot at a party in Argentina:

http://www.youtube.com/watch?v=Mxm8JEUXOuQ

... then the presenter proceeds to decrypt traffic to a tier 1
ecommerce website ...

http://www.youtube.com/watch?v=4clpbJEWCzE

... and steal the login session cookie using attacks enabled
by CBC A-t-E mode.

All I can figure is that proving A-[at]-E CBC modes are
secure is cryptographers' equivalent of what (Down South where
I come from) we refer to as "Hey Y'all watch this!" E.g.,

http://www.youtube.com/results?search_query=hey+y%27all+watch+this

We have a long, sad, bibliography of *practical* attacks on A-[at]-E,
especially in conjunction with CBC modes. Bellovin, Rogaway, Wei
Dei, Vaudenay (many I missed) . IPsec, SSH, SSL, TLS .
all broken to various degrees. Too many operations where
attacker-supplied data interacts with must-be-kept-secret data.
Straightforward implementations result in side channels. Minor
info leaks turn into oracles. Oracles turn into practical attacks.

Has there ever been a serious attack on HMAC<hashfn> ?

Here's what I found for HMAC<MD4>

Practical Electromagnetic Template Attack on HMAC
by Pierre-alain Fouque, Gaëtan Leurent, Denis Réal, Frédéric Valette
(2007?)
> In this paper, we show a very efficient side channel attack against
> HMAC. Our attack assumes the presence of a side channel that
> reveals the Hamming distance of some registers
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.156.4969

But wait, HMAC<MD4> is worse. Again, *MD4*. IIRC TLS has only
ever supported HMAC<MD5> and later.

Full Key-Recovery Attacks on. HMAC/NMAC-MD4 and NMAC-MD5.
Pierre-Alain Fouque, Gaëtan Leurent, Phong Q. Nguyen.
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.98.7316
http://www.di.ens.fr/~fouque/pub/crypto07b.pdf

So if, say, TLS had supported HMAC<MD4> and the adversary had
the ability to make 2^88 record integrity queries, then with
2^95 time he could possibly (in 2007) insert a forged record
in that connection. But he'd better be careful, because if
he breaks it he'll have to start all over.

This technique seems unlikely to be of any use attacking the TLS PRF
"back through" the record MAC, because the PRF operates upon
completely new data with every handshake.

But it looks like SSLv2 used a bare hash rather than HMAC and even had
an option for MD2! Still, it would likely have been the 512 bit RSA certs
that were the weakest link.

Regards,

- Marsh

Unless stated otherwise, these are my own personal opinions.

---

From: Bodo Moeller <[email-masked]>
Date: Tue, 19 Nov 2013 10:36:40 +0100

Marsh, as I said, you *are* right [*], it's just that there's a lot more to
it than Bellare/Namprempre (which doesn't consider side-channel attacks,
for example).

[*] Another gross over-simplification :-)