redpwnCTF 2020 Crypto

# alien tx v2

We are provide with an explanation that has some key points and a file that contains the double XOR encrypted message.

The aliens are at it again! We've discovered that their communications are in base 512 and have transcribed them in base 10. However, it seems like they used XOR encryption twice with two different keys! We do have some information: This alien language consists of words delimitated by the character represented as 481 The two keys appear to be of length 21 and 19 The value of each character in these keys does not exceed 255 Find these two keys for me; concatenate their ASCII encodings and wrap it in the flag format.

Our goal here is to recover the two keys but not the message. So we could leverage the message and the special factors of the aliens language to "guess" the keys.

## Effective Key Length

By doing an XOR encryption with a key length of 21 and 19, we have a effective key length of `21*19=399`

. This means that the text will be encrypted by the same key every 399 chars. Here's a visualization.

key1 = 101 key2 = 11010 plaintext = 00000 First XOR with key1 10110 ('101' plus '10' to fill the length of the plaintext) XOR 00000 ------------------ 10110 Second XOR with key2 10110 XOR 11010 ------------------ 01100

You can see the result more clearly with a test script `@GeoffreyY(Discord)`

showed me

from itertools import cycle key1 = [1,2,3] key2 = [4,5,6,7,8] ptxt = [0]*50 [z^k1^k2 for ((z,k1),k2) in zip(zip(ptxt,cycle(key1),cycle(key2)))] OUTPUT: [ 5,7,5,6,10,7,4,4,4,9,6,6,7,5,11 5,7,5,6,10,7,4,4,4,9,6,6,7,5,11 5,7,5,6,10 ]

## Sorting

After we determine the effective key length, we could sort the provide alien message into 399 different bins, as each bin is using the same key to encrypt the data. To do this, a python script could do the job, this will be included in the final exploit.

from collections import * encrypted = open("encrypted.txt", 'r').read().strip().split('\n') bins=defaultdict(list) k399=[0]*399 k21=[[]]*21 k19=[[]]*19 for x in range(len(encrypted)): bins[x%399].append(encrypted[x])

## Finding Deliminator

By the provided information about the alien language, we know that the deliminator is `481`

and that should be the most common "word" in each bin. By using the `Counter()`

in itertools, we can see that there is always a significant difference between the most used word and the second most used word. Therefore, we could tell that the most used word in each bin should be `481`

. Now we need a piece of script to pick out these deliminators.

for x in range(0,399): count = Counter(bins[x]) delim = list(count.keys())[list(count.values()).index(max(list(count.values())))] k399[x]=int(delim)^481

After finding the deliminators, by XORing it with 481 the known deliminator, we can get the encryption key for `k399[i]`

## "Brute Forcing" the Keys

We know the relation of key399, key21 and key19 by examining the test script @GeoffreyY wrote which is key399[i] = key21[i % 21] ^ key19[i % 19]

By knowing this information in addition to the other specification of the alien language `The value of each character in these keys does not exceed 255`

we can try every value between `0 ~ 255`

. Since we know all `k399`

by finding the deliminators, we just need to guess a value for `k21`

or `k19`

and see if the other one makes since, since we want our final output to be readable characters. I wrote this script that will write all the possibilities of `k19`

when `k21`

is a certain value, and evaluate `k21`

with the found `k19`

value and `k399`

.

with open("ape1.txt", 'w') as f: with open("ape.txt",'w') as j: for c in range(0, 255): for idx in range(0, 399, 21): k19[idx % 19] = k399[idx] ^ c f.write("".join([chr(c) for c in k19]) + '\n') for i in range(0,399): k21[i % 21]=k19[i%19]^k399[i] j.write("".join([chr(c) for c in k21])+"".join([chr(c) for c in k19])+'\n')

## Final Output and Finding the Flag

For our output, we get a huge list of characters and we need to find the one that "looks" right.

. . .(Giberish) e>>*8Rye>Rk<8yRe9akRye>R8>n=ciR<8Rye<8 f=|=);Qzf=Qh?|;zQf:bhQzf=Q;=m>`jQ?;Qzf?; g<}<(:P{g<Pi>}:{Pg;ciP{g<P:<l?akP>:P{g>: h3r3'5_th3_f1r5t_h4lf_th3_53c0nd_15_th15 i2s2&4^ui2^g0s4u^i5mg^ui2^42b1oe^04^ui04 j1p1%7]vj1]d3p7v]j6nd]vj1]71a2lf]37]vj37 k0q0$6\wk0\e2q6w\k7oe\wk0\60`3mg\26\wk26 .(Giberish) . .

Just find the string that "Seems" like the flag, you should be able to spot it!