Lesson 9 of 9
Breaking XOR encryption
- 15 min
- 5 checks
- 3 hints
- Go to task
Goal
Undo XOR and try every key
Explanation
XOR compares two bits and gives 1 if they differ and 0 if they're the same. It has one property that made it the most popular way to hide data inside programs: apply it twice with the same key and the value comes back unchanged, so a ^ k ^ k == a. That means encrypting and decrypting are the same operation.
The simplest form is a one-byte key applied to every byte, with the expression bytes(b ^ key for b in data). A little stronger is a repeating key: several bytes that cycle over the data, so byte number i is XORed with key byte number i % len(key).
A one-byte key is very weak, because it has only 256 possible values, so you can try them all. But how do you tell which key is right? If the original is English text, most wrong keys produce non-printable bytes and get ruled out. That still leaves quite a few keys with printable output: in this example 56 of the 256 keys are left, and every one of them except the right key gives meaningless symbols. So from what's left you pick the key that produces the most letters and spaces:
xor(c, 0x00) b"qddqs{0qd0tqg~" 10
xor(c, 0x1d) b"lyylnf-ly-ilzc" 12
xor(c, 0x10) b"attack at dawn" 14
The number at the end of each line is the count of letters and spaces in the output. The first key that gives printable output isn't necessarily the right one, and this score is what settles it.
Your task
Write a function xor(data, key) with a one-byte key and a function xor_repeat(data, key_bytes) with a repeating key, both returning bytes. Then write a function recover(data) that tries the keys from 0 to 255, rules out every key that produces a non-printable byte, and returns, from the keys that are left, the one that produces the most letters and spaces.
Checks
5 checks- xor undoes itself
- The repeating key cycles over the bytes
- recover finds a hidden key
- recover finds other keys
- The recovered text is all printable