crypto/subtle: add XORBytes

[jech]

The function crypto/cipher.xorBytes performs a well defined, simple operation that is very common in cryptographic algorithms and network protocols. The stdlib contains a number of optimised assembler versions of this function.

The Pion libraries, in particular, contain their own version of xorBytes, which is far from being as optimised as the Go version. If xorBytes were exported, it would yield an immediate performance boost for Pion, and possibly other cryptographic or networking libraries.

An alternative would be to put that function under x/, so that it doesn't need to remain compatible. However, since the operation that this function performs is simple and well-defined, the cost of exporting it from the stdlib itself seems fairly minor to me.

[seankhliao]

cc @golang/security

[josharian]

Previously discussed and declined in #30553. Sounds like x/ was OK but no one did the work(?).

See also #42010 #35381 #28465. There’s a lot of demand.

[rsc]

Where would it go if it were exported? crypto/subtle? (It's definitely the case that if you are XOR'ing two byte slices together you'd better know what you are doing.)

It seems too special-purpose for package bytes. Are there any uses that are not crypto?

/cc @golang/security

[rsc]

This proposal has been added to the active column of the proposals project
and will now be reviewed at the weekly proposal review meetings.
— rsc for the proposal review group

[josharian]

Are there any uses that are not crypto?

The only other things I can think of are RAID/ECC and some unusual codecs. In practice, every request I've seen in the Go world is for cryptography.

[meling]

@racin implemented a function for this for entanglement codes. Arguably our use-case is not a commonly used coding technique, but it's at least one data point that xorBytes does have other uses than cryptography.

[rsc]

If we can figure out where it should go, then it seems OK in principle to add something to the standard library.

But we could also recognize the pattern and optimize it in the compiler without any visible API. That's what we do already for:

for i := range a {
    a[i] = 0
}

which turns into a memset. We could also recognize

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

and turn that into some other library call.
We also do this kind of thing for encoding/binary's various integer assembly/disassembly routines.

I suppose we'd have to figure out what the right pattern is, but maybe that's easier than designing new API.

[jech]

But we could also recognize the pattern and optimize it in the compiler without any visible API.

Perhaps I'm in the minority here, but I prefer a library function to some magic pattern. I find it easier to call a well-documented library function than to check the generated assembler in order to make sure that some magic pattern has matched.

[rsc]

I'm OK with adding it to the library but we haven't figured out a good place.
If we did add it to bytes, I assume we wouldn't add it to strings.
And it wouldn't allocate, it would have to take a dst, which is different from things in bytes.

If it were to go into a new package that was super-fast operations on byte slices,
what related operations might go into that package?
Maybe zeroing a byte slice?
Copying is just 'copy' the builtin.

Having the compiler recognize it doesn't seem so bad compared to all this.

[racin]

If it were to go into a new package that was super-fast operations on byte slices,
what related operations might go into that package?

As @meling mentioned I used xorBytes previously for snarl.

However, there seems to be a subtle difference with the xorBytes in crypto/cipher, for the case where the two input byte slices differ in length.

In my case, I kept the overflowing bytes of the longest one, whilst in the latter implementation the overflowing input seems to be discarded.

[josharian]

One advantage to the library function is that the implementation bar is lower. The compiler optimization must ensure that it preserves the semantics precisely, including in the case of panics partway through (exactly what memory writes occur, exactly what panic occurs, and on what line). That could end up making a difference for short byte slices, where overhead matters.

On the other hand, the compiler optimization can apply to xor of anything (named uint8s, uint64s, etc.), which seems pretty nice.

My 2c would be to start with the compiler optimization, unless there's some reason that this needs to be constant time, in which case it (a) clearly belongs in crypto/subtle and (b) cannot be done just with compiler optimizations.

[iDigitalFlame]

Been following this as I use xorBytes in some packages of mine.

@racin Brings up a good point, which bit me also. If this does get exported/linked we should make that known in the comment/doc for it.

While I agree with @josharian, my 2c would be to just add it to crypto/subtle for now (it should just be a simple linkname) that would fulfill the need. The compiler optimization scenario, which seems more complicated, could be implemented later on as an added benefit.

[mvdan]

Given that xorBytes does a bitwise XOR, we could also consider math/bits. None of its current APIs work on slices, but conceptually I think it fits better than in bytes, and it doesn't restrict us to cryptography either.

[josharian]

we could also consider math/bits

We could also consider it the seed of a future SIMD package.

/me ducks

[jech]

If it were to go into a new package that was super-fast operations on byte slices, what related operations might go into that package?

I think it's pretty much a one-off — I don't think there are many operations that are both that simple and impossible to avoid. Let's just dump it in bytes, and be done with it. We can always create a more comprehensive package if more such functions appar (and deprecate the version in bytes).

[rsc]

It seems like the choices are:

crypto/subtle.XorBytes
math/bits.XorBytes
bytes.Xor

What people want this for is crypto, so it seems like crypto/subtle is probably the right place to start. It just doesn't seem general enough for bytes, nor does it fit into the rest of the operations in math/bits (none of them are about slices).

Does anyone object to crypto/subtle.XorBytes?

[FiloSottile]

Agreed on crypto/subtle. Maybe subtle.XORBytes or subtle.XOR though?

[rsc]

I spelled it Xor instead of XOR to match math/big.
It doesn't matter much but it seems like we should be consistent.

[rsc]

Does anyone object to crypto/subtle.XorBytes?

(Didn't do plain Xor because maybe some other thing will need subtle xor'ing too.)

[rsc]

On the other hand, Ian points out that crypto/cipher has XORKeyStream, so maybe XORBytes is better to match other things in crypto. I'm happy to do that too.

[rsc]

Fixed title to match my comment from last week.

[rsc]

Based on the discussion above, this proposal seems like a likely accept.
— rsc for the proposal review group

[rsc]

No change in consensus, so accepted. 🎉
This issue now tracks the work of implementing the proposal.
— rsc for the proposal review group

[gopherbot]

Change https://go.dev/cl/421435 mentions this issue: crypto/subtle: add XORBytes