CryptoCTF adalah event CTF tahunan yang diorganisir oleh ASIS sejak 2019 lalu, CTF ini hanya berfokus pada permasalahan kriptografi. Tahun ini, CryptoCTF diselenggarakan pada 30-31 Juli 2021, berformat Jeopardy dengan durasi kompetisi 24 jam.
Tulisan kali ini akan membahas solusi dari beberapa challenge berikut:
- Mic Check (warm-up)
- Farm (easy): Finite Field
- KeyBase (easy): Block chaining untuk recover IV pada AES-CBC
- Symbols (easy): LaTeX
- Hamul (easy-medium): Dependent primes pada kriptosistem RSA
- Rima (easy-medium): Bit manipulation
- Tuti (medium): Diopantine equations
- Ferman (medium): Brahmagupta-Fibonacci identity
- Salt and Pepper (medium): Hash length extension attack
- Wolf (medium-hard): Improper nonce implementation pada AES-GCM
Mic Check
Flag terdapat pada halaman rules CryptoCTF.
CCTF{W3lc0me_t0_The_0ne_&_0nly_Crypt0_CTF_Mad3ـw1th_L0ve_f0r_Crypt0!}
Farm
Diberikan attachment farm.sage dan enc.txt.
#!/usr/bin/env sage
from sage.all import *
import string, base64, math
from flag import flag
ALPHABET = string.printable[:62] + '\\='
F = list(GF(64))
def keygen(l):
key = [F[randint(1, 63)] for _ in range(l)]
key = math.prod(key) # Optimization the key length :D
return key
def maptofarm(c):
assert c in ALPHABET
return F[ALPHABET.index(c)]
def encrypt(msg, key):
m64 = base64.b64encode(msg)
enc, pkey = '', key**5 + key**3 + key**2 + 1
for m in m64:
enc += ALPHABET[F.index(pkey * maptofarm(chr(m)))]
return enc
# KEEP IT SECRET
key = keygen(14) # I think 64**14 > 2**64 is not brute-forcible :P
enc = encrypt(flag, key)
print(f'enc = {enc}')
enc = 805c9GMYuD5RefTmabUNfS9N9YrkwbAbdZE0df91uCEytcoy9FDSbZ8Ay8jj
Solution
Pada fungsi keygen, key di-generate dari perkalian 14 angka random yang berada pada rentang angka 1-63, sehingga key yang dihasilkan akan berukuran 84-bit. Proses enkripsi cukup unik, indeks tiap karakter pada plainteks akan dikalikan dengan key, yang nantinya indeks hasil perkalian akan digunakan untuk mengambil karakter pada ALPHABET sebagai cipherteks. Karena hasil perkalian berada di Finite Field berukuran $ 2^{6} $, otomatis key yang digunakan pada tahap enkripsi menjadi memungkinkan untuk di-bruteforce.
Implementation
#!/usr/bin/env sage
import string, base64
ALPHABET = string.printable[:62] + '\\='
target = '805c9GMYuD5RefTmabUNfS9N9YrkwbAbdZE0df91uCEytcoy9FDSbZ8Ay8jj'
F = list(GF(64))
def maptofarm(c):
assert c in ALPHABET
return F[ALPHABET.index(c)]
def encrypt(msg, key):
m64 = msg
enc, pkey = '', key**5 + key**3 + key**2 + 1
for m in m64:
enc += ALPHABET[F.index(pkey * maptofarm(chr(m)))]
return enc
flag = base64.b64encode(b'CCT') # format flag
for key in F:
enc = encrypt(flag, key)
if enc == target[:len(enc)]:
break
print(f'{key = }')
found = True
while found:
found = False
for c1 in ALPHABET:
tmp = c1
test = flag + tmp.encode()
enc = encrypt(test, key)
if enc == target[:len(enc)]:
flag += tmp.encode()
found = True
break
flag = base64.b64decode(flag).decode()
print(f'{flag = }')
$ sage solve.sage
key = z6^5 + 1
flag = 'CCTF{EnCrYp7I0n_4nD_5u8STitUtIn9_iN_Fi3Ld!}'
KeyBase
Diberikan attachment keybase.py dan servis ke 01.cr.yp.toc.tf 17010.
#!/usr/bin/env python3
from Crypto.Util import number
from Crypto.Cipher import AES
import os, sys, random
from flag import flag
def keygen():
iv, key = [os.urandom(16) for _ in '01']
return iv, key
def encrypt(msg, iv, key):
aes = AES.new(key, AES.MODE_CBC, iv)
return aes.encrypt(msg)
def decrypt(enc, iv, key):
aes = AES.new(key, AES.MODE_CBC, iv)
return aes.decrypt(enc)
def die(*args):
pr(*args)
quit()
def pr(*args):
s = " ".join(map(str, args))
sys.stdout.write(s + "\n")
sys.stdout.flush()
def sc():
return sys.stdin.readline().strip()
def main():
border = "+"
pr(border*72)
pr(border, " hi all, welcome to the simple KEYBASE cryptography task, try to ", border)
pr(border, " decrypt the encrypted message and get the flag as a nice prize! ", border)
pr(border*72)
iv, key = keygen()
flag_enc = encrypt(flag, iv, key).hex()
while True:
pr("| Options: \n|\t[G]et the encrypted flag \n|\t[T]est the encryption \n|\t[Q]uit")
ans = sc().lower()
if ans == 'g':
pr("| encrypt(flag) =", flag_enc)
elif ans == 't':
pr("| Please send your 32 bytes message to encrypt: ")
msg_inp = sc()
if len(msg_inp) == 32:
enc = encrypt(msg_inp, iv, key).hex()
r = random.randint(0, 4)
s = 4 - r
mask_key = key[:-2].hex() + '*' * 4
mask_enc = enc[:r] + '*' * 28 + enc[32-s:]
pr("| enc =", mask_enc)
pr("| key =", mask_key)
else:
die("| SEND 32 BYTES MESSAGE :X")
elif ans == 'q':
die("Quitting ...")
else:
die("Bye ...")
if __name__ == '__main__':
main()
Solution
Kode program memberikan 3 opsi yang dapat dipilih oleh user:
- Get the encrypted flag
- Test the encryption
- Quit
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+ hi all, welcome to the simple KEYBASE cryptography task, try to +
+ decrypt the encrypted message and get the flag as a nice prize! +
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
| Options:
| [G]et the encrypted flag
| [T]est the encryption
| [Q]uit
g
| encrypt(flag) = 438e77d6479cfa357e3fc58fde48028f2dd0bbc5dc2f126db0cb1daf6cd9dd91
| Options:
| [G]et the encrypted flag
| [T]est the encryption
| [Q]uit
t
| Please send your 32 bytes message to encrypt:
00000000000000000000000000000000
| enc = 5f38****************************a71c747cd176a8f66ba5ab69a4cfbadf
| key = 267a269a56464842b12133ae5ca4****
| Options:
| [G]et the encrypted flag
| [T]est the encryption
| [Q]uit
ENCRYPTED_FLAG = '438e77d6479cfa357e3fc58fde48028f2dd0bbc5dc2f126db0cb1daf6cd9dd91'.decode('hex')
ENCRYPTED_ZERO = ['5f38'.decode('hex'), 'a71c747cd176a8f66ba5ab69a4cfbadf'.decode('hex')]
KNOWN_14_KEY = '267a269a56464842b12133ae5ca4'.decode('hex')
Pada pilihan ke-2, kita bisa memasukkan arbitrary plainteks namun dibatasi hanya sebanyak 2 blocks (32 bytes). Program akan menampilkan output yang terdiri dari:
- Cipherteks, namun ~14 bytes pada block pertama hilang
- Key, namun 2 bytes terakhir hilang
Meskipun demikian, 2 bytes yang hilang pada key dapat di-bruteforce dengan membandingkan pasangan plainteks-cipherteks yang kita inputkan. Idenya, asumsikan 2 blocks cipherteks yang kita peroleh menjadi IV dan 1 block cipherteks. Hal ini dapat dilakukan karena peran IV pada CBC Mode Decryption hanya digunakan untuk xor intermediate state sebelum menjadi plainteks.
Ingat! $ \mathrm{chr}(\mathrm{0x30}) = $ "0".
keys = []
for i in range(256):
for j in range(256):
tmp_key = KNOWN_14_KEY + chr(i) + chr(j)
aes = AES.new(tmp_key, AES.MODE_CBC, tmp_iv)
dec = aes.decrypt(enc)
if dec[:2] == '0'*2:
keys.append(tmp_key)
for key in keys:
aes = AES.new(key, AES.MODE_CBC, ENCRYPTED_FLAG[:16])
res = aes.decrypt(ENCRYPTED_FLAG[16:])
if all(x in string.printable for x in res):
print('key: {}'.format(key.encode('hex')))
break
$ python solve.py
key: 267a269a56464842b12133ae5ca44d52
Setelah didapat nilai key, tugas selanjutnya yaitu mencari nilai IV. Kita tahu plainteks yang kita inputkan merupakan "0"*32, sehingga "0" dapat digunakan untuk mengisi kekosongan bytes pada block pertama pada cipherteks. Hal ini dapat dilakukan karena xor yang bersifat reversible.
Kita akan dekrip block kedua menggunakan block pertama sebagai IV. Sebanyak 14 bytes terakhir dari hasil dekripsi merupakan 14 bytes yang hilang dari block pertama. Untuk recover IV yang asli, kita bisa dekrip block pertama (yang telah diperoleh secara menyeluruh) menggunakan null bytes sebagai IV, kemudian xor dengan block pertama plainteks. Dengan demikian, IV asli akan berhasil didapatkan.
Implementation
#!/usr/bin/python
from Crypto.Cipher import AES
from pwn import xor
import string
'''
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+ hi all, welcome to the simple KEYBASE cryptography task, try to +
+ decrypt the encrypted message and get the flag as a nice prize! +
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
| Options:
| [G]et the encrypted flag
| [T]est the encryption
| [Q]uit
g
| encrypt(flag) = 438e77d6479cfa357e3fc58fde48028f2dd0bbc5dc2f126db0cb1daf6cd9dd91
| Options:
| [G]et the encrypted flag
| [T]est the encryption
| [Q]uit
t
| Please send your 32 bytes message to encrypt:
00000000000000000000000000000000
| enc = 5f38****************************a71c747cd176a8f66ba5ab69a4cfbadf
| key = 267a269a56464842b12133ae5ca4****
| Options:
| [G]et the encrypted flag
| [T]est the encryption
| [Q]uit
'''
ENCRYPTED_FLAG = '438e77d6479cfa357e3fc58fde48028f2dd0bbc5dc2f126db0cb1daf6cd9dd91'.decode('hex')
ENCRYPTED_ZERO = ['5f38'.decode('hex'), 'a71c747cd176a8f66ba5ab69a4cfbadf'.decode('hex')]
KNOWN_14_KEY = '267a269a56464842b12133ae5ca4'.decode('hex')
tmp_iv = ENCRYPTED_ZERO[0] + '0'*14
enc = ENCRYPTED_ZERO[1]
keys = []
for i in range(256):
for j in range(256):
tmp_key = KNOWN_14_KEY + chr(i) + chr(j)
aes = AES.new(tmp_key, AES.MODE_CBC, tmp_iv)
dec = aes.decrypt(enc)
if dec[:2] == '0'*2:
keys.append(tmp_key)
for key in keys:
aes = AES.new(key, AES.MODE_CBC, ENCRYPTED_FLAG[:16])
res = aes.decrypt(ENCRYPTED_FLAG[16:])
if all(x in string.printable for x in res):
print('key: {}'.format(key.encode('hex')))
break
tmp_iv = ENCRYPTED_ZERO[0] + '0'*14
aes = AES.new(key, AES.MODE_CBC, tmp_iv)
dec = aes.decrypt(ENCRYPTED_ZERO[1])
ENCRYPTED_ZERO[0] = ENCRYPTED_ZERO[0] + dec[2:]
aes = AES.new(key, AES.MODE_CBC, '\x00'*16)
dec = aes.decrypt(ENCRYPTED_ZERO[0])
iv = xor(dec, '0')
print('IV: {}'.format(iv.encode('hex')))
aes = AES.new(key, AES.MODE_CBC, iv)
flag = aes.decrypt(ENCRYPTED_FLAG)
print('flag: {}'.format(flag))
$ python solve.py
key: 267a269a56464842b12133ae5ca44d52
IV: 9375156770ac1db95257cc1188d02055
flag: CCTF{h0W_R3cOVER_7He_5eCrET_1V?}
Symbols
Peserta hanya diberikan file gambar, dimana terdapat beberapa simbol matematika yang dibuat menggunakan LaTeX.
Solution
Kita dapat mencari tahu sintaks LaTeX seperti apa yang persis menampilkan seperti gambar tersebut. Setelah mencari beberapa dokumentasi mengenai LaTeX, didapati gambar tersebut dibuat menggunakan sintaks sebagai berikut.
Flag merupakan huruf pertama sintaks dari masing-masing simbol.
CCTF{Play_with_LaTeX}
Hamul
Diberikan attachment hamul.py dan output.txt.
#!/usr/bin/env python3
from Crypto.Util.number import *
from flag import flag
nbit = 64
while True:
p, q = getPrime(nbit), getPrime(nbit)
P = int(str(p) + str(q))
Q = int(str(q) + str(p))
PP = int(str(P) + str(Q))
QQ = int(str(Q) + str(P))
if isPrime(PP) and isPrime(QQ):
break
n = PP * QQ
m = bytes_to_long(flag.encode('utf-8'))
if m < n:
c = pow(m, 65537, n)
print('n =', n)
print('c =', c)
n = 98027132963374134222724984677805364225505454302688777506193468362969111927940238887522916586024601699661401871147674624868439577416387122924526713690754043
c = 42066148309824022259115963832631631482979698275547113127526245628391950322648581438233116362337008919903556068981108710136599590349195987128718867420453399
Solution
Inti dari challenge ini berada pada pembangkitan kedua bilangan prima yang digunakan oleh RSA. Pembentukan bilangan prima tersebut diilustrasikan sebagai berikut.
misal A,B,C,D,E,F,G,H,I,J,K,L merepresentasikan digit angka
p = ABCDEF -> P = ABCDEFGHIJKL -> PP = ABCDEFGHIJKLGHIJKLABCDEF
q = GHIJKL -> Q = GHIJKLABCDEF -> QQ = GHIJKLABCDEFABCDEFGHIJKL
Secara garis besar, solusi dari challenge ini tidak berbeda jauh dari Midnight Sun CTF 2019 Qual: open-gyckel-crypto dan S4CTF 2021: Baby RSA. Namun pada challenge ini, kita tidak tahu pasti jumlah digit pada basis 10 yang terdapat pada variabel $ p $ dan $ q $ (antara 19-20).
Solusi yang saya gunakan adalah dengan menebak jumlah digit variabel $ p $ dan $ q $. Mengingat bruteforce space sangat kecil, hal ini dapat menjadi solusi cepat meskipun terdapat banyak variabel yang tidak diketahui dalam implementasinya.
Implementation
#!/usr/bin/env python3
from gmpy2 import *
c = 42066148309824022259115963832631631482979698275547113127526245628391950322648581438233116362337008919903556068981108710136599590349195987128718867420453399
e = 65537
n = 98027132963374134222724984677805364225505454302688777506193468362969111927940238887522916586024601699661401871147674624868439577416387122924526713690754043
pq = n
def find():
for i in range(16):
for a1 in range(38, 43):
for a2 in range(38, 43):
for a3 in range(38, 43):
for a4 in range(38, 43):
for a5 in range(70, 90):
ab = (int(str(pq)[:a1]) - i) * 10**a2 + int(str(pq)[-a3:])
a2_p_b2 = (pq - ab * 10**a5 - ab) // 10**a4
try:
a_p_b, ok = iroot(a2_p_b2 + 2 * ab, 2)
if ok:
return int(a_p_b)
except:
continue
a_p_b = find()
for i in range(256):
p_p_q = a_p_b * 10 ** i + a_p_b
phi = n+1 - p_p_q
d = invert(e, phi)
m = pow(c, d, n)
flag = int.to_bytes(int(m), 72, 'big')
if b'CCTF' in flag:
print(flag.strip(b'\x00').decode())
$ python3 solve.py
CCTF{wH3Re_0Ur_Br41N_Iz_5uP3R_4CtIVe_bY_RSA!!}
Rima
Diberikan 3 attachment yang terdiri dari:
- Kode program
rima.py - Output program
g.enc - Output program
h.enc
#!/usr/bin/env python
from Crypto.Util.number import *
from flag import FLAG
def nextPrime(n):
while True:
n += (n % 2) + 1
if isPrime(n):
return n
f = [int(x) for x in bin(int(FLAG.hex(), 16))[2:]]
f.insert(0, 0)
for i in range(len(f)-1): f[i] += f[i+1]
a = nextPrime(len(f))
b = nextPrime(a)
g, h = [[_ for i in range(x) for _ in f] for x in [a, b]]
c = nextPrime(len(f) >> 2)
for _ in [g, h]:
for __ in range(c): _.insert(0, 0)
for i in range(len(_) - c): _[i] += _[i+c]
g, h = [int(''.join([str(_) for _ in __]), 5) for __ in [g, h]]
for _ in [g, h]:
if _ == g:
fname = 'g'
else:
fname = 'h'
of = open(f'{fname}.enc', 'wb')
of.write(long_to_bytes(_))
of.close()
Solution
Untuk menyelesaikan challenge ini, saya me-reverse urutan kode program dari bawah ke atas untuk mengembalikan flag. Pertama-tama, kita perlu mencari tahu panjang list variabel $ f $. Saya membandingkan panjang output dari g.enc dan h.enc ke nilai $ f $ yang dicari.
from deom import *
gg = open('g.enc', 'rb').read()
hh = open('h.enc', 'rb').read()
gg = digits(int.from_bytes(gg, 'big'), 5)
hh = digits(int.from_bytes(hh, 'big'), 5)
print(len(gg))
print(len(hh))
for f in range(0, 512, 8):
a = next_prime(f)
b = next_prime(a)
g = f * a
h = f * b
c = next_prime(f >> 2)
if g + c == len(gg) and h + c == len(hh):
print(f, g+c, h+c)
break
$ python3 solve.py
65859
67395
256 65859 67395
Didapat nilai $ f $ yang tepat adalah 256, sehingga dapat disimpulkan panjang flag adalah $ \frac{256}{8} = 32 $ karakter.
Implementation
#!/usr/bin/env python3
from deom import *
gg = open('g.enc', 'rb').read()
hh = open('h.enc', 'rb').read()
gg = digits(int.from_bytes(gg, 'big'), 5)
hh = digits(int.from_bytes(hh, 'big'), 5)
print(len(gg))
print(len(hh))
# for f in range(0, 512, 8):
# a = next_prime(f)
# b = next_prime(a)
# g = f * a
# h = f * b
# c = next_prime(f >> 2)
# if g + c == len(gg) and h + c == len(hh):
# print(f, g+c, h+c)
# break
f = 256
c = next_prime(f >> 2)
gg = list(map(int, gg))
hh = list(map(int, hh))
for i in range(len(gg)-c-1, -1, -1):
gg[i] = gg[i] - gg[i+c]
for i in range(len(hh)-c-1, -1, -1):
hh[i] = hh[i] - hh[i+c]
gg = gg[c:]
hh = hh[c:]
gg = gg[:f]
hh = hh[:f]
for i in range(f-1-1, -1, -1):
gg[i] = gg[i] - gg[i+1]
res = ''.join(str(x) for x in gg)
flag = int.to_bytes(int(res, 2), 32, 'big').decode()
print(flag)
$ python3 solve.py
65859
67395
CCTF{_how_finD_7h1s_1z_s3cr3T?!}
Tuti
Kita hanya diberikan kode program tuti.py.
#!/usr/bin/env python3
from Crypto.Util.number import *
from flag import flag
l = len(flag)
m_1, m_2 = flag[: l // 2], flag[l // 2:]
x, y = bytes_to_long(m_1), bytes_to_long(m_2)
k = '''
000bfdc32162934ad6a054b4b3db8578674e27a165113f8ed018cbe9112
4fbd63144ab6923d107eee2bc0712fcbdb50d96fdf04dd1ba1b69cb1efe
71af7ca08ddc7cc2d3dfb9080ae56861d952e8d5ec0ba0d3dfdf2d12764
'''.replace('\n', '')
assert((x**2 + 1)*(y**2 + 1) - 2*(x - y)*(x*y - 1) == 4*(int(k, 16) + x*y))
Solution
Idenya, kita harus menemukan nilai $ x $ dan $ y $ yang memenuhi persamaan di atas.
- $ (x^{2} + 1) (y^{2} + 1) - 2(x - y) (xy - 1) = 4(k + xy) $
- $ x^{2} y^{2} + x^{2} + y^{2} + 1 - 2(x^{2}y - x - xy^{2} + y) = 4(k + xy) $
- $ x^{2} y^{2} + x^{2} + y^{2} + 1 - 2x^{2}y + 2x + 2xy^{2} - 2y = 4k + 4xy $
Pada tahap ini, asumsikan $ u = y^{2} $ agar mempermudah penyederhanaan persamaan.
- $ ux^{2} + x^{2} + u + 1 - 2x^{2}y + 2x + 2ux - 2y = 4k + 4xy $
- $ ux^{2} + 2ux + u + x^{2} + 2x + 1 - 2x^{2}y - 2y = 4k + 4xy $
- $ (ux + u)(x + 1) + (x + 1)(x + 1) - 2x^{2}y - 2y = 4k + 4xy $
- $ (ux + u)(x + 1) + (x + 1)(x + 1) - 2x^{2}y - 2y - 4xy = 4k $
- $ u(x + 1)(x + 1) + (x + 1)(x + 1) - 2x^{2}y - 2y - 4xy = 4k $
Substitusi kembali $ y^{2} $ ke $ u $.
- $ y^{2}(x + 1)(x + 1) + (x + 1)(x + 1) - 2x^{2}y - 2y - 4xy = 4k $
- $ y^{2}(x + 1)^{2} + (x + 1)^{2} - 2x^{2}y - 2y - 4xy = 4k $
- $ (y^{2} + 1)(x + 1)^{2} - 2x^{2}y - 2y - 4xy = 4k $
- $ (y^{2} + 1)(x + 1)^{2} - 2y (x^{2} + 2x + 1) = 4k $
- $ (y^{2} + 1)(x + 1)^{2} - 2y (x + 1)^{2} = 4k $
- $ (y^{2} - 2y + 1)(x + 1)^{2} = 4k $
- $ (y - 1)^{2}(x + 1)^{2} = 4k $
- $ \sqrt{(y - 1)^{2}(x + 1)^{2}} = \sqrt{2^{2}k} $
- $ (y - 1)(x + 1) = 2 \sqrt{k} $
Dapat disimpulkan bahwa $ 2 \sqrt{k} $ merupakan perkalian antara $ y-1 $ dan $ x+1 $. Dengan memanfaatkan fungsi divisors yang terdapat pada modul sage.arith.misc, kita dapat mencari nilai $ y-1 $ dan $ x+1 $ yang memenuhi persamaan.
Implementation
from Crypto.Util.number import *
from gmpy2 import *
from sage.all import *
k = '''
000bfdc32162934ad6a054b4b3db8578674e27a165113f8ed018cbe9112
4fbd63144ab6923d107eee2bc0712fcbdb50d96fdf04dd1ba1b69cb1efe
71af7ca08ddc7cc2d3dfb9080ae56861d952e8d5ec0ba0d3dfdf2d12764
'''.replace('\n', '')
k = iroot(int(k, 16), 2)
assert k[1]
k = int(k[0]) * 2
print(k)
ks = divisors(k)
print(len(ks))
# (y-1)*(x+1) == 2*sqrt(k)
isPrintable = lambda x: all(i >= 0x20 and i < 0x7f for i in x)
for tmp in ks:
a = tmp - 1
if not a: continue
b = k // tmp + 1
x = long_to_bytes(a)
y = long_to_bytes(b)
if isPrintable(x) and isPrintable(y):
flag = x+y
if flag.startswith(b'CCTF{'):
print(flag.decode())
$ sage -python solve.py
992752253935874779143952218845275961347009322164731344882417010624071055636710540798045985678351986133612
9216
CCTF{S1mPL3_4Nd_N!cE_Diophantine_EqUa7I0nS!}
Ferman
Diberikan servis ke 07.cr.yp.toc.tf 22010 tanpa adanya file attachment pada challenge kali ini. Terdapat 3 opsi yang tersedia pada servis, yaitu:
- Print encrypted flag
- Reveal the parameters
- Quit
$ nc 07.cr.yp.toc.tf 22010
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+ hi talented participants, welcome to the FERMAN cryptography task! +
+ Solve the given equations and decrypt the encrypted flag! Enjoy! +
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
| Parameters generation is a bit time consuming, so please be patient :P
| Options:
| [P]rint encrypted flag
| [R]eveal the parameters
| [Q]uit
p
| encrypt(flag) = 231943209108551364462499001833007833339471858509636903278777063625331785566177786876600883615579527538615449262965247345037039607956522411513272817618458127569994469550455219738226018767357372553130829156939915512881378019724932997157155395756993371652694606158039648511432571482664432642345638869625234178788155010122530376971444998919814539291576949527410495332000913070325460431669781091685926807159246810108562287609768925930433885165034652885839565911250630355513691399221705
| Options:
| [P]rint encrypted flag
| [R]eveal the parameters
| [Q]uit
r
e = 65537
isPrime(p) = True
isPrime(q) = True
n = p * q
(p - 101)**2 + (q - 640)**2 = 12585581867200760491901063218977008095777706525365307913267337889812133401733866376423522953619723513985288148041129036865848253118431620861635892195147618664084314783941500430569307840513730914732163671370801485277342439063100992039682753530924508927481297232132764512175962671321299489617673153858637922542612084091616376653006320421825225775179652753229398478629738230473614938248244076160394614556972508910519652684982889251539480613394248296145136678927126153770492875305723149
m = bytes_to_long(flag)
c = pow(m, e, n)
| Options:
| [P]rint encrypted flag
| [R]eveal the parameters
| [Q]uit
Solution
Disclaimer! Challenge ini berhasil diselesaikan setelah kompetisi berakhir.
Pada saat kompetisi berlangsung, beberapa cara telah saya lakukan untuk mendapatkan nilai $p$ dan $q$ dari persamaan $ (p - a)^{2} (q - b)^{2} = k $, namun tidak ada yang membuahkan hasil.
Setelah kompetisi berakhir, saya mencoba untuk menambahkan assume(p, "integer") dan assume(q, "integer") agar solusi bisa ditemukan oleh sage.symbolic.relation.solve. Terdapat beberapa kandidat solusi, sehingga kandidat solusi perlu dibandingkan menggunakan Brahmagupta-Fibonacci identity untuk mendapatkan $ p $ dan $ q $ yang digunakan oleh servis.
Implementation
from sage.all import *
from Crypto.Util.number import *
import gmpy2
k7 = 12585581867200760491901063218977008095777706525365307913267337889812133401733866376423522953619723513985288148041129036865848253118431620861635892195147618664084314783941500430569307840513730914732163671370801485277342439063100992039682753530924508927481297232132764512175962671321299489617673153858637922542612084091616376653006320421825225775179652753229398478629738230473614938248244076160394614556972508910519652684982889251539480613394248296145136678927126153770492875305723149
k = gmpy2.iroot(k7, 7)
assert k[1]
k = Integer(k[0])
print(f'{k = }')
p = var('p')
q = var('q')
assume(p, "integer")
assume(q, "integer")
res = solve(p ** 2 + q ** 2 == k, p, q)
res = [(Integer(p), Integer(q)) for p, q in res if p > 0 and q > 0]
a = 101
b = 640
c = 231943209108551364462499001833007833339471858509636903278777063625331785566177786876600883615579527538615449262965247345037039607956522411513272817618458127569994469550455219738226018767357372553130829156939915512881378019724932997157155395756993371652694606158039648511432571482664432642345638869625234178788155010122530376971444998919814539291576949527410495332000913070325460431669781091685926807159246810108562287609768925930433885165034652885839565911250630355513691399221705
e = 65537
def mul(r, s):
a, b = r
c, d = s
x1 = a * c - b * d
y1 = a * d + b * c
x2 = a * c + b * d
y2 = a * d - b * c
return (abs(x1), abs(y1)), (abs(x2), abs(y2))
def sqr(r):
return mul(r, r)[0]
def find(res):
for r in res:
r2 = sqr(r)
r4 = sqr(r2)
for r3 in mul(r, r2):
for r7 in mul(r4, r3):
p, q = r7
assert p ** 2 + q ** 2 == k ** 7
p += a
q += b
if is_prime(p) and is_prime(q):
return [p, q]
p, q = find(res)
n = p * q
d = gmpy2.invert(e, (p-1)*(q-1))
flag = long_to_bytes(pow(c, d, n)).decode()
print(flag)
$ sage -python solve.sage
k = 535245874316620332296772953273538077513756072907285297884311803942949
CCTF{Congrats_Y0u_5OLv3d_x**2+y**2=z**7}
Salt and Pepper
Diberikan attachment salt_pepper.py dan servis ke 02.cr.yp.toc.tf 28010.
#!/usr/bin/env python3
from hashlib import md5, sha1
import sys
from secret import salt, pepper
from flag import flag
assert len(salt) == len(pepper) == 19
assert md5(salt).hexdigest() == '5f72c4360a2287bc269e0ccba6fc24ba'
assert sha1(pepper).hexdigest() == '3e0d000a4b0bd712999d730bc331f400221008e0'
def auth_check(salt, pepper, username, password, h):
return sha1(pepper + password + md5(salt + username).hexdigest().encode('utf-8')).hexdigest() == h
def die(*args):
pr(*args)
quit()
def pr(*args):
s = " ".join(map(str, args))
sys.stdout.write(s + "\n")
sys.stdout.flush()
def sc():
return sys.stdin.readline().strip()
def main():
border = "+"
pr(border*72)
pr(border, " welcome to hash killers battle, your mission is to login into the ", border)
pr(border, " ultra secure authentication server with provided information!! ", border)
pr(border*72)
USERNAME = b'n3T4Dm1n'
PASSWORD = b'P4s5W0rd'
while True:
pr("| Options: \n|\t[L]ogin to server \n|\t[Q]uit")
ans = sc().lower()
if ans == 'l':
pr('| send your username, password as hex string separated with comma: ')
inp = sc()
try:
inp_username, inp_password = [bytes.fromhex(s) for s in inp.split(',')]
except:
die('| your input is not valid, bye!!')
pr('| send your authentication hash: ')
inp_hash = sc()
if USERNAME in inp_username and PASSWORD in inp_password:
if auth_check(salt, pepper, inp_username, inp_password, inp_hash):
die(f'| Congrats, you are master in hash killing, and it is the flag: {flag}')
else:
die('| your credential is not valid, Bye!!!')
else:
die('| Kidding me?! Bye!!!')
elif ans == 'q':
die("Quitting ...")
else:
die("Bye ...")
if __name__ == '__main__':
main()
Solution
Disclaimer! Challenge ini berhasil diselesaikan setelah kompetisi berakhir.
Inti dari challenge ini terletak pada fungsi auth_check:
def auth_check(salt, pepper, username, password, h):
return sha1(pepper + password + md5(salt + username).hexdigest().encode('utf-8')).hexdigest() == h
Variabel salt dan pepper tidak diketahui, namun md5sum dari salt, sha1sum dari pepper, dan panjang dari keduanya diketahui. Hal ini menunjukkan tipikal serangan hash length extension, dimana kita dapat menambahkan beberapa bit dengan panjang tertentu untuk menebak checksumnya, meskipun kedua variabel tersebut tidak diketahui isinya. Ada beberapa tools yang dapat membantu kita dalam melakukan hash length extension attack, salah satunya hashpump. Namun entah kenapa hashpump yang saya gunakan mengeluarkan output yang berbeda sehingga perlu “diakali” agar bisa menemukan hasil yang valid.
Implementation
#!/usr/bin/env python3
from pwn import *
import hashpumpy, re
MD5_v0 = '5f72c4360a2287bc269e0ccba6fc24ba'
MD5_v1 = 'a'
MD5_v2 = 'n3T4Dm1n'
MD5_v3 = 19-1
SHA_v0 = '3e0d000a4b0bd712999d730bc331f400221008e0'
SHA_v1 = 'a'
SHA_v2 = 'P4s5W0rd'
SHA_v3 = 19-1
r = remote('02.cr.yp.toc.tf', 28010, level='warn')
# r = process(['python3', 'dup.py'], level='warn')
r.sendline('l')
z_md5 = hashpumpy.hashpump(MD5_v0, MD5_v1, MD5_v2, MD5_v3)
z_md5_hash, z_md5_payload = z_md5
print(z_md5_hash)
z_sha = hashpumpy.hashpump(SHA_v0, SHA_v1, SHA_v2 + z_md5_hash, SHA_v3)
z_sha_hash, z_sha_payload = z_sha
print(z_sha_hash)
username = z_md5_payload[1:]
password = z_sha_payload[1:-32]
print(repr(username))
print(repr(password))
r.sendline(f'{username.hex()},{password.hex()}')
r.recvuntil('authentication hash:')
r.sendline(z_sha_hash)
r.recvline(0)
res = r.recvline(0).decode()
res = re.findall(r'CCTF{(.+)}', res)[0]
print('CCTF{\%s}' % (res))
$ python3 solve.py
...
95623660d3d04c7680a52679e35f041c
...
83875efbe020ced3e2c5ecc908edc98481eba47f
b'\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x98\x00\x00\x00\x00\x00\x00\x00n3T4Dm1n'
b'\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x98P4s5W0rd'
...
CCTF{Hunters_Killed_82%_More_Wolves_Than_Quota_Allowed_in_Wisconsin}
Wolf
Diberikan attachment Wolf.py dan servis ke 01.cr.yp.toc.tf 27010.
#!/usr/bin/env python3
from Cryptodome.Cipher import AES
import os, time, sys, random
from flag import flag
passphrase = b'HungryTimberWolf'
def encrypt(msg, passphrase, niv):
msg_header = 'EPOCH:' + str(int(time.time()))
msg = msg_header + "\n" + msg + '=' * (15 - len(msg) % 16)
aes = AES.new(passphrase, AES.MODE_GCM, nonce = niv)
enc = aes.encrypt_and_digest(msg.encode('utf-8'))[0]
return enc
def die(*args):
pr(*args)
quit()
def pr(*args):
s = " ".join(map(str, args))
sys.stdout.write(s + "\n")
sys.stdout.flush()
def sc():
return sys.stdin.readline().strip()
def main():
border = "+"
pr(border*72)
pr(border, " hi wolf hunters, welcome to the most dangerous hunting ground!! ", border)
pr(border, " decrypt the encrypted message and get the flag as a nice prize! ", border)
pr(border*72)
niv = os.urandom(random.randint(1, 11))
flag_enc = encrypt(flag, passphrase, niv)
while True:
pr("| Options: \n|\t[G]et the encrypted flag \n|\t[T]est the encryption \n|\t[Q]uit")
ans = sc().lower()
if ans == 'g':
pr(f'| encrypt(flag) = {flag_enc.hex()}')
elif ans == 't':
pr("| Please send your message to encrypt: ")
msg_inp = sc()
enc = encrypt(msg_inp, passphrase, niv).hex()
pr(f'| enc = {enc}')
elif ans == 'q':
die("Quitting ...")
else:
die("Bye ...")
if __name__ == '__main__':
main()
Solution
Terdapat kerentanan pada potongan kode program berikut:
niv = os.urandom(random.randint(1, 11))
flag_enc = encrypt(flag, passphrase, niv)
Ketika kita melakukan beberapa kali koneksi ke servis, kita memiliki peluang sebesar $ \frac{1}{11} $ atau sekitar 9% untuk mendapatkan randint(1, 11) bernilai 1. Idenya, kita akan mengumpulkan beberapa encrypted flag yang bisa kita peroleh dengan cara melakukan koneksi berulang kali ke servis, dengan harapan kita menerima encrypted flag dengan 1 byte nonce. Dengan demikian, kita hanya perlu melakukan bruteforce 1 byte nonce karena passphrase dari AES-GCM yang telah diketahui dari source code yang diberikan.
Implementation
#!/usr/bin/env python3
from pwn import *
from Crypto.Cipher import AES
while True:
r = remote('01.cr.yp.toc.tf', 27010, level='warn')
r.sendline('g')
r.recvuntil('encrypt(flag) = ')
ct = r.recvline(0).decode()
r.close()
for ni in range(256):
niv = bytes([ni])
aes = AES.new(b'HungryTimberWolf', AES.MODE_GCM, nonce = niv)
flag = aes.decrypt(bytes.fromhex(ct))
if b'EPOCH' in flag:
print(flag.decode())
exit()
$ python3 solve.py
...
EPOCH:1628059598
CCTF{____w0lveS____c4n____be____dan9er0uS____t0____p3oplE____!!!!!!}===========