back_to_basics
Simple beginner challenge about base-n encodings

Description

Shoutout to those people who think that base64 is proper encryption
author: epistemologist
main.py
761B
Text
main.py
flag_enc
2MB
Binary
flag_enc

Solution

We are provided with the following source code.
1
from Crypto.Util.number import long_to_bytes, bytes_to_long
2
from gmpy2 import mpz, to_binary
3
#from secret import flag, key
4
​
5
ALPHABET = bytearray(b"0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ#")
6
​
7
def base_n_encode(bytes_in, base):
8
return mpz(bytes_to_long(bytes_in)).digits(base).upper().encode()
9
​
10
def base_n_decode(bytes_in, base):
11
bytes_out = to_binary(mpz(bytes_in, base=base))[:1:-1]
12
return bytes_out
13
​
14
def encrypt(bytes_in, key):
15
out = bytes_in
16
for i in key:
17
print(i)
18
out = base_n_encode(out, ALPHABET.index(i))
19
return out
20
​
21
def decrypt(bytes_in, key):
22
out = bytes_in
23
for i in key:
24
out = base_n_decode(out, ALPHABET.index(i))
25
return out
26
​
27
"""
28
flag_enc = encrypt(flag, key)
29
f = open("flag_enc", "wb")
30
f.write(flag_enc)
31
f.close()
32
"""
33
​
Copied!
This is a custom encryption algorithm that repeatedly base-n encodes the ciphertext for each character of the key. In the encryption function, we see that the base is determined by the position of the key character i in the ALPHABET.
1
def encrypt(bytes_in, key):
2
out = bytes_in
3
for i in key:
4
print(i)
5
out = base_n_encode(out, ALPHABET.index(i))
6
return out
Copied!
The base_n_encode() simply implements the base-n encoding.
1
def base_n_encode(bytes_in, base):
2
return mpz(bytes_to_long(bytes_in)).digits(base).upper().encode()
Copied!
The flaw in this encryption scheme is that we know every input to base_n_encode(), other than the original plaintext, must also be a base-n encoded string. This allows us to bruteforce the key by ruling out invalid decoded outputs.
The following solver script implements this. Since there might be multiple valid bases, a depth-first search is performed on all possible bases. This turned out to be unnecessary, because the smallest valid base worked every time.
1
def decrypt_flag(enc, base):
2
​
3
if base:
4
​
5
try:
6
enc = base_n_decode(enc, base).decode()
7
​
8
except:
9
return False
10
11
else:
12
if "uiuctf" in enc:
13
return enc
14
​
15
for possible_base in range(2, len(ALPHABET)):
16
​
17
decrypted = decrypt_flag(enc, possible_base)
18
​
19
# This base works
20
if decrypted:
21
return decrypted
22
23
return False
24
​
25
with open('flag_enc', 'rb') as f:
26
enc = f.read()
27
28
print(decrypt_flag(enc, None))
Copied!
Running this gives us the flag, uiuctf{r4DixAL}.
Last modified 2mo ago
Copy link