[Cfrg] questions on performance and side channel resistance for ChaCha20 and Poly1305 for IPsec and TLS

David McGrew <mcgrew@cisco.com> Thu, 23 January 2014 14:54 UTC

Return-Path: <mcgrew@cisco.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 B85A61A03ED for <cfrg@ietfa.amsl.com>; Thu, 23 Jan 2014 06:54:28 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -10.036
X-Spam-Level:
X-Spam-Status: No, score=-10.036 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, RP_MATCHES_RCVD=-0.535, SPF_PASS=-0.001, USER_IN_DEF_DKIM_WL=-7.5] autolearn=ham
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 tegd5Pz_NjK0 for <cfrg@ietfa.amsl.com>; Thu, 23 Jan 2014 06:54:25 -0800 (PST)
Received: from aer-iport-1.cisco.com (aer-iport-1.cisco.com [173.38.203.51]) by ietfa.amsl.com (Postfix) with ESMTP id 076CC1A00D3 for <cfrg@irtf.org>; Thu, 23 Jan 2014 06:54:24 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=cisco.com; i=@cisco.com; l=4460; q=dns/txt; s=iport; t=1390488864; x=1391698464; h=message-id:date:from:mime-version:to:cc:subject: references:in-reply-to:content-transfer-encoding; bh=jMgNnBvTYnOapUVd2fUPczotj8ZlzX6FwjCVVnZPd3c=; b=L4Svwr/0vWnLn6k4aAycTKoqeDg3auqXbt/WaEBzUtUzu9sdacMte8Tw lvVl0IakgtZCmP61xm1Y0zEbO/0prXcj3nXPSm3JAjUbq8NwxaODFOfms 8m7kTIPSDI59j1OIf+gSJp2wKkL5QtSvM97kQbMI3WBhXIfzE4H0uanfM w=;
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: AgsFANss4VKQ/khN/2dsb2JhbABbgwyEDLh1gRAWdIIlAQEBBCMVQRAZCgICBSECAg8CRgYBDAEFAgIVh2ypUJwbF4EpjGwDGk4Hgm+BSQEDiUiKM4QohkeLUYFvgVwe
X-IronPort-AV: E=Sophos;i="4.95,706,1384300800"; d="scan'208";a="4075473"
Received: from ams-core-4.cisco.com ([144.254.72.77]) by aer-iport-1.cisco.com with ESMTP; 23 Jan 2014 14:54:23 +0000
Received: from [10.0.2.15] ([10.148.144.89]) by ams-core-4.cisco.com (8.14.5/8.14.5) with ESMTP id s0NEsNPU005242; Thu, 23 Jan 2014 14:54:23 GMT
Message-ID: <52E12D1F.80701@cisco.com>
Date: Thu, 23 Jan 2014 09:54:23 -0500
From: David McGrew <mcgrew@cisco.com>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:17.0) Gecko/20130922 Icedove/17.0.9
MIME-Version: 1.0
To: Adam Langley <agl@google.com>, Yoav Nir <ynir@checkpoint.com>
References: <180998C7-B6E5-489E-9C79-80D9CAC0DE68@checkpoint.com> <CAL9PXLy9hrq+i_neP96FbTJRvRLbLEXnMYdBdwSeHunFAwF+jQ@mail.gmail.com> <A867BB8E-4556-44B1-A0AF-16771626BF5C@checkpoint.com> <52CB358D.3050603@cisco.com> <A6BDE08D-1F7D-4813-A9C4-61AF8C14412B@checkpoint.com> <52CB482D.6090807@cisco.com> <09031D92-9A14-4CF0-A000-123E71D4F784@checkpoint.com> <3861F1D4-B412-42BE-AE6C-FF5DE213854C@checkpoint.com> <CAL9PXLzgo5a2dk0JM-kWvawPhO1arpurcYSuqcffTWGdrCGY7A@mail.gmail.com>
In-Reply-To: <CAL9PXLzgo5a2dk0JM-kWvawPhO1arpurcYSuqcffTWGdrCGY7A@mail.gmail.com>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: [Cfrg] questions on performance and side channel resistance for ChaCha20 and Poly1305 for IPsec and TLS
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: Thu, 23 Jan 2014 14:54:28 -0000

Hi Adam and Yoav,

I have some questions and comments on these crypto algorithms and their 
use in TLS and IPsec.

On 01/21/2014 01:06 PM, Adam Langley wrote:
> On Tue, Jan 21, 2014 at 11:47 AM, Yoav Nir <ynir@checkpoint.com> wrote:
>> Reviews and comments would be greatly appreciated, as well as anyone checking my examples.
> In the introduction: I think ChaCha20+Poly1305 are useful for software
> implementations, beyond their use as a backup to AES. AES in not
> suitable for pure, software implementations and they tend to be be
> slow and have side-channels. (AES-GCM even more so.)

The claims that ChaCha20+Poly1305 are faster than AES GCM in pure 
software environments should be quantified in (at least one of) the 
drafts.   I am not challenging the fact that ChaCha20+Poly1305 will 
perform better than a side-channel resistant implementation of AES GCM 
on some processors, and I support the development of an alternative AEAD 
mechanism for TLS, for diversity's sake even if there were no other 
considerations.   But as performance is cited as a motivation for 
adoption, it is important to document the true state of affairs by 
citing some relevant performance study for the combined AEAD algorithm, 
or at the very least extrapolate the performance of the combined 
algorithm from published performance of the constituent algorithms.

The important questions that I see:

- how much faster is ChaCha20+Poly1305 on typical 16 or 32-bit 
processors, when no hardware support for AES or GF multiplication are 
available?   The most interesting "typical" processor, I think, would be 
a mobile phone class processor, like a Snapdragon.

- how much slower is ChaCha20+Poly1305 when that hardware support is 
available?

It would also be interesting to look into the power used by the 
different algorithms, since battery life is important on mobile devices.

Another goal for this ciphersuite is to avoid side channel attacks, 
though it is not directly mentioned in the draft.    The design 
rationale for Salsa describes how timing channels are avoided by not 
using multiplication in that function.   However, Poly1305 uses *lots* 
of multiplication operations, by a fixed constant.  Unless I am missing 
something, this is an inconsistency with the motivation for the 
ciphersuite.  In any case, if Poly1305 requires implementation 
techniques to avoid side channels, they should be documented in the 
draft that specifies that function.

As a side note: the timing channels in GCM and Poly1305 can potentially 
leak the authentication key, but this would not affect 
confidentiality.   A timing channel in an AES implementation, on the 
other hand, could leak the encryption key.    So using ChaCha in some 
environments (a CPU small enough that bitslicing AES is unwieldy, for 
instance) seems well motivated.   Perhaps the timing channel on Poly1305 
is smaller than that of GHASH, at least for some implementation 
techniques, but regardless, the use of Poly1305 as a replacement for 
GHASH is less well motivated.

I assume that the timing channels are the major concern, and that the 
attack model is one in which an untrusted process running on a trusted 
operating system aims to discover the key of a ciphersuite in use by 
some other process.   It would be good to document that fact, to give 
implementers an idea of what the important channel is.   (Otherwise, 
they might mistakenly think that the attacker is only able to observe 
network traffic.)  Is it also a goal to avoid power analysis attacks?    
It would be good to document that fact, either way.

I think your goal here is to have both client and server use a 
hardware-friendly ciphersuite when they both have the right hardware, 
and to use a software-friendly ciphersuite otherwise. This would imply 
that the hardware-friendly ciphersuite comes first in the proposal when 
it is available; does it also mean that when the hardware support is 
absent, that the hardware-friendly ciphersuite is not offered?    Also, 
it seems that it would be necessary, in TLS, to have ciphersuites 
offered in hardware/software pairs, to ensure that an appropriate 
authentication method is available.   Maybe I misunderstood the goal, if 
so I trust that you will set me straight.   But if this is the goal, it 
would make sense to include guidance to this effect in the draft.

regards,

David