Uncovering Cicada Wiki
Advertisement

What does XOR mean?

XOR simply means one or the other but not both (or "eXclusive-OR") are true.

"You took an apple (x)OR you took an orange."

If you take neither or both, you didn't follow the rules and the entire thing is false - but parts (eg: you took an orange) can be true

If you take an orange and you did not not take an apple then you would have

"You took an apple" = false

"You took an orange" = true

"You took an apple (x)OR you took an orange." = false XOR true = true (exactly one must be true).


Similar words like 'and', 'or', 'not' also can also form phrases that can be true or false.

These words are Logical operators.

Because Xor, Or, And all take two things (A or B, C and D) to make sense, they are called "binary operators" (binary meaning 2 - not to be confused with binary numbers yet).

In Computers

From this you can see that XOR outputs a single yes/no (true/false) and takes two single yes/nos.

In computers, a single no/yes value is referred to as a "bit" and is represented by 0's and 1's.

(aside: this is the smallest unit of computer information and helps form every other number computers use)

So you could see how you could say 0 XOR 1 = 1 from the above example and be saying the exact same thing.

From before, we know XOR acts on a pair of bits (since it is a 'binary operator') to output a new one.

if were to feed in two series of bits (1010,1001) into XOR we could make it check each corresponding pair of bits (the 1st pair, the 2nd pair, etc...)

1 XOR 1 = 0

0 XOR 0 = 0

1 XOR 0 = 1

0 XOR 1 = 1

so it would provide a third series of bits containing the result of each pair (0011)

In most modern implementations, this is actually what XOR does - it takes in two numbers representing series of bits and outputs a third being the result of comparing the two.

Because XOR can act on bits of a number in this way, it is referred to as a bitwise operation.

Finally consider that a modern byte on most systems is 8 bits, and serves as a basic unit for files in most systems to the extent that text is commonly saved as a byte for each letter.

Since bytes are made of bits (and can be represented as numbers), you can also XOR them - the result probably won't be text though if you put text in.

 Applications

One thing you may notice about XOR (considering the two inputs and one output) is that if you know any two values, you can tell for sure what the third is with certainty.

This is not the case with OR (? OR yes = yes) and AND ( ? AND no = no) which can be ambiguous.

In fact, XOR is self-reversible in that if you XOR any two values, you receive the third!

XOR also preserves the statistical randomness of values - a random value XORd with a nonrandom one can result in a value that is indistinguishable from random.

Because of these traits XOR is useful in efficient programming (swapping values without keeping track), some cryptography and many many other fields.

XOR can be thought of in a few different useful ways as well:

  • it shows you which bits are different between two inputs (detect change).  Combine with NOT to get an equivalence check XNOR.
  • XORing an input against 1 always negates it (same as NOT)
  • you can XOR bits against a "toggle mask" which negates only the selected bits. (selective NOT)


There are many other applications for XOR, these are just a few obvious examples.

XOR and OTPs

The traits listed above (self-reversibility and preservation of randomness) make XOR a useful option to encode messages in an unbreakable cipher known as a one-time-pad. (although something with these qualities is not required).

In a one-time-pad you have a series of numbers or letters used as a secret "key" which ideally cannot be guessed, is not reused in any way, and will only be used for a single message.

By XORing each corresponding number of a key and a message, you receive a ciphertext which can't be reversed or easily anaylzed without information about the key or message. (assuming the key is strong/random). It could be considered a naive deniable encryption since a random key will produce a random-like result.

While this is useful in theory, used in the past by intelligence bodies, and even used in components of cryptography - it is not typically used as a crytographic option by itself in modern times.

Tools and Tutorials for XORing

Nox Populi has made a video on the XOR operation that we recommend watching. It can be found here.

Crash Demons's tool from OTP22, XORs files with different offsets looking for ASCII characters. It can be found here

A truth table for XOR, AND, and OR:

XOR
x1 x2 x1⊕x2
0 0
0
0 1
1
1 0
1
1 1
0
AND
x1 x2 x1∧x2
0 0
0
0 1
0
1 0
0
1 1
1
OR
x1 x2 x1∨x2
0 0
0
0 1
1
1 0
1
1 1
1
Advertisement