Re: [TLS] Salsa20 and Poly1305 in TLS

Rene Struik <rstruik.ext@gmail.com> Mon, 29 July 2013 21:06 UTC

Return-Path: <rstruik.ext@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 E7ADC21F972C for <tls@ietfa.amsl.com>; Mon, 29 Jul 2013 14:06:23 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.365
X-Spam-Level:
X-Spam-Status: No, score=-2.365 tagged_above=-999 required=5 tests=[AWL=0.234, 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 mma2pjY1at2c for <tls@ietfa.amsl.com>; Mon, 29 Jul 2013 14:06:23 -0700 (PDT)
Received: from mail-qe0-x22c.google.com (mail-qe0-x22c.google.com [IPv6:2607:f8b0:400d:c02::22c]) by ietfa.amsl.com (Postfix) with ESMTP id EBB5521F962D for <tls@ietf.org>; Mon, 29 Jul 2013 14:06:22 -0700 (PDT)
Received: by mail-qe0-f44.google.com with SMTP id 6so2667383qeb.17 for <tls@ietf.org>; Mon, 29 Jul 2013 14:06:22 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=message-id:date:from:user-agent:mime-version:to:cc:subject :references:in-reply-to:content-type:content-transfer-encoding; bh=wH57EUuXSdxaVBdzOwmUx9vppZt6c8C2fkCU3gFhsxs=; b=MXarZKJpsbJI09smBkH5WhAWesl1fPN2D3dgqFHvKu5RgaCiiLGCI7I37xfRNJfnnW Q0PHw1ONbhHxUR4tks8CXToIqKXEPFVVa2rgClGnr5mowS0lxi69KsbKiyiXTCmoEdgg YFSlL8Xn7KIbcNg1nK3WEDydxIy6qQcE9K82aOvHxBNWfV2ch92BuVs/kK/TzKlC2b/a 6qegcsQMIwuDt0Kj4GfqjFZjCIhVeW5dLuax7cRcpRkdnl5L0InqXLcXrG6pkUaFJtjo lxml9OJuJ25B+FVnlX7vSJpbOQBewkdSPu+/TtBysxFFHtIyr7fCzH2oj09PZc2WtC1L 9hdQ==
X-Received: by 10.49.15.130 with SMTP id x2mr74877371qec.47.1375131981670; Mon, 29 Jul 2013 14:06:21 -0700 (PDT)
Received: from [192.168.1.101] (CPE0013100e2c51-CM001cea35caa6.cpe.net.cable.rogers.com. [99.231.4.27]) by mx.google.com with ESMTPSA id t5sm24922690qae.9.2013.07.29.14.06.20 for <multiple recipients> (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Mon, 29 Jul 2013 14:06:20 -0700 (PDT)
Message-ID: <51F6D946.50109@gmail.com>
Date: Mon, 29 Jul 2013 17:06:14 -0400
From: Rene Struik <rstruik.ext@gmail.com>
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:17.0) Gecko/20130620 Thunderbird/17.0.7
MIME-Version: 1.0
To: Adam Langley <agl@google.com>
References: <CAL9PXLySuS1gn8YisobYrbEnNpxJuYPbKB0qtkCOMnb+m90Jjg@mail.gmail.com>
In-Reply-To: <CAL9PXLySuS1gn8YisobYrbEnNpxJuYPbKB0qtkCOMnb+m90Jjg@mail.gmail.com>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Cc: tls@ietf.org
Subject: Re: [TLS] Salsa20 and Poly1305 in TLS
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: Mon, 29 Jul 2013 21:06:24 -0000

Hi Adam:

Let us add (re)tweetability to the requirements for algorithm design! 
While we are at it, let us impose this to all RFCs, technical papers, 
source code, poetry, text books, and our daily news as well.  Well, with 
the latter we are already nearly there...

Darn, now I may have surpassed the tweet limit myself!

Rene

==

Additionally, Poly1305 can be written in a tweet(*), while UMAC is
dramatically more complex.



On 7/29/2013 3:09 PM, Adam Langley wrote:
> I cannot make it to Berlin I'm afraid (or, indeed, any meetings until
> at least IETF 91) so I'm writing my thoughts on
> draft-josefsson-salsa20-tls-02, which is scheduled for discussion.
>
> We (Google) support the addition of Salsa20 as a cipher in TLS. Having
> a secure cipher which is fast and constant time on all platforms is
> important. It's also good to have an alternative to AES in the wings
> should that be needed in the future. At the moment I consider RC4 and
> AES-CBC to be mortally wounded, even if we have to continue supporting
> them for many years yet.
>
> Salsa20/12 is something that we are currently working on supporting.
>
> However, I believe that Poly1305 is superior to UMAC and we're looking
> at Salsa20/12+Poly1305, not UMAC. (Note: that's Poly1305 with the
> nonce generated directly by Salsa20/12, not via AES.)
>
> (For the following, I used UMAC in nettle 2.7 and Andrew M's
> implementation of Poly1305[1], both on a E5-2690@2.90GHz with
> Hyperthreading and Turboboost disabled.)
>
> UMAC96 (with AES for the nonce generation) takes 9146.1ns to
> authenticate 1K of data, HMAC-SHA1(1K) takes 3667ns and Poly1305 takes
> 561.4ns.
>
> However, that's not the whole story for UMAC because it can use 1.5KB
> of memory for precomputation, after which it can authenticate 1KB of
> memory in just 329ns with that in L1. That's typically the headline
> speed that's advertised.
>
> However, I consider cache pressure to be a way of cheating on
> benchmarks :) Benchmarks don't show cache pressure until the algorithm
> itself spills the L1 cache but, in a real system, cache costs.
>
> With the precomputed data only in L3 cache (tested by cycling through
> 10,000 contexts), UMAC takes 922.16ns to authenticate 1KB.
>
> So UMAC may give a small benefit to cases with few, busy connections,
> but it's a loss in the case where there are many connections (a
> server), or a few connections, intermittently used (i.e. a web
> browser).
>
> Additionally, Poly1305 can be written in a tweet(*), while UMAC is
> dramatically more complex. Since they are both Wegman-Carter style
> hashes I believe that they both have, fundamentally, well understood
> security properties. (See [2] for a good overview.)
>
> Thus Poly1305 is looking much more attractive to us.
>
>
> (* Here's an attempt in 159 chars: "Take msg in 16 byte chunks. Append
> 1 to each msg chunk&0-pad to 17 bytes. Interpt little-endian. Calc
> polynom in key[:16] mod 2^130-5. Add key[:16]. Mod 2^128.")
>
> [1] https://github.com/floodyberry/poly1305-donna
> [2] http://eprint.iacr.org/2013/144.pdf
>
>
> Cheers
>
> AGL
> _______________________________________________
> TLS mailing list
> TLS@ietf.org
> https://www.ietf.org/mailman/listinfo/tls


-- 
email: rstruik.ext@gmail.com | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 690-7363