Add ChaCha20Poly1305@Bitcoin AEAD #15649

jonasschnelli commented at 9:00 PM on March 22, 2019: contributor

This adds a new AEAD (authenticated encryption with additional data) construct optimised for small messages (like used in Bitcoins p2p network).

Includes: #15519, #15512 (please review those first).

The construct is specified here. https://gist.github.com/jonasschnelli/c530ea8421b8d0e80c51486325587c52#ChaCha20Poly1305Bitcoin_Cipher_Suite

This aims for being used in v2 peer-to-peer messages.

jonasschnelli added the label P2P on Mar 22, 2019

jonasschnelli commented at 9:04 PM on March 22, 2019: contributor

Benchmark compared with dbl-SHA256 (Intel x86 and ARM64 both with enabled and supported SHA256 asm)

EDIT: Attention, those benchmark test a decryption that fails the MAC test (that's why its faster).

i7-8700 CPU @ 3.20GHz
# Benchmark, evals, iterations, total, min, max, median
CHACHA20_POLY1305_AEAD_1MB_DECRYPT, 5, 340, 0.974806, 0.000571213, 0.000575483, 0.000573147
CHACHA20_POLY1305_AEAD_1MB_ENCRYPT, 5, 340, 3.45589, 0.00200816, 0.00206032, 0.00203075
CHACHA20_POLY1305_AEAD_256BYTES_DECRYPT, 5, 250000, 0.353133, 2.7904e-07, 2.87463e-07, 2.81879e-07
CHACHA20_POLY1305_AEAD_256BYTES_ENCRYPT, 5, 250000, 0.844029, 6.69314e-07, 6.84823e-07, 6.73278e-07
CHACHA20_POLY1305_AEAD_64BYTES_DECRYPT, 5, 500000, 0.445114, 1.74585e-07, 1.79382e-07, 1.79109e-07
CHACHA20_POLY1305_AEAD_64BYTES_ENCRYPT, 5, 500000, 0.756779, 3.02316e-07, 3.03721e-07, 3.02433e-07
HASH_1MB, 5, 340, 4.05031, 0.00234962, 0.00239718, 0.00238811
HASH_256BYTES, 5, 250000, 1.13878, 9.01793e-07, 9.20163e-07, 9.1145e-07
HASH_64BYTES, 5, 500000, 1.19347, 4.71828e-07, 4.8229e-07, 4.76693e-07

RK3399 64-bit Hexa Core A72/A53 CPU (aarch64)
CPU Features	: fp asimd evtstrm aes pmull sha1 sha2 crc32
CHACHA20_POLY1305_AEAD_1MB_DECRYPT, 5, 340, 4.77829, 0.00277495, 0.00295277, 0.00277533
CHACHA20_POLY1305_AEAD_1MB_ENCRYPT, 5, 340, 12.8776, 0.00757471, 0.00757529, 0.00757509
CHACHA20_POLY1305_AEAD_256BYTES_DECRYPT, 5, 250000, 1.45431, 1.159e-06, 1.16777e-06, 1.16348e-06
CHACHA20_POLY1305_AEAD_256BYTES_ENCRYPT, 5, 250000, 3.15133, 2.51743e-06, 2.5251e-06, 2.52047e-06
CHACHA20_POLY1305_AEAD_64BYTES_DECRYPT, 5, 500000, 1.64303, 6.5714e-07, 6.57362e-07, 6.57166e-07
CHACHA20_POLY1305_AEAD_64BYTES_ENCRYPT, 5, 500000, 2.84952, 1.13826e-06, 1.14302e-06, 1.13909e-06
HASH_1MB, 5, 340, 11.9929, 0.00705427, 0.00705483, 0.00705473
HASH_256BYTES, 5, 250000, 3.44999, 2.75893e-06, 2.76146e-06, 2.75963e-06
HASH_64BYTES, 5, 500000, 3.68293, 1.47287e-06, 1.47352e-06, 1.4732e-06

DrahtBot commented at 10:35 PM on March 22, 2019: 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:

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

in src/bench/chacha_poly_aead.cpp:25 in 8dd9f11261 outdated

  20 | +static ChaCha20Poly1305AEAD aead(k1, 32, k2, 32);
  21 | +
  22 | +static void CHACHA20_POLY1305_AEAD(benchmark::State& state, size_t buffersize, bool encrypt)
  23 | +{
  24 | +    std::vector<unsigned char> in(buffersize + 3 + 16, 0);
  25 | +    std::vector<unsigned char> out(buffersize + 3 + 16, 0);

skwp commented at 7:40 PM on March 23, 2019:

not sure if these magic numbers are supposed to be obvious, but some named constants might be nice for people who are new to this stuff

jonasschnelli commented at 9:18 PM on March 26, 2019:

Thanks. Using the available constantes now.

in src/test/crypto_tests.cpp:701 in 3f5a4c745d outdated

 696 | +        cmp_ctx.SetIV(htole64(seqnr_aad));
 697 | +        cmp_ctx.Seek(0);
 698 | +        cmp_ctx.Output(nullptr, cmp_ctx_buffer.data(), 64);
 699 | +
 700 | +        // crypt the 3 length bytes and compare the length
 701 | +        uint64_t len_cmp = 0;

practicalswift commented at 9:24 AM on March 26, 2019:

Nit:

Shadows existing len_cmp and also redundant initialization to zero?

Could be just uint64_t len_cmp_inner = XOR(ciphertext_buf[0], …?

in src/test/crypto_tests.cpp:642 in 3f5a4c745d outdated

 677 | +    len_cmp = le32toh(len_cmp);
 678 | +    BOOST_CHECK_EQUAL(len_cmp, expected_aad_length);
 679 | +
 680 | +    // encrypt / decrypt 1000 packets
 681 | +    for (size_t i = 0; i < 1000; ++i) {
 682 | +        res = aead.Crypt(seqnr_payload, seqnr_aad, aad_pos, ciphertext_buf.data(), ciphertext_buf.size(), plaintext_buf.data(), plaintext_buf.size(), true);

practicalswift commented at 9:25 AM on March 26, 2019:

This res is never used. Should be checked?

jonasschnelli commented at 9:17 PM on March 26, 2019:

Thanks. Fixed.

in src/crypto/chacha_poly_aead.cpp:54 in 68617154ec outdated

  51 | +        // if we decrypt, make sure the source contains at least the expected AAD+MAC and the destination has at least space for the source - MAC
  52 | +        (!is_encrypt && (src_len < CHACHA20_POLY1305_AEAD_AAD_LEN + POLY1305_TAGLEN || dest_len < src_len - POLY1305_TAGLEN))) {
  53 | +        return false;
  54 | +    }
  55 | +
  56 | +    unsigned char expected_tag[POLY1305_TAGLEN], poly_key[POLY1305_KEYLEN];

practicalswift commented at 9:25 AM on March 26, 2019:

Scope can be reduced?

jonasschnelli commented at 9:15 PM on March 26, 2019:

You mean of expected_tag? Not sure it this makes things cleaner or more optimized.

Empact commented at 8:48 PM on May 27, 2019:

I would say it makes things cleaner by virtue of narrower scope. 🤷‍♂

promag commented at 7:07 AM on June 12, 2019:

I think it's fine as it is.

in src/test/crypto_tests.cpp:659 in 3f5a4c745d outdated

 654 | +    // create a chacha20 instance to compare against
 655 | +    ChaCha20 cmp_ctx(aead_K_2.data(), 32);
 656 | +
 657 | +    // encipher
 658 | +    bool res = aead.Crypt(seqnr_payload, seqnr_aad, aad_pos, ciphertext_buf.data(), ciphertext_buf.size(), plaintext_buf.data(), plaintext_buf.size(), true);
 659 | +    // make sure the opperation succeeded if expected to succeed

practicalswift commented at 9:26 AM on March 26, 2019:

Should be "operation" :-)

jonasschnelli commented at 9:17 PM on March 26, 2019:

Fixed

sipa commented at 7:48 PM on March 26, 2019: member

Why is encrypting ~3 times slower than decrypting?

jonasschnelli commented at 8:34 PM on March 26, 2019: contributor

Why is encrypting ~3 times slower than decrypting?

Because the decryption in the benchmark always fails the MAC check... facepalm. Currently fixing.

jonasschnelli force-pushed on Mar 26, 2019

jonasschnelli commented at 9:23 PM on March 26, 2019: contributor

Overhauled the AEAD benchmark, now it measures:

only encryption of 64, 256 and 1MB
encryption and decryption (also including the previous-to-decryption GetLength() call)

sipa commented at 10:01 PM on March 26, 2019: member

Feel like posting new numbers?

jonasschnelli commented at 10:09 PM on March 26, 2019: contributor

i7-8700 CPU @ 3.20GHz
# Benchmark, evals, iterations, total, min, max, median
CHACHA20_POLY1305_AEAD_1MB_ENCRYPT_DECRYPT, 5, 340, 6.89749, 0.00401996, 0.004089, 0.00405691
CHACHA20_POLY1305_AEAD_1MB_ONLY_ENCRYPT, 5, 340, 3.42802, 0.00199702, 0.00206066, 0.00200356
CHACHA20_POLY1305_AEAD_256BYTES_ENCRYPT_DECRYPT, 5, 250000, 1.73244, 1.38097e-06, 1.39262e-06, 1.38631e-06
CHACHA20_POLY1305_AEAD_256BYTES_ONLY_ENCRYPT, 5, 250000, 0.866814, 6.89058e-07, 6.98332e-07, 6.92555e-07
CHACHA20_POLY1305_AEAD_64BYTES_ENCRYPT_DECRYPT, 5, 500000, 1.61924, 6.33995e-07, 6.61294e-07, 6.45421e-07
CHACHA20_POLY1305_AEAD_64BYTES_ONLY_ENCRYPT, 5, 500000, 0.794098, 3.15846e-07, 3.22632e-07, 3.16612e-07
HASH_1MB, 5, 340, 4.02255, 0.00233675, 0.00239431, 0.00236953
HASH_256BYTES, 5, 250000, 1.14968, 9.16826e-07, 9.2569e-07, 9.17793e-07
HASH_64BYTES, 5, 500000, 1.20545, 4.78177e-07, 4.87008e-07, 4.80163e-07

RK3399 64-bit Hexa Core A72/A53 CPU (aarch64)
CPU Features	: fp asimd evtstrm aes pmull sha1 sha2 crc32
CHACHA20_POLY1305_AEAD_1MB_ENCRYPT_DECRYPT, 5, 340, 25.8159, 0.0151542, 0.015309, 0.0151552
CHACHA20_POLY1305_AEAD_1MB_ONLY_ENCRYPT, 5, 340, 12.8818, 0.00757678, 0.00757883, 0.00757744
CHACHA20_POLY1305_AEAD_256BYTES_ENCRYPT_DECRYPT, 5, 250000, 6.28925, 5.02614e-06, 5.0389e-06, 5.0307e-06
CHACHA20_POLY1305_AEAD_256BYTES_ONLY_ENCRYPT, 5, 250000, 3.1574, 2.5177e-06, 2.53455e-06, 2.52181e-06
CHACHA20_POLY1305_AEAD_64BYTES_ENCRYPT_DECRYPT, 5, 500000, 5.67636, 2.26775e-06, 2.27397e-06, 2.26921e-06
CHACHA20_POLY1305_AEAD_64BYTES_ONLY_ENCRYPT, 5, 500000, 2.85557, 1.13888e-06, 1.14831e-06, 1.14157e-06
HASH_1MB, 5, 340, 11.9764, 0.00704443, 0.0070454, 0.00704505
HASH_256BYTES, 5, 250000, 3.43234, 2.74542e-06, 2.74639e-06, 2.74585e-06
HASH_64BYTES, 5, 500000, 3.6589, 1.4629e-06, 1.46428e-06, 1.46323e-06

in src/bench/chacha_poly_aead.cpp:35 in a07f18c62c outdated

  29 | +    uint64_t seqnr_aad = 0;
  30 | +    int aad_pos = 0;
  31 | +    uint32_t len = 0;
  32 | +    while (state.KeepRunning()) {
  33 | +        // encrypt or decrypt the buffer with a static key
  34 | +        assert(aead.Crypt(seqnr_payload, seqnr_aad, aad_pos, out.data(), out.size(), in.data(), buffersize, true));

practicalswift commented at 9:28 AM on March 27, 2019:

Could be bool ok = aead.Crypt(…); assert(ok); to guarantee side-effect free use of assert(...);?

in src/bench/chacha_poly_aead.cpp:40 in a07f18c62c outdated

  34 | +        assert(aead.Crypt(seqnr_payload, seqnr_aad, aad_pos, out.data(), out.size(), in.data(), buffersize, true));
  35 | +
  36 | +        if (include_decryption) {
  37 | +            // if we decrypt, include the GetLength
  38 | +            assert(aead.GetLength(&len, seqnr_aad, aad_pos, in.data()));
  39 | +            assert(aead.Crypt(seqnr_payload, seqnr_aad, aad_pos, out.data(), out.size(), in.data(), buffersize, true));

practicalswift commented at 9:30 AM on March 27, 2019:

Same here :-)

DrahtBot added the label Needs rebase on Mar 27, 2019

jonasschnelli force-pushed on Mar 27, 2019

jonasschnelli commented at 4:40 PM on March 27, 2019: contributor

rebased

DrahtBot removed the label Needs rebase on Mar 27, 2019

in src/crypto/chacha_poly_aead.cpp:123 in 63851d38e5 outdated

 118 | +        m_chacha_header.Seek(0);                                                        // block counter 0
 119 | +        m_chacha_header.Output(nullptr, m_aad_keystream_buffer, CHACHA20_ROUND_OUTPUT); // write keystream to the cache
 120 | +    }
 121 | +
 122 | +    // decrypt the ciphertext length by XORing the right position of the 64byte keystream cache with the ciphertext
 123 | +    *len24_out = 0;

practicalswift commented at 7:40 AM on April 2, 2019:

*len24_out = 0; here serves no purpose AFAICT since assigned on the next line?

jonasschnelli commented at 7:54 AM on May 10, 2019:

Fixed.

jonasschnelli force-pushed on May 10, 2019

jonasschnelli commented at 7:53 AM on May 10, 2019: contributor

Rebased

jonasschnelli force-pushed on May 10, 2019

jonasschnelli commented at 1:45 PM on May 11, 2019: contributor

Here are some number of the comparison against the @openSSH form of the AEAD (quick implementation is here) on Intel i7 and RK [arm64])

There are moderate gains with our @Bitcoin AEAD construct especially for 64byte messages (~1.4 times faster)

I also added HASH (dbl sha256) with no asm (to compare apples with apples since ChaCha20 is also not NI accelerated).

i7-8700 CPU @ 3.20GHz

ChaCha20Poly1305AEAD@Bitcoin
CHACHA20_POLY1305_AEAD_1MB_ENCRYPT_DECRYPT, 5, 340, 6.96947, 0.00405818, 0.00418744, 0.00407654
CHACHA20_POLY1305_AEAD_1MB_ONLY_ENCRYPT, 5, 340, 3.483, 0.00202816, 0.00208079, 0.00204615
CHACHA20_POLY1305_AEAD_256BYTES_ENCRYPT_DECRYPT, 5, 250000, 1.72781, 1.35975e-06, 1.44466e-06, 1.36874e-06
CHACHA20_POLY1305_AEAD_256BYTES_ONLY_ENCRYPT, 5, 250000, 0.883109, 6.80501e-07, 7.98644e-07, 6.83484e-07
CHACHA20_POLY1305_AEAD_64BYTES_ENCRYPT_DECRYPT, 5, 500000, 1.58456, 6.14057e-07, 6.57714e-07, 6.38866e-07
CHACHA20_POLY1305_AEAD_64BYTES_ONLY_ENCRYPT, 5, 500000, 0.791489, 3.05361e-07, 3.57775e-07, 3.062e-07

ChaCha20Poly1305AEAD@OpenSSH
CHACHA20_POLY1305_OPENSSH_AEAD_1MB_ENCRYPT_DECRYPT, 5, 340, 7.0763, 0.00410207, 0.00423358, 0.00416736
CHACHA20_POLY1305_OPENSSH_AEAD_1MB_ONLY_ENCRYPT, 5, 340, 3.50153, 0.00202787, 0.00211423, 0.00204805
CHACHA20_POLY1305_OPENSSH_AEAD_256BYTES_ENCRYPT_DECRYPT, 5, 250000, 2.10268, 1.64571e-06, 1.76881e-06, 1.66784e-06
CHACHA20_POLY1305_OPENSSH_AEAD_256BYTES_ONLY_ENCRYPT, 5, 250000, 0.990221, 7.72714e-07, 8.65131e-07, 7.74143e-07
CHACHA20_POLY1305_OPENSSH_AEAD_64BYTES_ENCRYPT_DECRYPT, 5, 500000, 2.29661, 9.06308e-07, 9.4192e-07, 9.1748e-07
CHACHA20_POLY1305_OPENSSH_AEAD_64BYTES_ONLY_ENCRYPT, 5, 500000, 1.03205, 4.03511e-07, 4.38993e-07, 4.05953e-07

(NO ASM DBL-SHA256)
HASH_1MB, 5, 340, 6.18416, 0.003603, 0.0036835, 0.00363839
HASH_256BYTES, 5, 250000, 1.84485, 1.45055e-06, 1.53387e-06, 1.46062e-06
HASH_64BYTES, 5, 500000, 1.81658, 7.14499e-07, 7.56105e-07, 7.21112e-07

RK3399 64-bit Hexa Core A72/A53 CPU (aarch64)
CHACHA20_POLY1305_AEAD_1MB_ENCRYPT_DECRYPT, 5, 340, 25.8472, 0.015143, 0.0153498, 0.0151757
CHACHA20_POLY1305_AEAD_1MB_ONLY_ENCRYPT, 5, 340, 12.8757, 0.00756406, 0.00758074, 0.00757862
CHACHA20_POLY1305_AEAD_256BYTES_ENCRYPT_DECRYPT, 5, 250000, 6.44229, 5.15237e-06, 5.1555e-06, 5.15375e-06
CHACHA20_POLY1305_AEAD_256BYTES_ONLY_ENCRYPT, 5, 250000, 3.22662, 2.57975e-06, 2.58201e-06, 2.5817e-06
CHACHA20_POLY1305_AEAD_64BYTES_ENCRYPT_DECRYPT, 5, 500000, 5.96034, 2.37337e-06, 2.38984e-06, 2.38668e-06
CHACHA20_POLY1305_AEAD_64BYTES_ONLY_ENCRYPT, 5, 500000, 2.97761, 1.18648e-06, 1.19878e-06, 1.18715e-06

CHACHA20_POLY1305_OPENSSH_AEAD_1MB_ENCRYPT_DECRYPT, 5, 340, 25.7817, 0.0151531, 0.0151865, 0.0151633
CHACHA20_POLY1305_OPENSSH_AEAD_1MB_ONLY_ENCRYPT, 5, 340, 12.8959, 0.00757261, 0.00759154, 0.00758821
CHACHA20_POLY1305_OPENSSH_AEAD_256BYTES_ENCRYPT_DECRYPT, 5, 250000, 7.6112, 6.08182e-06, 6.10197e-06, 6.08393e-06
CHACHA20_POLY1305_OPENSSH_AEAD_256BYTES_ONLY_ENCRYPT, 5, 250000, 3.59548, 2.87162e-06, 2.87949e-06, 2.87783e-06
CHACHA20_POLY1305_OPENSSH_AEAD_64BYTES_ENCRYPT_DECRYPT, 5, 500000, 8.39425, 3.3108e-06, 3.53569e-06, 3.31353e-06
CHACHA20_POLY1305_OPENSSH_AEAD_64BYTES_ONLY_ENCRYPT, 5, 500000, 3.73337, 1.48799e-06, 1.49965e-06, 1.49489e-06

DrahtBot added the label Needs rebase on May 16, 2019

jonasschnelli force-pushed on May 16, 2019

DrahtBot removed the label Needs rebase on May 16, 2019

jonasschnelli added this to the "Mergeable" column in a project

jonasschnelli moved this from the "Mergeable" to the "Blockers" column in a project

in src/test/crypto_tests.cpp:646 in 02a73a8a00 outdated

 641 | +    BOOST_CHECK_EQUAL(len_cmp, expected_aad_length);
 642 | +
 643 | +    // encrypt / decrypt 1000 packets
 644 | +    for (size_t i = 0; i < 1000; ++i) {
 645 | +        res = aead.Crypt(seqnr_payload, seqnr_aad, aad_pos, ciphertext_buf.data(), ciphertext_buf.size(), plaintext_buf.data(), plaintext_buf.size(), true);
 646 | +        BOOST_CHECK_EQUAL(res, true);

Empact commented at 9:14 PM on May 27, 2019:

nit: BOOST_CHECK()

jonasschnelli commented at 8:07 AM on June 11, 2019:

Thanks. Fixed.

in src/test/crypto_tests.cpp:622 in 02a73a8a00 outdated

 619 | +
 620 | +    // encipher
 621 | +    bool res = aead.Crypt(seqnr_payload, seqnr_aad, aad_pos, ciphertext_buf.data(), ciphertext_buf.size(), plaintext_buf.data(), plaintext_buf.size(), true);
 622 | +    // make sure the operation succeeded if expected to succeed
 623 | +    BOOST_CHECK_EQUAL(res, must_succeed);
 624 | +    if (!res) return;

Empact commented at 9:18 PM on May 27, 2019:

How about splitting out TestChaCha20Poly1305AEADFails, rather than passing must_succeed?

jonasschnelli commented at 8:07 AM on June 11, 2019:

I think passing the must_succeed argument is fine and simpler.

Empact commented at 9:19 PM on May 27, 2019: member

I compared the implementation to http://bxr.su/OpenBSD/usr.bin/ssh/cipher-chachapoly.c and did not find any notable incongruities.

Disclaimer: I am not a cryptographer.

in src/test/crypto_tests.cpp:589 in 9985e3c87b outdated

 585 | @@ -585,6 +586,135 @@ BOOST_AUTO_TEST_CASE(hkdf_hmac_sha256_l32_tests)
 586 |                  "8da4e775a563c18f715f802a063c5a31b8a11f5c5ee1879ec3454e5f3c738d2d");
 587 |  }
 588 |  
 589 | +#define XOR(v, w) ((v) ^ (w))

laanwj commented at 12:56 PM on June 5, 2019:

What is the advantage of defining XOR as a macro here ? (same in chacha_poly_aead.cpp)

jonasschnelli commented at 10:14 AM on June 6, 2019:

I thought it improves readability (got inspired by DJBs code). But happy to remove it since it saves space.

laanwj commented at 10:56 AM on June 6, 2019:

It doesn't make the code more readable to me, at least. I recognize the C operator but the macro I had to look up. But I don't feel strongly about it.

jonasschnelli commented at 8:19 AM on June 11, 2019:

Removed the extra XOR macro.

promag commented at 1:46 PM on June 11, 2019:

🤔 there are still 6 XOR usages, is this intended?

jonasschnelli force-pushed on Jun 11, 2019

in src/crypto/chacha_poly_aead.cpp:71 in 95d24be0c4 outdated

  66 | +        const unsigned char* tag = src + src_len - POLY1305_TAGLEN;
  67 | +        poly1305_auth(expected_tag, src, src_len - POLY1305_TAGLEN, poly_key);
  68 | +
  69 | +        // constant time compare the calculated MAC with the provided MAC
  70 | +        if (timingsafe_bcmp(expected_tag, tag, POLY1305_TAGLEN) != 0) {
  71 | +            memory_cleanse(expected_tag, sizeof(expected_tag));

promag commented at 1:44 PM on June 11, 2019:

Could add a auxiliary function at the top like:

template <typename T>
void memory_cleanse(T v) {
    memory_cleanse(v, sizeof(T));
}

to prevent an invalid 2nd argument?

jonasschnelli commented at 6:54 AM on June 12, 2019:

Both cleansed values can only be POLY1305_TAGLEN and I think it's fine using the default memory_cleanse.

promag commented at 1:53 PM on June 11, 2019: member

Should delete ChaCha20Poly1305AEAD copy constructor?

I mean

 public:
     ChaCha20Poly1305AEAD(const unsigned char* K_1, size_t K_1_len, const unsigned char* K_2, size_t K_2_len);

+    explicit ChaCha20Poly1305AEAD(const ChaCha20Poly1305AEAD&) = delete;

jonasschnelli force-pushed on Jun 12, 2019

jonasschnelli commented at 7:00 AM on June 12, 2019: contributor

Removed the XOR macro in the test as well.

in src/crypto/chacha_poly_aead.h:131 in 21d07ab4fe outdated

 124 | +
 125 | +public:
 126 | +    ChaCha20Poly1305AEAD(const unsigned char* K_1, size_t K_1_len, const unsigned char* K_2, size_t K_2_len);
 127 | +
 128 | +    /** Encrypts/decrypts a packet
 129 | +        seqnr_payload, the message sequence number

elichai commented at 1:15 AM on June 17, 2019:

Is the "message sequence number" randomly generate or is it a counter?

Could it be reseted while the key will still be in use?

elichai commented at 1:16 AM on June 17, 2019:

A. If it could get reseted without getting rid of the key this is not a good source for the nonce.

B. If it's randomly generated then 64bit isn't secure enough. We should either move to the chacha20 from the RFC which has 96bit nonce and 32bit counter or increment it manually every time.

sipa commented at 1:47 AM on June 17, 2019:

@elichai I think discussion of the proposed AEAD should probably go on the mailing list discussing the BIP (https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-March/016806.html). Comments here should probably be just about implementation, or on discrepancies between the implementation and the BIP.

sipa commented at 1:49 AM on June 17, 2019:

That said, I believe the sequence number is a simple counter, counting up from 0, incrementing by one for every message. It will get reset only when rekeying. Note that the security of ChaCha20 does not rely on the nonce being unpredictable, just on not reusing one, so it doesn't need any entropy.

elichai commented at 2:00 AM on June 17, 2019:

I'll move it to the mailing list thanks.

jonasschnelli commented at 2:50 PM on June 18, 2019:

This has been resolved on the mailing list: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-June/017034.html

jonasschnelli force-pushed on Jun 18, 2019

jonasschnelli commented at 3:50 PM on June 18, 2019: contributor

Followed the advice by @promag and added default constructor avoidance.

in src/crypto/chacha_poly_aead.cpp:56 in a6397f15a8 outdated

  51 | +        return false;
  52 | +    }
  53 | +
  54 | +    unsigned char expected_tag[POLY1305_TAGLEN], poly_key[POLY1305_KEYLEN];
  55 | +    memset(poly_key, 0, sizeof(poly_key));
  56 | +    m_chacha_main.SetIV(htole64(seqnr_payload));

laanwj commented at 3:15 PM on June 20, 2019:

are you sure the htole64 is correct here? SetIV is implemented as

void ChaCha20::SetIV(uint64_t iv)
{
    input[14] = iv;
    input[15] = iv >> 32;
}

where input is an array of 32-bit unsigned integers that are (afaik) always used in LE fashion with ReadLE32 / WriteLE32 when doing byte operations. htole64 flips the bytes of an integer on a big-endian platform so on LE, the output looks like

0      1       2        3        4        5        6        7
iv0..7 iv8..15 iv16..23 iv24..31 iv32..39 iv40..47 iv48..55 iv56.63

on BE, however you'd get

0       1         2        3        4        5        6       7      
iv56.63 iv48..55  iv40..47 iv32..39 iv24..31 iv16..23 iv8..15 iv0..7

I might be wrong, but this needs testing on a big-endian platform.

If it is necessary: as you always use SetIV with htole64, might make sense to move it into it.

elichai commented at 4:49 PM on June 20, 2019:

I think it is necessary, because even though input is always used with ReadLE32/WriteLE32 when you shift the iv and split it into input[14] and input[15] you'll get different results in BE or LE platforms. (unless you use htole64 or something equivalent to make sure that the bits are sorted the same way)

But I do agree that this should be part of the chacha20 implementation. because this is what requires that everything will be LE.

sipa commented at 5:22 PM on June 20, 2019:

There should not be any need for byteswapping. The IV is specified as an integer before serialization. The ChaCha20 implementation uses the LE serialization of that number, even on BE platforms.

laanwj commented at 6:12 PM on June 20, 2019:

I think it is necessary, because even though input is always used with

If this is true, I still think it's done in the wrong way if the goal is to be consistent between LE and BE, you'd need a different kind of word-level swap. But I think @sipa is right here.

elichai commented at 9:09 PM on June 20, 2019:

The only thing that bothers me is the split using r/l shift. Chacha20 defines everything as LE serialized/deserialized and if you shift than you bypass this requirement on BE platforms.

(unless seqnr_payload is somehow already LE and not the host native endianess)

sipa commented at 9:12 PM on June 20, 2019:

seqnr_payload is an integer. The IV argument to ChaCha20 is an integer. Byte orders are only relevant when byte arrays are encoded as integers; that's not the case here. This is a pointless discussion. The htole call needs to go away.

elichai commented at 9:16 PM on June 20, 2019:

Ok, I went back to look at the definitions and tested, and right/left shifts work the same in all platforms (which actually is the sane thing, otherwise it will be a bit UB). you and Wladimir are right, the htole64 isn't needed here. Sorry.

jonasschnelli commented at 8:41 AM on June 25, 2019:

Thanks for looking into this... I'm actually unsure also by comparing against openSSH's implementation:

Going to setup a BE machine to test against various test vectors.

laanwj commented at 12:18 PM on June 25, 2019:

and right/left shifts work the same in all platforms

C++ has plenty of cruel and unusual cases of UB and IDB, but this luckily isn't one

I'm actually unsure also by comparing against openSSH's implementation:

Looking at these, they have POKE_U64 which pokes a unsigned 64-bit integer into memory (big-endian byte order, see https://github.com/openssh/openssh-portable/blob/master/sshbuf.h#L266). This is used to poke the IV to a byte buffer iv. e.g.

iv[0] = (seqnr >> 56) & 0xff;
iv[1] = (seqnr >> 48) & 0xff;
iv[2] = (seqnr >> 40) & 0xff;
iv[3] = (seqnr >> 32) & 0xff;
iv[4] = (seqnr >> 24) & 0xff;
iv[5] = (seqnr >> 16) & 0xff;
iv[6] = (seqnr >> 8) & 0xff;
iv[7] = seqnr & 0xff;

Then, in chacha_ivsetup (U8TO32_LITTLE is defined here: https://github.com/openssh/openssh-portable/blob/master/chacha.c#L27)

x->input[14] = U8TO32_LITTLE(iv + 0);
x->input[15] = U8TO32_LITTLE(iv + 4);

So if I get this right, this is equivalent to:

x->input[14] = (((seqnr >> 56) & 0xff)      ) |
               (((seqnr >> 48) & 0xff) <<  8) |
               (((seqnr >> 40) & 0xff) << 16) |
               (((seqnr >> 32) & 0xff) << 24);

x->input[15] = (((seqnr >> 24) & 0xff)      ) |
               (((seqnr >> 16) & 0xff) <<  8) |
               (((seqnr >>  8) & 0xff) << 16) |
               (( seqnr        & 0xff) << 24);

Which is weird in some sense, but not dependent on platform.

jonasschnelli commented at 1:13 PM on June 25, 2019:

Thanks for clearing up. @sipa and @laanwj are def. correct. Removed all byteswappings.

jonasschnelli commented at 1:21 PM on June 25, 2019:

The only important part is, that "producers" or the AEAD stream (which is not part of this PR, we only intend to test against already produced test vectors) need to make sure that the 3 byte length is correctly in LE order (which is easy to screw up because htole32 won't work in the 24bit case).

in src/test/crypto_tests.cpp:634 in a6397f15a8 outdated

 629 | +    cmp_ctx.SetIV(htole64(seqnr_aad));
 630 | +    cmp_ctx.Seek(0);
 631 | +    cmp_ctx.Keystream(cmp_ctx_buffer.data(), 64);
 632 | +    BOOST_CHECK(memcmp(expected_aad_keystream.data(), cmp_ctx_buffer.data(), expected_aad_keystream.size()) == 0);
 633 | +    // crypt the 3 length bytes and compare the length
 634 | +    uint64_t len_cmp = 0;

elichai commented at 5:06 PM on June 20, 2019:

shouldn't that be a 32bit number? (because of le32toh and that you later compare with expected_aad_length which is unsigned int(so either 32 or 64))

jonasschnelli commented at 12:57 PM on June 25, 2019:

Indeed. Fixed.

jonasschnelli force-pushed on Jun 25, 2019

Add ChaCha20Poly1305@Bitcoin AEAD implementation af5d1b5f4a

jonasschnelli force-pushed on Jun 25, 2019

in src/test/crypto_tests.cpp:629 in 4f53406444 outdated

 624 | +    // verify ciphertext & mac against the test vector
 625 | +    BOOST_CHECK_EQUAL(expected_ciphertext_and_mac.size(), ciphertext_buf.size());
 626 | +    BOOST_CHECK(memcmp(ciphertext_buf.data(), expected_ciphertext_and_mac.data(), ciphertext_buf.size()) == 0);
 627 | +
 628 | +    // manually construct the AAD keystream
 629 | +    cmp_ctx.SetIV(htole64(seqnr_aad));

laanwj commented at 1:40 PM on July 1, 2019:

there's still IV byte swapping here (another one below)

jonasschnelli commented at 8:08 PM on July 2, 2019:

Missed the ones in test. Will fix asap.

prusnak commented at 12:48 PM on July 2, 2019: contributor

Is the construct RFC7539 compliant?

jonasschnelli commented at 8:19 PM on July 2, 2019: contributor

@prusnak

Thanks for asking. It probably belongs more to the mailing list discussion (here we discuss the actual implementation). However:

Initially, the plan was to use the OpenSSH version of the AEAD construct over the IETF one because encrypting the length field seems desirable in our case (would allow new message types that could pad arbitrary data to make packet inspection harder).

Since the OpenSSH version is not very efficient for small messages, and, most nodes in synced state deal with around 40% of messages below 64 bytes, we decided to further optimize the AEAD construct to require less ChaCha20 operations, thus making it faster. Even faster than the current non-encrypted packet transport on most systems (hence the dbl-sha256 cpu cost).

Again, this discussion doesn't belong here so please move further questions regarding the concept to the mailing list. The details are described in the BIP: https://gist.github.com/jonasschnelli/c530ea8421b8d0e80c51486325587c52

Add ChaCha20Poly1305@Bitcoin tests 99aea045d6

Add ChaCha20Poly1305@Bitcoin AEAD benchmark bb326add9f

jonasschnelli commented at 9:54 AM on July 3, 2019: contributor

Removed the invalid byte swapping in crypto_tests
Followed @practicalswift recommondation to not directly check and execute in assert() in the chacha_poly_aead bench

jonasschnelli force-pushed on Jul 3, 2019

laanwj commented at 7:48 PM on July 11, 2019: member

code review ACK bb326add9f38f2a8e5ce5ee29d98ce08038200d8

there's nothing to test yet (besides running the unit tests), as this is the first step and the code here is currently unused

laanwj removed this from the "Blockers" column in a project

laanwj merged this on Jul 11, 2019

laanwj closed this on Jul 11, 2019

laanwj referenced this in commit 28d1353f48 on Jul 11, 2019

sidhujag referenced this in commit aae6de0fc9 on Jul 11, 2019

PastaPastaPasta referenced this in commit 1bf6613178 on Jul 18, 2019

PastaPastaPasta referenced this in commit 0840ce3a92 on Jul 23, 2019

PastaPastaPasta referenced this in commit 8214c765d4 on Aug 6, 2019

barrystyle referenced this in commit 7ebc414298 on Jan 22, 2020

in src/crypto/chacha_poly_aead.cpp:62 in bb326add9f

  57 | +
  58 | +    // block counter 0 for the poly1305 key
  59 | +    // use lower 32bytes for the poly1305 key
  60 | +    // (throws away 32 unused bytes (upper 32) from this ChaCha20 round)
  61 | +    m_chacha_main.Seek(0);
  62 | +    m_chacha_main.Crypt(poly_key, poly_key, sizeof(poly_key));

rajarshimaitra commented at 11:28 AM on June 16, 2020:

BIP324 says the following on poly1305 key.

The AEAD is constructed as follows: for each packet, generate a Poly1305 key by taking the first 256 bits of ChaCha20 stream output generated using K_2, an IV consisting of the packet sequence number encoded as an LE uint64 and a ChaCha20 block counter of zero.

Here to me, it seems the key is being derived by encrypting a vector of zeros with m_chacha_main instead of simply taking the keystream of m_chacha_main? Are they the same thing? if not, then should the bip draft be changed to reflect this?

elichai commented at 3:03 PM on June 16, 2020:

encrypting in chacha means generating a random string and XORing with the plaintext, so yes taking a stream is equal to encrypting zeros.

rajarshimaitra commented at 3:11 PM on June 16, 2020:

Thanks for clarifying.

in src/crypto/chacha_poly_aead.cpp:36 in bb326add9f

  31 | +ChaCha20Poly1305AEAD::ChaCha20Poly1305AEAD(const unsigned char* K_1, size_t K_1_len, const unsigned char* K_2, size_t K_2_len)
  32 | +{
  33 | +    assert(K_1_len == CHACHA20_POLY1305_AEAD_KEY_LEN);
  34 | +    assert(K_2_len == CHACHA20_POLY1305_AEAD_KEY_LEN);
  35 | +    m_chacha_main.SetKey(K_1, CHACHA20_POLY1305_AEAD_KEY_LEN);
  36 | +    m_chacha_header.SetKey(K_2, CHACHA20_POLY1305_AEAD_KEY_LEN);

rajarshimaitra commented at 11:31 AM on June 16, 2020:

Nit: From BIP draft

The instance keyed by K_1 is a stream cipher that is used only to encrypt the 3 byte packet length field and has its own sequence number. The second instance, keyed by K_2, is used in conjunction with poly1305 to build an AEAD (Authenticated Encryption with Associated Data) that is used to encrypt and authenticate the entire packet.

To keep parity with the BIP should K_1 and K_2 be interchanged (either in BIP or in code)?

jonasschnelli commented at 3:15 PM on June 16, 2020:

Good point. It's technically not wrong but confusing. Code update would probably be better.

dhruv commented at 5:00 PM on June 23, 2021:

If it's helpful, I've created #22331 to fix this.

rajarshimaitra commented at 11:33 AM on June 16, 2020: contributor

I understand this is already merged, But below are two following small doubts that occurred to me while reviewing.

jasonbcox referenced this in commit 0934172526 on Sep 21, 2020

fanquake referenced this in commit 607a6338a7 on Aug 19, 2021

sidhujag referenced this in commit 1ca38972fc on Aug 20, 2021

dhruv added this to the "Done" column in a project

fanquake referenced this in commit 650382e4ec on Jun 10, 2022

fanquake referenced this in commit 491bb14c0c on Jun 10, 2022

laanwj referenced this in commit 1557014378 on Jun 14, 2022

sidhujag referenced this in commit d23210a8d8 on Jun 15, 2022

DrahtBot locked this on Aug 16, 2022