Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

x/crypto: add chacha20, xchacha20 #24485

Closed
riobard opened this issue Mar 22, 2018 · 46 comments
Closed

x/crypto: add chacha20, xchacha20 #24485

riobard opened this issue Mar 22, 2018 · 46 comments

Comments

@riobard
Copy link

@riobard riobard commented Mar 22, 2018

Package chacha20 currently lives at x/crypto/internal/chacha20 which is not importable by users outside of x/crypto. Please move it to x/crypto/chacha20. Additionally, please make the API similar to x/crypto/salsa20 (along with its subpackage x/crypto/salsa20/salsa) as the two are extremely similar.

Background: x/crypto/internal/chacha20 was previously located at x/crypto/chacha20poly1305/internal/chacha20. It was moved up one level to be imported by x/crypto/ssh.

@gopherbot gopherbot added this to the Unreleased milestone Mar 22, 2018
@ALTree
Copy link
Member

@ALTree ALTree commented Mar 22, 2018

Related: #23885 (add support for XChaCha20).

@bcmills
Copy link
Member

@bcmills bcmills commented Mar 22, 2018

(CC: @FiloSottile)

@rsc
Copy link
Contributor

@rsc rsc commented Apr 20, 2018

It sounds like doing x/crypto/chacha20 and x/crypto/xchacha20 is OK (or maybe just one package), but @agl and @FiloSottile will need to think a bit more about what the API should be. Because the current code is internal, not as much care has been taken with the API details.

@rsc
Copy link
Contributor

@rsc rsc commented Apr 20, 2018

The proposal is approved but the API is still yet to be decided.

@rsc rsc changed the title x/crypto: make chacha20 importable by 3rd party x/crypto: add chacha20, xchacha20 Apr 20, 2018
@aead
Copy link
Contributor

@aead aead commented Apr 20, 2018

If everyone is okay with it, I'll send a CL based on https://github.com/aead/chacha20.

@FiloSottile
Copy link
Member

@FiloSottile FiloSottile commented Apr 20, 2018

We'll want a AEAD version of XChaCha20, and we don't want to expose HChaCha20, so we have some work to do on the API. Let's discuss it here rather than on a CL.

@aead
Copy link
Contributor

@aead aead commented Apr 21, 2018

But a chacha20 package should expose the XChaCha20 variant (as stream cipher / XORKeystream) too?
If so we probably have to duplicate the HChaCha20 logic.

Another question is whether it's worth to add all the optimized asm implementations (SSE,AVX(2) for x86/amd64 and NEON for arm64)? Like shown by Vlad's chacha20poly1305 implementation we can get the best performance for the AEAD by combining the chacha20 and poly1305 implementations.

@thaidn
Copy link

@thaidn thaidn commented Apr 21, 2018

Is there a published security analysis of XChaCha20?

We wanted to add it to Tink, but decided not to because we cannot find any published cryptanalysis results or RFC. There are plenty results for Salsa20. There's a paper for XSalsa20, but there's nothing for XChaCha20.

@riobard
Copy link
Author

@riobard riobard commented Apr 22, 2018

@aead Optimized implementations are really helpful, even just for stream ciphers alone.

@riobard
Copy link
Author

@riobard riobard commented Apr 22, 2018

@rsc Do you think the API of x/crypto/salsa20 and x/crypto/salsa20/salsa is alright? It would be nice for the chacha-variants to expose consistent API with their salsa siblings.

@aead
Copy link
Contributor

@aead aead commented Apr 22, 2018

@thaidn A security analysis of ChaCha20 can be found here. I'm not aware of a explicit scientific analysis of XChaCha20's HChaCha20 function. However D. Bernstein published an analysis of XSalsa20 containing a security reduction to Salsa20.

The XChaCha20 construction is equivalent to the XSalsa20 expect for using ChaCha20/r and HChaCha20 instead of Salsa20/r and HSalsa20:
XChaCha20 takes a 192 bit nonce where keyxchacha := KDF(key, nonce[0:16]) (the first 128 bit of the nonce) and noncexchacha := nonce[16:24] (the remaining 64 bit of the nonce) where KDF is the HChaCHa20 function.

Conceptually the reduction for XChaCha20 should be the same as for XSalsa20 (D.B. does not assume anything specific about HSalsa20 which is not true for HChaCha20). The security proof for generalized cascades should also work for XChaCha20. So it's at least a reasonable assumption that XChaCha20 is secure if ChaCha20 is secure. However, I haven't done the formal proof.

@aead
Copy link
Contributor

@aead aead commented Apr 22, 2018

@riobard

Optimized implementations are really helpful, even just for stream ciphers alone.

Well, you should always prefer (X)ChaCha20Poly1305 over plain (X)ChaCha20. I'm not aware of an reasonable use case for (X)ChaCha20 which could and should not use (X)ChaCha20Poly1305. Assembler code is hard to maintain and it's easy to screw up. We should only add (a lot) of assembler - ChaCha20 asm is a lot - if there is a real benefit.
We should not do it just because we could.

@riobard
Copy link
Author

@riobard riobard commented Apr 22, 2018

@aead I respectfully disagree. There are lots of valid use cases where stream ciphers are desired.

@aead
Copy link
Contributor

@aead aead commented Apr 22, 2018

@riobard I don't want to start a fundamental discussion about this topic - Providing confidentially but not integrity is considered "not state of the art" and should/must be considered as security issue for almost all use cases. Exceptions may be use cases like PRNG or legacy systems, but these are quite rare and adding a lot of complexity/maintenance cost is probably not worth it.
If "important" projects/protocols cannot use (X)ChaCha20Poly1305 as provided by chacha20poly1305 it's maybe okay, otherwise probably not....

@riobard
Copy link
Author

@riobard riobard commented Apr 22, 2018

@aead You're making too much assumption about how/why people use stream ciphers. Not everything is a nail when you have a hammer. Both stream ciphers and AEAD ciphers have their important use cases, and sometimes they are even used together (e.g. x/crypto/ssh).

@aead
Copy link
Contributor

@aead aead commented Apr 22, 2018

@riobard Again, I admit that PRFs (stream ciphers) can be used not only for encryption. But:

  1. If they are, they should be combined with a MAC. Usually the passive/honest-but-curious adversary model does not reflect the real world.
  2. If they are not, than it's questionable whether we should optimize for these use cases since they are quite rare.

SSH only allows C20P1305 AFAIK - and I would consider the CTR suites (without GHASH/auth.) as legacy crypto.

If there is one/some use cases for PRFs which seems to be common or if one/some protocols cannot use the AEAD API for some reason, than we may want to provide optimized code. Otherwise probably not. IIRC the x/crypto policy is/was to balance cost and benefit - and only optimize if the benefits outweighs the costs. But this must be decided by @FiloSottile and/or @agl ...

@riobard
Copy link
Author

@riobard riobard commented Apr 22, 2018

@aead IMHO x/crypto/ssh is an important-enough use case to justify optimized chacha20 code. Its use of C20P1305 does not work with cipher.AEAD interface.

@zx2c4
Copy link
Contributor

@zx2c4 zx2c4 commented May 13, 2018

In wireguard-go, we're just doing this -- https://git.zx2c4.com/wireguard-go/tree/xchacha20poly1305/xchacha20.go#n142 -- pretty ugly, and I'd very much appreciate having this in x/crypto instead.

@gopherbot
Copy link

@gopherbot gopherbot commented Aug 3, 2018

Change https://golang.org/cl/127819 mentions this issue: chacha20poly1305: add XChaCha20-Poly1305

gopherbot pushed a commit to golang/crypto that referenced this issue Aug 6, 2018
The XChaCha20 construction does not have an authoritative spec, but this
implementation is based on the following documents:

https://cr.yp.to/snuffle/xsalsa-20081128.pdf
https://download.libsodium.org/doc/secret-key_cryptography/aead.html
http://loup-vaillant.fr/tutorials/chacha20-design
https://tools.ietf.org/html/draft-paragon-paseto-rfc-00#section-7

Tested against the following implementations:

https://github.com/jedisct1/libsodium/blob/7cdf3f0e841/test/default/aead_xchacha20poly1305.c
https://git.kernel.org/pub/scm/linux/kernel/git/zx2c4/linux.git/diff/lib/zinc/selftest/chacha20poly1305.h?h=zinc
https://git.zx2c4.com/wireguard-go/tree/xchacha20poly1305/xchacha20.go

name                            time/op          speed
Chacha20Poly1305/Open-64-8         225ns ± 1%     283MB/s ± 1%
Chacha20Poly1305/Open-64-X-8       390ns ± 0%     164MB/s ± 0%
Chacha20Poly1305/Seal-64-8         222ns ± 0%     287MB/s ± 0%
Chacha20Poly1305/Seal-64-X-8       386ns ± 0%     165MB/s ± 1%
Chacha20Poly1305/Open-1350-8      1.12µs ± 1%    1.21GB/s ± 1%
Chacha20Poly1305/Open-1350-X-8    1.28µs ± 0%    1.05GB/s ± 0%
Chacha20Poly1305/Seal-1350-8      1.15µs ± 0%    1.17GB/s ± 0%
Chacha20Poly1305/Seal-1350-X-8    1.32µs ± 1%    1.02GB/s ± 0%
Chacha20Poly1305/Open-8192-8      5.53µs ± 0%    1.48GB/s ± 0%
Chacha20Poly1305/Open-8192-X-8    5.71µs ± 1%    1.44GB/s ± 1%
Chacha20Poly1305/Seal-8192-8      5.54µs ± 1%    1.48GB/s ± 1%
Chacha20Poly1305/Seal-8192-X-8    5.74µs ± 1%    1.43GB/s ± 1%

Updates golang/go#24485

Change-Id: Iea6f3b4c2be67f16f56720a200dcc895c0f9d520
Reviewed-on: https://go-review.googlesource.com/127819
Run-TryBot: Filippo Valsorda <filippo@golang.org>
Reviewed-by: Adam Langley <agl@golang.org>
@FiloSottile
Copy link
Member

@FiloSottile FiloSottile commented Feb 13, 2019

The APIs I'm thinking about for golang.org/x/crypto/chacha20 are

func NewUnauthenticated(key []byte) (cipher.Stream, error)
func NewXUnauthenticated(key []byte) (cipher.Stream, error)

returning a cipher.Stream because most other Stream implementations are not type-assertable anyway.

I agree the golang.org/x/crypto/salsa20 API should match, but the one-shot XORKeyStream function is bad because it doesn't match any interface and can't be chunked, even if Salsa and ChaCha have good key agility, so instead let's add NewUnauthenticated to golang.org/x/crypto/salsa20.

Sounds good to everyone who needs these?

@bcmills
Copy link
Member

@bcmills bcmills commented Feb 14, 2019

@FiloSottile, crypto/rc4.NewCipher is an example of a standard-library function that returns a concrete implementation of the cipher.Stream interface. In addition to the XORKeyStream method required by the interface, it provides an additional Reset method.

@FiloSottile
Copy link
Member

@FiloSottile FiloSottile commented Feb 14, 2019

I definitely want it to be called NewUnauthenticated. chacha20 vs chacha20poly1305 is too subtle a difference, and chacha20 is easier to type. (Otherwise by style when there's only a single type in a package the function should just be called New.)

We should not have a package-level XORKeyStream function in chacha20, I only included it in #24485 (comment) because it's already in golang.org/x/crypto/salsa20.

In addition to the XORKeyStream method required by the interface, it provides an additional Reset method.

@bcmills I recognized in #24485 (comment) that you are right, but about Reset... https://go-review.googlesource.com/c/go/+/162297 ;)

@FiloSottile
Copy link
Member

@FiloSottile FiloSottile commented Feb 14, 2019

@aead Are you taking this? Otherwise I was going to work on it this week.

@aead
Copy link
Contributor

@aead aead commented Feb 14, 2019

@FiloSottile I'm okay with you sending the CL. Let me know if I should review :)

@riobard
Copy link
Author

@riobard riobard commented Feb 14, 2019

@FiloSottile I wouldn't worry too much about the potential confusion about chacha20 and chacha20poly1305 as the two feature vastly different API. Calling it NewUnauthenticated is rather confusing because there's no NewAuthenticated counterpart in any packages. Further, I think your concern should probably be better reflected in documentation if necessary at all.

We should not have a package-level XORKeyStream function in chacha20, I only included it in #24485 (comment) because it's already in golang.org/x/crypto/salsa20.

So we're not going to keep salsa20 and chacha20 consistent?

@dgl
Copy link

@dgl dgl commented May 6, 2019

I'd also be interested in access to chacha20, I'd like a pure Go implementation of libsodium's secretstream (https://download.libsodium.org/doc/secret-key_cryptography/secretstream). Implementing this needs HChaCha20 as the key construction is based on HChaCha20.

@gopherbot
Copy link

@gopherbot gopherbot commented Jul 10, 2019

Change https://golang.org/cl/185439 mentions this issue: internal/chacha20: refactor for readability and consistency

@gopherbot
Copy link

@gopherbot gopherbot commented Jul 10, 2019

Change https://golang.org/cl/185440 mentions this issue: internal/chacha20: cache first round across XORKeyStream invocations

@gopherbot
Copy link

@gopherbot gopherbot commented Jul 12, 2019

Change https://golang.org/cl/185980 mentions this issue: chacha20: expose package and implement XChaCha20

@gopherbot
Copy link

@gopherbot gopherbot commented Jul 13, 2019

Change https://golang.org/cl/185991 mentions this issue: chacha20: implement XChaCha20

@marten-seemann
Copy link
Contributor

@marten-seemann marten-seemann commented Sep 6, 2019

I'd like to add a use case for ChaCha20. QUIC uses it for protecting the QUIC packet header, see https://tools.ietf.org/html/draft-ietf-quic-tls-22#section-5.4.4.

Unfortunately, as far as I can see, the interface suggested in https://go-review.googlesource.com/c/crypto/+/185991/ would not be sufficient for this use case, since QUIC's header protection algorithm relies on setting both the counter as well as the nonce.

@FiloSottile
Copy link
Member

@FiloSottile FiloSottile commented Sep 6, 2019

@marten-seemann Would a SetCounter method help?

@marten-seemann
Copy link
Contributor

@marten-seemann marten-seemann commented Sep 7, 2019

Yes, I think a SetCounter method would work, as long as it allow setting the counter to any uint32 value.

@stevenshea
Copy link

@stevenshea stevenshea commented Sep 26, 2019

Come on, guys, please add the support for xchacha20-ietf-poly1305

@FiloSottile
Copy link
Member

@FiloSottile FiloSottile commented Sep 26, 2019

@stevenshea That's already implemented! :)

https://godoc.org/golang.org/x/crypto/chacha20poly1305#NewX

bored-engineer pushed a commit to bored-engineer/ssh that referenced this issue Oct 13, 2019
The XChaCha20 construction does not have an authoritative spec, but this
implementation is based on the following documents:

https://cr.yp.to/snuffle/xsalsa-20081128.pdf
https://download.libsodium.org/doc/secret-key_cryptography/aead.html
http://loup-vaillant.fr/tutorials/chacha20-design
https://tools.ietf.org/html/draft-paragon-paseto-rfc-00#section-7

Tested against the following implementations:

https://github.com/jedisct1/libsodium/blob/7cdf3f0e841/test/default/aead_xchacha20poly1305.c
https://git.kernel.org/pub/scm/linux/kernel/git/zx2c4/linux.git/diff/lib/zinc/selftest/chacha20poly1305.h?h=zinc
https://git.zx2c4.com/wireguard-go/tree/xchacha20poly1305/xchacha20.go

name                            time/op          speed
Chacha20Poly1305/Open-64-8         225ns ± 1%     283MB/s ± 1%
Chacha20Poly1305/Open-64-X-8       390ns ± 0%     164MB/s ± 0%
Chacha20Poly1305/Seal-64-8         222ns ± 0%     287MB/s ± 0%
Chacha20Poly1305/Seal-64-X-8       386ns ± 0%     165MB/s ± 1%
Chacha20Poly1305/Open-1350-8      1.12µs ± 1%    1.21GB/s ± 1%
Chacha20Poly1305/Open-1350-X-8    1.28µs ± 0%    1.05GB/s ± 0%
Chacha20Poly1305/Seal-1350-8      1.15µs ± 0%    1.17GB/s ± 0%
Chacha20Poly1305/Seal-1350-X-8    1.32µs ± 1%    1.02GB/s ± 0%
Chacha20Poly1305/Open-8192-8      5.53µs ± 0%    1.48GB/s ± 0%
Chacha20Poly1305/Open-8192-X-8    5.71µs ± 1%    1.44GB/s ± 1%
Chacha20Poly1305/Seal-8192-8      5.54µs ± 1%    1.48GB/s ± 1%
Chacha20Poly1305/Seal-8192-X-8    5.74µs ± 1%    1.43GB/s ± 1%

Updates golang/go#24485

Change-Id: Iea6f3b4c2be67f16f56720a200dcc895c0f9d520
Reviewed-on: https://go-review.googlesource.com/127819
Run-TryBot: Filippo Valsorda <filippo@golang.org>
Reviewed-by: Adam Langley <agl@golang.org>
gopherbot pushed a commit to golang/crypto that referenced this issue Nov 11, 2019
Separated the complex buffering logic from key stream generation more
clearly, added plenty of comments and generally refactored the Go
implementation for readability. Made the interface with the
generic/assembly cores smaller and more consistent, according to
golang.org/wiki/TargetSpecific.

We will recover the lost performance on unaligned calls by caching 3/4
of the first round across XORKeyStream invocations, which we now have
complexity budget for.

name                old speed     new speed     delta
ChaCha20/64-4       435MB/s ± 2%  429MB/s ± 2%  -1.47%  (p=0.013 n=10+9)
ChaCha20/256-4      496MB/s ± 1%  493MB/s ± 2%    ~     (p=0.280 n=10+10)
ChaCha20/10x25-4    283MB/s ± 1%  274MB/s ± 2%  -3.13%  (p=0.000 n=10+10)
ChaCha20/4096-4     494MB/s ± 1%  493MB/s ± 5%    ~     (p=0.631 n=10+10)
ChaCha20/100x40-4   421MB/s ± 3%  408MB/s ± 1%  -3.14%  (p=0.003 n=9+9)
ChaCha20/65536-4    515MB/s ± 1%  519MB/s ± 3%    ~     (p=0.161 n=7+10)
ChaCha20/1000x65-4  501MB/s ± 2%  501MB/s ± 3%    ~     (p=0.497 n=9+10)

Also applied a fix for a lingering bug in the ppc64le assembly written
by Lynn Boger <laboger@linux.vnet.ibm.com>.

Updates golang/go#24485

Change-Id: I10cf24a7f10359b1b4ae63c9bb1946735b98ac9b
Reviewed-on: https://go-review.googlesource.com/c/crypto/+/185439
Reviewed-by: Michael Munday <mike.munday@ibm.com>
gopherbot pushed a commit to golang/crypto that referenced this issue Nov 11, 2019
name                old speed     new speed     delta
ChaCha20/64-4       428MB/s ± 1%  432MB/s ± 1%    ~     (p=0.089 n=10+10)
ChaCha20/256-4      497MB/s ± 1%  507MB/s ± 2%  +1.94%  (p=0.000 n=9+10)
ChaCha20/10x25-4    273MB/s ± 1%  285MB/s ± 3%  +4.37%  (p=0.000 n=10+10)
ChaCha20/4096-4     495MB/s ± 1%  508MB/s ± 1%  +2.51%  (p=0.000 n=8+10)
ChaCha20/100x40-4   407MB/s ± 1%  439MB/s ± 1%  +7.92%  (p=0.000 n=9+9)
ChaCha20/65536-4    521MB/s ± 2%  537MB/s ± 1%  +3.00%  (p=0.000 n=10+10)
ChaCha20/1000x65-4  498MB/s ± 2%  521MB/s ± 2%  +4.70%  (p=0.000 n=10+10)

Curiously, even if we omit the critical s.precompDone = true step, we
see a significant performance improvement across the board, maybe due to
reduced register pressure. (See below. Actually using the precomputed
values only impacts the 10x25, 100x40 and 1000x65 benchmarks, as
expected.)

name                old speed     new speed     delta
ChaCha20/64-4       428MB/s ± 1%  428MB/s ± 1%    ~     (p=0.912 n=10+10)
ChaCha20/256-4      497MB/s ± 1%  510MB/s ± 1%  +2.64%  (p=0.000 n=9+10)
ChaCha20/10x25-4    273MB/s ± 1%  277MB/s ± 2%  +1.36%  (p=0.003 n=10+10)
ChaCha20/4096-4     495MB/s ± 1%  507MB/s ± 2%  +2.28%  (p=0.000 n=8+10)
ChaCha20/100x40-4   407MB/s ± 1%  418MB/s ± 1%  +2.69%  (p=0.000 n=9+10)
ChaCha20/65536-4    521MB/s ± 2%  536MB/s ± 1%  +2.76%  (p=0.000 n=10+8)
ChaCha20/1000x65-4  498MB/s ± 2%  519MB/s ± 1%  +4.15%  (p=0.000 n=10+9)

Updates golang/go#24485

Change-Id: I117fab938787819aae1cc4371354888701e4e54b
Reviewed-on: https://go-review.googlesource.com/c/crypto/+/185440
Reviewed-by: Michael Munday <mike.munday@ibm.com>
gopherbot pushed a commit to golang/crypto that referenced this issue Nov 11, 2019
const KeySize = 32
const NonceSize = 12
func HChaCha20(key, nonce []byte) ([]byte, error)
type Cipher struct {}
func NewUnauthenticatedCipher(key, nonce []byte) (*Cipher, error)
func (s *Cipher) XORKeyStream(dst, src []byte)

Small performance hit in chacha20poly1305, probably due to the loss
of the Advance API, which we might consider adding later. No new
allocations, thanks to the mid-stack inliner.

name                            old time/op    new time/op    delta
Chacha20Poly1305/Open-64-8        1.60µs ± 0%    1.68µs ± 1%  +4.94%  (p=0.000 n=9+10)
Chacha20Poly1305/Seal-64-8        1.56µs ± 0%    1.64µs ± 1%  +5.21%  (p=0.000 n=8+10)
Chacha20Poly1305/Open-64-X-8      2.10µs ± 1%    2.22µs ± 1%  +5.81%  (p=0.000 n=10+10)
Chacha20Poly1305/Seal-64-X-8      2.07µs ± 1%    2.17µs ± 0%  +4.88%  (p=0.000 n=10+10)
Chacha20Poly1305/Open-1350-8      15.4µs ± 0%    15.7µs ± 1%  +1.65%  (p=0.000 n=10+10)
Chacha20Poly1305/Seal-1350-8      15.6µs ± 2%    15.9µs ± 1%  +1.58%  (p=0.028 n=10+9)
Chacha20Poly1305/Open-1350-X-8    16.0µs ± 1%    16.3µs ± 2%  +2.00%  (p=0.000 n=10+10)
Chacha20Poly1305/Seal-1350-X-8    15.9µs ± 0%    16.3µs ± 1%  +1.91%  (p=0.000 n=10+8)
Chacha20Poly1305/Open-8192-8      85.6µs ± 0%    86.6µs ± 1%  +1.21%  (p=0.000 n=10+10)
Chacha20Poly1305/Seal-8192-8      85.7µs ± 0%    86.3µs ± 0%  +0.68%  (p=0.001 n=9+9)
Chacha20Poly1305/Open-8192-X-8    86.4µs ± 1%    87.1µs ± 1%  +0.76%  (p=0.035 n=10+9)
Chacha20Poly1305/Seal-8192-X-8    86.0µs ± 0%    87.0µs ± 1%  +1.14%  (p=0.000 n=9+9)

Updates golang/go#24485

Change-Id: I2ec2ef487a03f013049915d9063751c75a78408b
Reviewed-on: https://go-review.googlesource.com/c/crypto/+/185980
Reviewed-by: Michael Munday <mike.munday@ibm.com>
@golang golang locked and limited conversation to collaborators Nov 10, 2020
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
You can’t perform that action at this time.