proposal: bytes.Xor

[kixelated]

Variation of #28113 (rejected proposal)

I would like to export the optimized xorBytes implementation in crypto/cipher. Unlike the above ticket, I think it should be a member of the bytes package as bytes.Xor.

Applying a XOR over multiple bytes is commonly used in crypto as well as parity generation. It is was relatively trivial to implement yourself but thanks to a recent contribution, the Go version is now very optimized.

package bytes

// Xor will xor each byte in a and b, writing the result to dst. 
// The destination should have enough space, otherwise Xor will panic.
// Returns the number of bytes written, which will be the minimum of len(a), and len(b).
func Xor(dst, a, b []byte) int

Currently, xorBytes will panic when dst is not large enough. It could follow copy semantics and write up to min(len(dst), len(a), len(b)) bytes. But it seems relatively common to panic in the crypto package when the dst buffer is not large enough, such as XORKeyStream.

[kixelated]

My use-case is for a webrtc library.

I'm currently profiling the application and a sizable amount of time is spent in NewCTR. The SRTP spec states that each packet (<1400 bytes) uses a new CTR cipher based on the header information (it's careful to not reuse the same IV).

This line is one of my current bottlenecks, as it generates a slice of size 512 on the heap each time. NewCTR accounts for 2.16% of the program's execution time according to pprof.

My plan was to write my own CTR class, potentially abusing the fact that AES has a fixed block size to allocate on the stack. However, I'm not able to go down this route without lifting the fast xorBytes implementation from crypto/cipher. It's probably not a blocker; I just don't think it should be necessary to copy the assembly optimized functions that are used extensively in the stdlib but are not exposed.

For now, I'm evaluating a few alternative approaches but all of them involve Go changes.

Later in the project, I will have to implement FEC. Forward error correction is performed by XORing multiple packets together (in a specific way) to create parity packets. This is similar to RAID5, which is another example of when a fast bytes.Xor function would be desirable.

[kixelated]

Also worth mentioning, this is similar to the purpose of the math/bits package. Go developers should not have to resort to assembly implementations for efficiency if the function is common and can be well defined.

[josharian]

This might be a better fit for golang.org/x/crypto(?).

cc @FiloSottile

Btw, Filippo, I see that the amd64 version uses SSE2. Any interest in me adding an AVX2 version?

[kixelated]

@josharian Possibly, but I was thinking crypto/cipher would import bytes instead of having two disjoint implementations.

[josharian]

I think the chance of adding this to bytes is vanishingly small.

To ask some obvious questions: what about And? Or? Andnot? All three of those (but not Xor) are used in sometimes hot code in the compiler (bv.go). And package bytes is not really a catchall home for things related to byte slices; it’s more a sibling package to strings, which makes it more focused on textual tasks.

[kixelated]

Yeah, that's fair. Adding it somewhere like golang.org/x/crypto would help my situation so long as you guys are okay with the code duplication.

[mvdan]

What about adding it to crypto/cypher directly?

[mundaym]

For now, I'm evaluating a few alternative approaches but all of them involve Go changes.

For the AES-CTR use case I think changing the Go standard library implementation of the CTR cipher mode would be preferable to adding any new APIs. It shouldn't be too complicated to make the buffer lazily allocated, i.e. allocated only if extra state is needed across XORKeyStream calls. Note also that you probably want to stick with the Go standard library implementation to pick up any future assembly optimizations (see #20967).

[kixelated]

@mundaym that's what I thought of doing too, but crypto/aes would need access to xorBytes in crypto/cipher. It would have to be moved to an internal package or made public somehow.

[mundaym]

@kixelated I think it would be reasonable to put it in an internal package, probably under crypto/internal. That is definitely preferable to a new public API.

The implementation of xorBytes should be constant time for crypto uses (i.e. the execution time should be not depend on the data) so it might perhaps make sense for it to live in crypto/internal/subtle rather than adding another internal package. We could then consider moving it to the crypto/subtle package if we wanted to make it public later.

[rsc]

Like Josh said, there's basically no chance of this being bytes.Xor.

One option would be for the compiler to recognize

for i := range d {
  d[i] = a[i] ^ b[i]
}

but even that seems too specialized. Probably better would be to start with a package x/crypto/bits or something like that.

/cc @FiloSottile to see if we want to retitle as an x/crypto proposal or else close.

[FiloSottile]

If it looks good to the compiler folks, I'd rather have it via pattern-matching than make a name-conflicting bits package for a single function.

[josharian]

@FiloSottile does it need to be constant time (per #30553 (comment))? If so it seems like it belongs in subtle and definitely not in the compiler. (There’s nothing about the Go code that is necessarily constant time—if a compiler could prove that b is all zero, then it a no-op.)

Assuming that that is ok, I don’t personally object to the pattern matching. It’s easy enough to implement and maintain, and though it does contribute a little bit to binary bloat, it is nice to have obvious, clear Go code be fast.

P.S. Did you want an AVX2 version?