Re: [TLS] padding bug

Nikos Mavrogiannopoulos <nmav@gnutls.org> Tue, 24 September 2013 11:26 UTC

Return-Path: <n.mavrogiannopoulos@gmail.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 EB6A411E810B for <tls@ietfa.amsl.com>; Tue, 24 Sep 2013 04:26:27 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.472
X-Spam-Level:
X-Spam-Status: No, score=-2.472 tagged_above=-999 required=5 tests=[AWL=0.127, BAYES_00=-2.599]
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 n-ibziSdc1B9 for <tls@ietfa.amsl.com>; Tue, 24 Sep 2013 04:26:27 -0700 (PDT)
Received: from mail-ea0-x236.google.com (mail-ea0-x236.google.com [IPv6:2a00:1450:4013:c01::236]) by ietfa.amsl.com (Postfix) with ESMTP id A6B5611E8104 for <tls@ietf.org>; Tue, 24 Sep 2013 04:26:26 -0700 (PDT)
Received: by mail-ea0-f182.google.com with SMTP id o10so2369146eaj.41 for <tls@ietf.org>; Tue, 24 Sep 2013 04:26:25 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=sender:message-id:date:from:user-agent:mime-version:to:cc:subject :references:in-reply-to:openpgp:content-type :content-transfer-encoding; bh=C7wYRjehCtr8HVro3v9OrlABrDh7A8qqOg//7pDwi/I=; b=rpVWTV0pXYgeV/9wfvyVJBQ0FkJPPeQso+qeweYdW4KQNwOYen0x/ij2jjFt8CFBMb 4vtRyb0v5EPYAjdydD0Gz5Gle3lWy0AgIVruR1vj/WATs4GPgmFi2MCI5pp266u1Q5CI +YESTIXN/MAPzcUml3M++c6bM5Tz2llIrXPaKCV4MBdCAxb3BmhVHUWj/bCE4kbcnE4n V8iSzsvs4NBEFjnAK8p0OH4Zb34N8SpHb4Uszb9XsjYaMzz42DrdhwO+7dfJIfC13nuQ SQrLFG5h5LzKTRYM5/J75DRcaqOy1O7mVwrjVLEqPk6lN5gQwzPpmMppzHPwmlh6/0NF guqQ==
X-Received: by 10.15.76.68 with SMTP id m44mr2039123eey.78.1380021985712; Tue, 24 Sep 2013 04:26:25 -0700 (PDT)
Received: from [10.100.2.17] (94-224-103-174.access.telenet.be. [94.224.103.174]) by mx.google.com with ESMTPSA id d8sm52223106eeh.8.1969.12.31.16.00.00 (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Tue, 24 Sep 2013 04:26:25 -0700 (PDT)
Sender: Nikos Mavrogiannopoulos <n.mavrogiannopoulos@gmail.com>
Message-ID: <524176EA.3090401@gnutls.org>
Date: Tue, 24 Sep 2013 13:26:34 +0200
From: Nikos Mavrogiannopoulos <nmav@gnutls.org>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:17.0) Gecko/20130630 Icedove/17.0.7
MIME-Version: 1.0
To: Ben Laurie <benl@google.com>
References: <9A043F3CF02CD34C8E74AC1594475C73556760EA@uxcn10-6.UoA.auckland.ac.nz> <524148C3.7090709@gnutls.org> <CABrd9SRHheYhNjcbKosaEASfJ6EvZtN93HaLG=Cvzn_1ohKFgw@mail.gmail.com>
In-Reply-To: <CABrd9SRHheYhNjcbKosaEASfJ6EvZtN93HaLG=Cvzn_1ohKFgw@mail.gmail.com>
X-Enigmail-Version: 1.5.1
OpenPGP: id=96865171
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Cc: "tls@ietf.org" <tls@ietf.org>
Subject: Re: [TLS] padding bug
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: Tue, 24 Sep 2013 11:26:28 -0000

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

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 <bart.preneel@esat.kuleuven.be>
To: Nikos Mavrogiannopoulos <nmav@gnutls.org>

> 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