917571 - Support ChaCha20+Poly1305 cipher

Status: RESOLVED FIXED

(NSS :: Libraries, enhancement)

Description

[Adam Langley]

Attachment: basic support. Does not yet include tests, thus no r?

http://tools.ietf.org/html/draft-agl-tls-chacha20poly1305-01 details the addition of ChaCha20Poly1305 based cipher suites to TLS. This AEAD is believed to be secure to 256-bit level for confidentiality and to a ~95-bit level for authenticity. Additionally, it's fast on CPUs even without special instruction support and is naturally constant time.

Comment 1

[Adam Langley]

Attachment: patch

wtc: you've seen the ssl/ changes previously in Chromium.

Comment 2

[Adam Langley]

Attachment: patch

I have updated the patch to switch the order of the length and data when calculating the MAC, as suggested by wtc on the TLS WG mailing list. This is a very small change, but it means that all the test vectors changed.

(The test vectors now match the values in OpenSSL.)

Comment 3

[Wan-Teh Chang]

Comment on attachment 814476 [details] [diff] [review]
patch

Review of attachment 814476 [details] [diff] [review]:
-----------------------------------------------------------------

::: lib/ssl/ssl3con.c
@@ +5201,4 @@
>  
>      flags = 0;
>      if (!ss->firstHsDone && !requestingResume && !IS_DTLS(ss)) {
> +	//flags |= ssl_SEND_FLAG_CAP_RECORD_VERSION;

This looks like an unrelated change. I will remove it from the patch.

::: lib/util/secport.c
@@ +69,4 @@
>  PORTCharConversionFunc ucs2Utf8ConvertFunc;
>  PORTCharConversionWSwapFunc  ucs2AsciiConvertFunc;
>  
> +#define MAX_SIZE 0x7fffffffUL

The changes to secport.c are for a different bug.
I will remove this file from the patch.

Comment 4

[Wan-Teh Chang]

Attachment: patch v2, by Adam Langley

1. I removed the unrelated changes in secport.c and ssl3con.c.

2. I fixed a pre-existing bug in pk11gcmtest.c, so that it actually exits
with status 1 on test failure.

3. I changed tests/cipher/cipher.sh to check the exit status of pk11gcmtest.c
and output the test status in results.html.

4. I disabled the use of poly1305-donna-x64-sse2-incremental-source.c because
it uses the __int128 type, which requires recent versions of GCC or clang.

Comment 5

[Wan-Teh Chang]

Attachment: patch v3, by Adam Langley

Incorporated the latest patch from https://codereview.chromium.org/27510015/

Renamed CK_AEAD_PARAMS to CK_NSS_AEAD_PARAMS and changed ulTagBits to ulTagLen
(length in bytes).

Changed pk11gcmtest.c to use CK_NSS_AEAD_PARAMS for CKM_NSS_CHACHA20_POLY1305.

Comment 6

[Ben Bucksch (:BenB)]

+#error -- Implementation supports only machines with neon or SSE2

Shouldn't there be a slower fallback impl that works on all machines?

Comment 7

[Adam Langley]

(In reply to Ben Bucksch (:BenB) from comment #6)
> Shouldn't there be a slower fallback impl that works on all machines?

There is. However, the build may not be correctly configured yet.

Comment 8

[Ben Bucksch (:BenB)]

ah, the comment applies only to 64 bit machines:
+ifeq ($(CPU_ARCH),x86_64)
...
+    EXTRA_SRCS += chacha20/chacha20_vec.c
+else
+    EXTRA_SRCS += chacha20/chacha20.c

Maybe you could make the build fall back to that, as you said.

Comment 9

[Adam Langley]

Wait, you have a x86_64 machine without SSE2? I wasn't aware that they existed.

Comment 10

[Ben Bucksch (:BenB)]

New CPUs, new architectures. ARM has NEON. There could be other archs.
Alternatively, you could just adjust the error message in chacha20_vec.c to point to the chacha20.c implementation.

Comment 11

[u474838]

Update?

Comment 12

[Reed Loden [:reed]]

http://googleonlinesecurity.blogspot.com/2014/04/speeding-up-and-strengthening-https.html

"We hope there will be even greater adoption of this cipher suite, and look forward to seeing other websites deprecate AES-SHA1 and RC4-SHA1 in favor of AES-GCM and ChaCha20-Poly1305 since they offer safer and faster alternatives."

Comment 13

[Chris Newman]

Comment on attachment 820740 [details] [diff] [review]
patch v3, by Adam Langley

Review of attachment 820740 [details] [diff] [review]:
-----------------------------------------------------------------

Can you please put the new cipher suites and code under a compile-time #define? US companies that bundle NSS or Firefox+NSS with their products or Operating Systems will have to file a new export control request when this shows up and may want to ship the current version of NSS without these ciphers while that request is processed.

Comment 14

[Kosuke Kaizuka]

https://tools.ietf.org/html/draft-agl-tls-chacha20poly1305-04 has been expired.
https://tools.ietf.org/html/draft-mavrogiannopoulos-chacha-tls-02 seems to be a new draft including ChaCha20+Poly1305 and ChaCha20 with HMAC-SHA1.

Comment 15

[twr2600]

Are there any updates on this?

Comment 16

[Peter Kasting]

Comment on attachment 820740 [details] [diff] [review]
patch v3, by Adam Langley

Review of attachment 820740 [details] [diff] [review]:
-----------------------------------------------------------------

When building Chromium locally with this patch while trying to enable some currently-disabled MSVC warnings, I ran across some minor issues.  Please see the review comments below for my proposed fixes.

::: lib/freebl/chacha20/chacha20.c
@@ +77,5 @@
> +    input[1] = U8TO32_LITTLE(sigma + 4);
> +    input[2] = U8TO32_LITTLE(sigma + 8);
> +    input[3] = U8TO32_LITTLE(sigma + 12);
> +
> +    input[12] = counter;

Avoids MSVC warnings about possible value truncation:

    input[12] = (PRUint32)counter;

::: lib/freebl/poly1305/poly1305.c
@@ +249,5 @@
> +
> +	U32TO8_LE(&mac[ 0], f0); f1 += (f0 >> 32);
> +	U32TO8_LE(&mac[ 4], f1); f2 += (f1 >> 32);
> +	U32TO8_LE(&mac[ 8], f2); f3 += (f2 >> 32);
> +	U32TO8_LE(&mac[12], f3);

Avoids MSVC warnings about possible value truncation:

        U32TO8_LE(&mac[ 0], (uint32_t)f0); f1 += (f0 >> 32);
	U32TO8_LE(&mac[ 4], (uint32_t)f1); f2 += (f1 >> 32);
	U32TO8_LE(&mac[ 8], (uint32_t)f2); f3 += (f2 >> 32);
	U32TO8_LE(&mac[12], (uint32_t)f3);

Comment 17

[Wan-Teh Chang]

Peter: thank you for suggesting the fixes. I will fix these MSVC warnings
in the Chromium source tree first and then update the patch in this bug
report when we're ready to check in the patch.

My Chromium changelist for your proposed fixes is
https://codereview.chromium.org/515383002/

Comment 18

[twr2600]

The Chromium issue seems to be resolved. What else is needed for this bug?

Comment 19

[Dirkjan Ochtman (:djc)]

I asked Richard Barnes about this bug, and he provided the following feedback, which seems useful for this bug.

> Actually, my recollection from the [NSS call] is that these are on hold pending:
> 
> 1. Finalization of the AEAD construct in CFRG
> 2. Finalization of the protocol aspects in TLS WG
> 3. Assignment of a PKCS#11 mechanism
> 
> All of those things are pretty close, but could cause breakage if they change.

Comment 20

[Dirkjan Ochtman (:djc)]

CloudFlare now supports this cipher suite:

https://blog.cloudflare.com/do-the-chacha-better-mobile-performance-with-cryptography/

Comment 21

[Harlan Lieberman-Berg]

At this point, I would suggest going ahead without the approval of the CFRG and the TLS WG.  The latest draft (https://tools.ietf.org/html/draft-mavrogiannopoulos-chacha-tls-05) is almost identical to the one submitted in September, with the exception of the removal of the ChaCha20+HMAC suite not applicable to this bug.

The CFRG has not had any discussion on it since February, and the branch containing the implementation in OpenSSL is stalled with no commits pulled to it since October 2013.

Even despite it being, at least from an outside-perspective, stalled in both the CFRG and the TLS WG, implementation has spread across all CloudFlare-enabled and Google-controlled websites.  It's in the communities' best interest to press forward, considering the well-respected nature of the cipher and the low likelihood of misimplementation.

I'm not one for normally saying "Google did it, so everyone should do it too", but in this case, they made the right choice and we haven't.  Yet.

Comment 22

[Chris Newman]

No opinion about whether this should go in, but if there's no IANA registered cipher number assigned to this cipher suite, it should be off-by-default. Deploying Internet software with a private-use cipher number on (as LibreSSL did) is rude and risks interoperability problems because it is standards compliant to interpret a private-use cipher number as whatever you wish.

Also, anyone who ships software including NSS will need a new export approval due to the new cipher so it would be handy to those NSS consumers if this feature was under a compile time #ifdef initially.

Comment 23

[cloos]

I don't see it in iana's tls-parameters as of today, but my understanding is that that CCxx values as specified in draft-mavrogiannopoulos-chacha-tls-04 are formally assigned, at least on a preliminary basis.

They are:

RSA_CHACHA20_POLY1305            0xCC, 0xA0
ECDHE_RSA_CHACHA20_POLY1305      0xCC, 0xA1
ECDHE_ECDSA_CHACHA20_POLY1305    0xCC, 0xA2
DHE_RSA_CHACHA20_POLY1305        0xCC, 0xA3
DHE_PSK_CHACHA20_POLY1305        0xCC, 0xA4
PSK_CHACHA20_POLY1305            0xCC, 0xA5
ECDHE_PSK_CHACHA20_POLY1305      0xCC, 0xA6
RSA_PSK_CHACHA20_POLY1305        0xCC, 0xA7

Comment 24

[Eric Rescorla (:ekr)]

This isn't stalled in either CFRG or the TLS WG. Here is the relevant passage
from the minutes:

"  Draft status update; see pages 5 and 6 of
   http://tools.ietf.org/agenda/92/slides/slides-92-tls-1.pdf   WG chairs
   intend to ask if WG wants to adopt
   draft-mavrogiannopoulos-chacha-tls, draft-josefsson-tls-curve25519 and
   draft-bmoeller-tls-falsestart as documents (starting points,"


I don't believe that the code point assignments in the draft are in fact
formally assigned (though it's of course possible that the TLS WG will
ask for the same assignments that Chrome is presently using).

Comment 25

[Dirkjan Ochtman (:djc)]

RFC 7539 has been published: https://www.rfc-editor.org/info/rfc7539.

Comment 26

[twr2600]

Is this good to go? The RFC has been published and it's not stalled in either CFRG or the TLS WG.
(https://bugzilla.mozilla.org/show_bug.cgi?id=917571#c24)

Comment 27

[Eric Rescorla (:ekr)]

No. The code points haven't been assigned yet and there is active discussion in the TLS WG about the details.

Comment 28

[sjw]

The PQCRYPTO team of the European Union recommends Salsa20: http://pqcrypto.eu.org/docs/initial-recommendations.pdf
(server seems to be down atm)

Comment 29

[Martin Thomson [:mt:]]

Comment on attachment 820740 [details] [diff] [review]
patch v3, by Adam Langley

Review of attachment 820740 [details] [diff] [review]:
-----------------------------------------------------------------

A few things need to be fixed here, but I don't see many structural issues.

::: lib/freebl/Makefile
@@ +460,5 @@
>  
> +ifeq ($(CPU_ARCH),x86_64)
> +    # poly1305-donna-x64-sse2-incremental-source.c requires __int128 support
> +    # in GCC 4.6.0.
> +    #EXTRA_SRCS += poly1305/poly1305-donna-x64-sse2-incremental-source.c

We should be detecting gcc version (we have detection code for 4.8 already) and including this.  Otherwise we have dead code checked in.

::: lib/freebl/chacha20/chacha20.c
@@ +9,5 @@
> +
> +#include "prtypes.h"
> +#include "chacha20.h"
> +
> +#define ROTL32(v, n) (((v) << (n)) | ((v) >> (32 - (n))))

We have code elsewhere that uses intrinsics for this.  See lib/freebl/sha512.c for instance:

#if defined(_MSC_VER)
#pragma intrinsic (_lrotr, _lrotl) 
#define ROTR32(x,n) _lrotr(x,n)
#define ROTL32(x,n) _lrotl(x,n)
#else
#define ROTR32(x,n) ((x >> n) | (x << ((8 * sizeof x) - n)))
#define ROTL32(x,n) ((x << n) | (x >> ((8 * sizeof x) - n)))
#endif

::: lib/freebl/chacha20poly1305.c
@@ +122,5 @@
> +    ChaCha20XOR(block, block, sizeof(block), ctx->key, nonce, 0);
> +    ChaCha20XOR(output, input, inputLen, ctx->key, nonce, 1);
> +
> +    Poly1305Do(tag, ad, adLen, output, inputLen, block);
> +    memcpy(output + inputLen, tag, ctx->tagLen);

PORT_Memcpy throughout.

@@ +152,5 @@
> +	PORT_SetError(SEC_ERROR_OUTPUT_LEN);
> +	return SECFailure;
> +    }
> +
> +    memset(block, 0, sizeof(block));

PORT_Memset throughout.

::: lib/freebl/poly1305/poly1305-donna-x64-sse2-incremental-source.c
@@ +311,5 @@
> +		T4 = _mm_add_epi64(T4, M4);
> +
> +		/* reduce */
> +		C1 = _mm_srli_epi64(T0, 26); C2 = _mm_srli_epi64(T3, 26); T0 = _mm_and_si128(T0, MMASK); T3 = _mm_and_si128(T3, MMASK); T1 = _mm_add_epi64(T1, C1); T4 = _mm_add_epi64(T4, C2);
> +		C1 = _mm_srli_epi64(T1, 26); C2 = _mm_srli_epi64(T4, 26); T1 = _mm_and_si128(T1, MMASK); T4 = _mm_and_si128(T4, MMASK); T2 = _mm_add_epi64(T2, C1); T0 = _mm_add_epi64(T0, _mm_mul_epu32(C2, FIVE));

80 columns.

::: lib/ssl/ssl3con.c
@@ +2025,4 @@
>      pwSpec->client.write_mac_context = NULL;
>      pwSpec->server.write_mac_context = NULL;
>  
> +    if (calg == calg_aes_gcm || calg == calg_chacha20) {

I wonder if we can't get to type_aead somehow here.

Comment 30

[Tim Taubert [:ttaubert] (inactive)]

Here's a new patch based on Adam's last one:

https://codereview.appspot.com/277040044

I've adapted it to use a 96-bit nonce and 32-bit block count (per RFC 7539), added gtests for the PK11 API and finished the freebl tests. Most of it is clang-formatted with Franziskus' settings, except overlong lines implementing the core of the cipher. I can wrap those at 80 columns and use one line per statement if that's wanted.

bltests and gtests succeed with any of the three possible compiler/arch combinations (x86, x86_64, x86_64 + GCC 4.6+).

I removed the parts touching TLS for now, I think we should move that to a separate bug and possibly do it after ekr landed his TLS 1.3 patch to avoid conflicts.

Comment 31

[Eric Rescorla (:ekr)]

I don't think it should be a problem to land a patch for this before TLS 1.3 as
long as it's otherwise fine. I can rebase as needed.

Comment 32

[sjw]

Note: Goolge priorize ChaCha on Android devices, because the cpu of smartphones and tablets doesn't support AES-NI (hardware side AES). As Google said, this improoved TLS performance a lot. Also Cloudflare supports ChaCha ciphers and got similar results.

So it would be really intressting for us to have this on Firefox OS, hopefully before TLS 1.3 :)

Comment 33

[Tim Taubert [:ttaubert] (inactive)]

(In reply to Eric Rescorla (:ekr) from comment #31)
> I don't think it should be a problem to land a patch for this before TLS 1.3
> as long as it's otherwise fine. I can rebase as needed.

Ok, cool. Will work on TLS integration in a follow-up, but start the work now. Shouldn't be a lot of work anyway because Adam did the bulk of that already.

Comment 34

[Martin Thomson [:mt:]]

r+ in rietveld.

Comment 35

[sjw]

OpenSSL 1.1.0 will support ChaCha20+Poly1305
https://github.com/openssl/openssl/commit/7dcb21869bec05d574d55e4c29daa5d58480d2a1

Comment 36

[Tim Taubert [:ttaubert] (inactive)]

Patch updated: https://codereview.appspot.com/277040044/

Martin, Wan-Teh, can you both please take another look?

Comment 37

[Martin Thomson [:mt:]]

r=mt

Comment 38

[Chris Newman]

Per comment #13, can I request that this be added under a compiler conditional? When NSS is used in a US product, that product requires export approval and most vendors can only pick up new cryptographic algorithms in a feature release. This means we'll need to build without this cipher for patch releases. I doubt I'm the only NSS consumer with this issue. I believe it would be better for this project if it's easier for such consumers to stay current without forking.

Comment 39

[Chris]

Just to chip in here, not only do all cloudflare sites use this cipher, but cloudflare supply a working patch against openssl 1.0.2 so the amount of servers based on openssl will probably be slowly growing as well that support chacha20, I have rolled it out to a couple of servers during the past week.

However my thread on ssllabs https://community.qualys.com/thread/15922 revealed there is an old and new version of chacha ciphers which cloudflare uses the old variant.  The new variant is in chrome v50, I dont know which variant google web site's currently use but is very likely the old variant as its not hit chrome stable yet.  Just something for mozilla dev's to be aware off.

Comment 40

[Tim Taubert [:ttaubert] (inactive)]

(In reply to Chris from comment #39)
> However my thread on ssllabs https://community.qualys.com/thread/15922
> revealed there is an old and new version of chacha ciphers which cloudflare
> uses the old variant.  The new variant is in chrome v50, I dont know which
> variant google web site's currently use but is very likely the old variant
> as its not hit chrome stable yet.  Just something for mozilla dev's to be
> aware off.

Yes, the old variant as supported by Chrome pre-v50 has CSIDs 0xCC13-15, where as the new draft [1] defines ChaCha cipher suites from 0xCCA8-AE, we will only support A8-AA for now.

[1] https://tools.ietf.org/html/draft-ietf-tls-chacha20-poly1305-04

Comment 41

[Tim Taubert [:ttaubert] (inactive)]

(In reply to Chris Newman from comment #38)
> Per comment #13, can I request that this be added under a compiler
> conditional? When NSS is used in a US product, that product requires export
> approval and most vendors can only pick up new cryptographic algorithms in a
> feature release. This means we'll need to build without this cipher for
> patch releases. I doubt I'm the only NSS consumer with this issue. I believe
> it would be better for this project if it's easier for such consumers to
> stay current without forking.

I will look into making ChaCha cipher suites available only if the cipher itself is available. We might have code that does that already but I need to check. If we then conditionally compile the cipher you should not have to fork NSS.

Comment 42

[Tim Taubert [:ttaubert] (inactive)]

I will take care of conditionally compiling ChaCha20/Poly1305 in a follow-up that will have to land before we release the next version.

Comment 43

[Tim Taubert [:ttaubert] (inactive)]

(In reply to Tim Taubert [:ttaubert] from comment #36)
> Patch updated: https://codereview.appspot.com/277040044/

Martin, can you please take another look at the coreconf/Werror.mk and lib/freebl/Makefile changes in patch set 7? I rebased it on top of the changes you landed yesterday.

Comment 44

[Tim Taubert [:ttaubert] (inactive)]

https://hg.mozilla.org/projects/nss/rev/f4a05e89dfad

Will file follow-ups later today and start working on them.

Comment 45

[Tim Taubert [:ttaubert] (inactive)]

Backed out due to Windows bustage:

https://hg.mozilla.org/projects/nss/rev/b32c1401102b

Comment 46

[Tim Taubert [:ttaubert] (inactive)]

The proposed fixes for Windows builds are here:

https://codereview.appspot.com/290130043/

And have r+ from ekr. Will fold them into the existing patches.

Comment 47

[Tim Taubert [:ttaubert] (inactive)]

https://hg.mozilla.org/projects/nss/rev/db4f87eed8ff

Comment 48

[Tim Taubert [:ttaubert] (inactive)]

Pushed another bustage fix for Windows 7 builds:

https://hg.mozilla.org/projects/nss/rev/d5caccdaa28d

Comment 49

[Tim Taubert [:ttaubert] (inactive)]

Had to back out again, there was some more breakage and I didn't want to block the tree for too long:

https://hg.mozilla.org/projects/nss/rev/74597951379c
https://hg.mozilla.org/projects/nss/rev/2ce7bb639b44

Comment 50

[Tim Taubert [:ttaubert] (inactive)]

Will merge the Windows XP build fixes [1] with r=wtc into this patch.

[1] https://codereview.appspot.com/285450043/

Comment 51

[Tim Taubert [:ttaubert] (inactive)]

https://hg.mozilla.org/projects/nss/rev/b7b1d793bc64

Comment 52

[Tim Taubert [:ttaubert] (inactive)]

Mysteriously, cmd/blapitest was failing and it turns out I forgot to add some AADs and IVs. I'm sure these were passing before I pushed last...

https://hg.mozilla.org/projects/nss/rev/ac1ad4ae73c7