Go: x/crypto: add chacha20, xchacha20

[riobard]

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.

[ALTree]

Related: #23885 (add support for XChaCha20).

[bcmills]

(CC: @FiloSottile)

[rsc]

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]

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

[aead]

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

[FiloSottile]

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]

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]

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]

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

[riobard]

@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]

@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]

@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]

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

[aead]

@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]

@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]

@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]

@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]

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]

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

[FiloSottile]

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?

[riobard]

@FiloSottile For low-level crypto code, I think it's better to keep it consistent with DJB's original NaCl and libsodium API, as it makes the job easier to port code from/to C. Fewer things to learn and mess up at least.

I need to supply different nonce and key per invocation so the one-shot function is fine.

[FiloSottile]

@riobard Since we have an idiomatic Go interface which works for a superset of use-cases, we should use it. Matching C APIs is not a goal of the Go crypto libraries.

[bcmills]

@FiloSottile, I'm curious why you suggest returning cipher.Stream rather than a concrete type that implements it. What leads you to believe that the chacha20 implementation will never have any interesting methods beyond XORKeyStream?

(See http://golang.org/wiki/CodeReviewComments#interfaces.)

[riobard]

@FiloSottile But the cipher.Stream interface has different signature and semantics than that of salsa20 and chacha20.

Salsa20 differs from many other stream ciphers in that it is message orientated rather than byte orientated. Keystream blocks are not preserved between calls, therefore each side must encrypt/decrypt data with the same segmentation.

Another aspect of this difference is that part of the counter is exposed as a nonce in each call. Encrypting two different messages with the same (key, nonce) pair leads to trivial plaintext recovery. This is analogous to encrypting two different messages with the same key with a traditional stream cipher.

If you give me just a cipher.Stream, I cannot specify nonce. Therefore it's a subset rather than a superset of use cases. I'd still need a way to call the underlying XORKeyStream function somehow.

[riobard]

@bcmills Yeah, this problem appears elsewhere too, e.g. AEAD implementations return cipher.AEAD interface instead of concrete types. Does changing from returning an interface to returning a concrete type implementing that interface violate Go1 compatibility promise? API does change, but nothing should break I guess?

[FiloSottile]

@riobard Ah, no, the issue here is that I forgot the nonce argument to NewUnauthenticated. Now the issue is that I dislike both having two easy to invert []byte arguments, and clunky *[N]byte arguments requiring extra copies and risking incomplete copy()s. The good news is that there is no overlap in nonce and key lengths, so we can catch inversions at runtime, so let's go for

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

Does that make it a superset?

@bcmills Well I can't imagine what else it might be doing, after all the alternative we are discussing is a single XORKeyStream package level function. And the other advantage of returning concretes—type assertions—is blocked by the fact that most other cipher.Stream implementations (from crypto/cipher) are unexported. So a CIpher type felt like API clutter. But maybe it's not a good enough reason to break style?

[FiloSottile]

SetCounter is actually an example of a possible useful method, proving there's a reason style should be followed even if one can't think of why at the moment. Let's have a Cipher type.

And while at it, no need for NewXUnauthenticated when we can look at the nonce length.

import "golang.org/x/crypto/chacha20"
func NewUnauthenticated(nonce, key []byte) (*Cipher, error)
func (*Cipher) XORKeyStream(dst, src []byte)

import "golang.org/x/crypto/salsa20"
func NewUnauthenticated(nonce, key []byte) (*Cipher, error)
func (*Cipher) XORKeyStream(dst, src []byte)
func XORKeyStream(out, in []byte, nonce []byte, key *[32]byte) // Existing.

I'm glad to see this nearly matches the github.com/aead/chacha20 API by @aead.

[riobard]

Ah I see.

In which case I would propose we go for the same API as in https://godoc.org/github.com/aead/chacha20 by @aead and make the main function func NewCipher(nonce, key []byte) (*Cipher, error), as there's nothing about authentication in stream ciphers anyway.

Wait… so why don't we just take @aead's implementation and amend crypto/salsa20 to match that? :D

[aead]

To summarize the current state:

• New struct type Cipher representing a (X)ChaCha20 stream cipher instance.
• New function NewUnauthenticated(nonce, key []byte) (*Cipher, error) or
  NewCipher(nonce, key []byte) (*Cipher, error).
• Cipher implements cipher.Stream (and maybe SetCounter(...) to allow e.g. random access)

---

Now some personal opinions:

1. I can see the idea behind NewUnauthenticated to explicitly mention that the primitive does not provide integrity (IND-CTXT). However, I would go for NewCipher for two reasons:
   
   
   
   • NewCipher(...) matches the crypto/aes package API that is probably used most frequently. So chacha20.NewCipher(...) will look familiar and consistent.
   
   
   • If there is a type Cipher then it is obvious that NewCipher will create a new instance of that type.
     
     The package doc should mention that chacha20 does not provide integrity, anyway.
   
   
2. It's not really clear to me what's the rationale behind XORKeyStream(out, in []byte, nonce []byte, key *[32]byte) (salsa20 and chacha20 API). It's implementation is pretty much:
   c, err := NewCipher(nonce, key) if err != nil { panic(err) } c.XORKeyStream(dst, src)
   Maybe it's worth to implement it just to make code using it a bit simpler - but is
   chacha20.XORKeyStream(...) really a common thing to do?!

[bcmills]

I can't imagine what else it might be doing, after all the alternative we are discussing is a single XORKeyStream package level function.

The main thing you can do with concrete types is add methods later: for example, methods to report block sizes or the number of blocks encoded, or to seed initial state.

I'm not saying that you need any of those now — just that it's difficult to predict that you will not need them, and if you do the package will be much cleaner if the type on which those methods are documented is the same as one returned by the corresponding New function.

[bcmills]

@riobard

Does changing from returning an interface to returning a concrete type implementing that interface violate Go1 compatibility promise?

Yes. Consider the following snippet:

s := cipher.NewCTR(block, iv)
s = chacha20.NewAuthenticated(nonce, key)

[bcmills]

@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]

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 https://github.com/golang/go/issues/24485#issuecomment-463525235 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 https://github.com/golang/go/issues/24485#issuecomment-463525235 that you are right, but about Reset... https://go-review.googlesource.com/c/go/+/162297 ;)

[FiloSottile]

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

[aead]

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

[riobard]

@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]

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]

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

[gopherbot]

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

[gopherbot]

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

[gopherbot]

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

[marten-seemann]

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]

@marten-seemann Would a SetCounter method help?

[marten-seemann]

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

[stevenshea]

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

[FiloSottile]

@stevenshea That's already implemented! :)

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