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

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

+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" <[e-mail]> wrote:

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