Add chacha20/poly1305 and chacha20poly1305

jonasschnelli commented at 3:11 pm on August 24, 2018: contributor

This adds ChaCha20 and Poly1305 and the openSSH form of the AEAD.

The implementations of ChaCha20 are from DJB himself and directly taken (unchanged as much as possible) from the openSSH source code: https://github.com/openssh/openssh-portable/blob/master/chacha.c

Poly1305 is written by Andrew Moon is also directly taken (unchanged as much as possible) from the openSSH source code: https://github.com/openssh/openssh-portable/blob/master/poly1305.c

The code for the ChaCha20/Poly1305@openssh AEAD is taken from https://github.com/openssh/openssh-portable/blob/master/cipher-chachapoly.c with minimal changes.

More details on the AEAD construction: https://github.com/openssh/openssh-portable/blob/master/PROTOCOL.chacha20poly1305 https://gist.github.com/jonasschnelli/c530ea8421b8d0e80c51486325587c52

Test vectors are taken from the RFC draft: https://tools.ietf.org/html/draft-agl-tls-chacha20poly1305-04#section-7

Taking existing implementations should reduce risks of screwing up at the implementation level.

OUT OF SCOPE:

AVX,SSE acceleration (possible, see libsodium a.s.o.)
To Bitcoin Core adjusted C++ implementations
Combining with the existing ChaCha20 RNG (can all be done later, after verification of the correctness)

This is a subset of #14032 and a pre-requirement for BIP151.

DrahtBot commented at 3:49 pm on August 24, 2018: member

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Conflicts

Reviewers, this pull request conflicts with the following ones:

#15649 (Add ChaCha20Poly1305@Bitcoin AEAD by jonasschnelli)
#15519 (Add Poly1305 implementation by jonasschnelli)
#15512 (Add ChaCha20 encryption option (XOR) by jonasschnelli)
#14047 (Add HKDF_HMAC256_L32 and method to negate a private key by jonasschnelli)
#14032 (Add p2p layer encryption with ECDH/ChaCha20Poly1305 by jonasschnelli)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

DesWurstes commented at 7:09 am on August 25, 2018: contributor

Why not reuse the existing ChaCha20?

laanwj added the label P2P on Aug 25, 2018

jonasschnelli commented at 11:59 am on August 27, 2018: contributor

@DesWurstes: see PR description (out of scope).

jonasschnelli commented at 7:37 pm on August 27, 2018: contributor

Added benchmark for the AEAD (and for direct comparison also added the dbl-SHA (HASH) benchmark). Benchmarking 1MB data as well as 256bytes.

My system reports (!we compare SSE4 SHA256 vs non-optimized chacha20):

0# Benchmark, evals, iterations, total, min, max, median
1CHACHA20POLY1305AEAD_BIG, 5, 340, 3.68279, 0.00215035, 0.00219169, 0.00216025
2CHACHA20POLY1305AEAD_SMALL, 5, 250000, 1.08673, 8.51516e-07, 8.93585e-07, 8.61119e-07
3HASH256_BIG, 5, 340, 3.81384, 0.00222589, 0.00226436, 0.00224086
4HASH256_SMALL, 5, 250000, 1.1305, 8.96669e-07, 9.15482e-07, 9.03866e-07

jonasschnelli force-pushed on Aug 28, 2018

jonasschnelli referenced this in commit 955ac1d876 on Aug 29, 2018

in src/crypto/chachapoly_aead.cpp:30 in 90702f472e outdated

25+
26+    /* As best as we can tell, this is sufficient to break any optimisations that
27+       might try to eliminate "superfluous" memsets. If there's an easy way to
28+       detect memset_s, it would be better to use that. */
29+#if defined(_MSC_VER)
30+    SecureZeroMemory(ptr, len);

ken2812221 commented at 5:17 pm on August 29, 2018:

Seems this should include windows.h

jonasschnelli force-pushed on Aug 30, 2018

jonasschnelli force-pushed on Aug 31, 2018

in src/crypto/chachapoly_aead.h:18 in ac477bcf8b outdated

13+                          int keylen);
14+int chacha20poly1305_crypt(struct chachapolyaead_ctx *ctx, uint32_t seqnr,
15+                           uint8_t *dest, const uint8_t *src, uint32_t len,
16+                           uint32_t aadlen, int is_encrypt);
17+
18+// extracts the LE 24bit (3byte) length from the AAD and puts it into a uint32_t (host endiannes)

practicalswift commented at 9:05 pm on September 1, 2018:

Typo found by codespell: endiannes

jonasschnelli commented at 8:47 am on September 2, 2018:

Fixed.

jonasschnelli force-pushed on Sep 2, 2018

in src/test/crypto_tests.cpp:590 in 995c41af1b outdated

585+       Testvectors have been taken from the draft RFC
586+       https://tools.ietf.org/html/draft-agl-tls-chacha20poly1305-04#section-7
587+    */
588+
589+    static const struct chacha20_testvector chacha20_testvectors[] = {
590+        {{0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,

Sjors commented at 10:33 am on September 2, 2018:

This would be much easier to verify against the RFC document if you parse a hex string.

in src/crypto/poly1305.cpp:24 in 09ec49ba31 outdated

19+    (p)[1] = (uint8_t)((v) >> 8);                                              \
20+    (p)[2] = (uint8_t)((v) >> 16);                                             \
21+    (p)[3] = (uint8_t)((v) >> 24);                                             \
22+  } while (0)
23+
24+void poly1305_auth(unsigned char out[POLY1305_TAGLEN], const unsigned char *m,

Sjors commented at 10:44 am on September 2, 2018:

Why did you remove the poly1305_init, poly1305_update, poly1305_finish separation?

jonasschnelli commented at 10:58 am on September 2, 2018:

Which separation? I took Andrew Moons implementation found at https://github.com/openssh/openssh-portable/blob/90e51d672711c19a36573be1785caf35019ae7a8/poly1305.c

Sjors commented at 11:09 am on September 2, 2018:

Ah, I see, in that case the source code URL at the top of the file is confusing; probably should add a link to Moons’ implementation instead / in addition.

in src/crypto/chacha.cpp:77 in 09ec49ba31 outdated

72+  x->input[1] = U8TO32_LITTLE(constants + 4);
73+  x->input[2] = U8TO32_LITTLE(constants + 8);
74+  x->input[3] = U8TO32_LITTLE(constants + 12);
75+}
76+
77+void chacha_ivsetup(chacha_ctx *x, const u8 *iv, const u8 *counter) {

Sjors commented at 10:48 am on September 2, 2018:

I can confirm this function in 09ec49ba31867187cecd631593d37bcc5f3ca72f is identical to the original at de624c626ea081929df000b09932dbc804eda51d, modulo some whitespace.

Sjors commented at 10:53 am on September 2, 2018: member

Re out of scope “Combining with the existing ChaCha20 RNG”: perhaps you can add some tests to show they’re identical?

jonasschnelli commented at 10:59 am on September 2, 2018: contributor

@Sjors The existing ChaCha20 implementation doesn’t do the XORing and can therefore only be used for the RNG.

sipa commented at 11:34 am on September 2, 2018: member

Instead of those U8TOU32_LE macros you can use our own function (ReadLE32, WriteLE32).

jonasschnelli commented at 11:44 am on September 2, 2018: contributor

@sipa: agree. Though as written in the PR description. I’d like to keep the code (extracted from openSSH) as identical as possible. I think (or hope) we can do refactoring after this has been merged.

in src/crypto/chachapoly_aead.cpp:88 in d415a02a48 outdated

80+
81+  uint64_t seqnr64 = htole64(seqnr); //use LE for the nonce
82+  chacha_ivsetup(&ctx->header_ctx, (uint8_t *)&seqnr64, NULL);
83+  chacha_encrypt_bytes(&ctx->header_ctx, ciphertext, buf, 3);
84+  *len24_out = 0;
85+  *len24_out = buf[0] | (buf[1] << 8) | (buf[2] << 16);

practicalswift commented at 9:49 am on September 12, 2018:

This seems like a mistake? *len24_out is assigned twice? *len24_out = 0; should be removed? :-)

jonasschnelli commented at 12:54 pm on October 1, 2018:

I’m not sure if applying 3 time a uint_8t (24bits) the way its done here will guarantee to set the other 8 bits to 0. This is why I initialise with 0, then set bit 0 to 23. Could be that I’m wrong though.

practicalswift commented at 3:16 pm on October 1, 2018:

We wouldn’t initialise before assignment if the RHS was an integer, right? :-)

buf[0] | (buf[1] << 8) | (buf[2] << 16) evaluates to an integer.

But don’t trust me – I’m just a fellow human.

Let’s verify using our favourite C++ interpreter cling:

 0$ cling
 1
 2****************** CLING ******************
 3* Type C++ code and press enter to run it *
 4*             Type .q to exit             *
 5*******************************************
 6[cling]$ typeid(1).name()
 7(const char *) "i"
 8[cling]$ #include <cstdint>
 9[cling]$ uint8_t buf[3] = {1, 2, 3}
10(uint8_t [3]) { '0x01', '0x02', '0x03' }
11[cling]$ typeid(buf[0] | (buf[1] << 8) | (buf[2] << 16)).name()
12(const char *) "i"
13[cling]$ buf[0] | (buf[1] << 8) | (buf[2] << 16)
14(int) 197121

:-)

in src/crypto/poly1305.cpp:186 in d415a02a48 outdated

181+  h1 = (h1 & nb) | (g1 & b);
182+  h2 = (h2 & nb) | (g2 & b);
183+  h3 = (h3 & nb) | (g3 & b);
184+  h4 = (h4 & nb) | (g4 & b);
185+
186+  f0 = ((h0) | (h1 << 26)) + (uint64_t)U8TO32_LE(&key[16]);

practicalswift commented at 9:52 am on September 12, 2018:

Just to double check: This bit shifting takes place on a 32-bit value which is then expanded to a 64-bit type. That is the intention? Applies to h1 << 26, h2 << 20, h3 << 14 and h4 << 8.

jonasschnelli commented at 12:55 pm on October 1, 2018:

Looks like. This has been taken from openSSH (https://github.com/openssh/openssh-portable/blob/90e51d672711c19a36573be1785caf35019ae7a8/poly1305.c).

in src/test/crypto_tests.cpp:758 in d415a02a48 outdated

753+    uint32_t out_len = 0;
754+    chacha20poly1305_get_length24(&aead_ctx, &out_len, seqnr, ciphertext_buf);
755+    assert(out_len == 255);
756+    chacha20poly1305_crypt(&aead_ctx, seqnr, plaintext_buf_new, ciphertext_buf,
757+        252, 3, 0);
758+    assert(memcmp(plaintext_buf, plaintext_buf_new, 252) == 0);

practicalswift commented at 3:08 pm on September 12, 2018:

Shouldn’t this be assert(memcmp(plaintext_buf, plaintext_buf_new, 255) == 0); or assert(memcmp(plaintext_buf, plaintext_buf_new, sizeof(plaintext_buf)) == 0);?

in src/crypto/poly1305.cpp:176 in d415a02a48 outdated

171+  b = g2 >> 26;
172+  g2 &= 0x3ffffff;
173+  g3 = h3 + b;
174+  b = g3 >> 26;
175+  g3 &= 0x3ffffff;
176+  g4 = h4 + b - (1 << 26);

practicalswift commented at 3:50 pm on September 30, 2018:

An unsigned integer wraparound takes place here which is triggered by the tests. Worth adding a comment to make it clear it is intentional?

jonasschnelli commented at 12:44 pm on October 1, 2018:

Its upstream code from openssh,.. the plan is to refactor this to c++ after initial merge to master.

in src/crypto/chachapoly_aead.cpp:37 in d415a02a48 outdated

32+int chacha20poly1305_crypt(struct chachapolyaead_ctx *ctx, uint32_t seqnr,
33+                           uint8_t *dest, const uint8_t *src, uint32_t len,
34+                           uint32_t aadlen, int is_encrypt) {
35+  const uint8_t one[8] = {1, 0, 0, 0, 0, 0, 0, 0}; /* NB little-endian */
36+  uint8_t expected_tag[POLY1305_TAGLEN], poly_key[POLY1305_KEYLEN];
37+  int r = -1;

practicalswift commented at 3:53 pm on September 30, 2018:

This is a dead store :-)

Initialize to zero instead and remove the r = 0 below?

in src/crypto/chachapoly_aead.cpp:46 in d415a02a48 outdated

37+  int r = -1;
38+
39+  uint64_t seqnr64 = seqnr;
40+  uint64_t chacha_iv = htole64(seqnr64);
41+  memset(poly_key, 0, sizeof(poly_key));
42+  chacha_ivsetup(&ctx->main_ctx, (uint8_t *)&chacha_iv, NULL);

practicalswift commented at 3:54 pm on September 30, 2018:

Use nullptr :-)

jonasschnelli commented at 12:51 pm on October 1, 2018:

I’d like to keep this as C code for now, the .cpp filename extension is for bypassing the CXXFLAGS/CFLAGS issue.

in src/crypto/chachapoly_aead.cpp:60 in d415a02a48 outdated

51+      goto out;
52+    }
53+  }
54+
55+  if (aadlen) {
56+    chacha_ivsetup(&ctx->header_ctx, (uint8_t *)&chacha_iv, NULL);

practicalswift commented at 3:54 pm on September 30, 2018:

Use nullptr :-)

Add chacha20/poly1305 and chacha20poly1305_AEAD from openssh 124a14f02e

QA: add ChaCha20/Poly1305 test vectors from the RFC draft ae68baa902

Add benchmark for ChaCha20Poly1305-openssh AEAD and dbl-SHA256 e65a41853d

in src/crypto/chachapoly_aead.cpp:85 in d415a02a48 outdated

77+                                uint32_t *len24_out, uint32_t seqnr,
78+                                const uint8_t *ciphertext) {
79+  uint8_t buf[3];
80+
81+  uint64_t seqnr64 = htole64(seqnr); //use LE for the nonce
82+  chacha_ivsetup(&ctx->header_ctx, (uint8_t *)&seqnr64, NULL);

practicalswift commented at 3:54 pm on September 30, 2018:

Use nullptr :-)

jonasschnelli force-pushed on Oct 1, 2018

jonasschnelli commented at 1:18 pm on October 1, 2018: contributor

Fixed points reported by @practicalswift

practicalswift commented at 8:37 am on December 7, 2018: contributor

I’m afraid this PR doesn’t compile when rebased on master

jonasschnelli commented at 4:14 pm on March 1, 2019: contributor

Partially superseded by #15512 (the ChaCha20 part)

jonasschnelli commented at 7:43 pm on March 24, 2019: contributor

Closing… It’s now replaced with #15512, #15519 and #15649.

jonasschnelli closed this on Mar 24, 2019

DrahtBot locked this on Dec 16, 2021

dhruv added this to the "Closed unmerged" column in a project

Add chacha20/poly1305 and chacha20poly1305_AEAD from openssh #14050

Conflicts