Subject: Re: [TLS] padding bug

From: Peter Gutmann <[email-masked]>
Date: Tue, 24 Sep 2013 05:17:14 +0000

Just a small amount of Schadenfreude here when I point out that as I was
reading through the long list of GnuTLS security advisories at
http://www.gnutls.org/security.html it seems that a number of them would have
been avoided through the use of the EtM that Nikos has been so strongly
opposed to :-).

Peter.

---

From: Nikos Mavrogiannopoulos <[email-masked]>
Date: Tue, 24 Sep 2013 10:09:39 +0200

> been avoided through the use of the EtM that Nikos has been so strongly

I don't understand what does this prove. I was one of the first to ask
for a solution to the issue. Pointing an issue in your draft doesn't
mean I'm against solving the problem.

regards,
Nikos

---

From: Ben Laurie <[email-masked]>
Date: Tue, 24 Sep 2013 11:24:18 +0100

> mean I'm against solving the problem.

The issue you claim is that it does not defend against key recovery
attacks. I am not aware of any key recovery attacks against HMAC, and
MAC truncation was not proposed as a countermeasure for a key recovery
attack against any MAC.

Can you provide a reference for your claim?

---

From: Nikos Mavrogiannopoulos <[email-masked]>
Date: Tue, 24 Sep 2013 13:26:34 +0200

On 09/24/2013 12:24 PM, Ben Laurie wrote:

>>> Just a small amount of Schadenfreude here when I point out that 
>>> as I was reading through the long list of GnuTLS security 
>>> advisories at http://www.gnutls.org/security.html it seems that a
>>> number of them would have been avoided through the use of the EtM
>>> that Nikos has been so strongly opposed to :-).
>> 
>> I don't understand what does this prove. I was one of the first to
>>  ask for a solution to the issue. Pointing an issue in your draft 
>> doesn't mean I'm against solving the problem.
> 
> attacks. I am not aware of any key recovery attacks against HMAC,
> and MAC truncation was not proposed as a countermeasure for a key 
> recovery attack against any MAC.

Hello Ben,
 I believe it would be better to consult the opinion of an expert on
hash functions and MAC designs. The fact that you (or me for that
matter) don't know something doesn't mean much.

> Can you provide a reference for your claim?

I believe we make circles. I previously referenced IPSec (RFC2104) at:
http://www.ietf.org/mail-archive/web/tls/current/msg09832.html
The same RFC references the Preneel-van-Oorschot paper.

I take your question that you actually read RFC2104 and the
Preneel-van-Oorschot paper and you disagree with their points?

PS. I attach the comment of Bart Preneel on the topic (a cryptographer
with significant expertise on hash functions).

regards,
Nikos

-------- Original Message --------
Subject: Re: truncation of MACs
Date: Tue, 24 Sep 2013 10:51:37 +0200 (CEST)
From: Bart Preneel <[email-masked]>
To: Nikos Mavrogiannopoulos <[email-masked]>

> As I am not familiar with new trends in MACs may I ask you whether 
> this practice of truncation is still believed to provide benefits?

Nikos,
I hope all is well.

There is a tradeoff: if you output more bits, it becomes
harder to predict the whole string (that is, to forge the MAC)
On the other hand, you release more information about the
internal state, hence attacks based on internal collisions
as discussed in the Crypto '95 paper with Paul van Oorschot
becomes more efficient - in some sense you expose more information
about the secret key.

If we look at the attacks during the last 18 years, it is
clear that no (forgery) attack has found that exploits the
fact that a subset of bits of say HMAC-MD5 is easier to predict
than any other subset or that exploits truncation (except for
a reduced guessing cost). On the other hand, several (key recovery)
attacks on MAC algorithms (including HMAC-MD4 and HMAC-MD5)
have been found based on internal collisions. These attacks
would become more difficult if fewer output bits are available.

I am in general more concerned about key recovery attacks (allowing
an unlimited number of forgeries) than about forgery attacks.

My conclusion is that my intuition as cryptanalyst was correct
and that it would be best to shorten the output of a MAC
algorithm to half the internal state.

Note that many strong designs in the SHA-3 competition are
wide-pipe, which means that the internal state is larger than
the output; this is to preclude multi-collision attacks,
long message second preimage attacks, and herding attacks on
hash functions (these are attacks on hash functions discovered
between 1999 and 2005 that exploit the fact that the output size
is equal to the internal state). There is some solid theory
underpinning these design choices.
Part of the current controversy on the NIST planned draft
for SHA-3 (FIPS 202) is that the Keccak design was wide-pipe
while the planned draft will reduce the internal state to increase
performance.

While hash functions are not exactly the same as MAC algorithms, I
believe that these developments in hash functions go along the
same lines as our recommendations from 1995:
  - new attacks are discovered that exploit the fact that the
    size of the output is equal to the size of the internal state
  - the response is to make designs with internal state equal to
    twice the output state.

I hope that this helps.

Regards,
Bart

---

From: Ben Laurie <[email-masked]>
Date: Tue, 24 Sep 2013 12:40:39 +0100

> matter) don't know something doesn't mean much.

I have consulted experts. This is why I am puzzled by the objection.

> Preneel-van-Oorschot paper and you disagree with their points?

Actually, I did, and I don't disagree with their points, but I
disagree with _your_ points.

a) The paper describes a collision attack, not a key recovery attack.

b) Step one of the attack is "find a collision". Since that is
impractical, even for (untruncated) HMAC-MD5, hash truncation provides
no useful defence against the attack.

c) In any case, the whole point of the truncation defence is to make
it harder to go from _observing_ a colliding MAC to the ability to
construct more collisions. But it mostly does this by making it easier
to observe MAC collisions.

d) If you _really_ want to defend against this attack, the right
answer is to design hash functions with bigger internal state.

> with significant expertise on hash functions).

In which he says he was right for the wrong reasons. So, you need to
reference the right papers (i.e. the ones that describe key recovery
attacks) so we can evaluate the severity of these attacks. I am not
aware of any even vaguely practical attacks against even HMAC-MD5, let
alone any HMAC we're actually contemplating.

Please present your evidence.

(Incidentally, he also agrees that the right answer is to have larger
internal state, not to truncate. SHA-3 gives us this, right?).

---

From: Nikos Mavrogiannopoulos <[email-masked]>
Date: Tue, 24 Sep 2013 14:17:48 +0200

> disagree with _your_ points.

I am confused now. My point was to truncate the MAC and this is what
RFC2104 and the paper argues for. What do you actually disagree with?

> Please present your evidence.

Since you are the one claiming that MAC truncation isn't necessary when
all existing protocols do it (even TLS does it on the Finished message
MAC), it may be better for you to present evidence that this isn't
necessary. Just add a paragraph in the Security considerations of the
existing draft. That would be sufficient for me.

> internal state, not to truncate. SHA-3 gives us this, right?).

I agree, but the discussion was about converting the old ciphersuites
that use HMAC-MD5 and HMAC-SHA1. There is no HMAC-SHA3 (in TLS or
anywhere else).

regards,
Nikos

---

From: Bodo Moeller <[email-masked]>
Date: Tue, 24 Sep 2013 16:28:40 +0200

> to observe MAC collisions.

I think this reasoning is not quite right because that attack requires
*internal* collisions (and the internal state wouldn't be truncated).  Of
course, it's not an attack on HMAC.

> answer is to design hash functions with bigger internal state.

Exactly. Given a particular l-bit MAC with an l-bit internal state,
truncating its outputs (such as to l/2 bits) isn't demonstrably an
improvement.  Rather, if we want an l-bit MAC, it makes sense to have an
internal state larger than l bits.

Nikos, you pointed to RFC 2104. The following is a literal quote from that
RFC: "The results in this area are not absolute as for the overall security
advantages of truncation."  In particular, encrypt-then-MAC with
untruncated MACs isn't a broken design.  (Assuming hypothetically there's a
key recovery attack on the MAC alone, the encryption step means that the
attacker can't pick MAC inputs after all.)

Bodo

---

From: Ben Laurie <[email-masked]>
Date: Tue, 24 Sep 2013 17:03:55 +0100

On 24 September 2013 15:28, Bodo Moeller <[email-masked]> wrote:
> *internal* collisions (and the internal state wouldn't be truncated).

That's what makes it harder :-)

>  Of
> advantages of truncation."  In particular, encrypt-then-MAC with untruncated
> MACs isn't a broken design.  (Assuming hypothetically there's a key recovery
> attack on the MAC alone, the encryption step means that the attacker can't
> pick MAC inputs after all.)
>
> Bodo
>