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

[David McGrew <[e-mail]>]

Hi Adam,

On 01/23/2014 11:51 AM, Adam Langley wrote:
> On Thu, Jan 23, 2014 at 9:54 AM, David McGrew <[e-mail]> wrote:
>> 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 <[e-mail]> 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 have no problem with that, but it's not something that I typically
> see in IETF drafts and so I didn't do any actual numbers for it.

Agreed that it is not something one would expect to see in a TLS draft, 
but if the definitive algorithm specification is going to be an RFC, it 
should be there.   Watson suggested having a separate RFC that defines 
this algorithm combination, which makes sense to me.

>
> ARM testing is done with with the AES-GCM from OpenSSL 1.0.1f (which
> has optimised asm routines for both AES and GCM, although they are
> *not* side-channel free). ChaCha20 and Poly1305 code come from
> SUPERCOP, but integrated into OpenSSL so the overhead is the same. A
> 1KB block size is used
>
> OMAP 4460: 24.1 MB/s (AES-GCM), 75.3 MB/s (ChaCha20-Poly1305)
> Snapdragon S4 Pro: 41.5 MB/s (AES-GCM), 130.9 MB/s (ChaCha20-Poly1305)
>
> So ChaCha20-Poly1305 is ~3x faster, with side-channel protection,
> little dcache pressure and with a 256-bit cipher rather than 128-bit.
>
> On a Sandy Bridge Xeon, AES-GCM runs at ~900 MB/s and
> ChaCha20-Poly1305 at ~500 MB/s.
>
> In both cases, I'm ignoring the extra cache pressure of AES-GCM.

Thanks, this is good data.

> Over time, AESNI will get faster but also the vector units will get
> wider, which helps ChaCha20 and Poly1305. I expect that on high-end,
> Intel chips, the gap will contain to be a small multiple, but it might
> not be as small as 2x on future chips.
>
>> It would also be interesting to look into the power used by the different
>> algorithms, since battery life is important on mobile devices.
> I don't have data on power usage I'm afraid because I don't have the
> equipment to test it. I'm happy to provide a testing binary for
> Android if anyone does.

Maybe it would be possible to write a "run until low battery" app on 
android?   I am no expert on the platform, but it seems that something 
like this would be possible using a receiver for ACTION_BATTERY_LOW.

Just for clarity's sake: I did not mean to suggest that the draft should 
include this data.   It would be good info to know, and it might support 
the case for the newer algorithms, but if the data doesn't exist, its 
not fair to ask that it to be in there.

>> 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.
> Some CPUs (the G4e is mentioned in the Salsa paper) do have
> non-constant time multiplication and, on those systems, a
> constant-time Poly1305 implementation will be troublesome.
>
> However, those CPUs are rare I believe. (Does anyone know if the PPC64
> chips have the same issue?) For the case of common Intel and ARM CPUs
> it's not a problem. But you're right that it's worth pointing out,
> although I'm not aware that anyone has attempted a constant-time
> Poly1305 on such a chip.

I bet that Dan has thought about the timing issues - it would be great 
to get his input.    He said that it was "often" an issue for 
multiplication, back in 2007, but Robert Ransom mentions in a separate 
note that many modern CPUs have constant-time integer multiplication.

>
>> 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 the goal is to make crypto as boring as possible. Avoiding
> clear side-channels is just more relaxing because there's less to
> worry about and all the things that you list (simple power analysis,
> mixing mutually untrusting code on the same system etc) are all
> concerns.
>
> But yes, a section on this in the draft is warranted.
>

My guess is that power analysis attacks are less relevant for TLS and 
for mobile phones, but more relevant for Internet of Things scenarios 
and long-term secret keys.


>> 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.
> I'm not sure whether this draft is the correct place for it, but it's
> currently the case that Chrome will switch the positions of AES-GCM
> and CHACHA20-POLY1305 in its ciphersuite preferences depending on
> whether AES hardware support is present. Additionally, some Google
> servers (the rollout is in progress) have partial ciphersuite
> preferences: they will respect the client's preference between some
> ciphersuites. This allows AES-GCM to be used when the client has
> hardware and CHACHA20-POLY1305 otherwise.

To me it seems worthwhile to have some guidance on this subject in the 
TLS draft, but if there is a separate draft defining the algorithm, then 
negotiation seems out of scope.

thanks,

David

>
>
> Cheers
>
> AGL
> .
>