XOR
An operation between bits used often in cryptography
Last updated
An operation between bits used often in cryptography
Last updated
Understanding XOR is very important in cryptography because a lot of encryption algorithms use it in some way. XOR stands for eXclusive OR, meaning it's the OR operation but without 1+1 being true. You can see a truth table below:
This means that only if the two values are different, the XOR function will return 1. It also means that if one value is 1, the result will be the inverse of the other value. So XORing with 1 is basically flipping a bit.
Often you're working with long strings of bytes that are XORed, but this works the same way, just doing XOR for every bit:
The nice thing about XOR is also the fact that encryption and decryption are the exact same operation because you're just flipping the bits where the key is 1. When decrypting you're just flipping the bits back:
But this also means that if you know the ciphertext, and the plaintext you can XOR them both to get the key:
Since XOR encryption works bit-by-bit you don't even need to know the whole plaintext to get part of the key. If you know only the first few characters of the plaintext, or in some special positions you can still get the key at those same positions.
Repeating-key XOR is when a key for XOR is shorter than the plaintext/ciphertext and needs to be repeated to fill the space.
Using some analytical techniques it's possible to abuse this fact to brute-force the key byte-by-byte by looking at what the plaintext would be after decrypting. You can filter out any non-printable characters for example to narrow down a lot of results, and there are lots of techniques fo finding how normal a text looks. As you can imagine this works better for longer plaintexts, because the key will be repeated more times.
There is a useful tool that finds the key length, and brute-forces it automatically:
The One-Time Pad (OTP) is a well-known unbreakable cipher. The important thing though is One-Time, and when the key is used multiple times instead, it becomes insecure very quickly.
This answer explains the idea behind the "Many-Time Pad" attack. The main takeaway is that if you guess one character at a position correctly, you can get back the secret at that index, and reuse that for other ciphertexts to make better guesses.
A simple but useful tool here is the one linked below. You provide two ciphertexts and can guess common strings like " the " or ". The " or others if you know part of the plaintext. The tool will show what the other plaintext must be at all positions. Try to find a plausible text here, and click Output 1/2 to save it there and continue:
After finding a chunk of plaintext, a useful interactive tool is MTP by CameronLonsdale. It allows you to write letters in all plaintext guesses at the same time to see if anything makes sense:
XOR
0
1
0
0
1
1
1
0
