ASC - Wargames Finals 2021

This is not only a writeup for the crypto challenges in the wargames final competition, but also an introduction to the future of cryptography.

September 19, 2021 - 22 minute read -
Security ASC-Wargames CTF Infosec Python Hacking Cryptography cracking Lattice-Based Hash-Based Quantum AES Padding-Oracle

ASC

Table of Content

Intro

Arab Security Conference was held this year from 5th till 7th of September and as always the last day was for the cyber wargames competition where ten qualified teams compete with each other and solve sophisticated challenges in 5 different categories in information security. In this write-up, we’re going to discuss and solve the 4 crypto challenges I created in the ASC wargames finals this year 2021 with my bro X-Vector. The challenges was a bit heavy and full of tricks for those who aren’t up-todate with the latest crypto systems and techniques. However, I’ll show you my thought process when I face a tough challenge and how to divide it into sub-challenges in order to find a correct solution.

:DISCLAIMER:

You’re not gonna find here all the tips and tricks in crypto since I wanted to leave some space for you to think and ask. So, feel free to think more about the challenge before jumping into the solution.

Black Box

Description:

A plane was attacked by a highly skilled hacker and in order to control it, he has to break the black box encryption. Can you help him to decrypt the commands and control the plane?

The challenge’s name and describtion seems to have a good hint about what type of attack we’re gonna do on this server. When connecting to the ip/port it gives us the following

Black Box

Analysis

The server uses AES CBC and of course from its name, we’ll assume it’s a padding oracle attack on AES. In order to test our assumtion, we should modify the last byte of ciphertext and pass it to the oracle and it gives us Padding Error! also after modifying the first byte and pass it to the oracle it given us MAC Error!, now we’re 100% sure it’s a padding oracle attack. The CBC uses PKCS7 scheme in order to pad the messages before the encryption. The given cipherhex contains 80 bytes which means we have to deal with 5 blocks of ciphertext 16 bytes each.

Solution

For those who unaware of this type of attack, I found this great article explaining the attack in detail.

The decryption process goes as following:

\[P_k = D(k,C_k) \oplus C_{k-1} \\ P_{k-1} = D(k,C_{k-1}) \oplus C_{k-2} \\ ... \\ P_1 = D(k,C_1) \oplus iv\]

Briefly, if we have just one block beside the iv, we have to start from the previous block (or iv) in our case we don’t know the iv, so we shall start attacking each block based on the previous block. To do so, we’ll start by the last or 5th block to determine the padding size and the following steps will be repeated for each block:

  • Pick a random byte \(B\) from \([0,255]\) and replace it with the last byte of \(C_k\).
\[C'_{k-1} = C_{k_{1:15}} \cdot B\]
  • If the decryptoin of \(C'_{k-1} \cdot C_k\) succeeds e.g.
\[P'_{k_{15}} = D(k, C_{k_{15}}) \oplus C'_{(k-1)_{15}} = 01 \\ C_{k_{15}} = E(k, P_{k_{15}} \oplus C_{(k-1)_{15}}\]
  • Rearraging the above equation, we shall get the plaintext byte
\[P_{k_{16-i}} = C_{(k-1)_{16-i}} \oplus C'_{(k-1)_{16-i}} \oplus i\]

where \(i = 1,..,15\).

This attack is pretty straightforward, but the implementation may be a little confusing due to multiple runs for trial and error. 

#!/usr/bin/env python3
from pwn import remote, context, xor
import os
from time import sleep, time_ns
context.log_level = 'critical'
BLOCK = 16
get_blocks = lambda msg: [msg[i:i+BLOCK] for i in range(0, len(msg), BLOCK)]

HOST, PORT = '10.0.0.4', 33176
r = remote(HOST, PORT)
# get ciphertext
ct = bytes.fromhex(r.recvuntil('(hex): ').split(b'\n')[-3].decode())

# convert ct into blocks each of size 16 bytes
blocks = get_blocks(ct)

flag = [b'' for _ in range(len(blocks))]
start = time_ns()
for j in range(4, -1, -1):
    plain = bytearray([0 for _ in range(BLOCK)])
    c_prime = bytearray([b for b in blocks[0]])
    for i in range(BLOCK):
        padding = bytearray([0 for _ in range(BLOCK - i)] + [(i+1) for _ in range(i)])
        c_prime = bytearray(xor(padding, plain, blocks[j - 1]))

        for byte in range(1,256):
            # performing step 1
            c_prime[15 - i] = byte
            to_decrypt = c_prime + blocks[j]
            r.sendline(to_decrypt.hex())
            if 'MAC' in r.recvuntil('\n').decode():
                # performing step 2 and 3
                poss_byte = blocks[j - 1][15 - i] ^ byte ^ (i + 1)
                # checking the correct padding, this step got first
                with trial and error
                if j == 4 and i == 0 and poss_byte != 0xf:
                    exit(1)
                plain[15 - i] = poss_byte
                break
            r.recvuntil('(hex): ')
    flag[j] = bytes(plain)
r.close()
print(b''.join([f for f in flag[1:]])[:-6])
print(f'Run in {(time_ns() - start)/1e9} secs')

And we’ll get the flag: ASCWG{0r4cl3_0r4cl3_0N_A3S_L3f7_R19H7_U9_D0wN!!}

Time To Guess

This challenge has no describtion and has 2 pitfalls. The first one is the intended solution and the other one for those who focus on details. It also gives us the source code and a server to connect. When connecting to the server it gives the following.

Time To Guess

Let’s look at the source code:

#!/usr/bin/env python3
from Crypto.Util.number import getRandomNBitInteger, long_to_bytes as ltb
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
from math import gcd

def BBS(N):
    seed = getRandomNBitInteger(512)
    assert gcd(seed, N) == 1
    X = pow(seed, 2, N)
    while True:
        X = pow(X, 2, N)
        yield X, X & 1

def encrypt(key):
    cipher = AES.new(key, AES.MODE_CBC, iv)
    ct = cipher.encrypt(pad(FLAG, 16))
    return ct.hex(), cipher.iv.hex()

if __name__ == '__main__':
    from secret import FLAG, N
    gen = BBS(N)
    print('It\'s time to guess!')
    print(f'n: {N}')
    print(f'v: {next(gen)[0]}')
    input('Give me the next 1000 bits!')
    for _ in range(1000):
        if int(input().strip()) != next(gen)[1]:
            print('Try again!')
            exit(0)
    key = ''
    for _ in range(128):
        key += str(next(gen)[1])
    ciphertext, iv = encrypt(ltb(int(key, 2)))
    print(f'{ciphertext=}\n{iv=}')

Analysis

After analyzing the code, the server wants from us to sumbit the next 1000 bits after it prints N and v based on some sort of function called BBS and the next 128 bits are the secret key for the AES encryption of the flag. Looking at BBS, it simply do the following:

  1. Generate 512 bit random integer as a seed and check it has no divisors with \(N\).
  2. Calculate \(X = seed^2 \pmod N\).
  3. Loop forever and for each iteration return \(X^2 \pmod N\) and its least significant bit (e.g. right-most bit).

Rearranging the equations gives:

\[X_{i+1} = X_i^{2^i} \pmod N : \ X_0 = seed\]

Surprisingly, this algorithm is called Blum Blum Shub, a pseudorandom number generator based on hardness of factorization of the modulus N and our goal is to find the seed in order to crack the BBS.

1st Solution

Connecting to the server multiple times gives us the same N but different v, so let’s try to factor N since it’s only 271 bits. Factordb couldn’t make it, let’s go to Alpertron. At first, there was no hope, but after awhile it seems to be able to factor it in almost 20 min.

N = 46404135538347313105324845256452679880827 × 62935919582590588934355071817888577583483

Now, we know that \(v = seed ^ {2^2} \pmod N\), so we want to find the 4th root module \(N\) which leads to a quadratic residue problem and hopefully it’s easy to compute after we found the primes of the modulus \(N\).

So, the whole attack goes as following:

  1. Find \(x, y\) such that \(v = x ^ 4 \pmod p\) and \(v = y ^ 4 \pmod q\) where \(p, q\) are the only prime factors of \(N\).
  2. Use The Chinees Remainder Theorem to get a unique solution \(seed \pmod {N=pq}\) for the following equations:
\[seed = x \pmod p \\ seed = y \pmod q\]

2nd Solution (Unintended)

If you noriced that v is the first value that BBS generates which means \(v = X^2 \pmod N\), however if you square it again you’ll get the second value of the function and of course its right-most bit and so on.

Therefore, the next random bits can be obtained by squaring v 1000 times each of which contains the bit you wanted in order to send it to the server. 

#!/usr/bin/env python3
from pwn import remote, context
from sympy.ntheory.modular import crt
from sympy.ntheory.residue_ntheory import nthroot_mod
from Crypto.Util.number import long_to_bytes as ltb
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
from math import gcd
from time import time_ns, sleep
context.log_level = 'critical'

def BBS(seed):
    assert gcd(seed, n) == 1
    X = pow(seed, 2, n)
    while True:
        X = pow(X, 2, n)
        yield X, X & 1

def decrypt(key, msg, iv):
    cipher = AES.new(key, AES.MODE_CBC, iv)
    ct = unpad(cipher.decrypt(msg), 16)
    return ct

host, port = '10.0.0.4', 33175
r = remote(host, port)
n, v = r.recvuntil('bits!').split(b'\n')[1:3]
n = int(n[3:].decode())
v = int(v[3:].decode())
p = 46404135538347313105324845256452679880827
q = 62935919582590588934355071817888577583483

# Solution 1
start = time_ns()
roots = [nthroot_mod(v, 4, p), nthroot_mod(v, 4, q)]
seed = int(crt([p, q], roots)[0])

gen = BBS(seed)
assert next(gen)[0] == v
for _ in range(1000):
    r.sendline(str(next(gen)[1]))
    # some delay to prevent crashing
    sleep(.03)
data = r.recvall().split(b'\n')
r.close()

# Solution 2
for _ in range(1000):
    r.sendline(str(pow(v,2,n) & 1))
    # some delay to prevent crashing
    sleep(.03)
data = r.recvall().split(b'\n')
r.close()

key = ''
for _ in range(128):
    key += str(next(gen)[1])
ct, iv = data[1:]
ct = bytes.fromhex(ct[12:-1].decode())
iv = bytes.fromhex(iv[4:-1].decode())
print(decrypt(ltb(int(key,2)), ct, iv))
print(f'Run in {(time_ns() - start) // 1e9}s')

And it gives us the flag: ASCWG{7h3_P0wer_0f_F@c7oR1z4t10n_T0_Br3aK_R4nd0mNe$$!}

Winter On The Street

Description:

Winter was walking around the street and he has found a new way of a public-key cryptosystem to encrypt messages in a quantum channel. He thinks that his idea is fascinating and no one can break it. Could you prove him wrong?

The challenge comes with a python script challenge.py and output.txt files. The name looks unfamiliar, but the description sounds a bit tricky since it mentioned a public-key system with a quantum sense.

The text file:

public = 70a79a427440334bb164dd221e987d1e988aea1ae331097d63f9a3d8e68cbec039707084e3cf6914e93fb732b8c5ffa5473c4f04aa745c922178faa6cba53bc9
ciphertext = d7ae83c99ba7ab3a4075ac6625883876274af2e04382f25c0528178f5a4448a23b6cca458c7207aa2ddfd8cb47b1e92639822bf723cc17b03d50b7804459d14e
iv = dbf4b3ba270f7389feb0a72b830cd6f3

The script contains:

#!/usr/bin/env python3
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Random.random import choice, bytes_to_long as btl
from hashlib import sha512
from secret import FLAG, secret_key
import os

BLOCK = 16
BITS = 2**BLOCK

def H(msg, n):
    public = msg
    for _ in range(n):
        public = sha512(public).digest()
    return public

def encrypt(plain, key):
    cipher = AES.new(key, AES.MODE_CBC)
    ct = cipher.encrypt(pad(plain, BLOCK))
    return ct, cipher.iv

# private key
private = H(secret_key, BITS)
binary = bin(btl(private))[2:]
msg_sign = [int(binary[i:i+BLOCK],2) for i in range(0, len(binary), BLOCK)]

# public key
public = H(secret_key, choice(msg_sign))

ct, iv = encrypt(FLAG, private[BLOCK:-BLOCK])

# Write info
with open('output.txt', 'w') as p:
    p.writelines([f'public = {public.hex()}\n', \
    f'ciphertext = {ct.hex()}\n', \
    f'iv = {iv.hex()}'])

Analysis

Looking at the code, it has a function H that hashing a message n times with sha512. It also generates a private key based on a secret and hash it 65536 times, and a public key based on the same secret, but hashing it with 16 bit random number from the private key after converting it into binary. Then, it encrypts the flag with the middle 16 bytes of the private key.

After searching about such known quantum cryptosystems, we found Winternitz One Time Signature. It’s a quantum resistant digital signature hash based scheme that uses relatively small key and signature sizes, but the challenge looks a modified version of it.

The scheme works as follow:

If you want to sign a message between \(0\) and \(w-1\), where \(w\) is some parameter of the scheme.

  1. The private key \(K\) to sign a message \(M\), where \(0 < M < w\), compute \(H^M (K)\).
  2. The public key is \(H^w(K)\).
  3. WOTS signature \(S\) verified by checking that \(H^{w-M}(S)\) is equal to the public key, where \(S\) is the private key after \(M\) hashing.

From the above, we shall get \(M + (w - M) = w\) times which is the public key.

Solution

To get all the pieces together, we don’t know what K = secret_key and \(M\), but we know only \(w = 2^{16}\). Notice that, \(M\) in the code generated by 16 bit integer chosen randomly from the private key and also we know that \(M < w\). Thus, our goal is to brute force over \(M\) in the range \([0, 2^{16}]\) and hash the public key \(M\) times in order to get the flag. 

#!/usr/bin/env python3
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
from hashlib import sha512
from tqdm import tqdm
import multiprocessing as mp

BLOCK_SIZE = 16
BITS = 2**BLOCK_SIZE

def H(msg, n):
    public = msg
    for _ in range(n):
        public = sha512(public).digest()
    return public

def decrypt(ct, key, iv):
    cipher = AES.new(key, AES.MODE_CBC, iv)
    try:
        plain = unpad(cipher.decrypt(ct), BLOCK_SIZE)
        return plain
    except:
        return b''

def attack():
    for M in range(BITS, 1, -1):
            #priv = H(public, BITS - M) the systematic way is to calculate the hash M times
            public = sha512(public).digest() # the correct one shall be here directly (optimized)
            dec = decrypt(ciphertext, public[16:-16], iv)
            if b'ASCWG{' in dec:
                print(f'Secret: {M}')
                print(f'Flag: {dec}')
                return True


public = bytes.fromhex('70a79a427440334bb164dd221e987d1e988aea1ae331097d63f9a3d8e68cbec039707084e3cf6914e93fb732b8c5ffa5473c4f04aa745c922178faa6cba53bc9')
ciphertext = bytes.fromhex('ea8174d42438c795c5e622a48fedb46a535115e1e95efb095266784e72f9f6ee14a1c5e50fe1f7e4e3c8e95d7755c904c2c2f836cb9abdc10eb7af3e3fdc73d5')
iv = bytes.fromhex('03a615eb6074a28fc06804c0d1e37264')

from time import time_ns
start = time_ns()
attack()
print(f'Run in {(time_ns() - start)/1e9} secs')

The flag:

ASCWG{H@sh1n9_B4s3d_CrYp70_15_N0_L0n93r_$3cUr3_1337}

Learn With Encryption

Description:

Y4mm1 has created a super-secure communication on a quantum computer so that he can easily send any messages to Vector, but somehow he messed up with his secret so that no one can retrieve it. Could you help Vector to read the message?

This was the toughest one among all the previous challenges. The description gives us a big hit along with the name that this one deals with a quantum system as well. However, this time it has 5 file cipher.txt, error.txt, U.txt, Vector.pub, and Y4mm1.pub and a Python script challenge.py. Looking at the text file, all of them contains a lot of lines contains nonsense long integers.

Let’s look at the script:

#!/usr/bin/env python3
from Crypto.Util.number import getStrongPrime, long_to_bytes, bytes_to_long, isPrime
from Crypto.Random.random import getrandbits, randint

BITS = 2048
m = 50

def random_sampling(A, B):
    A_sample = []
    B_sample = []
    for _ in range(5):
        idx = randint(0,len(A)-1)
        A_sample.append(A[idx])
        B_sample.append(B[idx])
    return A_sample, B_sample

def encrypt(binary, Y, V):
    u = []
    v = []
    for bit in binary:
        A_sample, B_sample = random_sampling(V, Y)
        u.append(sum(A_sample))
        v.append(sum(B_sample) + int(bit) * q // 2)
    return u, v

if __name__ == '__main__':
    from secret import FLAG
    flag_bin = bin(bytes_to_long(FLAG))[2:]

    # Vector's public V and q
    q = getStrongPrime(BITS//2) # 141005691252576910321815300061524449403845156924370242363315198848732371339932991756697517095443419110596785676030977421942118579454753665338366954459064297763829764285379194891675397250604611542915187836155005789963659035798773723913603251708665381916244748924954152641555562387549588439698777943453481516067
    V = [getrandbits(BITS*2) % q for _ in range(m)]

    # Secret keys
    s = getrandbits(BITS) % q
    Error = [getrandbits(BITS//8) for _ in range(m)]

    # Y4mm1's public
    Y = [(v*s + e) % q for v, e in zip(V, Error)]

    # cipher
    u, cb = encrypt(flag_bin, Y, V)

    import numpy as np
    np.array(V).tofile('Vector.pub', sep='\n')
    np.array(Y).tofile('Y4mm1.pub', sep='\n')
    np.array(Error).tofile('error.txt',sep='\n')
    np.array(u).tofile('U.txt', sep='\n')
    np.array(cb).tofile('cipher.txt', sep='\n')

Analysis

The script has 2 main functions encrypt and random_sampling. Then it does the following:

  1. Get the flag from the secret file, then converts it into binary.
  2. Generate a known random 1024 bit prime \(q\).
  3. Generate 50 random integers 4096 bit each as a Vector’s public key.
  4. Generate a 2048 bit random integer \(s\) along with 50 random integers 256 bit each.
  5. Generate Y4mm1’s public key based on Vector’s key and the Error with this equation \(Y = Vs + Error\).

All the previous are reduced module \(q\), then it encrypts the bits of the flag with the Vector and Y4mm1 public keys.

The encryption function get random samples from both public keys, iterate over the bits of the flag and in each iteration does the folowing:

  1. Sum the first sample that belongs to Vector’s public and append it into a list u.
  2. Sum the second sample that belongs to Y4mm1’s public and add to it the current flag bit multiplied by \(\frac{q}{2}\), then append it into a list v.

Solution

After some digging about quantum cryptography, this technique is pretty known in the robust quantum world of crypto systems called Learning With Errors. It’s a lattice based cryptography algorithm built on top of SVP & CVP hard problems. This challenge is a simplfied version of the LWE system.

The secret parameters should be \(s\) and \(Error\), but we know only the \(Error\) vector and from this equation \(Y = Vs + Error \pmod q\) the only unknown here is the secret integer \(s\), where \(Y\) and \(V\) are the public keys. Rearranging the equation, we shall get \(s = V^{-1}(Y - Error) \pmod q\) where \(xV = 1 \pmod q\) the equation to get the modular inverse of \(V \pmod q\).

Note that, the public keys are lists and the secret is a single integer, so for any values of the public keys, we should get the same secret value \(s\) from the previous equation.

Then, we can apply the decryption process \(dec = c - su \pmod q\) where \(c\) is the encrypted bit integer from cipher.txt and \(u\) is the value from U.txt. In order to get each bit of the flag, we should check \(dec < \frac{q}{2}\) for 0 and 1 otherwise. 

#!/usr/bin/env python3
from Crypto.Util.number import long_to_bytes, isPrime, inverse

q = 141005691252576910321815300061524449403845156924370242363315198848732371339932991756697517095443419110596785676030977421942118579454753665338366954459064297763829764285379194891675397250604611542915187836155005789963659035798773723913603251708665381916244748924954152641555562387549588439698777943453481516067
with open('Vector.pub', 'r') as alice, \
    open('Y4mm1.pub', 'r') as bob, \
    open('cipher.txt', 'r') as c, \
    open('U.txt', 'r') as u, \
    open('error.txt', 'r') as e :
    alice = list(map(int, alice.readlines()))
    bob = list(map(int, bob.readlines()))
    cipher = list(map(int, c.readlines()))
    u_vec = list(map(int, u.readlines()))
    e_vec = list(map(int, e.readlines()))

flag = ''
As = [(b - e) for b, e in zip(bob, e_vec)]
s = inverse(alice[0], q) * As[0] % q

for v, u in zip(cipher, u_vec):
    dec = (v - s*u) % q
    if dec < q // 4:
        flag += '0'
    else:
        flag += '1'
print(long_to_bytes(int(flag,2)))

It doesn’t matter \(dec < \frac{q}{2^i}\), for any arbitrary \(i>0\). The \(dec\) should be close to 0, you could notice that from the encryption function.

Finally, we’ll get the flag:

ASCWG{L@tt1c3_B4s3d_Cryp70_5y$7em_15_M0r3_53cUr3_7h4n_U_7h1nk!^_^}

Conclusion

This write-up discussed and analyzed not only the crypto challenges in the competition but also how to deal with difficult problems and how to cut them into pieces in order to be able to find a solution. In addition, it covered new topics in cryptography and post-quantum crypto in a simplified way to get into the concept and understand how it works.

The topics included:

  • Padding Oracle Attack on AES-CBC mode and implementation steps.
  • Attacking Blum Blum Shub pseudo random number generator algorithm.
  • Post Quantum Hash-Based Cryptography and Winternitz One Time Signature.
  • Post Quantum Lattice-Based Cryptography and Learning With Errors.

All post-quantum schemes are considered NP-Hard which means its security remains hard to quantify, but when security looks too good to be true, it often is. Because of the lack of understanding of the constructions of such a scheme, however you get the first step in the future of cryptography.

Finally, there isn’t one way of thinking about a challenge to find a solution. Although, you may take hours, days, weeks, or even months in order to understand how such a cryptosystem works and find flaws to break it.