Lecture 21: XOR: The Simple Binary Operation at the Heart of Modern Ciphers

Sequentia Explores: The Mathematics of Crypto

Part III: Historical Ciphers & the Dawn of Cryptanalysis

Lecture 21: XOR: The Simple Binary Operation at the Heart of Modern Ciphers

In our exploration of modern ciphers like AES, we’ve talked about high-level steps like “mixing in the key.” But what does that actually mean? How do you mathematically “combine” a block of plaintext with a secret key in a way that is both secure and perfectly reversible?

The answer lies in one of the simplest, most elegant, and most powerful operations in all of computer science: the Exclusive OR, universally known as XOR.

XOR is a bitwise logical operation. It works directly on the individual bits (the 1s and 0s) of your data. While we’ve discussed complex topics from number theory and abstract algebra, XOR brings us right back to the fundamental language of computers.

How XOR Works: The “One or the Other, But Not Both” Rule

The XOR operation compares two bits and produces a single bit as output based on a simple rule:

The output is 1 if the two input bits are different.
The output is 0 if the two input bits are the same.

Let’s look at the four possibilities:

• 0 XOR 0 = 0 (inputs are the same)
• 0 XOR 1 = 1 (inputs are different)
• 1 XOR 0 = 1 (inputs are different)
• 1 XOR 1 = 0 (inputs are the same)

This operation is performed on data bit by bit. For example, let’s XOR two 8-bit bytes together:

Plaintext Byte: 10110010
Key Byte: 01101011
————————-
Result (XOR): 11011001

You can see that for each column, we just apply the XOR rule. In the first column, 1 XOR 0 = 1. In the second, 0 XOR 1 = 1. In the third, 1 XOR 1 = 0, and so on.

The Magic of Reversibility

This simple operation has one truly magical property that makes it perfect for cryptography: XOR is its own inverse.

What does this mean? If you take a result and XOR it with the same key a second time, you get your original data back perfectly.

Let’s try it with our result from above:
Result from before: 11011001
The SAME Key Byte: 01101011
—————————–
Final Result (XOR): 10110010

Look familiar? It’s our original Plaintext Byte!

Mathematically, this can be expressed as:
(A XOR B) XOR B = A

This is the cryptographic equivalent of a reversible reaction. You combine your plaintext (A) with a key (B) to get ciphertext. To decrypt, you simply combine the ciphertext with the exact same key (B) to get your original plaintext (A) back.

Why XOR is a Cryptographer’s Best Friend

This property makes XOR the ideal tool for applying a key to data in symmetric cryptography.

1. Perfect Reversibility: As we’ve seen, the same simple, fast operation is used for both encryption and decryption. This is incredibly efficient.
2. Perfect Scrambling: If your key is truly random, the resulting ciphertext will also be truly random and bear no statistical relationship to the original plaintext. A 0 in the plaintext has an equal chance of becoming a 0 or a 1 in the ciphertext, depending on the corresponding bit in the key. This provides perfect confusion on a bit-by-bit level.
3. Speed: XOR is one of the fastest operations a computer’s processor can perform. It’s a fundamental instruction built directly into the hardware. This makes XOR-based encryption extremely fast.

XOR in Action: Stream Ciphers and the One-Time Pad

The power of XOR is most purely demonstrated in stream ciphers. A stream cipher generates a long sequence of pseudo-random bits from a secret key, called the keystream. This keystream is then XORed with the stream of plaintext bits to produce the ciphertext. To decrypt, the recipient uses the same secret key to generate the exact same keystream and XORs it with the ciphertext.

This leads us to the only theoretically perfect, unbreakable cryptosystem ever devised: the One-Time Pad (OTP). An OTP is a stream cipher with two strict rules:

1. The key must be truly random.
2. The key must be at least as long as the message and never, ever reused.

If these conditions are met, the resulting ciphertext is mathematically proven to be unbreakable. An attacker who sees the ciphertext has absolutely no information about the original plaintext, because every possible plaintext of the same length is an equally likely decryption. However, the practical difficulty of securely generating, distributing, and managing these long, single-use keys makes the OTP impractical for most modern applications.

XOR in Block Ciphers like AES

While not the only operation, XOR is still a critical component in block ciphers. In AES, the AddRoundKey step—where the secret key is mixed with the data in every round—is performed using a simple XOR operation. The 128-bit State is XORed with a 128-bit round key. This step is crucial for integrating the key’s secret information into the encryption process at every stage, preventing an attacker from analyzing the rounds in isolation.

The humble XOR operation, with its simple “different means 1, same means 0” rule, is a testament to how the most basic binary logic can be leveraged to create the most profound cryptographic effects. It is the ultimate reversible “scrambler” at the heart of nearly every modern symmetric cipher.

In our next lecture, we will look at Block Cipher Modes of Operation, exploring how we take a block cipher like AES, which can only encrypt a single fixed-size block, and use it securely to encrypt messages of any length.