Insomni'hack CTF 2023 - Still counting on you

There was only one crypto challenge at the Insomni’hack CTF 2023, and that was this one. Our application runs on a server, and we have a Python file that shows us how it works.

The python file consists of 4 functions:

xorshift128
encrypt_message
encrypt_user_message
menu

We have the ability to encrypt a message of your choice using the encrypt_user_message function and we can get the encrypted admin_message which most likely also contains the flag.

import time
from Crypto.Cipher import ChaCha20_Poly1305
from admin import admin_message, key

def xorshift128():
    x = int(time.time())
    y = 362436069
    z = 521288629
    w = 88675123

    while True:
        t = x ^ ((x << 11) & 0xFFFFFFFF)
        x = y
        y = z
        z = w
        w = w ^ (w >> 19) ^ t ^ (t >> 8)
        yield w

random = xorshift128()

def encrypt_message(message):
    # 12-byte nonce
    nonce = next(random).to_bytes(4, byteorder="little")
    nonce += next(random).to_bytes(4, byteorder="little")
    nonce += next(random).to_bytes(4, byteorder="little")
    cipher = ChaCha20_Poly1305.new(key=key, nonce=nonce)
    ciphertext, tag = cipher.encrypt_and_digest(bytes(message, 'utf-8'))
    return nonce.hex().upper() + ciphertext.hex().upper() + tag.hex().upper()

def encrypt_user_message():
    print("What message would you like to encrypt?")
    to_encrypt = input("> ")
    return encrypt_message(to_encrypt)

def menu():
    ENCRYPT = 1
    ADMIN_MESSAGE = 2
    LEAVE = 3

    choice = 0
    while choice != LEAVE:
        print(f"----- Encryption Toolbox -----\n"
            f"{ENCRYPT}. Encrypt a new message\n"
            f"{ADMIN_MESSAGE}. Read the administrator message\n"
            f"{LEAVE}. Leave. Goodbye.\n")
        try:
            choice = int(input("Enter your choice. "))
        except ValueError:
            continue

        if choice == ENCRYPT:
            print(encrypt_user_message())
        elif choice == ADMIN_MESSAGE:
            print(encrypt_message(admin_message))

if __name__ == "__main__":
    menu()

Each message gets encrypted by ChaCha20_Poly1305 which is an authenticated encryption mechanism. It uses ChaCha20 to encrypt messages and Poly1305 to generate a message authentication code.

If we look how ChaCha20 works we can see that it is a stream cipher.

alt text

The basic idea of a stream cipher is that given a secret key K and a nonce N we can generate a secret one-time pad which has the same size as the message M we try to encrypt. The one-time pad is also referred to as a key stream.

The key observation for us is that given the same key K and the same nonce N we will receive the same key stream.

Solution

If we look at how the nonce is created in our python file we can see that the only source of “randomness” is the x = int(time.time()). int(time.time()) gives us the current timestamp in seconds since we cast it to an integer.

This means that, if we can encrypt 2 ciphers simultaneously (within one second), we can get the same nonce N and, as a result, also the same key stream. If we know one of the two plaintext text then we can decrypt the second unknown cipher text like so

$$\begin{eqnarray} c1 = flag ⊕ key\_stream \\\ c2 = chosen\_pt ⊕ key\_stream \end{eqnarray}$$

Now since we know the chosen_pt we can get the flag by just xoring the two cipher text and then xoring chosen_pt and we are left with the flag.

$$\begin{eqnarray} chosen\_pt ⊕ flag = c1 ⊕ c2 \\\ flag = (chosen\_pt ⊕ flag) ⊕ chosen\_pt \end{eqnarray}$$

We created a python script that created two connections in parallel. One connection encrypts our chosen_pt (which in our case was just b'1'*100) and the second retrieves the encrypted flag. We can also check if we received the same key stream if the nonce we receive at the start of the string is the same.

return nonce.hex().upper() + ciphertext.hex().upper() + tag.hex().upper()

c1 is the encrypted flag and c2is our encrypted plaintext that we choose. We first have to remove the nonce and the tag since we don’t need those values.

c1 = "4129278E1D70D549012594C7CF87235528FF23D013D60BAEE9FC852DEF119262AD1771EB2501CDBABD3F2E623B37954115EE800162C32F5BD6AF69966AFC49FBDCD351EBF2BC53A2".lower()
c2 = "4129278E1D70D549012594C7B6D3600139A761C15B884FEDF83D2B86771A831AD2753B89270398D4E57D40276263FB2741BEDA5E36C72B17F2B7586F857BCFF628E28FF957439D53EF1A0C7B57F656A2B2EB05D101040762".lower()

c1 = bytes.fromhex(c1[24:-32])
c2 = bytes.fromhex(c2[24:-32])

def xor(var, key):
    return bytes((a ^ b ) for a, b in zip(var, key))

output = xor(c1, c2)
output = xor(output, b'1'*100)
print(output)

And then we find the flag

b'Here is your \xf0\x9f\x9a\xa9: INS{S33d_is_the_Weakne55}'

Solution#

Solution