Tahun ini, saya berkesempatan untuk membuat seluruh soal pada kategori Cryptography di kompetisi Cyber Jawara 2021. Berikut rangkuman soal yang telah saya buat:
- Qual
- shuvvler (300 points, 32 solves): Classic substitute and shift cipher
- RSASS (937 points, 9 solves): Common RSA modulus attack
- babynext (962 points, 7 solves): Dependent RSA primes (predictable $ p + q $)
- burve (981 points, 6 solves): Improper ECC private key generation
- gluckstag (1000 points, 1 solve): Improper AES-CFB implementation
- Final
- halftwin (699 points, 2 solves): Dependent RSA primes (share 50% LSB)
- anschlag (700 points, 1 solve): Zerologon Vulnerability in AES-CFB8
- sha256plus (700 points, 0 solves): Hash collision in custom hash function
Kali ini saya hanya akan menuliskan write-up sha256plus. Write-up seluruh soal Cryptography pada babak penyisihan dapat dilihat di sini (write-up tim Ainge CTF) dan editorial babak final dapat dilihat di sini.
sha256plus (700 points, 0 solves)
Termotivasi dari Bitcoin, Bob mencoba untuk mengembangkan hash function SHA256plus berbasis SHA256 yang nantinya digunakan untuk mekanisme PoW cryptocurrency miliknya. Karena Bob hanya mengenal dunia cryptocurrency dan tidak mempelajari basic cryptography, Bob butuh bantuanmu untuk melakukan pengecekan apakah hash function yang telah ia kembangkan sudah aman atau belum.
nc 178.128.96.125 33303
Author: deomkicer#3362
#!/usr/bin/env python3
import hashlib
import random
import re
import sys
class Unbuffered(object):
def __init__(self, stream):
self.stream = stream
def write(self, data):
self.stream.write(data)
self.stream.flush()
def writelines(self, datas):
self.stream.writelines(datas)
self.stream.flush()
def __getattr__(self, attr):
return getattr(self.stream, attr)
sys.stdout = Unbuffered(sys.stdout)
FLAG = re.findall(br'^CJ2021{(\w{40})}$', open('flag.txt', 'rb').read())[0]
def user_input(s):
inp = input(s).strip()
assert len(inp) < 256
return inp
def sha256plus(s):
res = 0
mod = 2**256
for i, c in enumerate(s.hex()):
res += pow(2021, i, 2069) * int.from_bytes(hashlib.sha256(c.encode()).digest(), 'big')
res %= mod
return int.to_bytes(res, 32, 'big')
def main():
print('Is there any collision on my hash function?')
m1 = user_input('Message #1: ').encode(); assert re.fullmatch(br'[\w]{0,10}', m1), '#$!@'
m2 = user_input('Message #2: ').encode(); assert re.fullmatch(br'[\w]{0,10}', m2), '#$!@'
if m1 != m2 and sha256plus(m1) == sha256plus(m2):
r = random.randrange(0, len(FLAG)-5, 5)
print(f'Oh no, you found the collision!')
print(f'Here take my flag(s): {sha256plus(FLAG[r:r+10]).hex()}')
else:
print('Ok, I guess it is secure enough.')
if __name__ == '__main__':
main()
TL;DR
- Mencari dua plainteks yang berbeda namun memiliki hash value yang sama (hash collision)
- Tiap plainteks dibatasi oleh regex (plainteks harus berupa word chars dan tidak lebih dari 10 chars)
- Plainteks diubah ke bentuk hex, lalu tiap karakter hex tersebut di-hash menggunakan SHA256 dan dikalikan dengan konstanta dari $ 2021^i $ modulo $ 2069 $
- Perhitungan di atas dijumlahkan dan di-modulo $ 2^{256} $
- Hanya potongan 10 random bytes flag yang di-hash, sehingga perlu melakukan beberapa kali koneksi ke servis yang diberikan
Part 1: Find hash collision
Panjang plainteks dibatasi maksimal 10 karakter. Ketika plainteks memiliki panjang 10 karakter, maka konstanta pengalinya adalah $ 2021^i $ modulo $ 2069 $ untuk $ i={0,…,19} $.
>>> [pow(2021, i, 2069) for i in range(20)]
[1, 2021, 235, 1134, 1431, 1658, 1107, 658, 1520, 1524, 1332, 203, 601, 118, 543, 833, 1396, 1269, 1158, 279]
Untuk membentuk hash collision, kita perlu mencari suatu elemen pada list di atas yang merupakan penjumlahan dari dua atau lebih elemen lainnya. Berikut kodenya.
def cari_subsets(s, a):
result = []
def cari(target, arr, backpack=[]):
if arr: # arr tidak kosong
if arr[-1] == target:
tmp = backpack + [arr[-1]]
result.append(tmp)
elif arr[-1] < target:
cari(target - arr[-1], arr[:-1], backpack + [arr[-1]])
cari(target, arr[:-1], backpack)
cari(s, sorted(a))
return result
potongan = 10
a = [pow(2021, i, 2069) for i in range(potongan*2)]
for s in a:
print(s, cari_subsets(s, a))
1 [[1]]
2021 [[2021]]
235 [[235]]
1134 [[1134]]
1431 [[1431]]
1658 [[1658], [601, 543, 279, 235]]
1107 [[1107]]
658 [[658]]
1520 [[1520]]
1524 [[1524]]
1332 [[1332]]
203 [[203]]
601 [[601], [279, 203, 118, 1]]
118 [[118]]
543 [[543]]
833 [[833]]
1396 [[1396]]
1269 [[1269]]
1158 [[1158], [601, 235, 203, 118, 1]]
279 [[279]]
- 1658 = 601 + 543 + 279 + 235
- 601 = 279 + 203 + 118 + 1
- 1158 = 601 + 235 + 203 + 118 + 1
Terdapat 3 solusi pada kasus di atas. Kita akan menggunakan solusi pertama sebagai pembentukan plainteks, dimana angka 1658 untuk membentuk plainteks pertama dan angka 601 + 543 + 279 + 235 untuk plainteks kedua.
import re
potongan = 10
a = [pow(2021, i, 2069) for i in range(potongan*2)]
charset = '0123456789abcdef'
b1 = ''.join(['1' if i == 1658 else '0' for i in a])
b2 = ''.join(['1' if i in [601, 543, 279, 235] else '0' for i in a])
for i in charset:
for j in charset:
t1 = b1.replace('0', i).replace('1', j)
t2 = b2.replace('0', i).replace('1', j)
m1 = bytes.fromhex(t1)
m2 = bytes.fromhex(t2)
if re.fullmatch(br'[\w]{0,10}', m1) and re.fullmatch(br'[\w]{0,10}', m2) and m1 != m2:
print(m1.decode())
print(m2.decode())
exit()
3343333333
3C3333CC34
$ nc 178.128.96.165 33303
Is there any collision on my hash function?
Message #1: 3343333333
Message #2: 3C3333CC34
Oh no, you found the collision!
Here take my flag(s): 2aaaf3169ed22072b7a32e2470c800142893bda1e2ed7a1d88f920d515b35ed6
Part 2: Reverse target hash
Notasikan fungsi hash SHA256 sebagai $ H $ dan target hash sebagai $ T $. Idenya, kita akan membuat matrix berukuran 18x18 yang berisikan elemen-elemen berikut:
\[\begin{bmatrix} 1 & 0 & 0 & \cdots & 0 & H(\textbf{0}) \\ 0 & 1 & 0 & & 0 & H(\textbf{1}) \\ 0 & 0 & 1 & & 0 & H(\textbf{2}) \\ \vdots & & & \ddots & & \\ 0 & 0 & 0 & 0 & 1 & -2^{256} \\ 0 & 0 & 0 & 0 & 0 & -T \end{bmatrix}\]Dengan harapan, LLL mengembalikan nilai weight tiap masing-masing elemen solusi dari subset sum. Namun kita perlu mengurangi elemen yang redundant karena nilai weight pada kasus ini tidak hanya bernilai 0 atau 1 seperti pada knapsack problem. Kita akan mengurangi satu elemen redundant pada matrix, sehingga matrix yang akan kita bentuk adalah matrix berukuran 17x17.
Proving redundant element exists
Ingat, flag merupakan word chars.
import random
charset = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz'
test = random.choices(charset, k=1000)
test = ''.join(test).encode()
a = [test[i:i+10] for i in range(0, len(test), 10)]
b = [len(set(x.hex())) for x in a]
print(b)
print(f'min: {min(b)}')
print(f'max: {max(b)}')
potongan = 10
print([pow(2021, i, 2069) for i in range(potongan*2)])
[9, 9, 10, 7, 10, 9, 9, 8, 11, 11, 9, 9, 9, 13, 9, 11, 9, 11, 9, 9, 8, 10, 9, 8, 7, 10, 8, 9, 10, 8, 11, 11, 7, 9, 9, 10, 6, 9, 9, 10, 9, 10, 9, 9, 8, 11, 10, 9, 10, 10, 10, 10, 9, 8, 11, 9, 10, 10, 8, 11, 9, 10, 10, 9, 11, 8, 10, 9, 7, 8, 10, 10, 10, 8, 8, 12, 9, 8, 9, 14, 8, 9, 9, 10, 11, 10, 11, 9, 9, 7, 11, 9, 9, 9, 11, 10, 11, 11, 8, 9]
min: 6
max: 14
[1, 2021, 235, 1134, 1431, 1658, 1107, 658, 1520, 1524, 1332, 203, 601, 118, 543, 833, 1396, 1269, 1158, 279]
Nilai max adalah 14, bukan 16. Dapat disimpulkan, dalam sebagai besar kasus, setidaknya terdapat dua elemen yang redundant pada matrix berukuran 18x18.
Finding complete subset
Setelah berhasil mendapatkan weight dari tiap elemen, kita juga perlu menyusun plainteks yang cocok dari himpunan weight tersebut. Pada kasus ini, saya menghitung product terhadap beberapa subset, lalu memastikan tidak ada suatu elemen yang digunakan lebih dari satu kali pada complete subset.
Implementation
#!/usr/bin/sage
from Crypto.Hash import SHA256
from functools import reduce
from itertools import combinations, product
import os, time
t0 = time.time()
sha256 = lambda s: SHA256.new(s.encode()).digest()
charsets = list(combinations('0123456789abcdef', 15))
dicc = {}
potongan = 10
message_1 = '3343333333'
message_2 = '3C3333CC34'
cmd = f'printf "{message_1}\n{message_2}\n" | ./server.py | tail -n 1 | cut -d " " -f 5'
# cmd = cmd.replace('./server.py', 'nc localhost 33303')
cmd = cmd.replace('./server.py', 'nc 178.128.96.165 33303')
################################################################
while len(dicc.keys()) != 7:
hashnya = os.popen(cmd).read().strip()
if hashnya in dicc.keys(): continue
s = Integer(hashnya, 16)
found = False
for charset in charsets:
a = [int.from_bytes(sha256(i), 'big') for i in charset] + [-1 * 2^256]
n = len(a)
################################################################
b = []
for i in range(n):
vec = [0 for _ in range(n + 1)]
vec[i] = 1
vec[-1] = a[i]
b.append(vec)
b.append([0 for _ in range(n)] + [-s])
B = matrix(ZZ, b)
################################################################
res = B.LLL()
for e in res:
e = list(e)
if e[-1] == 0 and e.count(0) >= 2 and all(x >= 0 for x in e):
dicc[hashnya] = [''.join(charset), e]
print(f'{len(dicc.keys())}: {hashnya[:8]}...{hashnya[-8:]} -> {dicc[hashnya]}')
found = True
break
if found: break
################################################################
def cari_depan(flags):
depan = []
for kiri in flags:
if all(kiri[:5] != kanan[-5:] for kanan in flags):
depan.append(kiri)
if len(depan) == 1:
return depan[0]
else:
return False
def susun_flag(flags, target=40):
kiri = cari_depan(flags)
flag = kiri
while len(flag) != target:
for kanan in flags:
if kiri[-5:] == kanan[:5]:
flag += kanan[5:]
kiri = kanan
break
return flag
def cari_subsets(s, a):
result = []
def cari(target, arr, backpack=[]):
if arr: # arr tidak kosong
if arr[-1] == target:
tmp = backpack + [arr[-1]]
result.append(tmp)
elif arr[-1] < target:
cari(target - arr[-1], arr[:-1], backpack + [arr[-1]])
cari(target, arr[:-1], backpack)
cari(s, sorted(a))
return result
def cari_complete_subset(kamus):
result = []
box = []
for key in kamus.keys():
box.append(kamus[key])
produc = list(product(*box))
for produ in produc:
t1 = reduce(lambda a, b: a + b, produ)
if len(set(t1)) == len(t1):
result.append(produ)
return result
################################################################
box = []
for hashnya in dicc.keys():
charset, arr = dicc[hashnya]
arr = arr[:-2] # 2 paling belakang itu weight dari 2^256 dan hash valuenya
naon = [Integer(pow(2021, i, 2069)) for i in range(potongan*2)]
ssss = {i: cari_subsets(i, naon) for i in arr if i}
cccc = cari_complete_subset(ssss)
box.append([])
for ccc in cccc:
res = ['_' for _ in range(potongan*2)]
for cc in ccc:
total = sum(cc)
char = charset[arr.index(total)]
for c in cc:
idx = naon.index(c)
res[idx] = char
res = ''.join(res)
res = bytes.fromhex(res)
box[-1].append(res)
print([len(bo) for bo in box])
probox = list(product(*box))
for v in probox:
tmp = cari_depan(v)
if tmp:
flags = [i.decode() for i in v]
flag = 'CJ2021{' + susun_flag(flags) + '}'
print(f'flag = {flag}')
print(f'time = {time.time()-t0} seconds')
$ sage solve.sage
1: 6306d8b2...331c887e -> ['0123456789abcdf', [0, 0, 0, 1134, 6380, 6733, 1158, 1, 279, 0, 0, 0, 1845, 0, 1491, 10158, 0]]
2: a594946b...69744c53 -> ['0123456789abdef', [0, 0, 0, 1134, 0, 3754, 6534, 1672, 0, 0, 0, 0, 658, 118, 5151, 11404, 0]]
3: aa4dbd37...0cd45768 -> ['0123456789abcdf', [0, 279, 0, 118, 894, 4951, 5406, 0, 1524, 203, 0, 0, 3155, 0, 2491, 11158, 0]]
4: 2aaaf316...15b35ed6 -> ['0123456789abcdf', [0, 0, 1658, 1883, 1525, 1846, 4528, 2121, 0, 2021, 0, 0, 0, 1269, 2170, 9865, 0]]
5: 50588764...4775b367 -> ['0123456789abcdf', [0, 2792, 0, 1784, 1991, 3850, 1521, 1332, 0, 2021, 1524, 0, 279, 0, 1927, 9642, 0]]
6: 9650b408...11db443d -> ['0123456789abcdf', [0, 2357, 279, 3674, 118, 2324, 5321, 0, 1269, 2021, 0, 0, 0, 0, 1658, 10029, 0]]
7: c2f04f2c...4730b007 -> ['0123456789abcef', [0, 951, 0, 1144, 0, 4161, 4157, 3044, 0, 203, 279, 0, 0, 1134, 3948, 10936, 0]]
[1, 1, 1, 1, 1, 1, 1]
flag = CJ2021{I_b3t_someone_wi11_juST_LLL_ThiS_eaf418b}
time = 4.9704320430755615 seconds
Flag
CJ2021{I_b3t_someone_wi11_juST_LLL_ThiS_eaf418b}
Flagnya terinspirasi dari Dragon CTF 2021: CRC Recursive Challenge
