Description:

Shoutout to those people who think that base64 is proper encryption

main.py

from Crypto.Util.number import long_to_bytes, bytes_to_long
from gmpy2 import mpz, to_binary
#from secret import flag, key

ALPHABET = bytearray(b"0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ#")

def base_n_encode(bytes_in, base):
	return mpz(bytes_to_long(bytes_in)).digits(base).upper().encode()

def base_n_decode(bytes_in, base):
	bytes_out = to_binary(mpz(bytes_in, base=base))[:1:-1]
	return bytes_out

def encrypt(bytes_in, key):
	out = bytes_in
	for i in key:
		print(i)
		out = base_n_encode(out, ALPHABET.index(i))
	return out

def decrypt(bytes_in, key):
	out = bytes_in
	for i in key:
		out = base_n_decode(out, ALPHABET.index(i))
	return out

"""
flag_enc = encrypt(flag, key)
f = open("flag_enc", "wb")
f.write(flag_enc)
f.close()
"""

flag_enc

The file can be found in the authors’ repository: flag_enc


Let’s look at the provided script:

As first step the alphabet of the key is defined:

ALPHABET = bytearray(b"0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ#")

base_n_encode reads the bytes of the given string as one big integer and expresses it in the given base.

def base_n_encode(bytes_in, base):
	return mpz(bytes_to_long(bytes_in)).digits(base).upper().encode()

base_n_decode reads the string as string-representation of a big integer in the given base and returns the binary representation of this integer.

def base_n_decode(bytes_in, base):
	bytes_out = to_binary(mpz(bytes_in, base=base))[:1:-1]
	return bytes_out

encrypt takes each char of the key and uses it as base for base_n_encode. For getting an integer base, the char is searched in the above alphabet and the position is used as base.

def encrypt(bytes_in, key):
	out = bytes_in
	for i in key:
		print(i)
		out = base_n_encode(out, ALPHABET.index(i))
	return out

decrypt takes each char of the key and uses in the same way as in encode for decoding the string with base_n_decode.

def decrypt(bytes_in, key):
	out = bytes_in
	for i in key:
		out = base_n_decode(out, ALPHABET.index(i))
	return out

Finally, there is a comment, which explains, how flag_enc was created:

flag_enc = encrypt(flag, key)
f = open("flag_enc", "wb")
f.write(flag_enc)
f.close()

At the start some considerations:

  • 0 and 1 cannot be part of the string, as their indices in the alphabet (0 & 1) are no bases
  • The base of the encrypted text will always be greater than each char in the text, as all characters in a string with base b are from interval [0, b-1]

With this knowledge, we can start the decryption. First we need to load the encrypted flag:

with open("flag_enc", "rb") as f:
	out = f.read()

For debug purposes we initialize some variables:

round = 0
key = ""

As we don’t know when we are done, we first loop infinitely. Furthermore we want to keep our debug variable up to date.

while True:
	round += 1

First we determine the alphabet of the current string:

	alphabet = set(out)

We only need the maximum for determining the smallest possible base. And again some debug printing.

	m = max(alphabet)
	print("{}: used {}, {}".format(round, m, alphabet))

Let’s get the smallest base. If the char is not found, the script will fail at this point with an error.

	b = ALPHABET.index(m) + 1

Now we can determine whether the calculated base is in range.

	if b >= len(ALPHABET):
		print("no")
		exit(1)

Now we can test for all possible bases and collect possible indices

	indices = list()
	for i in range(b, len(ALPHABET)):

As the decryption can fail, and we don’t want the script to be aborted, we have to wrap it in try. And again some debug printing.

		try:
			new_out = base_n_decode(out, i)
			print(max(new_out), min(new_out))

As # cannot be in the string and as the chars build a continues block in ASCII, we can simply check the boundaries to determine whether the decrypted string matches our requirements and the index is a candidate:

			if max(new_out) <= 90 and min(new_out) >= 48:
				indices.append(i)

Because the flag will have some additional chars outside this range, we also check if the decrypted string is a potential flag. For preventing spam, we also check the length and hope, that the flag is shorter than 100 chars. If not, we have to adjust the length.

			if max(new_out) <= 125 and min(new_out) >= 48 and len(out) < 100:
				print(f"key: {key + chr(ALPHABET[i])}, possible flag: {new_out}")

If the decryption fails, we don’t want to do something. As python requires a statement in except, we do some useless assignment.

		except:
			log = 1

For proceeding, we need an index. Let’s exit, if we haven’t found one.

	if len(indices) < 1:
		print("no")
		exit(1)

Now we must select the index for the next round. As it is unlikely that the base is much higher than the maximum char in the string, we use the smallest working base. As we haven’t stored the decrypted string, we have to decrypt it again. Furthermore we append the used character from the alphabet to the key. And again some debug printing.

	out = base_n_decode(out, indices[0])
	key += chr(ALPHABET[indices[0]])
	print(key)
	print(indices)
	print(f"{round}: used {chr(ALPHABET[b])}, len: {len(out)}")

The whole script looks as following:

from Crypto.Util.number import long_to_bytes, bytes_to_long
from gmpy2 import mpz, to_binary
#from secret import flag, key

ALPHABET = bytearray(b"0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ#")

def base_n_encode(bytes_in, base):
	return mpz(bytes_to_long(bytes_in)).digits(base).upper().encode()

def base_n_decode(bytes_in, base):
	bytes_out = to_binary(mpz(bytes_in, base=base))[:1:-1]
	return bytes_out

def encrypt(bytes_in, key):
	out = bytes_in
	for i in key:
		print(i)
		out = base_n_encode(out, ALPHABET.index(i))
	return out

def decrypt(bytes_in, key):
	out = bytes_in
	for i in key:
		out = base_n_decode(out, ALPHABET.index(i))
	return out

with open("flag_enc", "rb") as f:
	out = f.read()

round = 0
key = ""
while True:
	round += 1
	alphabet = set(out)
	m = max(alphabet)
	print("{}: used {}, {}".format(round, m, alphabet))
	b = ALPHABET.index(m) + 1
	if b >= len(ALPHABET):
		print("no")
		exit(1)
	indices = list()
	for i in range(b, len(ALPHABET)):
		try:
			new_out = base_n_decode(out, i)
			print(max(new_out), min(new_out))
			if max(new_out) <= 90 and min(new_out) >= 48:
				indices.append(i)
			if max(new_out) <= 125 and min(new_out) >= 48 and len(new_out) < 100:
				print(f"key: {key + chr(ALPHABET[i])}, possible flag: {new_out}")
		except:
			log = 1
	if len(indices) < 1:
		print("no")
		exit(1)
	out = base_n_decode(out, indices[0])
	key += chr(ALPHABET[indices[0]])
	print(key)
	print(indices)
	print(f"{round}: used {chr(ALPHABET[b])}, len: {len(out)}")

In the output we find the flag (b'uiuctf{r4DixAL}') and the corresponding key (WM5Z8CRJABXJDJ5W).