not crypto

4 minutes to read

This is the not crypto flag which is totaly not crypto, but crypto! Can we get a clap from the team for excessive crypto usage?

We are given the following Python script:

import base64

input_string = "REMOVED"


def secret(raw_string):
    result = []
    for char in raw_string:
        if 'a' <= char <= 'z':
            offset = ord('a')
            result.append(chr(((ord(char) - offset + 13) % 26) + offset))
        elif 'A' <= char <= 'Z':
            offset = ord('A')
            result.append(chr(((ord(char) - offset + 13) % 26) + offset))
        else:
            result.append(char)
    return ''.join(result)


encoded_bytes = base64.b64encode(input_string.encode("utf-8"))
encoded = encoded_bytes.decode("utf-8").lower()

print(secret(encoded))

# ehagd3gzmjrmajvkamx5mql4zqdmmgewa2z5a2iymqx2zjdmz2h2lwyuzjmubtzjbqwvbqowbgpkbgxmazv5mgmwagavsd==

The output of the script is the comment at the bottom.

Source code analysis

Basically, the script takes the flag, Base64-encodes it, transforms it to lowercase and then applies the secret function, which is just ROT13.

Solution

To solve this, first we can apply ROT13 to decode it (ROT13 encoding and decoding is the same), and then we get a lowercase Base64 string:

runtq3tmzweznwixnzk5zdy4mdqzztrjn2m5n2vlzdk2mwqzm2u2yjlhmwzhogmwodjiodbjotcxotkznmi5ztzjntnifq==

Now, all we need to do is figure out which letters must be uppercase and which ones must be lowercase.

Base64 encoding

Base64 is just a way of representing a number, like base 10 (decimal), base 16 (hexadecimal), base 2 (binary), base 256 (ASCII), base 8 (octal)…

In order to encode (manually) a string in Base64, we must encode the string in binary and then map each 6-bit chunk to its corresponding symbol (A to Z, a to z, 0 to 9, + and /). Some extra padding (=) is required at the end in case the binary string length is not divisible by 6.

One way to approach this challenge is to convert the lowercase string from Base64 to binary, and the same with the uppercase string:

r     u      n      t      q     3      t      m      z     w      e      z      ...  
10101110 11101001 11101101 10101011 01111011 01100110 11001111 00000111 10110011 ...
R     U      N      T      Q     3      T      M      Z     W      E      Z      ...
01000101 01000011 01010011 01000011 01110100 11001100 01100101 01100001 00011001 ...

The binary strings are separated in 8-bit chunks, so that we can identify valid bytes that can be present in the flag, and each Base64 symbol is positioned in the start of every 6-bit chunk.

Since the flag characters are all printable, we know that the most significant bit of every 8-bit chunk is 0, so we can eliminate some possibilities:

-     -      -      t      -     3      t      m      -     w      -      z      ...  
-------- -------- --101101 ------11 01111011 01100110 ------11 0000---- --110011 ...
R     U      N      T      Q     3      -      M      Z     W      E      Z      ...
01000101 01000011 01010011 01000011 0111---- --001100 01100101 01100001 00011001 ...

We can eliminate a bit more knowing that printable ASCII bytes are between 0x20 and 0x7e:

-     -      -      t      -     -      t      m      -     -      -      z      ...  
-------- -------- --101101 -------- ----1011 01100110 -------- -------- --110011 ...
R     U      N      T      Q     3      -      M      Z     W      E      -      ...
01000101 01000011 01010011 01000011 0111---- --001100 01100101 01100001 00------ ...

If we add the characters that correspond to each 8-bit chunk, we have this:

-     -      -      t      -     -      t      m      -     -      -      z      ...  
-------- -------- --101101 -------- ----1011 01100110 -------- -------- --110011 ...
R     U      N      T      Q     3      -      M      Z     W      E      -      ...
01000101 01000011 01010011 01000011 0111---- --001100 01100101 01100001 00------ ...
E        C        m/S      C        {        f/L      e        a        3

After doing some more chunks manually, we can guess that the flag contents are all lowercase hexadecimal digits, so we have:

-     -      -      -      -     -      t      m      -     -      -      z      ...  
-------- -------- -------- -------- ----1011 01100110 -------- -------- --110011 ...
R     U      N      T      Q     3      -      -      Z     W      E      -      ...
01000101 01000011 01010011 01000011 0111---- -------- 01100101 01100001 00------ ...
E        C        S        C        {        f        e        a        3

During the competition, I solved this challenge manually. Now that I have more time, I implemented an algorithm to find the flag.

The gist is to take chunks of 4 Base64 symbols ($4 \cdot 6 = 24$ bits) and Base64-decode them, resulting in $24 / 8 = 3$ bytes. For each chunk, we will consider all uppercase/lowercase possibilities ($2^4 = 16$) and we will take those that Base64-decode to printable ASCII characters (actually, lowercase hexadecimal digits or ECSC{}). Once we have all possible chunks, we just join them and Base64-decode all possibilities.

Flag

The script shows a unique possibility:

$ python3 solve.py
ECSC{fea35b1799d68043e4c7c97eed961d33e6b9a1fa8c082b80c9719936b9e6c53b}

The full script can be found in here: solve.py.