BMPaaS

Crypto challenge from ECW 2023

BMPaaS

The problem

We are given the server source :

import base64
import os


FLAG = base64.b85encode(open("flag.bmp", "rb").read()).decode()

CHARSET = base64._b85alphabet.decode()
N = len(CHARSET)


def generate_key(length):
    random_stream = os.urandom(length)
    return "".join(CHARSET[x % N] for x in random_stream)


def encrypt(plaintext, key):
    ciphertext = ""
    for i in range(len(plaintext)):
        ciphertext += CHARSET[(CHARSET.find(plaintext[i]) + CHARSET.find(key[i])) % N]
    return ciphertext


print("[+] Welcome to BMPaaS!")
print("[+] We offer a military-grade BMP encryption algorithm, powered by one of the safest OTP mechanisms in the world.")
print("[+] For now, uploading new BMP files is disabled. However, you can challenge our security by requesting an encrypted flag ;)\n")

print("[1] Request a new encrypted flag")
print("[2] Exit\n")

while True:

    choice = input("[?] Enter your choice: ")

    if choice == "1":
        key = generate_key(len(FLAG))
        print(encrypt(FLAG, key))

    elif choice == "2":
        exit()

    else:
        print("[x] Invalid choice.")

The script reads the flag from a bmp file and encodes it in base 85. Then for as many times as we want, we can get the flag encrypted.

The encryption is as follows :

  • Create a key as long as the flag where each value is CHARSET[os.urandom(1)%85] (85 is the size of the charset)
  • Add the indexes in the charset of the flag and the key and use it back in the charset.

The solution

So the vulnerability lies in the creation of the key, indeed they’re is a modulo bias when using the output of os.urandom to select a character in the charset.

If we take every possible value of a byte (so [0-255]) and apply the modulo 85 on it we can see something interesting :

>>> [i%85 for i in range(256)]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 0]

See that 0 at the end ? That’s a problem because that means we have 3 times each value except 0, which appears 4 times. So when we draw a random byte and take it modulo 85 we have 4/256 chances to get a 0, which is higher than any other value.

From that, if we request enough encrypted flags, we can take the value which appears the most times for each index, and it would be the good one.

I needed approximatly 35000 requests.

Solve script :

from pwn import remote
import base64

r = remote("instances.challenge-ecw.fr",40408)

flog = [[0 for i in range(85)] for _ in range(2198)]

CHARSET = base64._b85alphabet.decode()
N = len(CHARSET)

prev_flag = ""
flag = ""

j = 1
flag_count=0

while True:
	r.recvuntil(b"choice: ")
	r.sendline(b"1")
	msg = r.recvline().decode()[:-1]

	for i,m in enumerate(msg):
		flog[i][CHARSET.find(m)] += 1

	prev_flag = flag
	flag = "".join(CHARSET[f.index(max(f))] for f in flog)

	if prev_flag == flag:
		flag_count += 1
	else:
		flag_count = 0

	j+=1

	if j%3000 == 0:
		r.close()
		r = remote("instances.challenge-ecw.fr",40408)
		print(j)

	if flag_count == 3000:
		break


open("flag.bmp","wb").write(base64.b85decode(flag.encode()))

Flag : ECW{b85_modulo_bias_!!}

Shadowwws