This year, I had the opportunity to create all cryptography challenges for Cyber Jawara 2021 competition. Here’s a summary of the challenges I created:
- 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
This writeup only contains the solution for sha256plus. You can find writeups for all the cryptography challenges from the qual round here (by team Ainge CTF) and the final round editorial here.
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
- Find two different plaintexts that produce the same hash value (hash collision)
- Each plaintext is limited by regex (must be word chars and no more than 10 chars)
- Plaintext is converted to hex, then each hex character is hashed using SHA256 and multiplied by a constant from $ 2021^i $ modulo $ 2069 $
- The above calculation is summed and taken modulo $ 2^{256} $
- Only a random 10-byte chunk of the flag is hashed, so we need to connect to the service multiple times
Part 1: Find hash collision
The plaintext length is limited to 10 characters. When the plaintext is 10 characters long, the multiplier constant is $ 2021^i $ modulo $ 2069 $ for $ 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]
To form a hash collision, we need to find an element in the list above that is the sum of two or more other elements. Here’s the code.
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
There are 3 solutions in the above case. We’ll use the first solution to form our plaintexts, where 1658 is used for the first plaintext and 601 + 543 + 279 + 235 for the second plaintext.
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
Let’s denote the SHA256 hash function as $ H $ and the target hash as $ T $. The idea is to create an 18x18 matrix containing the following elements:
\[\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}\]We hope that LLL will return the weight values for each element in the subset sum solution. However, we need to reduce redundant elements because the weight values in this case are not just 0 or 1 like in the usual or common knapsack problem. We’ll reduce one redundant element from the matrix, so the matrix we’ll form will be 17x17.
Proving redundant element exists
Remember, the flag consists of 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]
The max value is 14, not 16. We can conclude that in most cases, there are at least two redundant elements in the 18x18 matrix.
Finding complete subset
After successfully getting the weights for each element, we also need to arrange the plaintext that matches the set of weights. In this case, I calculated the product against several subsets, then made sure no element was used more than once in the 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}
The flag was inspired by Dragon CTF 2021: CRC Recursive Challenge
