Down Under CTF 2022

Posted on Edited on In ,

We were ranked 185/1942, which means we were at Top 10% of the game. This is my second time playing CTF, I'm quite happy with the result. Although I think we could have jumped into TOP 100 but we'll wait until next time! :D

baby-arx

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
class baby_arx():
    def __init__(self, key):
        assert len(key) == 64
        self.state = list(key)

    def b(self):
        b1 = self.state[0]
        b2 = self.state[1]
        b1 = (b1 ^ ((b1 << 1) | (b1 & 1))) & 0xff
        b2 = (b2 ^ ((b2 >> 5) | (b2 << 3))) & 0xff
        b = (b1 + b2) % 256
        self.state = self.state[1:] + [b]
        return b

    def stream(self, n):
        return bytes([self.b() for _ in range(n)])


FLAG = open('./flag.txt', 'rb').read().strip()
cipher = baby_arx(FLAG)
out = cipher.stream(64).hex()
print(out)

# cb57ba706aae5f275d6d8941b7c7706fe261b7c74d3384390b691c3d982941ac4931c6a4394a1a7b7a336bc3662fd0edab3ff8b31b96d112a026f93fff07e61b

Solution

When I first looked at this problem, I thought this would be a bit operation problem which, if you are a applied cryptography engineer, you should be really familiar with. But this misled me so much that I paid more time working on this problem.

% 256 is equivalent to & 255; and & 0xff means getting the lowest 8 bits. I also tried lots of bit operation technique such as &1 is judging odd/even, right shift(resp. left shift) are \(\lfloor \frac{a}{2^{b}} \rfloor\) (resp. \(a\cdot 2^{b}\))... and so on. But they just didn't work.

So at the end of the day, I thought, oh, I'd just try z3 solver. And the result just popped up.

In fact, it can be solved by z3 solver, but I think it actually does have its arithmetical solution. I just didn't find it. Like the answer by the end: DUCTF{i_d0nt_th1nk_th4ts_h0w_1t_w0rks_actu4lly_92f45fb961ecf420}

Code

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
from os import urandom
from z3 import *

ct = "cb57ba706aae5f275d6d8941b7c7706fe261b7c74d3384390b691c3d982941ac4931c6a4394a1a7b7a336bc3662fd0edab3ff8b31b96d112a026f93fff07e61b"
streamhex_to_bytes = bytes.fromhex(ct)
stream_list_back = list(streamhex_to_bytes)

solver = Solver()
result = [BitVec('x{}'.format(i), 8) for i in range(64)]

for i in range(63):
    solver.add((((result[i] ^ ((result[i] << 1) | (result[i] & 1))) & 0xff)
    +((result[i+1] ^ ((result[i+1] >> 5) | (result[i+1] << 3))) & 0xff))
     % 256 == stream_list_back[i])

solver.add((((result[63] ^ ((result[63] << 1) | (result[63] & 1))) & 0xff)
+((stream_list_back[0] ^ ((stream_list_back[0] >> 5) | (stream_list_back[0] << 3))) & 0xff))
    % 256 == stream_list_back[63])

while solver.check() == sat:
    recover = solver.model()
    recover_list = []
    for i in range(64):
        recover_list.append(recover[result[i]].as_long())
    try:
        print(bytes(recover_list).decode())
    except:
        pass

oracle-for-block-cipher-enthusiasts

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#!/usr/bin/env python3

from os import urandom, path
from Crypto.Cipher import AES


FLAG = open(path.join(path.dirname(__file__), 'flag.txt'), 'r').read().strip()
MESSAGE = f'Decrypt this... {urandom(300).hex()} {FLAG}'


def main():
    key = urandom(16)
    for _ in range(2):
        iv = bytes.fromhex(input('iv: '))
        aes = AES.new(key, iv=iv, mode=AES.MODE_OFB)
        ct = aes.encrypt(MESSAGE.encode())
        print(ct.hex())


if __name__ == '__main__':
    main()

Solution

I really enjoyed this one because I didn't refer any previous solution, and I didn't play block cipher type problem before. I solved it by my own. But being a cryptography engineer, you always deal with those block cipher, so this problem is not only meaningful for obtaining some points in a CTF game, but also helped me understand how to avoid unsafely implementing cryptography algorithm. (Although I always have a fear that I might implement something wrong. It's inevitable. That's why it's also important to add security check for cryptography implementation in code review.)

Anyway, it's crystal clear that OFB will be vulnerable when you use the key twice. Because you can always have this so-called "bit-flipped" attack (I think I read it somewhere else, but can't remember).

The attack for this problem can be summarised by this photo below:

Code

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
#!/usr/bin/env python3

from operator import xor
from os import urandom, path
from Crypto.Cipher import AES


FLAG = f'ABCDEFGHIJK{urandom(67).hex()}'
MESSAGE = f'Decrypt this... {urandom(300).hex()} {FLAG}'


def main():
    ct_list = []
    
    ct1 = "75d0e05886a8dbd5631162ffc172b054d9b986115b46e81ee741873b429b363d4e6ef9615ca1a831a681f14289d79c69a08656c6b382319c7a2b6f53591890b21c5e146f1ccf5a84d8c21e8c0d8f6cf4b5cdefaa92d0f073588e05650384e1453d1d357e77c81f31f3cde44dad95a3b86098f8d0237f72490347ed5288d4d7f2fd9b9ef09ec24ef93f332267931f7070a806b5943c4e9e74282adfb756a9c9a67277c4f83555c389d8443bc57ccc3a569facc51b6164709a533b3184f4c0a3faacd6a0b694e0ada63749a911dbc840b0fb1b589b87e7a3e12b1109c138ad1eb23287b3e99763bff1c9a4c9eac40b6bab53d5281cf328a0ddc16ed53879f2ac7c831fc8f061889da96a032a5127a2315341ddf6908fc9d3f682ac22d1b176586ce72a92fe55fbef153caaf758151554b98ac7aec86314c3f34eadcdc0fe5c8710f6ddf7bcb023535034485ca66b729d53ba5d6fe85551c87547e9c69eb3e2c2a33320adea7dd9ccec6775a82580f3e53251f1c8a0cb7bfd0d12e2ce931d03bb7736807e7268d8957fbbfae0041b2e4258d0c2669919dd180cab1364f9e04b442aaa7772bd7200f1eab6883eac54e2650252ec0c6056414607d04d97abf517c016e2d2d0b10df0f80e5aafb79bee9721efbb195efcf38ffaf9b9e31eef6f97841b79275823df2ea429808ff15b27d017cc9bce7d9e1479a95919ce680706c22807507abb5e05ca865413922cf3f0d0306aacd5201b84a4a989f0129a3a566528d4cb9b81e17d6f21f3a979a7412b4798a20125d47da3e09232407fa2106f384a5763e8be30acf29d7b09973d2888db7c1fac3ed8ee85aea85342ff3a54ea4d8a7813d4ffb2fe918f6cbc15f4741c46cfd036b34cbad0a09e07a4747635238ad8a38326298bca3790e52775b6e9e31b10a51ac4e9e1da659e98c5e3e6ce606b5e8e8309fe91ebb3cd742baebb0ca4df1fd29edb53c71277f018f92989633aa73112c97bc9c3122b60ef61176736d51bc59c61b4949d6f13c769fbc2e9f4fe93d5ed77d12fbb6b8e966b0de18ff2ba37ed4b5fb3601f95bcd8888eee"
    ct1_bytes = bytes.fromhex(ct1)
    ct2 = "a5b9d5554601f95da210de7b09d120781532f9340caefe63a688f742db849d3cf38e079ce48d3ace2a7d3f555b179fb71c0943371acd03d4d89c4e8159d53ba7b4cfebfec0d2f2765a83503f0384e515681a3f7d78c84b3ef2cdb717f8c0a0bf66c2f484792d21165542eb528dda86f2f9c79ea4cbc21faf39612d6cc7137e76f653e3c36d1ecd7d2f29d2b751a8c2a22f7ec0f8625692848e143ec729cd3e539ca6924b6661269a563b30d4f793a6fda9dda7e491b7aea36419aa43d8cd40e2fa120fc083b1a4e929440fca6dfb1cb562d3b1b39635ebfb98a3cdb4950a6fab51832d1cf47af48b9e3cdd6f29a7ac7ad14997a161dbcbf86b5a750126f436574180fbc1dfcf85f58cf52587b2205b6ebc259eab07fdeb1038aeaf0d124604b984c6f5ca361597a548fccd93ae5fd24ca28fa7ecb7735051644e04ae3e26cb09ed5f64ee0452c67311ba94c5e1e596f33123a1ba2edbccea6623a324d4a5e73751f6c5f5907ea65845ecc2c31b03ed2161d17123638c9077ebf3b70e4d2a120a82c1619b128b4a52fe1436f5e01d152aa97e7abb7203f1bae6863cac59b0650457e156675b4342068542c2fdf945c212b5dfd6b359f0fe5c0cabe79dbb9775bde01958f9f0dfa8adb9b51fbd36c0801b237d5a76db2bf62f82dea3087a8014cc99997f9c1728ab0c1f993f5407927c55547de85902cf820017932bf3f5873068f084234187f3fa8ea6439a68563b7683c5cbd0bd243321f7fc7ea3457d1993a70271857afeedc063132ba4176d6d4e0332baba33aca09d270e923e28dcd17d1cf06cdabd86ffab0916af6a06e942852b1ed0afe5ad918d68ad65c5032a368d8564b376b290a2da3eb053570343a0cfeaba3702d2d166bbdc23649dacb50115ec30c4f1aceb67f58b99a6c0a1607107dd9d25f1d9c4bdca7318f4f237f5ec1fd7aab440c5107ef45b962ae6306bc16216a27b8a95587964ec324000318317909c64b3c6c86741963fadcae1f0f3c581b774d679be63de973d0fe4d9a5e166bc400bb0361e9ee9dd8ed8a73a88952d5764cc74fedfec9b29ad0886"
    ct2_bytes = bytes.fromhex(ct2)
    ct_list.append(ct1_bytes)
    ct_list.append(ct2_bytes)

    enc_list = ["31b5832affd8aff517790b8cef5c9e74"]
    pt1 = 'Decrypt this... '
    pt_list = [pt1]

    for i in range(47):

        ct2_cur = ct_list[1][i*16:(i+1)*16]
        pt_cur = pt_list[i].encode()
        enc2_cur = bytes(map(xor, ct2_cur, pt_cur))
        enc_list.append(enc2_cur)

        ct1_next = ct_list[0][(i+1)*16:(i+2)*16]
        pt_next = bytes(map(xor, ct1_next, enc2_cur)).decode()
        pt_list.append(pt_next)

    print(pt_list)

if __name__ == '__main__':
    main()

Result

1
2
3
4
5
6
7
8
9
10
11
12
['Decrypt this... ', '8e06d7ec1903ed8e', 'c90c483110637790', '01a9c78caff55865', 
'0f6ae5a3a868abaf', '1d2577c6c5cbabe6', 'dc868779b50847f1', 'b94bbedf40681971', 
'fe467e502b93e597', '80baf5f95a43b423', 'e9fa1674c1117566', 'f31163a4f10a4f31', 
'c86c3db15a337c3c', 'b1a872e97458b51d', '2ecb6d13f31f345d', '03fb16ee9a91ca5b', 
'be931e3488fab72f', 'b84bace76aa7aa1d', '97873ea22e9bf2ad', '76c5fd5d44916148', 
'cd3ea46ed2a9cebb', '4f8c078c2a3b1b62', '6e43c58e378ce447', '6b9f80c0d943c4ba', 
'a3673df840c95023', '3015824fa7155fc3', '09938146193584c5', '54c45307d6fc4fa1', 
'b9e6a36e226eaf5c', '99c3bcd12d77811c', 'ccafff6705edea2c', 'a4cde74b6b27d1f1', 
'e30cb2062c57aff3', '9b39aec1d25ea88d', '72be89c5151a7f3a', '4f3be41dba7f5375', 
'e47aef18ed4fa966', '9f52f72b14d4b69e', '4bee570f DUCTF{0', 'fb_mu5t_4ctu4lly', 
'_st4nd_f0r_0bvi0', 'usly_f4ul7y_bl0c', 'k_c1ph3r_m0d3_0f', '_0p3ra710n_7b9cb', 
'403e8332c980456b', '17a00abd51049cb8', '207581c274fcb233', 'f3a43df4a}']

cheap-ring-theory

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
from sage.all import *

p = 55899879511190230528616866117179357211
V = GF(p)^3
R = PolynomialRing(GF(p))
x = R.gen()
f = x^3 + 36174005300402816514311230770140802253*x^2 + 35632245244482815363927956306821829684*x + 10704085182912790916669912997954900147
Q = R.quotient(f)

def V_pow(A, n):
    return V([a^n for a in list(A)])

n, m = randint(1, p), randint(1, p)
A = Q.random_element()
B = Q.random_element()
C = A^n * B^m

print(' '.join(map(str, list(A))))
print(' '.join(map(str, list(B))))
print(' '.join(map(str, list(C))))

phi_A = V(list(map(int, input().split())))
phi_B = V(list(map(int, input().split())))
phi_C = V(list(map(int, input().split())))

check_phi_C = V_pow(phi_A, n).pairwise_product(V_pow(phi_B, m))

if phi_C == check_phi_C:
    print(open('./flag.txt', 'r').read().strip())

solution

First of all, this challenge can be solved by simply sending 0 0 0, 1 1 1, or null. But I didn't come up with this during the competition! What a pity! So, I didn't solve this challenge. The official solution is a good challenge, though. It involves homomorphism and the using of Sage.

I personally have an issue with reading text, so every time I do Sage challenge, I translate them into more maths syntax. \[ \begin{aligned} p &= 55899879511190230528616866117179357211\\ V &: \mathbb{Z}_p^3\\ R &: R_p=\mathbb{Z}_p[x]\\ x &: \text{variate in } R_p\\ f &= x^3 + 36174005300402816514311230770140802253x^2 \\ &+ 35632245244482815363927956306821829684x \\ &+ 10704085182912790916669912997954900147\\ Q &:R_p/f \end{aligned} \] We are also given random \(A, B\in Q\), and \(C:=A^nB^m\), where random integers \(n,m \in [1,p)\).

The function V_pow(A, n) take exponent \(n\) and: \[ A = a_0+a_1x+a_2x^2, \] where \((a_1,a_2,a_3) \in \mathbb{Z}_p^3\) as inputs, then calculate \(A'= a_0^n+a_1^nx+a_2^nx^2\).

We are now asked to provide 3 vector phi_A, phi_B, phi_C, each of which contains 3 elements corresponding to coefficients in degree 3 polynomials. To obtain the flag, the condition is:

\[ \begin{aligned} \phi_A &= a_0+a_1x+a_2x^2, \;{\phi_A}'= a_0^n+a_1^nx+a_2^nx^2\\ \phi_B &= b_0+b_1x+b_2x^2, \;{\phi_B}'= b_0^n+b_1^nx+b_2^nx^2\\ \phi_C &= c_0+c_1x+c_2x^2\\ &= a_0'b_0' + a_1'b_1'x + a_2'b_2'x^2 \end{aligned} \] The point is,