Details: Written by Michael Bann

Category: Crypto Points: 10,10,30,40 Solves: 436,381,224,63 Description:

Decrypt 4 flags.

In this challenge we're given 4 encrypted flags, and ask to decrypt them. They get successively more difficult, with the last one only having 63 successful solves. For each encrypted blob we were given a corresponding URL containing the encryption engine that would allow us to input anything and get back the corresponding output.

From a cryptography perspective, this means that for each of the flags we have at least two types of attacks. We have a chosen plain text attack in which we can decide what to encrypt and look at the results. We also have a known plain text since each flag is of the form "MMA{<values>}". Using these two types of attacks we can solve each of the challenges.

Flag 1

This encrypted flag is 36 36 2a 64 4b 4b 4a 21 1e 4b 1f 20 1f 21 4d 4b 1b 1d 19 4f 21 4c 1d 4a 4e 1c 4c 1b 22 4f 22 22 1b 21 4c 20 1d 4f 1f 4c 4a 19 22 1a 66. I should note here that each of the flags is hex encoded and each byte is separated by a space. This is just part of the mechanics of how it's displayed to the user.

http://bow.chal.mmactf.link/~scs/crypt2.cgi

Here's some example input and output:

Input	Output
a	4a
b	4b
c	4c
abc	4a 4b 4c

We can quickly see that the input is just incrementing. Further, we notice that adding new characters doesn't propagate any changes. Therefore, this would appear to be a shift cipher. Find the length like this:

>>> ord("a")-0x4a
23

Ok. Shift of 23. Now we just unshift to find the flag:

>>> ''.join([chr(int(x,16)+23) for x in "36 36 2a 64 4b 4b 4a 21 1e 4b 1f 20 1f 21 4d 4b 1b 1d 19 4f 21 4c 1d 4a 4e 1c 4c 1b 22 4f 22 22 1b 21 4c 20 1d 4f 1f 4c 4a 19 22 1a 66".split(" ")])
'MMA{bba85b6768db240f8c4ae3c29f9928c74f6ca091}'

Flag: MMA{bba85b6768db240f8c4ae3c29f9928c74f6ca091}

Flag 2

e3 e3 83 21 33 96 23 43 ef 9a 9a 05 18 c7 23 07 07 07 c7 9a 04 33 23 07 23 ef 12 c7 04 96 43 23 23 18 04 04 05 c7 fb 18 96 43 ef 43 ff

http://bow.chal.mmactf.link/~scs/crypt4.cgi

As usual, let's start by playing with input:

Input	Output
a	ef
b	aa
c	fb
abc	ef aa fb

The direct outputs of any given character don't appear to just be a shift. However, putting the characters together ends up just putting together there output. Just as before, there's no propagation of changes. This means we're dealing with a look-up table. The nice thing is, it's looking it up by character. There's only going to be so many characters (26+26+10=52 without special characters). Let's just enumerate it.

>>> import string
>>> print(string.printable)
i = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!\"#$%&'()*+,-./:;<=>?@[\]^_`{|}~"

I've removed the last bit of characters from the printable because we likely wouldn't use them. I apparently forgot to jot down what python script I used to enumerate, but really you can do it any way. Just give those input values to the website and record the output. We get the following output as our lookup table from values i.

>>> r = "04 c7 23 c3 18 96 05 9a 07 12 ef aa fb 43 4d 33 85 45 f9 02 7f 50 3c 9f a8 51 a3 40 8f 92 9d 38 f5 bc b6 da 83 2c 1a 1b 6e 5a a0 52 3b d6 b3 29 e3 2f 84 53 d1 00 ed 20 fc b1 5b 6a cb be fd 93 26 36 3f f7 cc 34 a5 e5 f1 71 d8 31 15 80 e2 eb 27 b2 75 09 39 4a 4c 58 cf d0 21 10 ff f3".split(" ")

Now we create a lookup dictionary in python and reverse the flag:

>>> lookup = {}
>>> for x in range(len(i)):
>>>   lookup[r[x]] = i[x]
>>> 
>>> ''.join([lookup[x] for x in "e3 e3 83 21 33 96 23 43 ef 9a 9a 05 18 c7 23 07 07 07 c7 9a 04 33 23 07 23 ef 12 c7 04 96 43 23 23 18 04 04 05 c7 fb 18 96 43 ef 43 ff".split(" ")])
'MMA{f52da776412888170f282a9105d2240061c45dad}'

Flag: MMA{f52da776412888170f282a9105d2240061c45dad}

Flag 3

60 00 0c 3a 1e 52 02 53 02 51 0c 5d 56 51 5a 5f 5f 5a 51 00 05 53 56 0a 5e 00 52 05 03 51 50 55 03 04 52 04 0f 0f 54 52 57 03 52 04 4e

http://bow.chal.mmactf.link/~scs/crypt5.cgi

This one is getting tougher. The encryption now does some form of chaining. Here are some examples:

Input	Output
a	60
aa	63 00
aaa	62 00 00
b	63
bb	60 00
bbb	61 00 00
ab	63 03
abbb	65 03 00 00

So I played around with many different inputs, those are just an example. Right off the bat we see they're not so random. When we repeat characters the first letter changes value and then the rest are filled with 00 values to indicate a repeat. Here's where our known plain text attack helps. Let's look at what we know to be our output:

Input	Output
M	4c
MM	4f 00
MMA	4e 00 0c
MMA{	49 00 0c 3a

Now we start to see a pattern. The first output character changes, but the rest do not. It feels like a check-sum of some kind. Because we're allowed to ask the engine to encrypt anything, we can step through the flag one character at a time, looking for a win. I wrote the following script to do just that.

#!/usr/bin/python3

import urllib.parse
import urllib.request

url = 'http://bow.chal.mmactf.link/~scs/crypt5.cgi'

alphabet = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!\"#$%&'()*+,-./:;<=>?@[\]^_`{|}~"

flag_enc = "60 00 0c 3a 1e 52 02 53 02 51 0c 5d 56 51 5a 5f 5f 5a 51 00 05 53 56 0a 5e 00 52 05 03 51 50 55 03 04 52 04 0f 0f 54 52 57 03 52 04 4e".split(" ")
flag_dec = ["M"]

def encrypt(value):
        data = urllib.parse.urlencode({'s':value})
        data = data.encode('utf-8') # data should be bytes
        req = urllib.request.Request(url, data)
        with urllib.request.urlopen(req) as response:
           the_page = response.read().decode('utf-8')
        return the_page.split("</h1>")[1].split(" <")[0].split(" ")


while len(flag_dec) != len(flag_enc):
        for c in alphabet:
                enc = encrypt(''.join(flag_dec + [c]))
                if enc[-1] == flag_enc[len(enc)-1]:
                        flag_dec.append(c)
                        print("{0}".format(''.join(flag_dec)))
                        break

I went ahead and started with only the known value of "M" just to test that it was working properly. You can certainly start anywhere in the flag if you happen to know it (such as starting with MMA{). All it's doing is trying each possible character, asking the website to encrypt it, then checking what the output encrypted to in that position to verify if it chose correctly. This means it's a linear search and definitely doable. Here's what the output looks like:

MM
MMA
MMA{
MMA{e
MMA{e7
MMA{e75
MMA{e75f
MMA{e75fd
MMA{e75fd5
MMA{e75fd59
MMA{e75fd59d
MMA{e75fd59d2
MMA{e75fd59d2c
MMA{e75fd59d2c9
MMA{e75fd59d2c9f
MMA{e75fd59d2c9f9
MMA{e75fd59d2c9f9c
MMA{e75fd59d2c9f9c2
MMA{e75fd59d2c9f9c22
MMA{e75fd59d2c9f9c227
MMA{e75fd59d2c9f9c227d
MMA{e75fd59d2c9f9c227d2
MMA{e75fd59d2c9f9c227d28
MMA{e75fd59d2c9f9c227d28f
MMA{e75fd59d2c9f9c227d28ff
MMA{e75fd59d2c9f9c227d28ff4
MMA{e75fd59d2c9f9c227d28ff41
MMA{e75fd59d2c9f9c227d28ff412
MMA{e75fd59d2c9f9c227d28ff412c
MMA{e75fd59d2c9f9c227d28ff412c3
MMA{e75fd59d2c9f9c227d28ff412c3f
MMA{e75fd59d2c9f9c227d28ff412c3fe
MMA{e75fd59d2c9f9c227d28ff412c3fea
MMA{e75fd59d2c9f9c227d28ff412c3fea3
MMA{e75fd59d2c9f9c227d28ff412c3fea37
MMA{e75fd59d2c9f9c227d28ff412c3fea378
MMA{e75fd59d2c9f9c227d28ff412c3fea3787
MMA{e75fd59d2c9f9c227d28ff412c3fea3787c
MMA{e75fd59d2c9f9c227d28ff412c3fea3787c1
MMA{e75fd59d2c9f9c227d28ff412c3fea3787c1f
MMA{e75fd59d2c9f9c227d28ff412c3fea3787c1fe
MMA{e75fd59d2c9f9c227d28ff412c3fea3787c1fe7
MMA{e75fd59d2c9f9c227d28ff412c3fea3787c1fe73
MMA{e75fd59d2c9f9c227d28ff412c3fea3787c1fe73}

Flag: MMA{e75fd59d2c9f9c227d28ff412c3fea3787c1fe73}

Flag 4

62 a9 6c 28 0e 33 31 c6 68 cd 66 66 59 46 cc 53 0c 98 31 65 c6 35 c9 a9 60 4e 37 b0 33 46 0d 60 46 26 66 33 cc e6 a9 f6 6c 07 2b 23 af

http://bow.chal.mmactf.link/~scs/crypt6.cgi

Again, we start off trying values. Here are some examples:

Input	Output
a	2c
b	4c
c	6c
f	cc
g	ec
i	2d
aa	2c c2
aaaa	c2 c2 2c c2
bbbb	89 89 4c 89
abab	c4 85 2c c4

Clearly a pattern. At this point, I was initially considering reversing what the crypto algorithm was as it seems doable. However, I later decided to be lazy and utilize the fact that we can ask the engine to encrypt anything. Basically, if you play around with it long enough you'll notice that there isn't real propagation of changes. Some changes affect 2 spots in the output, and some only affect 1. It's that characteristic that I took advantage of.

We also notice that the input and output character length is the same. So we know that our output will have a length of 45 due to how the flag is formatted (MMA{<40 chars>}). My initial question was how much overlap do those changes have. If there are minimal locations where the output value is dependent on two or more input values, then it becomes either a satisfiability problem or a brute force problem. To answer this question, I created a script:

#!/usr/bin/python3
 
import urllib.parse
import urllib.request
 
from copy import copy
 
url = 'http://bow.chal.mmactf.link/~scs/crypt6.cgi'
value = {'s' : 'MMA{'}
 
alphabet = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!\"#$%&'()*+,-./:;<=>?@[\]^_`{|}~"
 
flag_enc = "62 a9 6c 28 0e 33 31 c6 68 cd 66 66 59 46 cc 53 0c 98 31 65 c6 35 c9 a9 60 4e 37 b0 33 46 0d 60 46 26 66 33 cc e6 a9 f6 6c 07 2b 23 af".split(" ")
flag_dec = ['M', 'M', 'A', '{', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', '}']
 
def encrypt(value):
        data = urllib.parse.urlencode({'s':value})
        data = data.encode('utf-8') # data should be bytes
        req = urllib.request.Request(url, data)
        with urllib.request.urlopen(req) as response:
           the_page = response.read().decode('utf-8')
        return the_page.split("</h1>")[1].split(" <")[0].split(" ")
 
# Baseline what it looks like
base = encrypt("".join(flag_dec))
 
diff = {}
 
# Try changing one thing at a time and see what happens
for i in range(len(flag_dec)):
        # Change one thing and look for differences
        tmp = copy(flag_dec)
        tmp[i] = "1"
 
        o = encrypt("".join(tmp))
 
        for x in range(len(o)):
                if o[x] != base[x]:
                        #print("Found difference at index {}".format(x))
                        try:
                                diff[x].append(i)
                        except:
                                diff[x] = [i]
 
print("Here's the diff")
print(diff)

The encrypt function, like in the other examples, is just responsible for getting the output of asking the web page to encrypt something. The main logic is in the for loop where I make a change in one spot of the flag, and check the output to see what the corresponding areas of change are. The output, pretty printed for readability, is:

{0: [1, 23],
 1: [3, 23],
 2: [3],
 3: [5, 39],
 4: [5],
 5: [25],
 6: [7],
 7: [35],
 8: [9],
 9: [27],
 10: [11],
 11: [43],
 12: [13],
 13: [29],
 14: [15],
 15: [37],
 16: [17],
 17: [31],
 18: [19],
 19: [41],
 20: [21],
 21: [33],
 22: [0],
 23: [2],
 24: [4],
 25: [6],
 26: [8],
 27: [10],
 28: [12],
 29: [14],
 30: [16],
 31: [18],
 32: [20],
 33: [22],
 34: [24],
 35: [26],
 36: [28],
 37: [30],
 38: [32],
 39: [34],
 40: [36],
 41: [38],
 42: [40],
 43: [42],
 44: [44]}

What you should notice here is that the majority of the input characters only affect one output. The overlaps where two or more inputs affect the same output are:

3: [1, 2]
5: [3, 4]
23: [0, 1]

Note that we happen to know input index 0,1,2 and 3 (corresponding to M,M,A,{). That means that we actually have no areas in this encryption where we need to solve for two things at the same time. It actually would still likely be possible to solve if there were more overlap, but this makes it easier. Here's the script I wrote to crack it:

#!/usr/bin/python3

import urllib.parse
import urllib.request

from copy import copy

url = 'http://bow.chal.mmactf.link/~scs/crypt6.cgi'

alphabet = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!\"#$%&'()*+,-./:;<=>?@[\]^_`{|}~"

flag_enc = "62 a9 6c 28 0e 33 31 c6 68 cd 66 66 59 46 cc 53 0c 98 31 65 c6 35 c9 a9 60 4e 37 b0 33 46 0d 60 46 26 66 33 cc e6 a9 f6 6c 07 2b 23 af".split(" ")
flag_dec = ['M', 'M', 'A', '{', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', '}']

# bdiff describes what affects the input should have on the output.
# For instance, bdiff[1] = [3,23] means that the index 1 of input affects index 3 and 23 of the output
bdiff = {0: [1, 23], 1: [3, 23], 2: [3], 3: [5, 39], 4: [5], 5: [25], 6: [7], 7: [35], 8: [9], 9: [27], 10: [11], 11: [43], 12: [13], 13: [29], 14: [15], 15: [37], 16: [17], 17: [31], 18: [19], 19: [41], 20: [21], 21: [33], 22: [0], 23: [2], 24: [4], 25: [6], 26: [8], 27: [10], 28: [12], 29: [14], 30: [16], 31: [18], 32: [20], 33: [22], 34: [24], 35: [26], 36: [28], 37: [30], 38: [32], 39: [34], 40: [36], 41: [38], 42: [40], 43: [42], 44: [44]}


def encrypt(value):
        data = urllib.parse.urlencode({'s':value})
        data = data.encode('utf-8') # data should be bytes
        req = urllib.request.Request(url, data)
        with urllib.request.urlopen(req) as response:
           the_page = response.read().decode('utf-8')
        return the_page.split("")[1].split(" <")[0].split(" ")

# Given flag_dec (guess), and an index
# Check if the flag_dec guess is correct for the given index
def checkOutput(flag_dec,index):
        # Encrypt it
        enc = encrypt("".join(flag_dec))

        # Check the corresponding indexes
        for i in bdiff[index]:
                # If we're wrong
                if enc[i] != flag_enc[i]:
                        return False
        return True

# Loop through all values assuming it starts with "MMA{"
for x in range(4,len(flag_dec)):
        # Make a working copy
        tmp = copy(flag_dec)

        # Create variable to ensure we're finding results
        found = False

        # Try everything
        for c in alphabet:
                # Modify it
                tmp[x] = c

                # Try the answer
                if checkOutput(tmp,x):
                        # Update our answer with this new knowledge
                        flag_dec[x] = c
                        found = True
                        print("".join(flag_dec))
                        break

        # Ensure we didn't just mess up
        if not found:
                print("Error: Unable to find answer for index {0}\nExiting".format(x))
                exit(1)

As per before, the encrypt function just handles asking the webpage to encrypt for us. The checkOutput function handles calling the encryption function to get the new output, then verifying that the given index of the input maps correctly to the output. Remember, while the input index isn't mapping to the same spot (i.e.: input index 5 doesn't map to encrypted index 5), it is still static (i.e.: input index 5 maps to encrypted index 25). That's why this looks a little stranger than normal brute forcing, but it's really the same idea.

Here's what it looks like running:

MMA{fAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA}
MMA{f9AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA}
MMA{f9cAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA}
MMA{f9cfAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA}
MMA{f9cf7AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA}
MMA{f9cf7aAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA}
MMA{f9cf7a3AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA}
MMA{f9cf7a3dAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA}
MMA{f9cf7a3ddAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA}
MMA{f9cf7a3dddAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA}
MMA{f9cf7a3ddd5AAAAAAAAAAAAAAAAAAAAAAAAAAAAA}
MMA{f9cf7a3ddd57AAAAAAAAAAAAAAAAAAAAAAAAAAAA}
MMA{f9cf7a3ddd571AAAAAAAAAAAAAAAAAAAAAAAAAAA}
MMA{f9cf7a3ddd5710AAAAAAAAAAAAAAAAAAAAAAAAAA}
MMA{f9cf7a3ddd5710eAAAAAAAAAAAAAAAAAAAAAAAAA}
MMA{f9cf7a3ddd5710e8AAAAAAAAAAAAAAAAAAAAAAAA}
MMA{f9cf7a3ddd5710e85AAAAAAAAAAAAAAAAAAAAAAA}
MMA{f9cf7a3ddd5710e851AAAAAAAAAAAAAAAAAAAAAA}
MMA{f9cf7a3ddd5710e8511AAAAAAAAAAAAAAAAAAAAA}
MMA{f9cf7a3ddd5710e85116AAAAAAAAAAAAAAAAAAAA}
MMA{f9cf7a3ddd5710e851168AAAAAAAAAAAAAAAAAAA}
MMA{f9cf7a3ddd5710e8511681AAAAAAAAAAAAAAAAAA}
MMA{f9cf7a3ddd5710e85116814AAAAAAAAAAAAAAAAA}
MMA{f9cf7a3ddd5710e85116814fAAAAAAAAAAAAAAAA}
MMA{f9cf7a3ddd5710e85116814feAAAAAAAAAAAAAAA}
MMA{f9cf7a3ddd5710e85116814fefAAAAAAAAAAAAAA}
MMA{f9cf7a3ddd5710e85116814fef0AAAAAAAAAAAAA}
MMA{f9cf7a3ddd5710e85116814fef01AAAAAAAAAAAA}
MMA{f9cf7a3ddd5710e85116814fef01cAAAAAAAAAAA}
MMA{f9cf7a3ddd5710e85116814fef01c9AAAAAAAAAA}
MMA{f9cf7a3ddd5710e85116814fef01c90AAAAAAAAA}
MMA{f9cf7a3ddd5710e85116814fef01c907AAAAAAAA}
MMA{f9cf7a3ddd5710e85116814fef01c907fAAAAAAA}
MMA{f9cf7a3ddd5710e85116814fef01c907f4AAAAAA}
MMA{f9cf7a3ddd5710e85116814fef01c907f4dAAAAA}
MMA{f9cf7a3ddd5710e85116814fef01c907f4dfAAAA}
MMA{f9cf7a3ddd5710e85116814fef01c907f4df3AAA}
MMA{f9cf7a3ddd5710e85116814fef01c907f4df35AA}
MMA{f9cf7a3ddd5710e85116814fef01c907f4df35cA}
MMA{f9cf7a3ddd5710e85116814fef01c907f4df35ce}

Flag: MMA{f9cf7a3ddd5710e85116814fef01c907f4df35ce}

MMA CTF 2015 -- Smart Cipher System

Flag 1

Flag 2

Flag 3

Flag 4