Subject: [Cfrg] ChaCha20 and Poly1305 for IPsec

From: Yoav Nir <[email-masked]>
Date: Sun, 5 Jan 2014 16:18:28 +0000

Hi

Recently there has been some activity in trying to find alternative ciphers. In TLS the issue was RC4, which is now deemed insecure. Adam's draft ([1]) proposes to use another stream cipher, ChaCha20, in its place. Poly1305 is used in that draft as a faster (when compared with HMAC-SHA1) message authentication algorithm. 

For IPsec, RC4 was never used because it always produces the same keystream, so we cannot produce per-packet streams. What we have today is that the only widely-deployed algorithm other than AES is 3DES, and on modern hardware AES is 4x to 10x as fast as 3DES. That means that if ever an issue is found in AES, users will not be able to switch to 3DES - the performance is not even close, so much of the deployed hardware will not be able to handle the load. This sorry state is described in [2].

Unlike RC4, ChaCha20 has a 64-bit nonce, so different packets could use different keystreams, much like block ciphers in counter mode. Unlike 3DES, ChaCha20 has performance that is close to that of AES.

So my question is whether there is any reason not to use ChaCha20 (with or without the AEAD construction from Adam's draft) for IKE and/or IPsec. Could this be the standby algorithm that we have been looking for?

Yoav

[1] http://tools.ietf.org/html/draft-agl-tls-chacha20poly1305-04
[2] http://tools.ietf.org/html/draft-mcgrew-standby-cipher-00

---

From: Yoav Nir <[email-masked]>
Date: Mon, 6 Jan 2014 22:23:31 +0000

Thanks. Proposing this seems so obvious, that I thought I must be missing something that makes it unsuitable.

On Jan 6, 2014, at 8:05 PM, Adam Langley <[email-masked]> wrote:

> On Sun, Jan 5, 2014 at 11:18 AM, Yoav Nir <[email-masked]> wrote:
> I don't know of any problems with this. If IPsec has the concept of a
> counter than can be used as an nonce then I think the AEAD
> construction would be fine, as is.

IPsec has a 32- or 64-bit packet counter, but for some reason it has never been used as a nonce. Both AES-CTR and AES-GCM have explicit 64-bit IVs in IPsec, so I think a ChaCha implementation should do the same - have an explicit IV that's used as a nonce, with a MUST requirement for uniqueness of IV/key combination.

> If one needs to pick the nonces
> randomly, however, then a 64-bit space is too small and XChaCha (which
> has a 192-bit nonce) would be more suitable.

It would work, but IPsec requires re-keying when the 32-bit or 64-bit counter reaches 2^n-1, so that seems like overkill.

Thanks again

Yoav

---

From: David McGrew <[email-masked]>
Date: Mon, 06 Jan 2014 18:00:29 -0500

Hi Yoav,

> IPsec has a 32- or 64-bit packet counter, but for some reason it has never been used as a nonce. Both AES-CTR and AES-GCM have explicit 64-bit IVs in IPsec, so I think a ChaCha implementation shoul…

the reason that the ESP sequence number isn't used as a cryptographic 
nonce is that it was not regarded as reliable enough.   That is, the ESP 
standard does not insist that the sequence number never wrap, and many 
implementations are not careful about maintaining the uniqueness of the 
sequence number.  This situation is not ideal, but it does seem to be 
the case.

> It would work, but IPsec requires re-keying when the 32-bit or 64-bit counter reaches 2^n-1, so that seems like overkill.

Agreed that a 192-bit nonce sounds a bit big.

ESP supports multipoint security associations, in which case it is 
essential to coordinate nonces across all of the encrypters, to make 
sure that they are all distinct.   The requirements and a simple 
approach is outlined in rfc6054, and those requirements are followed in 
the latest version of the Group Domain of Interpretation rfc6407.  The 
nonce management is a bit ugly, but there is precedent for it.

We could do a lot worse than ChaCha as a cipher.   An AEAD construction 
could be used in a way that mirrors GCM/CCM, though if I recall right, 
Adam defined an 8-byte nonce rather than a 12-byte nonce for the ChaCha 
AEAD algorithm, which makes it incompatible with almost all of the other 
AEAD algorithms (see Table 1 of draft-mcgrew-iv-gen-02).   A 12-byte 
nonce would enable ESP implementations to use the same nonce generation 
techniques, including rfc6407 ones.

My biggest concern with ChaCha is: will it have the global credibility 
that we need?    If we think that it does, we should go about 
documenting the work that has been done analyzing it.  The record of the 
analysis will become extremely important once the cipher gets picked up 
by the semi-technical press and the user community.

Since so much of ESP is point to point and works at a high data rate, it 
makes sense to think about counter-based nonces and throughput-optimized 
algorithms, like ChaCha.   Algorithms that are misuse-resistant would be 
useful in scenarios other than point-to-point ones, and in my opinion 
are also worth considering as future work for ESP.

David

>
> Thanks again
>
> Yoav
>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg
>

---

From: Yoav Nir <[email-masked]>
Date: Mon, 6 Jan 2014 23:43:48 +0000

On Jan 7, 2014, at 1:00 AM, David McGrew <[email-masked]>
 wrote:

> the reason that the ESP sequence number isn't used as a cryptographic nonce is that it was not regarded as reliable enough.   That is, the ESP standard does not insist that the sequence number never wrap, and many implementations are not careful about maintaining the uniqueness of the sequence number.  This situation is not ideal, but it does seem to be the case.

I agree that the text could use some more RFC2119 language, but allowing the sequence to wrap is not allowed:

                                              If anti-replay is enabled
   (the default), the transmitted Sequence Number must never be allowed
   to cycle.  Thus, the sender's counter and the receiver's counter MUST
   be reset (by establishing a new SA and thus a new key) prior to the
   transmission of the 2^32nd packet on an SA.

> ESP supports multipoint security associations, in which case it is essential to coordinate nonces across all of the encrypters, to make sure that they are all distinct.   The requirements and a simple approach is outlined in rfc6054, and those requirements are followed in the latest version of the Group Domain of Interpretation rfc6407.  The nonce management is a bit ugly, but there is precedent for it.
> 
> We could do a lot worse than ChaCha as a cipher.   An AEAD construction could be used in a way that mirrors GCM/CCM, though if I recall right, Adam defined an 8-byte nonce rather than a 12-byte nonce for the ChaCha AEAD algorithm, which makes it incompatible with almost all of the other AEAD algorithms (see Table 1 of draft-mcgrew-iv-gen-02).   A 12-byte nonce would enable ESP implementations to use the same nonce generation techniques, including rfc6407 ones.

An 8-byte nonce is part of ChaCha. This is different from counter mode where the initial counter could be anything up to block size. I don't claim to understand why ChaCha has a 64-bit nonce and a 64-bit block counter instead of, say, a 96-bit nonce and a 32-bit block counter (good for 256 GB - plenty for an IP packet). Would ChaCha modified like that retain its security properties?

> My biggest concern with ChaCha is: will it have the global credibility that we need?    If we think that it does, we should go about documenting the work that has been done analyzing it.  The record of the analysis will become extremely important once the cipher gets picked up by the semi-technical press and the user community.

That sounds like a good task for CFRG. As some have mentioned in previous threads, we can't trust NIST for all our crypto needs. This is not that they're evil, but more in that they're reluctant to endorse something that didn't originate with them (GCM was a fluke). So we have to rely on other sources.

> Since so much of ESP is point to point and works at a high data rate, it makes sense to think about counter-based nonces and throughput-optimized algorithms, like ChaCha.   Algorithms that are misuse-resistant would be useful in scenarios other than point-to-point ones, and in my opinion are also worth considering as future work for ESP.
> 
> David

---

From: Ted Krovetz <[email-masked]>
Date: Mon, 6 Jan 2014 15:54:26 -0800

> An 8-byte nonce is part of ChaCha. This is different from counter mode where the initial counter could be anything up to block size. I don't claim to understand why ChaCha has a 64-bit nonce and a…

Indeed it would. The Chacha core maps 48 bytes to 64 bytes and is called repeatedly on (32-byte key) || (8-byte IV) || (8-byte counter) to produce the output stream. Each distinct (8-byte IV) || (8-byte counter) will produce a pseudorandom 64-byte output. So, (n-byte IV) || (16-n-byte counter) should be just fine (so long as n is fixed for the life of the key).

-Ted

---

From: David McGrew <[email-masked]>
Date: Mon, 06 Jan 2014 19:19:57 -0500

Hi Yoav,

On 01/06/2014 06:43 PM, Yoav Nir wrote:
> An 8-byte nonce is part of ChaCha.

  - faceplam -  Yes, of course.

> This is different from counter mode where the initial counter could be anything up to block size. I don't claim to understand why ChaCha has a 64-bit nonce and a 64-bit block counter instead of, say, a 96-bit nonce and a 32-bit block counter (good for 256 GB - plenty for an IP packet). Would ChaCha modified like that retain its security properties?

I think so - I would be surprised if it didn't retain its security 
properties.   But it might be best to avoid tweaking the design.

> That sounds like a good task for CFRG. As some have mentioned in previous threads, we can't trust NIST for all our crypto needs.

That makes sense to me, but I would also much like to hear other opinions.

David

> This is not that they're evil, but more in that they're reluctant to endorse something that didn't originate with them (GCM was a fluke). So we have to rely on other sources.
>
> .

---

From: Watson Ladd <[email-masked]>
Date: Mon, 6 Jan 2014 16:33:34 -0800

On Mon, Jan 6, 2014 at 4:19 PM, David McGrew <[email-masked]> wrote:
>>>> Thanks. Proposing this seems so obvious, that I thought I must be
>>>> missing something that makes it unsuitable.
>>>>
>>>>>> Unlike RC4, ChaCha20 has a 64-bit nonce, so different packets could
>>>>>> use different keystreams, much like block ciphers in counter mode. Unlike
>>>>>> 3DES, ChaCha20 has performance that is close to that of AES.
>>>>>>
>>>>>> So my question is whether there is any reason not to use ChaCha20
>>>>>> (with or without the AEAD construction from Adam's draft) for IKE and/or
>>>>>> IPsec. Could this be the standby algorithm that we have been looking for?
>>>>>
>>>> IPsec has a 32- or 64-bit packet counter, but for some reason it has
>>>> never been used as a nonce. Both AES-CTR and AES-GCM have explicit 64-bit
>>>> IVs in IPsec, so I think a ChaCha implementation should do the same - have
>>>> an explicit IV that's used as a nonce, with a MUST requirement for
>>>> uniqueness of IV/key combination.
>>>
>>> sequence number.  This situation is not ideal, but it does seem to be the
>>> case.
>>
>>>> It would work, but IPsec requires re-keying when the 32-bit or 64-bit
>>>> counter reaches 2^n-1, so that seems like overkill.
>>>
>>> essential to coordinate nonces across all of the encrypters, to make sure
>>> that they are all distinct.   The requirements and a simple approach is
>>> outlined in rfc6054, and those requirements are followed in the latest
>>> version of the Group Domain of Interpretation rfc6407.  The nonce management
>>> is a bit ugly, but there is precedent for it.
>>>
>>> could be used in a way that mirrors GCM/CCM, though if I recall right, Adam
>>> defined an 8-byte nonce rather than a 12-byte nonce for the ChaCha AEAD
>>> algorithm, which makes it incompatible with almost all of the other AEAD
>>> algorithms (see Table 1 of draft-mcgrew-iv-gen-02).   A 12-byte nonce would
>>> enable ESP implementations to use the same nonce generation techniques,
>>> including rfc6407 ones.
>>
>> This is different from counter mode where the initial counter could be
>> anything up to block size. I don't claim to understand why ChaCha has a
>> 64-bit nonce and a 64-bit block counter instead of, say, a 96-bit nonce and
>> a 32-bit block counter (good for 256 GB - plenty for an IP packet). Would
>> ChaCha modified like that retain its security properties?
>
>
>>> that we need?    If we think that it does, we should go about documenting
>>> the work that has been done analyzing it.  The record of the analysis will
>>> become extremely important once the cipher gets picked up by the
>>> semi-technical press and the user community.
>>
>> That sounds like a good task for CFRG. As some have mentioned in previous
>> threads, we can't trust NIST for all our crypto needs.
>
>

I don't think anything new has really been found, despite a lot of
kicking the tires
with BLAKE and Salsa20. However, DJB did use XSalsa20 instead of
XChaCha20 (a hypothetical
longer nonce variant) in NaCl, so maybe the performance benefit is
gone with new CPUs?

As for the nonce/block counter size adjustment, 96 bits still can't be
picked at random, but
32 bit objects are occasionally encrypted. If I can fit in memory, I
should be able to deal with it
is the philosophy. But for the security of ChaCha it doesn't matter:
the nonce and block counter
are treated alike, and both are public.
Sincerely,
Watson

>
> David
>
>
>> This is not that they're evil, but more in that they're reluctant to
>> endorse something that didn't originate with them (GCM was a fluke). So we
>> have to rely on other sources.
>>
>>> useful in scenarios other than point-to-point ones, and in my opinion are
>>> also worth considering as future work for ESP.
>>>
>>> David
>>

-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin

---

From: CodesInChaos <[email-masked]>
Date: Tue, 7 Jan 2014 15:01:52 +0100

> However, DJB did use XSalsa20 instead of XChaCha20 (a hypothetical longer nonce variant) in NaCl

ChaCha was published in January 2008, NaCl was published in March
2009. So I'd guess Salsa20 was chosen over ChaCha because it had seen
more analysis in the eStream contest whereas ChaCha was pretty new at
the time.

I think that's less of a concern now, most attacks were applied
against both Salsa20 and ChaCha, with ChaCha resisting them slightly
better.

The biggest difference in analysis I'm aware of is that there is a
proof of security against differential cryptoanalysis for Salsa20, but
not for ChaCha. This proof relies on the alternation of xor and
addition in Salsa20, it doesn't seem trivial to port it to ChaCha.
http://eprint.iacr.org/2013/328

---

From: Yoav Nir <[email-masked]>
Date: Thu, 9 Jan 2014 07:16:59 +0000

On Jan 7, 2014, at 2:19 AM, David McGrew <[email-masked]> wrote:

> I think so - I would be surprised if it didn't retain its security properties.   But it might be best to avoid tweaking the design.

Thinking it over, I think so too. While ChaCha20 can handle 64 TB messages, 256 GB is more than good enough for an IPsec packet (currently limited to 64KB). So we could reduce the block counter to 10 bits, but since everything else id ChaCha is 32-bit, I'll leave it at 32-bit. So the nonce could be expanded to 96-bit, but as long as an implementation makes sure that it *is* a nonce (only used once), 64-bit is plenty for a single SA. I will use the extra 32-bit word as sender-id. So it can be set to zero for regular ESP, and set to non-zero for GDOI with multiple senders.

Yoav

---

From: Yoav Nir <[email-masked]>
Date: Tue, 21 Jan 2014 20:58:41 +0000

On Jan 21, 2014, at 8:06 PM, Adam Langley <[email-masked]> wrote:

> On Tue, Jan 21, 2014 at 11:47 AM, Yoav Nir <[email-masked]> 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.)

I agree that a pure C-language implementation of AES is slower than either ChaCha20 or RC4, although it is still much faster than 3DES. Processor vendors have been adding hardware implementation of common tasks to so-called general purpose processors for years. So we got floating point in the late 80s, and "multi-media extension" 128-bit registers in the 90s, then vector processors, and now encryption functions. Is software that uses the AESENC opcode software or hardware? I think by now the line is blurred. For IPsec, AES has been the fastest algorithm even in pure C implementations.  I'll add something about being fast in software implementation to the next iteration.

> "The ChaCha20 block function"...
> 
> I asked DJB and he said that ChaCha is the name of the cipher and
> ChaCha20 is the specific variant with 20 rounds.

Yeah, that's how I used it.

> 
> "The 14th word is the least significant 32 bits of the input nonce
> (nonce | 0xffffffff)"
> 
> AND not OR, I think.

Oops. You're right, of course.

> You've changed the AEAD by switching the length values from uint64le
> to uint32be. Seems unnecessary.

I'll change it back. For some reason I thought AES-GCM for IPsec was like that, but looking again, I see that it isn't.

> 
> "for a particular key. counters"
> 
> nit: missing capital letter.

Will fix. Thanks.

> I'm not suitable to evaluate the higher-level integration into IPSec.
> 

I've posted this to ipsec as well. They said that we need a better normative reference for the functions. DJB's papers discuss security properties and link to source code, but don't have a good definition.

Yoav

---

From: Watson Ladd <[email-masked]>
Date: Tue, 21 Jan 2014 13:05:13 -0800

On Jan 21, 2014 12:59 PM, "Yoav Nir" <[email-masked]> wrote:
> I agree that a pure C-language implementation of AES is slower than
either ChaCha20 or RC4, although it is still much faster than 3DES.
Processor vendors have been adding hardware implementation of common tasks
to so-called general purpose processors for years. So we got floating point
in the late 80s, and "multi-media extension" 128-bit registers in the 90s,
then vector processors, and now encryption functions. Is software that uses
the AESENC opcode software or hardware? I think by now the line is blurred.
For IPsec, AES has been the fastest algorithm even in pure C
implementations.  I'll add something about being fast in software
implementation to the next iteration.
> I'll change it back. For some reason I thought AES-GCM for IPsec was like
that, but looking again, I see that it isn't.
> I've posted this to ipsec as well. They said that we need a better
normative reference for the functions. DJB's papers discuss security
properties and link to source code, but don't have a good definition.

Are you reading the same paper I am? He defines Salsa and ChaCha in terms
of applying a well defined quarter round function to the rows and diagonals
of a 4x4 matrix.

---

From: Yoav Nir <[email-masked]>
Date: Tue, 21 Jan 2014 21:07:16 +0000

On Jan 21, 2014, at 11:01 PM, Adam Langley <[email-masked]>
 wrote:

> On Tue, Jan 21, 2014 at 3:58 PM, Yoav Nir <[email-masked]> wrote:
> Would you like the ChaCha in TLS draft to be split into a draft to
> define Chacha, Poly1305 and the AEAD and a separate draft for the TLS
> bits?
> 

I think that would be useful.

Yoav

---

From: Yoav Nir <[email-masked]>
Date: Tue, 21 Jan 2014 23:25:07 +0200

On 21/1/14 11:05 PM, Watson Ladd wrote:
> Are you reading the same paper I am? He defines Salsa and ChaCha in 
> terms of applying a well defined quarter round function to the rows 
> and diagonals of a 4x4 matrix.
>

I'm reading this one:
http://cr.yp.to/chacha/chacha-20080128.pdf

It's mixing description, comparison with Salsa20, security analysis and 
performance data. That's fine for a paper. I could probably write an 
implementation based on that, but I would have very little confidence 
that it is correct.

For RFCs, we like to have a clear document that is as short as possible, 
and has a very clear definition, and a few test vectors so an 
implementer can check their code.

I'm not totally convinced by Yaron's response ([1]), but I'd rather not 
be forced to repeat much of the algorithm in my draft, as Adam did in 
sections 3 & 4 of [2].

Yoav

[1] http://www.ietf.org/mail-archive/web/ipsec/current/msg08929.html
[2] http://tools.ietf.org/html/draft-agl-tls-chacha20poly1305-04

---

From: Yoav Nir <[email-masked]>
Date: Tue, 21 Jan 2014 21:53:53 +0000

> I'll change it back. For some reason I thought AES-GCM for IPsec was like that, but looking again, I see that it isn't.

Looking into GCM, I see two other things:
 1. The lengths there are big-endian ("...a 64-bit string containing the nonnegative integer describing the number of bits in its argument, with the least significant bit on the right.")
 2. The lengths there are the number of bits, not bytes.

Big-endian always seemed to me to be more "natural" because most binary protocols transmit numbers that way, but I don't think there's any reason to count bits, is there?

Yoav

---

From: David McGrew <[email-masked]>
Date: Thu, 23 Jan 2014 09:54:23 -0500

Hi Adam and Yoav,

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

> 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

---

From: David McGrew <[email-masked]>
Date: Thu, 23 Jan 2014 10:01:43 -0500

On 01/21/2014 05:08 PM, Adam Langley wrote:
> On Tue, Jan 21, 2014 at 4:53 PM, Yoav Nir <[email-masked]> wrote:
> There might be an implementation of GCM that supports bit lengths that
> are not a multiple of 8, but I'm not aware of it.

I'm not aware of it either, if it exists.

With GCM, we took this strategy: make the inputs and outputs octet 
strings, since that is what really matters in the real world, but then 
use the number of bits in the computation of the authentication tag 
rather than the number of bytes, so that it would be possible for 
someone else to define a bit-oriented version of the algorithm if they 
really need to.

> I think little-endian makes more sense in a ChaCha20-Poly1305 AEAD
> because everything else in the AEAD (ChaCha and Poly1305) is handled
> as little-endian.
>
> (I've also done enough implementations of the arithmetic that I find
> little-endian to be preferable in general, but that might just be
> brain damage.)
>

For what it is worth, little endian has a legitimate advantage in that 
enables better pipelining of multiplications.   But I think this is a 
six-or-half-dozen issue.

David

> Cheers
> AGL

---

From: David McGrew <[email-masked]>
Date: Thu, 23 Jan 2014 10:06:06 -0500

Hi Yoav,

On 01/21/2014 04:25 PM, Yoav Nir wrote:
> It's mixing description, comparison with Salsa20, security analysis 
> and performance data. That's fine for a paper. I could probably write 
> an implementation based on that, but I would have very little 
> confidence that it is correct.

The "spec.pdf" file in the "Design, Specification, Security and Speed" 
zipfile submitted to ESTREAM might be useful to you 
http://www.ecrypt.eu.org/stream/e2-salsa20.html

David

>
> For RFCs, we like to have a clear document that is as short as 
> possible, and has a very clear definition, and a few test vectors so 
> an implementer can check their code.
>
> I'm not totally convinced by Yaron's response ([1]), but I'd rather 
> not be forced to repeat much of the algorithm in my draft, as Adam did 
> in sections 3 & 4 of [2].
>
> Yoav
>

---

From: Robert Ransom <[email-masked]>
Date: Thu, 23 Jan 2014 10:26:54 -0800

> draft that specifies that function.

Dr. Bernstein's original implementation of Poly1305 used the IA-32
floating-point unit to avoid timing leaks on the processors available
in 2005.  My understanding is that essentially all modern processors
have constant-time integer multipliers, so special implementation
techniques are no longer required.

Robert Ransom

---

From: David McGrew <[email-masked]>
Date: Fri, 24 Jan 2014 08:45:37 -0500

Hi Adam,

On 01/23/2014 11:51 AM, Adam Langley wrote:
> On Thu, Jan 23, 2014 at 9:54 AM, David McGrew <[email-masked]> wrote:
>> Hi Adam and Yoav,
>>
>> I have some questions and comments on these crypto algorithms and their use
>> in TLS and IPsec.
>>
>> 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.

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

---

From: David McGrew <[email-masked]>
Date: Fri, 24 Jan 2014 09:33:05 -0500

Hi Robert,

> techniques are no longer required.

this would be great news.   The issue does deserve to be documented, 
though, even if we can cite a study that shows that current processors 
don't have the issue, since future processors might behave differently.

thanks,

David

---

From: Yoav Nir <[email-masked]>
Date: Sat, 25 Jan 2014 01:19:23 +0200

On 24/1/14 3:45 PM, David McGrew wrote:
>>> software
> 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.

Hi David.

I'm trying to throw together a separate document describing ChaCha20, 
Poly1305, and Adam's AEAD, every step with test vectors. I hope to have 
it ready by Monday.

Yoav

---

From: David McGrew <[email-masked]>
Date: Sun, 26 Jan 2014 04:22:04 -0500

On 01/24/2014 06:19 PM, Yoav Nir wrote:
>> 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.
>
> Hi David.
>
> Poly1305, and Adam's AEAD, every step with test vectors. I hope to 
> have it ready by Monday.
>
> Yoav
>
>

Thanks Yoav, I offer to provide some detailed comments.   Can I ask for 
some other volunteers in the group to do the same?    It would be good 
to make sure that the review gets done in a timely way, considering the 
IETF interest.

David