Re: [Cfrg] Fwd: I-D Action: draft-nir-cfrg-chacha20-poly1305-00.txt

Robert Ransom <rransom.8774@gmail.com> Tue, 28 January 2014 14:55 UTC

Return-Path: <rransom.8774@gmail.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 9FF481A008E for <cfrg@ietfa.amsl.com>; Tue, 28 Jan 2014 06:55:42 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.75
X-Spam-Level:
X-Spam-Status: No, score=-1.75 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_ENVFROM_END_DIGIT=0.25, FREEMAIL_FROM=0.001, SPF_PASS=-0.001] autolearn=no
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id aqdY1zzdOEmo for <cfrg@ietfa.amsl.com>; Tue, 28 Jan 2014 06:55:41 -0800 (PST)
Received: from mail-qc0-x235.google.com (mail-qc0-x235.google.com [IPv6:2607:f8b0:400d:c01::235]) by ietfa.amsl.com (Postfix) with ESMTP id AF2001A0227 for <cfrg@irtf.org>; Tue, 28 Jan 2014 06:55:40 -0800 (PST)
Received: by mail-qc0-f181.google.com with SMTP id e9so669997qcy.12 for <cfrg@irtf.org>; Tue, 28 Jan 2014 06:55:38 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type:content-transfer-encoding; bh=olaw8Xc6TcH414boZL8+f1VlhDOiIPfmyuXh67tPbbE=; b=Stvt4fi48uEZgg81MC/0KMU2e0pa2s065H7KBxqCfrcwwcQOCuzyP2qrbeyiys2r0J DZlqt7OocYnMZDb/g7M+BRcSOFY2I4zTk18s1AHT/spwvE5WIp+DvZ2loU00XBzciU7C i/qmkkrlepC9CfoxFFKf2ecoexHITAdJhOrXLQALoeA2QAOED0GC2bm27m3JLkG5puRh hFdQi2rFulOC7a3UgeWdXgf6FK1gV5M1NquHy+PXC92Ci2M3JpYmkwZue/DUCfZqx9Sr m2eGOsBFUa0wyVmXcaN7DkaXiuOsjD3bH6WXM2MsIjUAfArgDqKe9YzHodCp7K2beQoo 9Q1g==
MIME-Version: 1.0
X-Received: by 10.224.129.138 with SMTP id o10mr2984050qas.13.1390920938065; Tue, 28 Jan 2014 06:55:38 -0800 (PST)
Received: by 10.140.86.42 with HTTP; Tue, 28 Jan 2014 06:55:38 -0800 (PST)
In-Reply-To: <07384966-B154-4CF8-9503-3A3ADA6276BE@checkpoint.com>
References: <20140127114546.8921.73181.idtracker@ietfa.amsl.com> <2DD6FE86-A5C6-4144-8778-2DFFCA8AD5F8@checkpoint.com> <CABqy+spVbfA2aGKaEftKrokbdXPZjQB9RDjT2b371H_bPB+NWQ@mail.gmail.com> <07384966-B154-4CF8-9503-3A3ADA6276BE@checkpoint.com>
Date: Tue, 28 Jan 2014 06:55:38 -0800
Message-ID: <CABqy+sp9WthLP0WcqwJN-sUrH2Q9U0vxb=q8Opf0WHJf06i11Q@mail.gmail.com>
From: Robert Ransom <rransom.8774@gmail.com>
To: Yoav Nir <ynir@checkpoint.com>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] Fwd: I-D Action: draft-nir-cfrg-chacha20-poly1305-00.txt
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <http://www.irtf.org/mail-archive/web/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Tue, 28 Jan 2014 14:55:42 -0000

On 1/28/14, Yoav Nir <ynir@checkpoint.com> wrote:
>
> On Jan 28, 2014, at 2:21 AM, Robert Ransom <rransom.8774@gmail.com>
> wrote:

>> Section 4 (‘Security Considerations’) discusses the risk that the
>> Poly1305 key derived from a ChaCha (key, nonce) pair will collide.
>> This is not a risk at all.  Poly1305 keys are supposed to be chosen
>> uniformly at random, and most of the effort of proving Poly1305-AES
>> secure was in bounding the security loss caused by the fact that AES
>> could not produce the same value of s for two different nonces.
>
> AES cannot, and if we took the entire 512-bits from ChaCha, they would not
> repeat either. But with taking only half the bytes, they will repeat much
> sooner. That is why you shouldn't use the first 64 bits of an AES-encrypted
> counter as an IV for 3DES. You'll likely get a collision after 2^32
> messages, and you'll get an unacceptably high chance of collision much
> sooner.
>
> With taking 128 bits for s out of 512, the odds are much better, so they're
> acceptable. That is what the section says.

You missed the point entirely.  The attacker does not benefit from the
repeated use of a Poly1305 key unless he/she/it knows that the key
will be repeated.  Poly1305's security relies on the assumption that
the attacker has no information at all about its keys.

Using an injective function to derive s from a nonce, as in
Poly1305-AES, does give the attacker information about Poly1305's
keys.  Dr. Bernstein's proof that the security loss due to this
information leak is tolerably small, even after 2^64 messages,
justified a paper of its own
(<http://cr.yp.to/antiforgery/permutations-20050323.pdf>).


Robert Ransom