Blog / Cryptography

1056 words

  • go
  • crypto-subtle
  • one-time-pad
  • xor
  • cryptography
  • security

Go's subtle.XORBytes and Why One-Time Pad Code Still Leaks

Here is a function that looks like a textbook one-time pad, using the standard library and nothing else:

package main

import (
	"crypto/rand"
	"crypto/subtle"
	"fmt"
)

func main() {
	msg := []byte("transfer 100 pounds to alice")

	key := make([]byte, 8)
	if _, err := rand.Read(key); err != nil {
		panic(err)
	}

	n := subtle.XORBytes(msg, msg, key)
	fmt.Printf("xored %d of %d bytes\n%q\n", n, len(msg), msg)
}

The key is random, from crypto/rand. The XOR is done by crypto/subtle, which exists specifically for this sort of thing. The output starts with eight bytes of noise and then continues, cheerfully, with " 100 pounds to alice" in the clear. The function did exactly what it documents, and the "encryption" did nothing for most of the message.

What XORBytes actually promises

subtle.XORBytes(dst, x, y []byte) int arrived in Go 1.20. It XORs x and y into dst and returns the number of bytes it processed, which is min(len(x), len(y)). Three details matter:

  • It does not complain when the inputs differ in length. It stops at the shorter one and tells you how many bytes it did, and it is on you to look at that number.
  • It panics if dst is shorter than that count, and it panics if dst partially overlaps x or y. Exact overlap, as in my example above, is allowed, and that is precisely the case that bites.
  • Its running time depends on the length, not on the contents. That is the "subtle" part, and it is a real property, but it is a property about timing. It says nothing about whether your scheme is secure.

The in-place call is where the example goes wrong. With dst equal to msg, any bytes beyond n are simply never touched, so they stay as plaintext. If you allocate a fresh zeroed dst instead, the tail comes out as zeros: no plaintext leak, but you have silently thrown half the message away. Both are bugs; the first is just quieter.

A pad has to be at least as long as the message, so check that before touching anything:

func xorPad(msg, key []byte) ([]byte, error) {
	if len(key) < len(msg) {
		return nil, fmt.Errorf("pad too short: %d key bytes for %d message bytes", len(key), len(msg))
	}
	out := make([]byte, len(msg))
	subtle.XORBytes(out, msg, key)
	return out, nil
}

Now the more interesting failures, because the length check is the easy one.

The pad is called one-time for a reason

XOR is its own inverse, so c1 = p1 ^ k and c2 = p2 ^ k gives you c1 ^ c2 = p1 ^ p2. The key drops out entirely. An attacker holding two ciphertexts made with the same pad has never needed the pad; they have the XOR of two plaintexts, and natural-language plaintexts are very bad at hiding inside each other.

func main() {
	key := make([]byte, 32)
	if _, err := rand.Read(key); err != nil {
		panic(err)
	}

	p1 := []byte("attack at dawn, bring the ladders")[:32]
	p2 := []byte("retreat to the harbour by noon!!")[:32]

	c1, _ := xorPad(p1, key)
	c2, _ := xorPad(p2, key)

	// attacker view: no key, two ciphertexts
	both := make([]byte, 32)
	subtle.XORBytes(both, c1, c2)

	// guess that the first message starts with "attack"
	guess := []byte("attack")
	leak := make([]byte, len(guess))
	subtle.XORBytes(leak, both, guess)
	fmt.Printf("%q\n", leak) // "retrea"
}

Guess a word in one message and the matching bytes of the other fall out. Slide the guess along ("crib dragging") and you recover both messages, given enough patience. This is how a lot of real-world stream-cipher and pad misuse gets broken, and it is not specific to Go; but Go makes it very easy to write because nothing in the API stops you calling XORBytes twice with the same key slice.

In practice the reuse rarely looks like two calls next to each other. It looks like a key file that is loaded at start-up and never advanced, or a "pad" that is a fixed-length random blob applied to every record, or a pad that wraps round with key[i % len(key)] when it runs out. A repeating key is a Vigenere cipher, and those were being broken by hand a long time before computers.

Also, and I keep meaning to write a whole post about this, a pad has to be truly random. Bytes from a seeded pseudo-random generator are not a pad; they are a stream cipher with a very small key (the seed), and usually a weak one. Use crypto/rand, and remember that the pad is as long as the data, so you also need a way to get it to the other party that is at least as secret as the message you are trying to protect. If you had that channel, you could have sent the message over it.

Perfect secrecy is not integrity

Actually, this is the bit people find least intuitive. Even a correctly used one-time pad, with a fresh random key of the right length, gives you no integrity at all. Ciphertext is malleable: flip a bit in the ciphertext and the same bit flips in the plaintext, and the receiver has no way to tell.

func main() {
	msg := []byte("transfer 100 pounds to alice")
	key := make([]byte, len(msg))
	if _, err := rand.Read(key); err != nil {
		panic(err)
	}

	ct, _ := xorPad(msg, key)

	// attacker knows the format, not the key
	ct[9] ^= '1' ^ '9'

	pt, _ := xorPad(ct, key)
	fmt.Printf("%s\n", pt) // transfer 900 pounds to alice
}

The attacker never learned the key and never needed to. They only needed to know that byte 9 holds the digit "1" and to want it to be a "9". Shannon's proof covers confidentiality against someone who only reads the ciphertext. It says nothing about someone who edits it.

The fix is a MAC over the ciphertext, verified before you decrypt anything, and this is where crypto/subtle earns its name for real: compare tags with subtle.ConstantTimeCompare, not bytes.Equal. Mind that it returns early on a length mismatch, which is fine for fixed-size tags but worth knowing about. If you are reaching for a pad plus a MAC plus a length check plus a way of never reusing keys, you have built a worse AEAD by hand. AES-GCM or ChaCha20-Poly1305 from the standard library does the same job with better failure modes (though GCM has its own nonce-reuse cliff, which is the same lesson wearing a different hat).

Length still leaks

One more, quickly. XOR preserves length exactly. The ciphertext is as long as the message, so anyone watching learns the length, and "yes" and "no, and here is why" are trivially distinguishable. If message size is sensitive, pad the plaintext to a fixed block size before XORing, and make sure the padding is part of what the MAC covers.

When XORBytes is the right tool

None of this makes XORBytes a bad function. It is the right thing for combining two equal-length byte strings without a hand-written loop: applying a keystream someone else's vetted cipher produced, masking values in a protocol that specifies exactly that, or XORing secret shares together (as in an XOR-based secret-splitting scheme, where every share is uniformly random and the same length as the secret). In those cases the surrounding design already answers the questions the function ignores: who guarantees the lengths, who guarantees the key is never reused, and who authenticates the result.

The function is constant-time and the arithmetic is trivial. All the cryptography is in the things it does not check, so check them yourself, and check the returned n while you are there.

← Back to the blog