An XOR cryptanalysis writeup

A slightly anonymised - variant of a writeup I did for a CTF.

The principle of XOR encryption is fairly simple: for each bit in your plaintext, you apply the following truth table:

	True	False
True	False	True
False	True	False

i.e. return True if and only if the two elements are different. This produces a strong ciphertext - if the key is as along as the text (and if you don’t retransmit the same information, or reuse keys, which in practice along with key-length demands is why we don’t use purely XOR all that much). This is the origin of the fabled one-time pad. With a short key, however, patterns emerge. In this case, we know the key is 6 chars, although you could find that out by comparing Hamming distances. For the record, this is very similar to challenges in cryptopals and project euler (the latter has a much shorter key, so is easier; the former requires you find the key length yourself).

Let’s make some guesses. First, that a “character” is one byte (i.e. standard ASCII), so we have a search space (or “entropy”) of (8 bits * 6 chars) = 48 bits. Second, we know that this is a CTF, so we have a crib (or known plaintext attack): ‘flag’. Let’s try some simple brute-forcing (here, I’ve used the python module secrets to generate random bytes):

import secrets
import re
from itertools import cycle

with open("ciphertext.txt") as f:
    ctxt = bytes.fromhex(f.read())

braces = re.compile("flag\{.*\}")

while True:
    trial_key = secrets.token_bytes(6) #random key generation
    trial_ptxt = ''.join([chr(c ^ t_k) for c, t_k in zip(ctxt, cycle(trial_key))]) #test decryption
    if braces.match(trial_ptxt):
        print(trial_ptxt)
        print(f"key: {trial_key}") # b'[)&.=h'
        break

This produced a match! It turned into a bit of a dead end however (similar with searching for words like " the “). Of course, an incorrect key can still produce “flag” by chance - one in 2 to the power of 32, in fact. We should probably check how long we’re expecting this to take.

You can look up tables for how long password cracking (a related task) should take, however since I’ve got the laptop in front of me I can search a subset and extrapolate from there. Unfortunately, we still don’t know ‘flag’ works as a crib, so even if we do punch through all 2 to the power of 48 combinations we’re not guaranteed a win.

attempts = 0
while attempts < 2**20:
    trial_key = secrets.token_bytes(6)
    trial_ptxt = ''.join([chr(c ^ t_k) for c, t_k in zip(ctxt, cycle(trial_key))])
    if braces.match(trial_ptxt):
        print(trial_ptxt)
        print(f"key: {trial_key}")
        break
    attempts += 1
print("this probably failed") #timing this, it takes a few seconds to go through 2**20 combinations.

That extrapolates to a completion time, for a search space of 48 bits, of several thousand years. That’s rather too long. We’re going to have to be smarter.

The best way to do that is to linearise - instead of trying to find the entire key at once, we’ll find the first character, than the second, and so on. This is tricky as we need to somehow work out when we’ve recovered the first character. However, instead of getting six 1-in-256 guesses simultaneously, we’ll only need them sequentially. A runtime of 256 to the power of 6 becomes 256 times 6.

To do this, we’ll try character frequency analysis: we know that, if the plaintext is in english (third guess!), “e” should be the most frequent letter, followed by “the” and so on. We can do similar with bigrams (sets of two characters) or even trigrams (which gets you the presence, or otherwise, or the sequence “the”).

key = []
for i in range(6):
    max_count = 0
    test_char = "e" #change to suit
    max_char = chr(0)
    for j in string.ascii_letters + string.digits:
        trial_ptxt = ''.join([chr(ctxt[(6*k) + i] ^ ord(j)) for k in range(len(ctxt) // 6)])
        count = trial_ptxt.count(test_char)
        if count > max_count:
            max_char = j
            max_count = count
    key.append(max_char)

#using e: b'.+4=wa'
#using t: b'.:%,fp'
#using a: b'./09se'
#using o: b

Hmmm. That’s not worked particularly well. It’s quite a short ciphertext (42 chars), which is hampering my efforts. …Actually, that’s a familiar number. Let’s just check it’s not…

len("whatdoyougetifyoumultiplysixbynine") #> 42
len("fortytwo") #>6

Oh well. Okay, let’s revisit a basic idea: that we are dealing with English, specifically ASCII. Our earlier attempts produced a lot of plaintexts like this:

!ËúÅpïËçÙ>òH®Ã|öHëÌmô 9Å
âxïõ
   àÈ9èËùÌj¡
®ÌzâëÃm¯

And other various terminal-reformatting characters, which is probably not the intention in the plaintext. Let’s suppose the plaintext has a high percentage of ascii letters, easily represented in python. Digits, punctuation and whitespace are also searchable, but they’re less likely and therefore less important. Playing with combinations of string.ascii_letters, string.digits etc in both the candidates and the scoring:

for j in string.ascii_letters + string.digits:
    trial_ptxt = ''.join([chr(ctxt[(6*k) + i] ^ ord(j)) for k in range(len(ctxt) // 6)])
    count = sum(1 for l in string.ascii_letters + string.digits + " " if trial_ptxt.find(l) != -1)

You can improve accuracy further by double-scoring characters like ’e’ if you like (I did). Let’s print some of those out.

I+tc9wk+iwj j e5n mej$lrn.+p]oe'pmegl+1wydnnppt+wj#9ae j3zioee$7
I+tc,nk+ibs j e w mej1urn.+eDoe'etegl+$nydnneit+wj6 ae j&cioee1

What’s exciting here is that, even though I never scored for whitespace, I’m still seeing sentence structure forming. A couple more combinations, and I finally need only to brute force two positions (1 and 4), individually. I’ll leave the final decryption to the reader :-).