Tahun 2020 menandakan sudah 3 tahun saya menjadi problem setter di HackToday. Pada tahun ini terdapat ±40 soal pada babak penyisihan yang dibuat oleh >10 problem setter, dimana saya membuat 4 soal yang terdiri dari 3 crypto dan 1 misc. Writeup yang akan saya tuliskan hanya bagian crypto saja karena banyak peserta yang mengerjakan misc hanya bermodalkan luck 
succss
Succss merupakan salah satu challenge dadakan yang saya tulis (H-3 sebelum babak penyisihan). Ide utama challenge ini sebenarnya terinspirasi dari salah satu topik Math StackExchange. Namun pada pembahasan tersebut, nilai $ a $ dan $ x $ kecil dan $ p $ merupakan 3-digit prime yang tidak diketahui.
Challenge
Pada challenge ini, $ p $ merupakan 64-bit prime yang nantinya digunakan sebagai modulus. Nilai $ x $ merupakan potongan 8 karakter flag, lalu diubah menjadi 64-bit integer.
#!/usr/bin/python
from random import randint
from flag import flag
conv = lambda num: hex(num)[2:].rstrip('L').rjust(16, '0')
p = 18446744073709551557
b = randint(1, p-1)
res = ''
for i in range(0, len(flag), 8):
x = int(flag[i:i+8].encode('hex'), 16)
for _ in range(2):
r = b * x % p
res += conv(r)
b = r
with open('flag.enc', 'w') as f:
f.write(res.decode('hex'))
f.close()
Solution
Intinya, flag.enc berasal dari persamaan $ bx $ modulo $ p $. Nilai $ b $ awal memanglah random, namun pada iterasi selanjutnya, nilai $ b $ diambil dari $ r $ yang bisa kita dapatkan dari flag.enc. Dari persamaan tersebut, kita bisa menghitung nilai $ x $ sejak nilai $ b $ dan $ p $ diketahui.
# b*x % p == r
10548191747025617241*x % 18446744073709551557 == 2251902629492118084
1561538295112991496*x % 18446744073709551557 == 366232838665939083
12906958383224310437*x % 18446744073709551557 == 5266784763463225371
9624942410065160910*x % 18446744073709551557 == 11468834452703655458
9420025632208547372*x % 18446744073709551557 == 6549147454529855774
10653623540301864980*x % 18446744073709551557 == 4026538432190439741
# (b*x - r) % p == 0
(10548191747025617241*x - 2251902629492118084) % 18446744073709551557 == 0
(1561538295112991496*x - 366232838665939083) % 18446744073709551557 == 0
(12906958383224310437*x - 5266784763463225371) % 18446744073709551557 == 0
(9624942410065160910*x - 11468834452703655458) % 18446744073709551557 == 0
(9420025632208547372*x - 6549147454529855774) % 18446744073709551557 == 0
(10653623540301864980*x - 4026538432190439741) % 18446744073709551557 == 0
Ada banyak cara yang dapat digunakan untuk menghitung x, salah satunya menggunakan modular inverse. Namun saya menggunakan Sage karena dirasa cukup cepat dan kode program cukup singkat.
Implementation
from sage.all import *
from Crypto.Util.number import bytes_to_long, long_to_bytes
p = 18446744073709551557
P.<x> = PolynomialRing(GF(p), implementation='NTL')
enc = open('flag.enc').read()
enc = [bytes_to_long(enc[i:i+8]) for i in range(0, len(enc), 8)]
flag = ''
for i in range(0, len(enc), 2):
f = enc[i]*x - enc[i+1]
m, _ = f.roots()[0]
flag += long_to_bytes(int(m))
print flag
Flag
hacktoday{some0ne_is_h4ving_fun_w_M4th_here}
MD45
Soal ini terinspirasi dari md5-maxmin. Saya mengeksekusi ide md5-maxmin ini ke bentuk soal CTF yang menyediakan servis custom AES dengan MODE ECB + IV, dimana user bebas memasukkan input namun input tersebut di-hash dan di-shuffle. Permutasi pengacakan akan berkurang ketika terdapat banyak byte yang sama pada md5sum.
Challenge
MD45 disini bukan hash function terbaru, namun hanya penggunaan hash md4 dan md5 secara bersamaan.
#!/usr/bin/python
from Crypto.Cipher import AES
from Crypto.Hash import MD4, MD5
import random, 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 = open('flag.txt').read().strip()
md4 = lambda x: MD4.new(x).digest()
md5 = lambda x: MD5.new(x).digest()
pad = lambda x: x + chr(AES.block_size - (len(x) % AES.block_size)) * (AES.block_size - (len(x) % AES.block_size))
xor = lambda x, y: ''.join([chr(ord(x[i]) ^ ord(y[i % len(y)])) for i in range(len(x))])
def banner():
return '''
,'|"\`45
|\ /| | |\ \
|(\ / | | | \ \
(_)\/ | | | \ \ > Generate your secure key and IV with MD45 now!
| \ / | /(|`-' /
| |\/| |(__)`--'
'-' '-' '''
def encrypt():
secret = raw_input('\nsecret (in hex): ').strip()
try:
secret = secret.decode('hex')
key, iv = md4(secret), md5(secret)
pt = pad(flag)
mid = AES.new(key, True).encrypt(pt)
ct = ''
for i in range(0, len(mid), 16):
iv = ''.join(random.sample(list(iv), len(iv)))
ct += xor(mid[i:i+16], iv)
return 'ciphertext: %s' % (ct.encode('hex'))
except:
return '>:('
print banner()
print encrypt()
Key didapat dari md4sum user input dan IV dari md5sum user input. Konteks IV disini bukan digunakan untuk block chaining, namun hanya shuffle position dari md5sum user input.
Block Cipher Mode
Pada potongan program AES.new(key, True), jenis block cipher yang digunakan adalah MODE_ECB karena True direpresentasikan bit 1 di python.
>>> True ^ 2
3
>>> True + True
2
>>> from Crypto.Cipher import AES
>>> help(AES)
...
DATA
MODE_CBC = 2
MODE_CFB = 3
MODE_CTR = 6
MODE_ECB = 1
MODE_OFB = 5
MODE_OPENPGP = 7
MODE_PGP = 4
__revision__ = '$Id$'
block_size = 16
key_size = (16, 24, 32)
Reduce Permutation
Untuk mengurangi permutasi, kita bisa generate md5sum sendiri atau secara instan mengambil salah satu string dari md5-maxmin. Berikut kode yang saya gunakan untuk generate md5sum dengan mencari banyak byte yang sama.
from hashlib import md5
from os import urandom
plain = ''
max_set = 0
best_hash = ''
ctr = 0
while True:
tmp = urandom(24) # bebas
h = md5(tmp).digest()
punten = max([h.count(i) for i in set(h)])
ctr += 1
if punten > max_set:
plain = tmp.encode('hex') # hex-encoded
max_set = punten
best_hash = h.encode('hex')
print 'plain: {}'.format(plain)
print 'max_set: {}'.format(max_set)
print 'best_hash: {}\n'.format(best_hash)
if ctr % 1000000 == 0:
print '{}m hashes generated'.format(ctr/1000000)
plain: 22c762eecd4c844d1b90c225543701868347660b3bfce62e
max_set: 1
best_hash: f5bbd0a4b1f1f092997be22cab8bf826
plain: 9702ef6dd0adda8933a032ad4fb5a3cb0723d62895f7355c
max_set: 2
best_hash: 8e1fc6ed2b8e1cd18367169c5e92c19c
plain: 2e7c9e411bd5ba39fa44ce36be36eaf94efe0d7bace00e7d
max_set: 3
best_hash: c4c669e8bcc432cfed93734cf01b6ac4
plain: 08d9a41713a2f31c5109e7a9ba2255a6bcd856b2700e1bd2
max_set: 4
best_hash: b5b172b5b54d0ef0901fd555b54f656e
1m hashes generated
plain: f97791919a8aaff33101e189d3e806b5876a2964a55ca800
max_set: 5
best_hash: 2339fc2380ea2323a2982356bbe5c2a3
2m hashes generated
3m hashes generated
4m hashes generated
...
plain: a836ffc70182a193edaafa60b0fbbb598106d94140384b6e
max_set: 6
best_hash: 60073e07079c076d07caa4542904e407
Dirasa cukup, saya akan menggunakan string a836ffc70182a193edaafa60b0fbbb598106d94140384b6e yang memiliki 6 byte yang sama (\x07) pada md5sum nya (60073e07079c076d07caa4542904e407) sebagai input.
Recover Encrypted Flag
Kumpulkan beberapa ciphertext (saya mengumpulkan 300 ciphertext agar hasil lebih akurat). Idenya, cari byte yang paling sering muncul pada ciphertext, lalu xor dengan byte \x07.
# 300 ciphertext yang didapat dari input a836ffc70182a193edaafa60b0fbbb598106d94140384b6e
1d2be8eb743dbb4783d0027f398a63f786dd5034dc892f34e91840a0af2a7727e60bcac8d19b6a24abef70cc2f954248
d02be885973db8474e4b3bf26ae0636feca55d97dc17b453fe1b402dac13c7ea453294a2d1529624302270022c956c66
334cc64c9704e8dc832ccf7f00e3d3f40fe53797e5f47cf9d01b408e3440978ddfc6f30161385e2457ef939a0295410c
604f7341973dbb47ba65cfdc00435a17eca519aedcda45f9d37c40dd0c2a9471c80b10a18238961d5aeff4cc2c95e135
332bd175b957184718a8cfdc00e033f4ef4637c4dcbdb434feb8798e4ce79480e50bf3a2619b2324fd85f4522c0e7b66
...
592be82694131814834be1dc00d9fd6f77a519ae8fda2f3473d62a8eaf29948ddf0bdda1e8380d77d3eff401e195d9c5
90d7e81f97dedc47e94b51dc2ee3fdf4ec4634c4dcda8c3433804043c513ba8d810bf0c819160de9d3ef93a27f957b66
90262525973dbb20604b2c8f00d9abf48b46370c3fda2f0dd01be3dd81e7fee9df0b99a2e538232430ef5ee27f0e41c5
fed7e826ae3ebb4783e8e1b667e01ea7778b37f0b6da0197d01b40dd96c997eae6e8f3a2829b234e30889052b7ac42ab
3362e825fda6584783863b7f53e057f421465d74dc792f34e91bdb8dc82abab9e625f3a1823896c79388c00146ac42ab
Implementation
from Crypto.Cipher import AES
from Crypto.Hash import MD4, MD5
import collections
import os
# cara instan pake https://github.com/hletrd/md5-maxmin
SECRET = '30386e6928673075336164615f4a69796f6e67596f756e2d484c45545244'
# atau pake md5 hasil generate sendiri
SECRET = 'a836ffc70182a193edaafa60b0fbbb598106d94140384b6e'
md4 = lambda x: MD4.new(x).digest()
md5 = lambda x: MD5.new(x).digest()
unpad = lambda data: data[:-ord(data[-1])]
xor = lambda x, y: ''.join([chr(ord(x[i]) ^ ord(y[i % len(y)])) for i in range(len(x))])
bait = md5(SECRET.decode('hex'))
bait = collections.Counter(bait).most_common(1)[0][0] # \x07
output = open('output').read().strip().split('\n')
output = [i.decode('hex') for i in output]
len_enc = len(output[0])
ct = ''
for j in range(len_enc):
tmp = ''
for i in range(len_enc):
tmp += output[i][j]
ct += collections.Counter(tmp).most_common(1)[0][0] # most common byte di tiap index
ct = xor(ct, bait) # balikin ciphertext asli
key = md4(SECRET.decode('hex'))
aes = AES.new(key, True)
pt = aes.decrypt(ct)
print unpad(pt)
Flag
hacktoday{yesh_We_play_hashg4me}
primeOn
primeOn adalah soal crypto pertama yang ada di repo HackToday 2020 (dipush sejak Desember 2019). Ide awal dalam membuat soal ini hanyalah multi-prime RSA biasa, namun ternyata cara menghasilkan $ n $ primeOn mirip dengan salah satu challenge redpwnCTF 2020: primimity, dimana pada waktu itu hanya bermodalkan next_prime sebanyak 3 kali. Akhirnya dimodifikasi lagi hingga pada akhirnya fungsi primeOn meng-generate $ n $ seperti yang dapat lihat di babak penyisihan kemarin.
Pada H-14 babak penyisihan, saya terpikirkan untuk meningkatkan kesulitan soal dengan menambahkan padding agar tidak terlalu mirip dengan soal basic multi-prime RSA.
Challenge
More prime or more pad? Why not both?
#!/usr/bin/env python3
from Crypto.Util.number import *
from random import getrandbits
from flag import flag
def nextPrime(x):
x |= 3
while not isPrime(x):
x += 4
return x
def primeOn(nbit):
n = x = getPrime(nbit)
for e in range(3):
x <<= pow(3, e)
n *= nextPrime(x)
return n
def pad(m):
nbit = m.bit_length()
x, y, z = [getrandbits(nbit) for _ in range(3)]
return x**4 + y**3 + z**2 + m
def main():
m = pad(bytes_to_long(flag))
e = 31337
n = primeOn(512)
assert m < n
c = pow(m, e, n)
print(f'[*] e: {e}')
print(f'[*] n: {n}')
print(f'[*] c: {c}')
if __name__ == '__main__':
main()
[*] e: 31337
[*] n: 6356326373093851050954113026446301903178711457486893936799699181190935856438724829625041678643784650009395008631119853494963132760748750556139150246716037950945542202944984463751041467066916655611873113922681196989785725128202767808090271041726436197716741535246312208869817552031190216680328460126414380694143767371432955648937013902620026107533670765139416413173485536322105337873993780082208669766051915042714328576678313470398432735206713170713953857575306167842504517834516034915931387402467418589508757064524490005482223694756296583917967689466986864800297486325468076916806794575464016768089261995092157863269789137
[*] c: 5437175132281357472583330705913386190422172883464017381354724322973310935467761783666478294384225358019319978457327573658689220055073579441985979611265963522069600938792464614427329222246957809777696525360378077015556889987981198551217443901435967658192647316938409593703844413684745499174633724212829328297315780663096808007449764705705377528747182284022334972512442959635377921986272448617993796706309560444213302488159359005598474322754301577411987424305929550579037187251898051126146855301745454156372230365827004229334080794993929056684670005796210255503939590177563814203092761056074036719198148793616829614031318867
Solution
Terdapat 2 concern utama pada challenge ini, yaitu fungsi primeOn dan pad.
Part 1: Factorize N
def primeOn(nbit):
n = x = getPrime(nbit)
for e in range(3):
x <<= pow(3, e)
n *= nextPrime(x)
return n
Untuk memahami fungsi primeOn, kita bisa lakukan cara sebagai berikut.
>>> def primeOn():
... n = x = 1
... print 'x =', x
... for e in range(3):
... x <<= pow(3, e)
... print 'x =', x
... n *= x
... return n
...
>>> primeOn()
x = 1
x = 2
x = 16
x = 8192
262144
Kurang lebih, modulus $ n $ dibentuk dari perkalian $ 1p $, $ 2p $, $ 16p $ dan $ 8192p $.
n = 1*p * 2*p * 16*p * 8192*p
n = 262144*p**4
n/262144 = p**4
iroot(n/262144, 4) = p
p = iroot(n/262144, 4)
Namun nilai $ p $ yang didapat masih memiliki presisi rendah. Hal ini dikarenakan pada fungsi primeOn, $ x $ masuk ke fungsi nextPrime terlebih dahulu sebelum dikalikan dengan $ n $. Namun hal ini bukan masalah besar, nilai $ x $ dan nextPrime(x) tidak berbeda jauh sehingga masih dapat dibruteforce. Berikut kodenya.
from Crypto.Util.number import isPrime
from gmpy2 import iroot
def nextPrime(x):
x |= 3
while not isPrime(x):
x += 4
return x
def factorize(n, prec=2**16):
p = iroot(n / 262144, 4)[0] - prec
for _ in range(prec):
p += 1
if n % p == 0:
print 'found!'
return [p, nextPrime(2*p), nextPrime(16*p), nextPrime(8192*p)]
n = 6356326373093851050954113026446301903178711457486893936799699181190935856438724829625041678643784650009395008631119853494963132760748750556139150246716037950945542202944984463751041467066916655611873113922681196989785725128202767808090271041726436197716741535246312208869817552031190216680328460126414380694143767371432955648937013902620026107533670765139416413173485536322105337873993780082208669766051915042714328576678313470398432735206713170713953857575306167842504517834516034915931387402467418589508757064524490005482223694756296583917967689466986864800297486325468076916806794575464016768089261995092157863269789137
p, q, r, s = factorize(n)
assert p*q*r*s == n
assert isPrime(p) and isPrime(q) and isPrime(r) and isPrime(s)
print 'p =', p
print 'q =', q
print 'r =', r
print 's =', s
found!
p = 12478620197867554067600956878271711756423233107922075407451110153020185395930478077082390953879395593997044904263925620981511592790640195794755986683025147
q = 24957240395735108135201913756543423512846466215844150814902220306040370791860956154164781907758791187994089808527851241963023185581280391589511973366050387
r = 199657923165880865081615310052347388102771729726753206519217762448322966334887649233318255262070329503952718468222809935704185484650243132716095786928403591
s = 102224856660931002921787038746801862708619125620097641737839494373541358763462476407458946694180008706023791855730078687080542968140924483950641042907342005063
Dekripsi ciphertext yang diberikan. Didapat padded-plaintext.
from Crypto.Util.number import inverse
e = 31337
n = 6356326373093851050954113026446301903178711457486893936799699181190935856438724829625041678643784650009395008631119853494963132760748750556139150246716037950945542202944984463751041467066916655611873113922681196989785725128202767808090271041726436197716741535246312208869817552031190216680328460126414380694143767371432955648937013902620026107533670765139416413173485536322105337873993780082208669766051915042714328576678313470398432735206713170713953857575306167842504517834516034915931387402467418589508757064524490005482223694756296583917967689466986864800297486325468076916806794575464016768089261995092157863269789137
c = 5437175132281357472583330705913386190422172883464017381354724322973310935467761783666478294384225358019319978457327573658689220055073579441985979611265963522069600938792464614427329222246957809777696525360378077015556889987981198551217443901435967658192647316938409593703844413684745499174633724212829328297315780663096808007449764705705377528747182284022334972512442959635377921986272448617993796706309560444213302488159359005598474322754301577411987424305929550579037187251898051126146855301745454156372230365827004229334080794993929056684670005796210255503939590177563814203092761056074036719198148793616829614031318867
# factors
p = 12478620197867554067600956878271711756423233107922075407451110153020185395930478077082390953879395593997044904263925620981511592790640195794755986683025147
q = 24957240395735108135201913756543423512846466215844150814902220306040370791860956154164781907758791187994089808527851241963023185581280391589511973366050387
r = 199657923165880865081615310052347388102771729726753206519217762448322966334887649233318255262070329503952718468222809935704185484650243132716095786928403591
s = 102224856660931002921787038746801862708619125620097641737839494373541358763462476407458946694180008706023791855730078687080542968140924483950641042907342005063
phi = (p-1)*(q-1)*(r-1)*(s-1)
d = inverse(e, phi)
m = pow(c, d, n)
assert pow(m, e, n) == c
print m
2205581320899595224803761961870767101590533905253680611178192352231267411944033645601437806951652107395523211129969135492072214117364957290430273746770367969098804487801337166544763893524408571724552039852623699851203687412548536035409021424674742451685573568623760932057729287826829177960228602273134185820765197307133056870751534220491305132614361450951678486538138442273637769788223250826918271421429595295383483696895199603049510243218336894591446961580534738683791993534810134
Part 2: Unpad Plaintext
Here comes another math part.
def pad(m):
nbit = m.bit_length()
x, y, z = [getrandbits(nbit) for _ in range(3)]
return x**4 + y**3 + z**2 + m
Nilai $ x, y, $ dan $ z $ memiliki ukuran bit yang sama. Maka,
from Crypto.Util.number import getPrime
from gmpy2 import iroot
nbit = 16 # ukuran bebas, untuk uji coba pake prime kecil
x = getPrime(nbit)
y = getPrime(nbit)
res = x**2 + y
print iroot(res, 2)[0] == x
True
Kenapa bisa menghasilkan True? Nilai $ y $ hilang begitu saja? Karena $ x $ dan $ y $ memiliki ukuran bit yang sama dan pada kasus ini, nilai $ y $ hanyalah least significant dari $ \sqrt{\mathrm{res}} $. Dengan demikian, kita bisa dapatkan nilai $ y $ dengan cara sebagai berikut.
from Crypto.Util.number import getPrime
from gmpy2 import iroot
nbit = 16 # ukuran bebas, untuk uji coba pake prime kecil
x = getPrime(nbit)
y = getPrime(nbit)
res = x**2 + y
print iroot(res, 2)[0] == x
print res - iroot(res, 2)[0]**2 == y
True
True
Namun terkadang terdapat error precision pada degree dan ukuran bit yang besar.
from Crypto.Util.number import getPrime
from gmpy2 import iroot
nbit = 512
for _ in range(10):
x = getPrime(nbit)
y = getPrime(nbit)
z = getPrime(nbit)
m = getPrime(nbit)
res = x**4 + y**3 + z**2 + m
print iroot(res, 4)[0] == x
True
True
False
True
False
True
True
True
True
False
Hal ini diakibatkan nilai $ y $ yang jauh lebih besar dibanding $ x $, sehingga nilai $ x $ asli dan $ x $ hasil perhitungan berbeda. Hal ini tentu saja dapat diatasi karena selisih bit yang kecil (maksimum 2-bit pada kasus ini).
Lakukan cara yang sama pada fungsi pad dan bruteforce nilai 2-bit error untuk setiap nilai $ x, y, $ dan $ z $.
Implementation
#!/usr/bin/python
from Crypto.Util.number import *
from gmpy2 import iroot
output = open('output').read().replace('[*] ', '').replace(': ', ' = ')
exec(output)
def nextPrime(x):
x |= 3
while not isPrime(x):
x += 4
return x
def factorize(n, const=2**16):
p = iroot(n / 262144, 4)[0] - const
for _ in range(const):
p += 1
if n % p == 0:
print 'found, p = {}'.format(p)
return [p, nextPrime(2*p), nextPrime(16*p), nextPrime(8192*p)]
print 'factors not found'
exit()
def unpad(msg):
for k in range(64):
m = msg
l = k
for i in range(4, 1, -1):
x = iroot(m, i)[0]
m = m - (x - (l & 3))**i
l >>= 2
flag = long_to_bytes(m)
if 'hacktoday' in flag:
return flag
return 'flag not found'
p, q, r, s = factorize(n)
phi = (p-1)*(q-1)*(r-1)*(s-1)
d = inverse(e, phi)
m = pow(c, d, n)
assert pow(m, e, n) == c
flag = unpad(m)
print flag
found, p = 12478620197867554067600956878271711756423233107922075407451110153020185395930478077082390953879395593997044904263925620981511592790640195794755986683025147
hacktoday{__pr1me_numbers__never_fail_t0_am4ze_me}
Flag
hacktoday{__pr1me_numbers__never_fail_t0_am4ze_me}