Add ChaCha20 encryption option (XOR) #15512

jonasschnelli · 2019-03-01T16:12:57Z

The current ChaCha20 implementation does not support message encryption (it can only output the keystream which is sufficient for the RNG).

This PR adds the actual XORing of the plaintext with the keystream in order to return the desired ciphertext.

Required for v2 message transport protocol.

DrahtBot · 2019-03-05T10:36:13Z

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)

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.

ryanofsky

utACK 4325da919a042dfb4eed87b6d038dbb236959e5b. I don't know very much about chacha20 or this method of encryption, but this seems to do what is described.

src/crypto/chacha20.cpp

ryanofsky · 2019-03-22T18:18:51Z

src/crypto/chacha20.cpp

Just memcpy(tmp, m, bytes) might be simpler and easy to read than this for loop.

I'm not to familiar with compiler optimisations and stuff but I just checked the reference implementation by DJB and some other C based ChaCha implementations and all of them seems to use the byte per byte assignment. I prefer to leave it as it is.

src/crypto/chacha20.cpp

src/crypto/chacha20.h

src/test/crypto_tests.cpp

e9d5e97 Poly1305: tolerate the intentional unsigned wraparound in poly1305.cpp (Jonas Schnelli) b34bf30 Add Poly1305 bench (Jonas Schnelli) 03be7f4 Add Poly1305 implementation (Jonas Schnelli) Pull request description: This adds a currently unused Poly1305 implementation including test vectors from RFC7539. Required for BIP151 (and related to #15512). Tree-SHA512: f8c1ad2f686b980a7498ca50c517e2348ac7b1fe550565156f6c2b20faf764978e4fa6b5b1c3777a16e7a12e2eca3fb57a59be9c788b00d4358ee80f2959edb1

sipa · 2019-03-27T17:48:22Z

src/crypto/chacha20.cpp

I think it would be better to duplicate the logic here and turn the stream cipher version into a separate function.

As is, it introduces an unnecessary branch in the output version.

Good point. Adapted the duplication approach.

What's the reasoning here? Performance?

How does the version in the refrence implementation compare?

void ECRYPT_keystream_bytes(ECRYPT_ctx *x,u8 *stream,u32 bytes) { u32 i; for (i = 0;i < bytes;++i) stream[i] = 0; ECRYPT_encrypt_bytes(x,stream,stream,bytes); }

ie setting Output(c, bytes) to call Crypt(c, c, bytes)?

I had it in the initial version like @jnewbery just proposed.
After @sipa recommended to separate it, I thought that a strict separation may be beneficial for verification and later optimizations. But maybe @sipa can clarify...

sipa · 2019-03-28T21:28:46Z

src/crypto/chacha20.cpp

No need for this if.

Yes. Fixed.

ryanofsky

utACK 427b49dcdbfb25153ee4228dda49aa07db16d59c. Changes since last review: splitting Output/Crypt functions, dropping comment describing function arguments, adding comment describing m/tmp copy, dropping XOR macro, and making suggested test changes.

jnewbery

Implementation and tests look good and match the reference implementation here: https://cr.yp.to/streamciphers/timings/estreambench/submissions/salsa20/chacha8/merged/chacha.c and test vector here: https://tools.ietf.org/html/rfc7539#section-2.4.2

I have a few minor comments inline, and would be curious about the answer to:
#15512 (comment)

src/crypto/chacha20.h

src/test/crypto_tests.cpp

jnewbery

Looks great. Thanks for adding the comments to chacha20.h!

Just a couple of nits in the bench file. I'm still curious about the code duplication between Keystream() and Crypt().

src/bench/chacha20.cpp

jnewbery · 2019-05-03T19:18:10Z

src/bench/chacha20.cpp

Is a reason you've added these CHash256 benchmarks to chacha20.cpp?

I added if for comparison and the impact on the networking... though I think it belong to an extra commit in #15649
Will remove it from here.

jnewbery · 2019-05-03T21:01:44Z

Looks good. utACK 2dfe275.

In general, it's better to have less code duplication, so I'd like to hear from @sipa his reasoning for #15512 (comment)

sipa · 2019-05-03T21:09:20Z

@jnewbery I just thought that it'd be preferable not to burden the RNG code with branches that are only used for encryption. In cryptographic code like this, I don't care too much about duplication, as it isn't code that subject to many possible future changes.

jnewbery · 2019-05-06T14:36:26Z

ok, my aesthetic preference is for less duplication, either by having a single Keystream/Crypt function, or by calling Keystream() from Crypt() with a zero'ed message. As sipa points out though, this code is unlikely to be modified much in future, so it's not a big deal either way.

utACK 2dfe275

ryanofsky

utACK 2dfe275. Changes since last review are just renaming the Crypt method, adding comments, and simplifying the benchmark.

I just thought that it'd be preferable not to burden the RNG code with branches that are only used for encryption.

I think the duplication is fine, but it's unclear if the concern with branches is about readability or performance. If it's performance, you could give the previous Output() function an additional template<bool use_input> template argument, and have Crypt() and Keystream() both call it inlined.

sipa · 2019-05-10T00:33:07Z

utACK 2dfe275

2dfe275 Add ChaCha20 bench (Jonas Schnelli) 2bc2b8b Add ChaCha20 encryption option (XOR) (Jonas Schnelli) Pull request description: The current ChaCha20 implementation does not support message encryption (it can only output the keystream which is sufficient for the RNG). This PR adds the actual XORing of the `plaintext` with the `keystream` in order to return the desired `ciphertext`. Required for v2 message transport protocol. ACKs for commit 2dfe27: jnewbery: Looks good. utACK 2dfe275. jnewbery: utACK 2dfe275 sipa: utACK 2dfe275 ryanofsky: utACK 2dfe275. Changes since last review are just renaming the Crypt method, adding comments, and simplifying the benchmark. Tree-SHA512: 84bb234da2ca9fdc44bc29a786d9dd215520f81245270c1aef801ef66b6091b7793e2eb38ad6dbb084925245065c5dce9e5582f2d0fa220ab3e182d43412d5b5

Kixunil · 2019-07-02T13:01:04Z

src/crypto/chacha20.cpp

+
+        if (bytes <= 64) {
+            if (bytes < 64) {
+                for (i = 0;i < bytes;++i) ctarget[i] = c[i];


Isn't this no-op? When bytes < 64 line 215 get's executed which makes ctarget and c equal pointers, therefore it's copying a value to itself.

I don't think so.
If we do less then 64 bytes, we execute the round on tmp (because we do 64bytes always, see line 216, c points to tmp if <64 bytes). So in the case of <64 bytes, c points to the temporary 64byte buffer and ctarget points to the function provided c argument.

Ah, yes, missed that. Thanks and sorry for bothering.

Kixunil · 2019-07-02T13:04:30Z

src/crypto/chacha20.h

-    void SetIV(uint64_t iv);
-    void Seek(uint64_t pos);
-    void Output(unsigned char* output, size_t bytes);
+    void SetKey(const unsigned char* key, size_t keylen); //!< set key with flexible keylength; 256bit recommended */


I like the renaming. Would be nice if the comments included information about pointers (e.g. "key must be non-null, pointer isn't stored").

Yes. That would have been useful. Feel free to PR.

bb326ad Add ChaCha20Poly1305@Bitcoin AEAD benchmark (Jonas Schnelli) 99aea04 Add ChaCha20Poly1305@Bitcoin tests (Jonas Schnelli) af5d1b5 Add ChaCha20Poly1305@Bitcoin AEAD implementation (Jonas Schnelli) Pull request description: 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. ACKs for top commit: laanwj: code review ACK bb326ad Tree-SHA512: 15bcb86c510fce7abb7a73536ff2ae89893b24646bf108c6cf18f064d672dbbbea8b1dd0868849fdac0c6854e498f1345d01dab56d1c92031afd728302234686

bb326ad Add ChaCha20Poly1305@Bitcoin AEAD benchmark (Jonas Schnelli) 99aea04 Add ChaCha20Poly1305@Bitcoin tests (Jonas Schnelli) af5d1b5 Add ChaCha20Poly1305@Bitcoin AEAD implementation (Jonas Schnelli) Pull request description: This adds a new AEAD (authenticated encryption with additional data) construct optimised for small messages (like used in Bitcoins p2p network). Includes: bitcoin#15519, bitcoin#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. ACKs for top commit: laanwj: code review ACK bb326ad Tree-SHA512: 15bcb86c510fce7abb7a73536ff2ae89893b24646bf108c6cf18f064d672dbbbea8b1dd0868849fdac0c6854e498f1345d01dab56d1c92031afd728302234686

2dfe275 Add ChaCha20 bench (Jonas Schnelli) 2bc2b8b Add ChaCha20 encryption option (XOR) (Jonas Schnelli) Pull request description: The current ChaCha20 implementation does not support message encryption (it can only output the keystream which is sufficient for the RNG). This PR adds the actual XORing of the `plaintext` with the `keystream` in order to return the desired `ciphertext`. Required for v2 message transport protocol. ACKs for commit 2dfe27: jnewbery: Looks good. utACK 2dfe275. jnewbery: utACK 2dfe275 sipa: utACK 2dfe275 ryanofsky: utACK 2dfe275. Changes since last review are just renaming the Crypt method, adding comments, and simplifying the benchmark. Tree-SHA512: 84bb234da2ca9fdc44bc29a786d9dd215520f81245270c1aef801ef66b6091b7793e2eb38ad6dbb084925245065c5dce9e5582f2d0fa220ab3e182d43412d5b5

e9d5e97 Poly1305: tolerate the intentional unsigned wraparound in poly1305.cpp (Jonas Schnelli) b34bf30 Add Poly1305 bench (Jonas Schnelli) 03be7f4 Add Poly1305 implementation (Jonas Schnelli) Pull request description: This adds a currently unused Poly1305 implementation including test vectors from RFC7539. Required for BIP151 (and related to bitcoin#15512). Tree-SHA512: f8c1ad2f686b980a7498ca50c517e2348ac7b1fe550565156f6c2b20faf764978e4fa6b5b1c3777a16e7a12e2eca3fb57a59be9c788b00d4358ee80f2959edb1

bb326ad Add ChaCha20Poly1305@Bitcoin AEAD benchmark (Jonas Schnelli) 99aea04 Add ChaCha20Poly1305@Bitcoin tests (Jonas Schnelli) af5d1b5 Add ChaCha20Poly1305@Bitcoin AEAD implementation (Jonas Schnelli) Pull request description: This adds a new AEAD (authenticated encryption with additional data) construct optimised for small messages (like used in Bitcoins p2p network). Includes: bitcoin#15519, bitcoin#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. ACKs for top commit: laanwj: code review ACK bb326ad Tree-SHA512: 15bcb86c510fce7abb7a73536ff2ae89893b24646bf108c6cf18f064d672dbbbea8b1dd0868849fdac0c6854e498f1345d01dab56d1c92031afd728302234686 Add new line

Summary: * Add ChaCha20 bench This is a backport of Core [[bitcoin/bitcoin#15512 | PR15512]] Test Plan: ninja all check bench-bitcoin Reviewers: #bitcoin_abc, majcosta Reviewed By: #bitcoin_abc, majcosta Differential Revision: https://reviews.bitcoinabc.org/D7491

cecbf6c Use secure.h header for secure allocators (Fuzzbawls) d9f67da net: add ifaddrs.h include (fanquake) e906436 build: check if -lsocket is required with *ifaddrs (fanquake) 414f405 rand: only try and use freeifaddrs if available (fanquake) 3a039d6 build: avoid getifaddrs when unavailable (Cory Fields) 77bddd7 Use GetStrongRandBytes in gmp bignum initialization (Fuzzbawls) b70b26f Fix typo in comment in randomenv.cpp (Fuzzbawls) fec460c Put bounds on the number of CPUID leaves explored (Pieter Wuille) 41ab1ff Fix CPUID subleaf iteration (Pieter Wuille) 8a9bbb1 Move events_hasher into RNGState() (Pieter Wuille) 88c2ae5 random: mark RandAddPeriodic and SeedPeriodic as noexcept (fanquake) 81d382f doc: correct random.h docs after bitcoin#17270 (fanquake) f363ea9 Seed RNG with precision timestamps on receipt of net messages. (Matt Corallo) 7d6ddcb Run background seeding periodically instead of unpredictably (Pieter Wuille) 4679181 Add information gathered through getauxval() (Pieter Wuille) 88d97d0 Feed CPUID data into RNG (Pieter Wuille) 8f5b9c9 Use sysctl for seeding on MacOS/BSD (Pieter Wuille) 67de246 Gather additional entropy from the environment (Pieter Wuille) 6142e1f Seed randomness with process id / thread id / various clocks (Pieter Wuille) 7bde8b7 [MOVEONLY] Move cpuid code from random to compat/cpuid (Fuzzbawls) 52b5336 [MOVEONLY] Move perfmon data gathering to new randomenv module (Pieter Wuille) 27cf995 doc: minor corrections in random.cpp (fanquake) fccd2b8 doc: correct function name in ReportHardwareRand() (fanquake) 909473e Fix FreeBSD build by including utilstrencodings.h (Fuzzbawls) 630931f break circular dependency: random/sync -> util -> random/sync (Fuzzbawls) 5eed08c random: remove call to RAND_screen() (Windows only) (fanquake) ada9868 gui: remove OpenSSL PRNG seeding (Windows, Qt only) (fanquake) 22a7121 Fix non-deterministic coverage of test DoS_mapOrphans (Fuzzbawls) 79e7fd3 Add ChaCha20 bench (Jonas Schnelli) 6966aa9 Add ChaCha20 encryption option (XOR) (Jonas Schnelli) 28c9cdb tests: Add script checking for deterministic line coverage (practicalswift) c82e359 test: Make bloom tests deterministic (MarcoFalke) 7b33223 Document strenghtening (Pieter Wuille) 0190dec Add hash strengthening to the RNG (Pieter Wuille) 67e336d Use RdSeed when available, and reduce RdRand load (Pieter Wuille) 4ffda1f Document RNG design in random.h (Pieter Wuille) 2b6381e Use secure allocator for RNG state (Pieter Wuille) 080deb3 Encapsulate RNGState better (Pieter Wuille) 787d72f DRY: Implement GetRand using FastRandomContext::randrange (Pieter Wuille) 5bc2583 Sprinkle some sweet noexcepts over the RNG code (Pieter Wuille) 774899f Remove hwrand_initialized. (Pieter Wuille) 698d133 Switch all RNG code to the built-in PRNG. (Pieter Wuille) 038a45a Integrate util/system's CInit into RNGState (Fuzzbawls) 5f20e62 Abstract out seeding/extracting entropy into RNGState::MixExtract (Pieter Wuille) 298f97c Add thread safety annotations to RNG state (Pieter Wuille) 2326535 Rename some hardware RNG related functions (Pieter Wuille) d76ee83 Automatically initialize RNG on first use. (Pieter Wuille) 1a5dbc5 Don't log RandAddSeedPerfmon details (Pieter Wuille) 32e6c42 Simplify testing RNG code (Fuzzbawls) 972effa Make unit tests use the insecure_rand_ctx exclusively (Fuzzbawls) af52bf5 Use a FastRandomContext in LimitOrphanTxSize (Fuzzbawls) 746d466 Introduce a Shuffle for FastRandomContext and use it in wallet (Fuzzbawls) 1cdf124 Use a local FastRandomContext in a few more places in net (Fuzzbawls) e862564 Make addrman use its local RNG exclusively (Fuzzbawls) 94b2ead Make FastRandomContext support standard C++11 RNG interface (Pieter Wuille) Pull request description: This is a collection of upstream PRs that have been backported to bring our RNG (`src/random`) code more up-to-date. The following upstream PRs have been included here: - bitcoin#12742 - bitcoin#14624 - some of this had already been merged previously - bitcoin#14955 - bitcoin#15250 - bitcoin#15224 - bitcoin#15324 - bitcoin#15296 - bitcoin#15512 - bitcoin#16878 - bitcoin#17151 - bitcoin#17191 - bitcoin#13236 - bitcoin#13314 - bitcoin#17169 - bitcoin#17270 - omitted last commit as our testing framework doesn't support it currently - omitted bitcoin@64e1e02, to be pulled in after our time utility is updated in a separate PR - bitcoin#17573 - bitcoin#17507 - bitcoin#17670 - bitcoin#17527 - bitcoin#14127 - bitcoin#21486 ACKs for top commit: furszy: ACK cecbf6c with a minor nit that can be easily tackled later. random-zebra: rebase utACK cecbf6c and merging... Tree-SHA512: 3463b693cc9bddc1ec15228d264a794f5c2f159073fafa2ccf6e2563abfeb4369e49505f97ca84f2478ca792bd07b66d2cd83c58044d6a0cae6af42d22f5784b

jonasschnelli mentioned this pull request Mar 1, 2019

Add chacha20/poly1305 and chacha20poly1305_AEAD from openssh #14050

Closed

laanwj added P2P Utils/log/libs and removed P2P labels Mar 2, 2019

jonasschnelli force-pushed the 2019/03/chacha branch from 009d0ab to b05bb64 Compare March 3, 2019 20:19

jonasschnelli mentioned this pull request Mar 3, 2019

Add Poly1305 implementation #15519

Merged

ryanofsky approved these changes Mar 22, 2019

View reviewed changes

jonasschnelli mentioned this pull request Mar 22, 2019

Add ChaCha20Poly1305@Bitcoin AEAD #15649

Merged

jonasschnelli force-pushed the 2019/03/chacha branch from 4325da9 to 9d3ea6a Compare March 25, 2019 20:43

sipa reviewed Mar 27, 2019

View reviewed changes

jonasschnelli force-pushed the 2019/03/chacha branch from 9d3ea6a to 7f2028f Compare March 28, 2019 19:30

sipa reviewed Mar 28, 2019

View reviewed changes

jonasschnelli force-pushed the 2019/03/chacha branch from 7f2028f to 427b49d Compare March 29, 2019 08:58

ryanofsky approved these changes Mar 29, 2019

View reviewed changes

jnewbery reviewed May 3, 2019

View reviewed changes

src/crypto/chacha20.h Outdated Show resolved Hide resolved

src/crypto/chacha20.h Outdated Show resolved Hide resolved

src/crypto/chacha20.h Outdated Show resolved Hide resolved

src/test/crypto_tests.cpp Outdated Show resolved Hide resolved

jonasschnelli force-pushed the 2019/03/chacha branch from 427b49d to d5d6f81 Compare May 3, 2019 18:27

Add ChaCha20 encryption option (XOR)

2bc2b8b

jonasschnelli force-pushed the 2019/03/chacha branch from d5d6f81 to 66d682b Compare May 3, 2019 18:32

jnewbery reviewed May 3, 2019

View reviewed changes

Add ChaCha20 bench

2dfe275

jonasschnelli force-pushed the 2019/03/chacha branch 2 times, most recently from c8df2c0 to 2dfe275 Compare May 3, 2019 20:53

ryanofsky approved these changes May 7, 2019

View reviewed changes

jonasschnelli merged commit 2dfe275 into bitcoin:master May 10, 2019

Kixunil reviewed Jul 2, 2019

View reviewed changes

Warrows mentioned this pull request Jul 9, 2019

Bring PIVX random on par with bitcoin PIVX-Project/PIVX#799

Closed

42 tasks

PastaPastaPasta mentioned this pull request Jul 18, 2019

Backport chacha-poly1305, prepare for V2 P2P Encrypted Messaging dashpay/dash#3032

Merged

Fuzzbawls mentioned this pull request Mar 30, 2021

[Refactor] Update RNG code from upstream PIVX-Project/PIVX#2278

Merged

bitcoin locked as resolved and limited conversation to collaborators Dec 16, 2021

Add ChaCha20 encryption option (XOR) #15512

Add ChaCha20 encryption option (XOR) #15512

Uh oh!

Conversation

jonasschnelli commented Mar 1, 2019 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

DrahtBot commented Mar 5, 2019 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Conflicts

Uh oh!

ryanofsky left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

sipa Mar 27, 2019 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

ryanofsky left a comment

Choose a reason for hiding this comment

Uh oh!

jnewbery left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

jnewbery left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

jnewbery commented May 3, 2019

Uh oh!

sipa commented May 3, 2019

Uh oh!

jnewbery commented May 6, 2019

Uh oh!

ryanofsky left a comment • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

sipa commented May 10, 2019

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Reviewers

Assignees

Labels

jonasschnelli commented Mar 1, 2019 •

edited

Loading

DrahtBot commented Mar 5, 2019 •

edited

Loading

sipa Mar 27, 2019 •

edited

Loading

ryanofsky left a comment •

edited

Loading