UIUCTF 2023 — Group Project [Cryptography]

Last week, i participated in UIUCTF 2023 with the TCP1P team and managed to solve several challenges. One of the challenges that I solved was the Group Project (Cryptography).

Challenge Description:

In any good project, you split the work into smaller tasks…

nc group.chal.uiuc.tf 1337

Attachment (chal.py):

from Crypto.Util.number import getPrime, long_to_bytes
from random import randint
import hashlib
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad


with open("/flag", "rb") as f:
    flag = f.read().strip()

def main():
    print("[$] Did no one ever tell you to mind your own business??")

    g, p = 2, getPrime(1024)
    a = randint(2, p - 1)
    A = pow(g, a, p)
    print("[$] Public:")
    print(f"[$]     {g = }")
    print(f"[$]     {p = }")
    print(f"[$]     {A = }")

    try:
        k = int(input("[$] Choose k = "))
    except:
        print("[$] I said a number...")

    if k == 1 or k == p - 1 or k == (p - 1) // 2:
        print("[$] I'm not that dumb...")

    Ak = pow(A, k, p)
    b = randint(2, p - 1)
    B = pow(g, b, p)
    Bk = pow(B, k, p)
    S = pow(Bk, a, p)

    key = hashlib.md5(long_to_bytes(S)).digest()
    cipher = AES.new(key, AES.MODE_ECB)
    c = int.from_bytes(cipher.encrypt(pad(flag, 16)), "big")

    print("[$] Ciphertext using shared 'secret' ;)")
    print(f"[$]     {c = }")


if __name__ == "__main__":
    main()

Analysis:

    .....snip....
    key = hashlib.md5(long_to_bytes(S)).digest()
    cipher = AES.new(key, AES.MODE_ECB)
    c = int.from_bytes(cipher.encrypt(pad(flag, 16)), "big")

    print("[$] Ciphertext using shared 'secret' ;)")
    print(f"[$]     {c = }")
    ....snip....

It is known that the key is the MD5 hash of the “S”, which is then returned in a byte format. This key is used to encrypt the flag using AES ECB mode.

To decrypt the AES ECB mode, this key is required.

How to get the key?

As we can see in the source code above, the script require user input for the value of “k”. There is if condition specifically checking for the weak values of “1”, “p-1”, and “(p-1) // 2”. So, we cannot use that values as the input for “k”.

Because its only checking for the specific weak values, i used the sympy.totient python library to count the positive integers less than “p” and coprime with “p”. It does not necessarily yield the same values as “1”, “p-1”, or “(p-1) // 2”.

When we choose the “k” to be the totient of “p”, a fascinating property arises. The property is that for any positive integer “a” and prime number “p”, “a ^ phi(p) = 1 (mod p)” holds if “a” is coprime with “p”.

    ....snip....
    try:
        k = int(input("[$] Choose k = "))
    except:
        print("[$] I said a number...")

    if k == 1 or k == p - 1 or k == (p - 1) // 2:
        print("[$] I'm not that dumb...")

    Ak = pow(A, k, p)
    b = randint(2, p - 1)
    B = pow(g, b, p)
    Bk = pow(B, k, p)
    S = pow(Bk, a, p)
    ....snip...

In the given code, after computing Ak = pow(A, k, p), “Ak” will become 1 (mod p) due to the property mentioned above. Consequently, when “Bk” is computed as pow(B, k, p), it will also be equal to 1 (mod p). As a result, when computing S = pow(Bk, a, p), “S” will still be 1 (mod p) since 1 raised to any power is still 1.

Since the shared secret “S” is always equal to 1 (mod p) when “k” is the totient of “p”, the derived encryption key “key” will be the MD5 hash of the same value every time. This results in a predictable encryption key.

Solver:

from Crypto.Util.number import *
from Crypto.Cipher import AES
from sympy import *
from pwn import *
import hashlib

io = remote("group.chal.uiuc.tf", 1337)
io.recvuntil(b"business??\n[$] Public:\n")
g = io.recvline().decode("utf-8").replace("[$]     ", "").replace("\n", "")
p = io.recvline().decode("utf-8").replace("[$]     ", "").replace("\n", "")
A = io.recvline().decode("utf-8").replace("[$]     ", "").replace("\n", "")

# if k == 1 or k == p - 1 or k == (p - 1) // 2:
k = totient(p.split("p = ")[1])

io.sendline(str(k).encode())
io.recvuntil(b"Ciphertext using shared 'secret' ;)\n")

c = io.recvline().decode("utf-8").replace("[$]     ", "").replace("\n", "")

io.close()

g = int(g.split("g = ")[1])
p = int(p.split("p = ")[1])
A = int(A.split("A = ")[1])
c = int(c.split("c = ")[1])

S = pow(A, k, p)

print(f"[+] K = {k}")
print(f"[+] S = {S}")

key = hashlib.md5(long_to_bytes(S)).digest()
print(f"[+] Key = {key}")
cipher = AES.new(key, AES.MODE_ECB)
flag = cipher.decrypt(long_to_bytes(c)).decode("utf-8")
print(f"[+] Flag = {flag}")

We got the flag:

Thank you for reading this article, i hope it was helpful :-D