HackademINT

Club de cybersécurité de Telecom SudParis


Macaque

Auteur : Alternatif

----------------------------------

Macaque - Crypto

This challenge was the first one in the Crypto category at the 2021 FCSC. It was worth 50 points at the beggining of the event, and ended up at 41.

Chall description

We’re given an access to a servor where this python script runs:

#!/usr/bin/env python3
import os 
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from flag import flag

class Macaque():
    def __init__(self, k1, k2):
        self.k1 = k1
        self.k2 = k2
        self.bs = AES.block_size
        self.zero = b"\x00" * self.bs

    def tag(self, m):
        m = pad(m, self.bs)
        c1 = AES.new(self.k1, AES.MODE_CBC, iv = self.zero).encrypt(m)
        c2 = AES.new(self.k2, AES.MODE_CBC, iv = self.zero).encrypt(m)
        return c1[-self.bs:] + c2[-self.bs:]

    def verify(self, m, tag):
        return self.tag(m) == tag

def usage():
    print("Commands are:")
    print("|-> t: Authenticate a message")
    print("|-> v: Verify a couple (message, tag)")
    print("|-> q: Quit")

if __name__ == "__main__":

    S = set()
    singe = Macaque(os.urandom(16), os.urandom(16))

    while True:
        usage()
        cmd = input(">>> ")

        if not len(cmd):
            exit(1)

        if cmd not in ['t', 'v', 'q']:
            usage()
            continue

        if cmd == 'q':
            exit(0)

        if cmd == 't':
            if len(S) < 3:

                print("Message (hex):")
                message = bytes.fromhex(input(">>> "))
                if not len(message):
                    exit(1)

                tag = singe.tag(message)
                print(f"Tag (hex): {tag.hex()}")
                S.add(message)
            else:
                print("Error: you cannot use this command anymore.")

        elif cmd == 'v':
            print("Message (hex):")
            message = bytes.fromhex(input(">>> "))
            
            print("Tag (hex):")
            tag = bytes.fromhex(input(">>> "))
            
            check = singe.verify(message, tag)
            if check and message not in S:
                print(f"Congrats!! Here is the flag: {flag}")

            elif check and message in S:
                print("Valid!")

            else:
                print("Wrong tag. Try again.")

First look

Let’s start by analyzing what the server does in the background when we connect. We can see that an object of the class Macaque is initialized with twice sixteen random bytes. This happens everytime we reconnect to the servor, and so we won’t be able to store any informations between our connection since we’ll need this object to get the flag. It also define a new Set that will serve after.

After that, the servor give us 3 options: Authenticate a message (t), Verify a couple (v), or quitting.

  • If we choose authenticate, we have to enter a hex input that is converted into bytes then padded, then put into the encrypt method of the singe object. It then prints the result and add the input to the Set. There is also a condition saying that if S already contains 3 messages, the commands can’t be used anymore. So we are only allowed to authenticate 3 messages.

  • The Verify option asks us a message in hex format, and a tag. It then pass the message in the tag method, and check if the message has already been tried with the authenticate method by checking the Set. If the message isn’t in the Set, it’s won.

In order to win, we basically have to guess the output of singe.tag on a message with the help of authenticate on 3 messages that aren’t the one we will guess.

The tag method

The tag method ciphers twice the padded message we give in input with AES in CBC mode. These AES ciphers are defined with null IVs and random keys that change everytime we reconnect to the servor. It then takes the last 16 bytes of both of the input, concatenates them and returns the result. This means that we’ll only be able to recover the last 16 bytes of each message we sent through the authentiate method. To see what it implies, we need to understand how CBC Mode works.

CBC Mode

CBC (Cipher Block Chaining) is a block cipher mode where the plaintext of each block is xored with the ciphertext of the last block (the first one is xored with the iv). This mode is regularly used with AES which is, if you didn’t know it, a block cipher. This schema can help to figure how CBC works:

CBC Mode

This is really interesting for us, because we can see that, after the first block, it is not the plaintext block that is directly put into the AES function, it is xored with the previous ciphertext. This could be the solution to our problem! Indeed, imagine we send a 2 blocks long message to an arbitrary AES function in CBC mode. Let’s write this plaintext P1P2, and let’s call the cipher we obtain C1C2. We have:

C1=AES(P1^IV)=AES(P1) (if IV=0, like in our case) and C2=AES(C1^P2) where ^=XOR

So if we know C1, P2 and C2, we can craft use C1^P2 as a payload, for which we will know the tag it will have once passed into the AES function wihtout authenticating itself.

The problems remaining

The situation presented is, however, slightly different from the one we have in our problem: here we have 2 AES functions, let’s call them AES1 and AES2, and we want to have the last 16 bytes (= the last cipher block) of each of them, so we need to know, with still P1P2 as the message, AES1(P1), AES2(P1), AES1(AES1(P1)^P2) AES2(AES2(P1)^P2) and we need to find the right P1P2.
There are more constraints too: we are only allowed to send 3 messages, we can only see the last cipher block of each AES functions if we send a more than 1 block long message, and lastly, everytime we send a plaintext it gets padded.

The pad function

The function pad is a function that makes sure that the input we give has a length that’s a multiple of the size of the AES cipher (here AES.block_size=16 bytes). This function was implemented in Python following the PKCS#7 standard.
You can find more informations about it here, but in short if you send a 14 bytes block, since 2 blocks are missing, it will be completed with 2 02 blocks. If 3 blocks are missing, 3 03 will be used, and so on.
However, and that’s going to be a problem here, if you send a message where the last cipher is 16 bytes long, it will add a full cipher composed of \x10 (16 in hexadecimal). This might not seem too concerning, but we only have access to the last cipher block of the AES functions!
For example, let’s say we wanted to authenticate P=0102030405060708090a0b0c0d0e0f to recover AES1(P) et AES2(P) (which should work if only 1 block is ciphered, as the last one is also the first, and P1 is xored to a null IV), the actual message that would be ciphered would be 0102030405060708090a0b0c0d0e0f 10101010101010101010101010101010, which means that we wouldn’t be able to get what we wanted.

The craft of the payload

Let’s recap: we need P1,P2,C1,C2 (for both AES functions) to craft our payload.
Let’s start by determining which P1 we want to use. I personally chose to send “0f” as a first payload, because it gets padded to P1=”0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f”, but technically you could send anything with a length strictly inferior to 16 (to avoid the padding problem we talked about) as long as you take in account the padding. So since the padded message is 1 block long, we receive a message that is exactly AES1(P1)AES2(P1) (I’ll call them A1(P1) and A2(P1)).
Now we need to find a P2 that would work. The last byte of P2 xored with the last byte of A1(P1) and with the last byte of A2(P1) must be 01, so we’ll be able to recover C2 for both AES functions, and the last byte of P2 must be between 01 and 0f so we can bypass the pad restriction. Obviously such P2 won’t exist every time, it will depend of A1(P1) A2(P1). The probability of such a P2 to exist with random A1(P1) and A2(P1) is 15/16**4 so around 1/4370.

The last step

Imagine that we looped on the servor enough time to get a P2 that works. We just have to finish the job: we can use our second authenticate to ask for the first 15 bytes of A1(P1)^P2. P2 has been chosen to allow this xor to end with a 01, so once padded it will give the exact number we’re looking for.
We just need to recover the first 16 bytes of the answer, as here we’re only interested in AES1. Then we do the same with A2(P1)^P2, we recover the last 16 bytes and concatenate them with the first ones. We just have now to check P1P2 with the tag we just formed, and we will get the flag!

The solving script

from Crypto.Util.strxor import strxor
from Crypto.Util.Padding import pad
from pwn import *

# A function to check a couple (message,tag)
def check( hexa, tag, s ):
    print(hexa,tag)
    print(s.recvline())
    print(s.recvline())
    print(s.recvline())
    print(s.recvline())
    s.sendline(b"v")
    print(s.recvline())
    s.sendline(hexa)
    print(s.recvline())
    s.sendline(tag)
    print(s.recvline())
    print(s.recvline())


# This function authenticate a message given in input and returns the hex digest output
def authenticate( mess, s ):
    s.recvline()
    s.recvline()
    s.recvline()
    s.recvline()
    s.sendline(b"t")
    s.recvline()
    s.sendline(mess)
    a = s.recvline()
    print(a)
    return str(a).split(" ") [-1] [:-3]

# This function craft a P2 payload that, once padded, will end with the byte we're interested in
def P2_maker( n ):
    l = b""
    for i in range(16 - n):
        l += bytes.fromhex(hex(n) [2:].zfill(2))
    return l


j = 0
while True:
    try:
        print(j) # Current number of tries done
        j += 1
        s = remote("challenges1.france-cybersecurity-challenge.fr", 6000) # Connecting to the servor with pwntools
        zf = authenticate(b"0f", s) # zf corresponds to P1, we authenticate it
        zf_1, zf_2 = bytes.fromhex(zf [:32]), bytes.fromhex(zf [32:]) # Split the answer in two to get A1(P1), A2(P1)
        l1, l2 = zf_1 [-1] ^ 1, zf_2 [-1] ^ 1 # Xor the two last bytes of each with 1 to get the potential last bytes of P2
        ran = [i for i in range(1, 16)]
        if l1 != l2 or l1 not in ran: # If the two numbers are different, P2 can't exist as it must have only 1 ending byte
                                      # If the two numbers aren't in 1,..,15, we can't craft a P2 that would work once padded
            continue                  # If at least one of this two conditions isn't True, we start again
        print(j, "possible", l1)      # We have found a P2 that should work

        P2 = P2_maker(l1)             # We make P2
        x1 = strxor(zf_1, pad(P2, 16))[:-1]      # We xor AI(P1) ^ P2 and take the 15 first bytes
        x2 = strxor(zf_2, pad(P2, 16))[:-1]      # Same with A2(P1)
        part1 = authenticate(x1.hex(), s) [:32]  # We recover the first part of the tag
        part2 = authenticate(x2.hex(), s) [32:]  # And the second
        check(("0f" * 16 + P2.hex()).encode(), (part1 + part2).encode(), s)  # We send the check and hope to recover a flag
        break

    except Exception as e: # Sometimes one connection will eventually break for no specific reason so this ensure that
                           # the script doesn't stop
        print("Erreur quelque part", e)
        continue

The Flag

After running the script for around 20 mins, we get the flag!

script result

FCSC{f7c50c0e5ad148a3321d9dd0e72c91420e243b42c9c803814f6d8554163b6260}