[ECW] - BMPaaS

Statement #

Use #

If we access the instance directly, we see that the BMPaaS.py script offers us to obtain an encrypted flag as many times as we wish:

Source code #

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.")

Code analysis #

The encryption algorithm in the previous script is an OTP type cryptographic algorithm (One Time Pad)

Here is a summary of what this algorithm does:

1. The script reads the bits from the flag.bmp file and encodes them as base85 in the variable FLAG
2. The script creates the variable CHARSET and N:
   1. CHARSET matches the base85 alphabet (0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz!#$%&()*+-;<=>?@^_`{|}~)
   2. N is the length of this alphabet (85)
3. The script generates a random OTP key:
   1. The key is the same length as the variable N
   2. The key is made up of random characters included in the variable CHARSET
   3. Example key: “kZds>~?4BJHkg{Z(Z@g9B;3zbo&1VM<k}jK>w+^W>&Yzx>3wXJnW&q=A`P1qh5MI+FNg8Zr|zlh2T@>mo<0hK”
4. The script encrypts the FLAG variable with the key created previously :
   1. For each character of the FLAG variable it looks for the index in the CHARSET variable and in the previously created key
   2. It adds these 2 indexes
   3. He modulo this result by the variable N

Several things can be deduced from this:

• The flag is a bmp image
• The os.urandom function is a secure function whose random nature cannot be called into question here (see statement)
• The algorithm (addition followed by the modulo) is also rather secure because the modulo is a one-way operation.

Explanation of the vulnerability #

Let’s do a little math (sorry but it will be useful!)

We can transcribe the encryption algorithm using the following equation:

$$ c_i=p_i+k_i[mod N] $$

• p is the base85 encrypted plaintext described in point 1 of the code analysis
• k is the OTP encryption key described in point 3 of the code analysis.
• c is the encrypted result

The os.urandom function randomly returns a byte, this byte has a value from 0 to 255, so 256 possibilities.

But when we generate the key, we will modulo each byte by the length of the base85 alphabet so 85:

def generate_key(length):
    random_stream = os.urandom(length)
    return "".join(CHARSET[x % N] for x in random_stream) // x est un octet qui peut prendre 256 possibilités et N est égale à 85

But 85*3=255, which means that there are 4 numbers between 0 and 255 which modulo 85 gives 0 —> [0, 85, 170 and 255]

Other numbers between 0 and 255 modulo 85 will give a result different from 0 3 times.

Put another way :

• All numbers between 0 and 255 modulo 85 will give the same result 3 times (between 1 and 84)
• Except the numbers [0, 85, 170 and 255] which will give 4 times the result 0

We can see it with this command:

>>> [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]

And this is where the vulnerability lies because there is statistically a greater chance of obtaining a key which modulo 85 will give 0.

We take the cryptographic equation again:

$$ c_i=p_i+k_i[modN] $$

If we encrypt a message with a key which modulo 85 gives 0, we then obtain k = 0:

$$ c_i=p_i[modN] $$

Now as p < N because p comes from base85 encoding and therefore contains characters belonging to the base85 alphabet, the equation becomes:

$$ c_i=p_i $$

The ciphertext is then equal to the plaintext.

Exploitation of the vulnerability #

To exploit this vulnerability we just need:

1. To recover enough samples of encrypted flags that we will store in a list (that’s good, we can recover as many as we want!)
2. To request a new encrypted flag that we will try to break
3. To recover for each character of this encrypted flag its most frequent value in our samples

Since for a large number of samples, statistically this value supposed to be encrypted will be equal to the value of the plaintext.

If we recover the plaintext, all we have to do is decode it in base85 (which will give us the binary data of the BMP image in plain text). Finally we just have to re-create the BMP file used to encrypt the flag.

This is what the following script does by retrieving 50,000 samples:

from pwn import *

HOST = "instances.challenge-ecw.fr"
PORT = 42581

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

NUMBER_FLAGS_FIGURES = 50000

# Function to retrieve the 50,000 encrypted flags
def get_flags_digits(nb):
     # We connect to the instance
     con = remote(HOST,PORT)
    
     # We initialize the table which will contain the 50,000 encrypted flags
     flags_digits = []
    
     for i in range(nb):
         con.sendlineafter(b"[?] Enter your choice:",b"1") # We ask the instance to send us an encrypted flag
         data = con.recvuntil("\n")[1:-1] # We recover the formatted data
         flags_chiffres.append(data) # We add them to the table
         print(f"\r-> {i}/{nb}",end='')
     return flags_digits

# Function to search for the most frequent character in encrypted flags
def find_cara(flags_digits):
     # List to store majority characters
     results = []
   
     # Character traversal of each position in encrypted flags
     for i in range(len(flags_numbers[0])):
         # Dictionary to count occurrences of each character at that position
         dictionary = dict()
        
         # Scan encrypted flags to count occurrences of each character
         for j in range(len(flags_numbers)):
             character = flags_chiffres[j][i] # Character at position i in encrypted flag j
             if character in dictionary:
                 dictionary[character] += 1
             else:
                 dictionary[character] = 1
        
         # Search for the character with the highest number of occurrences
         max_occurrence = 0
         majority_character = None
         for z in dictionary:
             if dictionary[z] > max_occurrence:
                 max_occurrence = dictionary[z]
                 majority_character = z
        
         # Added majority character to the results list
         results.append(majority_character)
    
     # Returns the list of majority characters
     return results

# Function to convert a list of characters to a text string
def to_string(results):
     s=""
     for i in results:
         s += chr(i) # Converts int to character and adds it to string
     return s

# Function to write a base85 encoded text string to a BMP file
def write_flag(e: str):
     # Decode base85 string into binary data
     b = base64.b85decode(e.encode())
    
     # Writes binary data to a BMP file
     with open("flag.bmp", "wb") as f:
         f.write(b)
    
def main():
     flags_chiffres = get_flags_chiffres(NUMBER_FLAGS_CHIFFRES)
     cara = find_cara(flags_digits)
     string = to_string(cara)
     write_flag(string)
    
if __name__ == "__main__":
     hand()

Flag #

We then obtain the following image:

🚩 Flag : ECW{b85_modulo_bias_!!}