Di penghujung tahun 2020 saya diberi amanah untuk menjadi salah satu problem setter event Capture The Flag (CTF) yang diselenggarakan oleh Indonesia Cyber Security Independence Resilience Team (CSIRT.ID), yaitu Redmask CTF. Redmask CTF adalah kompetisi keamanan siber nasional yang diselenggarakan secara online babak penyisihan maupun final. Redmask CTF merupakan Jeopardy-style, dimana terdiri dari 5 kategori utama (Reverse, Pwn, Crypto, Web, Forensic) dan 1 kategori tambahan (OSINT) yang hanya tersedia di babak penyisihan.
Sebelumnya terima kasih kepada CSIRT.ID selaku penyelenggara Redmask CTF, mas Anton Sahbana dan mas Hamdan Abdul Aziz selaku event organizer, dan juga @cacadosman, @hanasuru dan @circleous selaku problem setter. Tanpa adanya mereka kompetisi Redmask CTF tidak akan berjalan lancar.
Sebagai salah satu dari empat problem setter, saya diberi tanggung jawab untuk membuat soal kategori Crypto. Berikut beberapa soal dan pembahasan yang saya buat pada event Redmask CTF 2020. Enjoy!
Penyisihan
- Baby Remainder (Tags: Crypto, Math)
- Drakjoge (Tags: Crypto, AES)
- Red Prime (Tags: Crypto, RSA)
Final
- halftimepad (Tags: Crypto, OTP)
- Mini LFSR (Tags: Crypto, RNG)
- poggers (Tags: Reversing)
Baby Remainder
Description
You know what to do with this baby, right?
Author: deomkicer
Challenge
Peserta diberikan dua attachment, yaitu chall.py dan output.txt.
#!/usr/bin/python
from Crypto.Util.number import bytes_to_long, getPrime, isPrime
from Crypto.Util.Padding import pad
import random
FLAG = open('flag.txt').read().strip()
def gcd(x, y):
while y:
x, y = y, x % y
return x
def nextPrime(x):
y = x | 1
while not isPrime(y) or x == y:
y += 2
return y
def func1(m):
r = 0
n = getPrime(24)
for _ in range(20):
c = m % n
r = (r + c) << 24
n = nextPrime(n)
return r + n
def func2(m):
e = 65537
s = int(1.5 * m.bit_length())
p = getPrime(s)
q = getPrime(s)
n = p * q
phi = (p-1) * (q-1)
assert gcd(e, phi) == 1
c = pow(m, e, n)
return [c, n]
def main():
m = bytes_to_long(pad(FLAG, 16))
x = func1(m)
c, n = func2(m)
print '[*] x: {}'.format(x)
print '[*] c: {}'.format(c)
print '[*] n: {}'.format(n)
if __name__ == "__main__":
main()
[*] x: 23094165431786100355526044253709728814798463389708809102582728735375919100958575587180933434416065193831984219858333697884459439237225076085631323146599
[*] c: 35703828195014314779130572173838405792203827843838337164138324349054018626165405608631668424125354824088581206690470493715670441904715732670268298902314992522325166381192347787631033487842179185626477526402060448402994095952498184032625011762001368283090667915206705299930832531126368939887359502769489279148908735016512609818108700326025593402920304007229114235376763826366011429815102687106002897099462599442901323115537245513737287502192642632120652995972085
[*] n: 69322062056110811910771256698054585206504587085352309734114706285067271080556482705613601934594927074503445446788760755236171656631535180458709243715042135691514436000849977156915131384111573721148858175923910499712701585271174643759183003665224191766815397787666172266983527504656043546864175488365999898549975705381211336797642712384196936177534859747966267679353351832867589273653392437775139285515467259488716919224671730822202554164269755489504674616199041
Solution
Bisa dikatakan tidak ada vulnerability pada fungsi func2 selain mengenkripsi nilai $ m $, hanya saja kedua prime yang di-generate memiliki panjang bit yang berasal dari 1.5 kali panjang bit $ m $.
s = int(1.5 * m.bit_length())
p = getPrime(s)
q = getPrime(s)
n = p * q
Pada func1, nilai $ m $ di-modulo sebanyak 20 kali dengan prime yang berbeda-beda, namun 20 nilai prime tersebut tidak tersedia pada output.txt. Hal ini tidak menjadi masalah karena kita diberikan prime terakhir dari 20 prime tersebut, sehingga untuk mencari 19 prime lainnya, kita tinggal implementasi fungsi prevPrime.
def prevPrime(x):
y = x | 1
while not isPrime(y) or x == y:
y -= 2
return y
Dengan demikian, kita sudah memiliki 20 pasang remainder dan modulus. Selanjutnya, recover nilai $ m $ menggunakan algoritme Chinese Remainder Theorem (CRT). Kita dapat menggunakan fungsi solve_crt yang tersedia di library libnum.
Namun sayangnya hasil yang didapat masih berupa junk, hal ini dikarenakan nilai $ m $ memiliki panjang ±512-bit, sementara dari algoritme CRT yang dihasilkan memiliki panjang ±480-bit (karena kita hanya memiliki 20 pasang 24-bit remainder dan 24-bit modulus). Idenya kita dapat menggunakan dua cara untuk menghasilkan nilai CRT yang mendekati ±512-bit:
- Kalikan hasil CRT dengan kelipatan Least Common Multiple (LCM) seluruh modulus, dan
- Tambahkan satu pasang remainder dan modulus
Dari mana kita dapat menemukan satu pasang remainder dan modulus? Mari kita lihat kode program kembali.
m = bytes_to_long(pad(FLAG, 16))
Flag di-padding menggunakan PKCS#7, sehingga kita bisa bruteforce 16 kemungkinan padding bytes dan menambahkan pasangan remainder dan modulus tersebut ke algoritme CRT.
Untuk menghitung LCM dari seluruh modulus, kita tinggal kalikan seluruh modulus tersebut karena seluruh modulus merupakan prime. Seberapa besar kelipatan $ k $ yang nantinya perlu kita bruteforce? Harusnya tidaklah besar karena panjang bit $ m $ yang telah dihasilkan 21 pasang remainder dan modulus sudah mendekati ±512-bit.
Implementasi
Saya gunakan nilai $ c $ dan $ n $ RSA sebagai pengecekan apakah nilai $ m $ yang didapat merupakan flag.
from deom import *
output = open('../peserta/output.txt').read()
output = output.replace('[*] ', '')
output = output.replace(': ', '=')
exec(output)
C = c
N = n
print 'Flag bit-length: %d' % (int(N.bit_length() / 3.0))
def prevPrime(x):
y = x | 1
while not isPrime(y) or x == y:
y -= 2
return y
def prod(ns):
bign = 1
for n in ns:
bign *= n
return bign
rem_blocks = []
prime = prevPrime(x & 0xFFFFFF)
x >>= 24
while x:
rem_blocks.append(x & 0xFFFFFF)
x >>= 24
rem_blocks = rem_blocks
mod_blocks = [prime]
while len(rem_blocks) != len(mod_blocks):
prime = prevPrime(prime)
mod_blocks.append(prime)
mod_blocks = mod_blocks
for i in range(16):
tmp = '}' + (chr(i + 1) * (i + 1))
v0 = s2n(tmp)
v1 = 256 ** len(tmp)
cs = rem_blocks + [v0]
ns = mod_blocks + [v1]
res = solve_crt(cs, ns)
prodn = prod(ns)
for k in range(1024):
tes = k*prodn + res
if pow(tes, 65537, N) == C:
print i, k, unpad(n2s(tes), 16)
break
Flag bit-length: 510
3 350 redmask{____why_are_y0u_padding___why_are_you_paddin999____}
Flag
redmask{____why_are_y0u_padding___why_are_you_paddin999____}
Drakjoge
Description
Kamu adalah seorang komedian yang ingin mendaftar ke salah satu komunitas komedi yang cukup terkenal, yaitu Indonesian Drakjoge. Namun pada saat mendaftar, kamu dihadapkan dengan seorang Bang Haxor, salah satu sesepuh di komunitas Indonesian Drakjoge. Bang Haxor tidak bisa menerima kamu ke komunitas jika kamu tidak mengerti apa yang ia katakan. Ayo buktikan kalau kamu layak berada di komunitas Indonesian Drakjoge!
nc 202.148.27.84 30001
Author: deomkicer
Challenge
Peserta diberikan sebuah attachment server.py dan servis ke 202.148.27.84 30001.
#!/usr/bin/python
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from libnum import b2s, s2b
import struct
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)
class Cyclic:
def __init__(self):
self.mask = 0xFFFFFFFF
self.poly = 0xEDB88320
self.table = []
for byte in range(256):
tmp = 0
for _ in range(8):
if (byte ^ tmp) & 1:
tmp = (tmp >> 1) ^ self.poly
else:
tmp >>= 1
byte >>= 1
self.table.append(tmp)
def calc(self, string):
value = self.mask
for c in string:
value = self.table[(ord(c) ^ value) & 0xFF] ^ (value >> 8)
return struct.pack('>I', (-1 - value) & self.mask)
sys.stdout = Unbuffered(sys.stdout)
FLAG = open('flag.txt').read().strip()
KEY = AES.get_random_bytes(16)
CC = Cyclic()
def intro():
print '''
................................................................
........................----::::::::::---.......................
.............-/+syhdddmmmmmmddddddddmmmmmmddhhyyso+:............
.............yhhhhdddmmmmmmddddddddddmmmmmdddddhhhhh+...........
............-yhhhhdddmmmmmddddddddddddddmmmddddhhhhhs...........
............:yhhhhhhhddddmdddddddddddddddddhhhhhhhhhy...........
............/yyo------:/+shdddddddddddhso++::--:+yyyy...........
............/yyoyyyyys+:...:ohdddddho-..-/osyhyyo+yyy...........
............/syyyhhhhhhhys/-.-hdddy..-+syhhhhhhhyyyyy...........
............/ssyyyyyyyyyyyssosddddhoosyyyyyyyyyyyyyss...........
............/ysooo+////::::/oyhmmmhyso+//////++ooosss...........
............/ssyyyysoo+++osyhhhmmdhhys+//:://+syhyyso...........
............-yyhhddmmddddddddhhdmdhhhddddddddddddhhy+...........
.............ssyyhddddddddddhhhdmdhhhdddddddddhhhyys:...........
....... ....oosyyhhddddddhhhhhdmdhhhhhddddhhhyyssso............
..... . . -soosyyyyyyyyhhhhhddmhhhhhsssyyyyysooo+...... ...
..... . . ..:sos::syyhddhssyyhhhyyssyhhhyso/:/+os-.... .
..... ...../sss--shhhhhhy:://:-/yyhhhhhh+./syy+.... .
..... ..+ssyo..://+/...-+....+oo+/:.-osyyo-....
..... ...+sssyy+:-....-sss-......:+yysyys/.....
..... ....+sysssyyyhhhyyyyyyhhhhyssssyss+......
..... ....../syyyyyssss+oooooossssssyyss/.......
....... ......-oyhyyhhhhy. .:hhhyyssysso-........
.... .. ../syyyhhds...-hhhyyyyso:.
.+yyyhhs. .-hhhyyso:.
.+syyh. .ohyys+-.
.:+o/ -so/-.
........ ..... . ........
________ .... __ __ ...........
\______ \____________ | | __ |__| ____ ____ ____
| | \_ __ \__ \ | |/ / | |/ _ \ / ___\_/ __ \
| . \ | \// __ \| < | ( <_> ) /_/ > ___/
/_______ /__| (____ /__|_ \/\__| |\____/\___ / \___ >
\/ .... \/ \/\______| /_____/ \/ v1.0
'''
def main():
while True:
try:
inp = b2s(raw_input('Kamu: ').strip())
chs = CC.calc(inp + FLAG)
ptx = pad(inp + chs + FLAG, 16)
cip = AES.new(KEY, AES.MODE_ECB)
ctx = cip.encrypt(ptx)
print 'Bang Haxor: %s\n' % (s2b(ctx))
except:
break
if __name__ == "__main__":
intro()
main()
Solution
Yang perlu diketahui bahwa Cyclic.calc akan menghasilkan 4-byte, dimana itu merupakan algoritme CRC32 checksum.
ptx = pad(inp + chs + FLAG, 16)
cip = AES.new(KEY, AES.MODE_ECB)
ctx = cip.encrypt(ptx)
Variabel ptx di-encrypt menggunakan AES.MODE_ECB. Variabel inp dapat dikontrol, namun chs dan FLAG masing-masing tidak dapat kita kontrol dan tidak diketahui. Variabel chs ini memproteksi agar Chosen-plaintext attack tidak bisa dilakukan dari depan, namun kita tetap dapat melakukan attack dari belakang, dengan catatan harus mengetahui panjang flag terlebih dahulu. Panjang flag bisa diketahui dengan memanfaatkan banyaknya karakter input yang kita masukkan, lalu bandingkan berapa banyak block yang dihasilkan oleh Bang Haxor. Berikut kodenya.
Implementation
from deom import *
import string
# p = process('./server.py')
p = remote('localhost', 30001)
def kirim(x):
p.sendlineafter('Kamu: ', s2b(x))
p.recvuntil('Bang Haxor: ')
res = p.recvline().strip()
return b2s(res).encode('hex')
def panjang_flag():
for i in range(1, 16+1):
res = kirim('z' * i)
print i, len(res)
def potong(x):
res = []
for i in range(0, len(x), 32):
res.append(x[i:i + 32])
return res
panjang_flag()
LEN_FLAG = 128 / 2 - 13 - 4
JUNK = -(LEN_FLAG + 4) % 16
flag = ''
ctr = 0
while True:
for i in range(16):
payload = 'z'*(JUNK + i + 1)
correct_block = kirim(payload)
correct_block = potong(correct_block)[-ctr-1]
for c in string.printable:
payload = c + flag + chr(16 - i - 1) * (16 - i - 1)
test_block = kirim(payload)
test_block = potong(test_block)[0]
if test_block == correct_block:
flag = c + flag
print flag
if flag.startswith('redmask{'):
p.close()
exit()
if len(flag) % 16 == 0:
ctr = 0
break
ctr += 1
$ python solve.py
[+] Starting local process './server.py': pid 23273
1 128
2 128
3 128
4 128
5 128
6 128
7 128
8 128
9 128
10 128
11 128
12 128
13 160
14 160
15 160
16 160
}
a}
ya}
_ya}
e_ya}
re_ya}
are_ya}
_are_ya}
y_are_ya}
ny_are_ya}
wny_are_ya}
owny_are_ya}
lowny_are_ya}
clowny_are_ya}
_clowny_are_ya}
w_clowny_are_ya}
ow_clowny_are_ya}
how_clowny_are_ya}
_how_clowny_are_ya}
__how_clowny_are_ya}
e__how_clowny_are_ya}
ge__how_clowny_are_ya}
oge__how_clowny_are_ya}
joge__how_clowny_are_ya}
kjoge__how_clowny_are_ya}
akjoge__how_clowny_are_ya}
rakjoge__how_clowny_are_ya}
drakjoge__how_clowny_are_ya}
_drakjoge__how_clowny_are_ya}
o_drakjoge__how_clowny_are_ya}
to_drakjoge__how_clowny_are_ya}
_to_drakjoge__how_clowny_are_ya}
3_to_drakjoge__how_clowny_are_ya}
m3_to_drakjoge__how_clowny_are_ya}
om3_to_drakjoge__how_clowny_are_ya}
com3_to_drakjoge__how_clowny_are_ya}
lcom3_to_drakjoge__how_clowny_are_ya}
elcom3_to_drakjoge__how_clowny_are_ya}
Welcom3_to_drakjoge__how_clowny_are_ya}
{Welcom3_to_drakjoge__how_clowny_are_ya}
k{Welcom3_to_drakjoge__how_clowny_are_ya}
sk{Welcom3_to_drakjoge__how_clowny_are_ya}
ask{Welcom3_to_drakjoge__how_clowny_are_ya}
mask{Welcom3_to_drakjoge__how_clowny_are_ya}
dmask{Welcom3_to_drakjoge__how_clowny_are_ya}
edmask{Welcom3_to_drakjoge__how_clowny_are_ya}
redmask{Welcom3_to_drakjoge__how_clowny_are_ya}
[*] Stopped process './server.py' (pid 23273)
Flag
redmask{Welcom3_to_drakjoge__how_clowny_are_ya}
Red Prime
Description
Kalo ada cara ribet kenapa harus gampang?
Author: deomkicer
Challenge
Peserta diberikan dua attachment chall.py dan output.txt.
#!/usr/bin/python
from Crypto.Util.number import *
from fractions import Fraction
from flag import flag
def calc(a, b, c):
s = float(a if b else -a)
while True:
s *= -c
a += s
if abs(s) < .0001:
return int(a) + 1
def genPrime(nbit):
while True:
x = getRandomNBitInteger(nbit)
p = calc(x, False, Fraction(11, 17))
q = calc(x, True, Fraction(13, 19))
if isPrime(p) and isPrime(q):
return p, q
def encrypt(m, n):
m = bytes_to_long(m)
assert m < n
return pow(m, 65537, n)
nbit = 512
p, q = genPrime(nbit)
n = p * q
c = encrypt(flag, n)
print 'c =', c
print 'n =', n
c = 36329427815660857273975769241128439913876212605062992262994190763574776272663976674103443716897608306230018751864075024103462484630058628345543656344514348327259129134588398512790627389534011046346572424412645320049318379077699227840195565804368461545343159195445136776937608078872952802876228889700607871824
n = 90426937012775177429000599791153537960097523093679151685293953736111122844607505842911804538666518238999277005201661454277975570212424800306742495208980816771772338412911631058816972038342529285531308198920534491617390252583741071016207659940881379473007727445261857366529091574347745852612560736676904697857
Solution
Fokus challenge ini berada pada fungsi calc.
def calc(a, b, c):
s = float(a if b else -a)
while True:
s *= -c
a += s
if abs(s) < .0001:
return int(a) + 1
Variabel $ c $ merupakan pecahan yang berada pada rentang nilai $ 0 < c < 1 $, dan jika dilihat dari fungsi calc, nilai $ s $ dikalikan $ -c $ secara terus-menerus hingga nilai $ s $ benar-benar mendekati nol. Dengan demikian, kita bisa menyadari ini sebagai jumlah deret geometri tak hingga, dengan rasio sebesar $ -c $. Dengan menggunakan rumus jumlah deret geometri tak hingga $ \frac{a}{1 - r} $, kita bisa menemukan formula yang dihasilkan fungsi calc terhadap nilai $ x $.
p = calc(x, False, Fraction(11, 17))
q = calc(x, True, Fraction(13, 19))
p = 39 * x / 28
q = 19 * x / 32
n = p * q
n = (39 * x / 28) * (19 * x / 32)
n = (741 * x * x / 896)
896 * n = 741 * x * x
896 * n / 741 = x * x
x = sqrt(896 * n / 741)
Sebenernya nilai $ x $ yang didapat dari persamaan ini tidak begitu akurat, tapi salah satu prime $ q $ masih bisa didapat dari nilai $ x $ tersebut. Untuk mengembalikan prime $ p $, kita bisa membagi $ n $ terhadap $ q $.
Implementation
from deom import *
exec(open('output.txt').read())
def calc(a, b, c):
s = float(a if b else -a)
while True:
s *= -c
a += s
if abs(s) < .0001:
return int(a) + 1
def genPrime(x):
p = calc(x, False, Fraction(11, 17))
q = calc(x, True, Fraction(13, 19))
return p, q
x = iroot(896 * n / 741, 2)[0]
print 'x =', x
_, q = genPrime(x)
p = n / q
print 'p =', p
print 'q =', q
d = inverse(65537, (p - 1) * (q - 1))
m = pow(c, d, n)
print n2s(m)
x = 10456679839079558435741293278799951804696465146133756844686290313160766675050958143205793164740013321816920439873929284909687775742842280579847027557233139
p = 14564661204432239532713999155601891754421924746339293744623528128911381783311842948286857271889672256015768465228080468579260508202704806823788292375314433
q = 6208653654453488918561497666988432859118874764084736512542892043121192330662698577624399240484750055090263661210623544244224366737822586320004311446192129
redmask{an0ther_w4yyy_to_5um_RSA_up_45d1e8}
Unintended solution dari peserta cukup mengejutkan saya sebagai problem setter. Kita juga bisa bruteforce nilai $ x $ dengan pendekatan binary search karena nilai $ x $ dan $ n $ berbanding lurus. Sadge.
Flag
redmask{an0ther_w4yyy_to_5um_RSA_up_45d1e8}
halftimepad
Description
I’ll generate a new random key each time you connect. There’s no way for you to decrypt my flag!
nc 103.55.38.18 30001
Author: deomkicer
Challenge
Peserta diberikan sebuah attachment server.py dan servis ke 103.55.38.18 30001.
#!/usr/bin/python
from binascii import hexlify
from re import findall
from os import urandom
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)
madpad = lambda a, b: ''.join([chr(ord(i) ^ ord(j) ^ 0x69) for i, j in zip(a, b)])
genkey = lambda n: hexlify(urandom(n / 2))
if __name__ == '__main__':
flag = open('flag.txt').read().strip()
m = findall(r'^redmask{(\w+)}$', flag)[0]
print hexlify(madpad(m, genkey(len(m))))
Solution
Kode program singkat, padat dan jelas. Variabel $ m $ merupakan flag tanpa format flag redmask{...}, lalu flag di-xor dengan random hex character. Karena hex character hanya ada 16 kemungkinan (0123456789abcdef), maka kita tinggal kumpulkan beberapa ciphertext yang didapat dari servis, lalu amati kemunculan flag xor dengan salah satu karakter 0123456789abcdef. Solusi tercepat yang dapat problem setter temukan yaitu kita dapat recover flag secara menyeluruh dengan mengumpulkan kurang dari 100 ciphertext. Berikut kodenya.
Implementation
#!/usr/bin/python
from pwn import *
LEN = 20
boxes = [[] for _ in range(LEN)]
ctr = 0
while not all(len(box) == 16 for box in boxes):
# p = process('./server.py', level='warn')
p = remote('localhost', 30001, level='warn')
pantun = p.recvline(0).decode('hex')
assert len(pantun) == LEN
for i in range(LEN):
if pantun[i] not in boxes[i]:
boxes[i].append(pantun[i])
p.close()
ctr += 1
print ctr
flag = ''
for i in range(LEN):
box = sorted(boxes[i])
for j in range(256):
baru = []
for k in '0123456789abcdef':
baru.append(chr(j ^ ord(k)))
baru = sorted(baru)
if baru == box:
flag += chr(j ^ 0x69)
print flag
break
assert len(flag) == LEN
print 'Flag: redmask{\%s}' % (flag)
$ python solve.py
97
e
ey
eyy
eyy_
eyy_y
eyy_y0
eyy_y0_
eyy_y0_W
eyy_y0_Wh
eyy_y0_Wha
eyy_y0_What
eyy_y0_What_
eyy_y0_What_t
eyy_y0_What_t1
eyy_y0_What_t1m
eyy_y0_What_t1me
eyy_y0_What_t1me_
eyy_y0_What_t1me_p
eyy_y0_What_t1me_p4
eyy_y0_What_t1me_p4d
Flag: redmask{eyy_y0_What_t1me_p4d}
Flag
redmask{eyy_y0_What_t1me_p4d}
Mini LFSR
Description
Plz help me to decrypt my encrypted flag with my encrypted key ://
Author: deomkicer
Challenge
Peserta diberikan dua attachment chall.py dan output.txt.
#!/usr/bin/env python3
from Crypto.Cipher import PKCS1_OAEP
from Crypto.PublicKey import RSA
from Crypto.Util.number import getRandomNBitInteger
import re
from flag import flag
class LFSR64:
def __init__(self, state, taps):
self.mask = (1 << 64) - 1
self.state = state
self.taps = taps
def encrypt(self, m: bytes) -> bytes:
r = bytearray()
for b in m:
r.append(b ^ self._gene(8) ^ 0x69)
return bytes(r)
def _gene(self, n: int) -> int:
s = 0
for _ in range(n):
s ^= self._tick()
s <<= 1
s >>= 1
return s
def _tick(self) -> int:
r = self.state
self.state = (r << 1) & self.mask
i = (r & self.taps) & self.mask
s = 0
while i:
s ^= (i & 1)
i >>= 1
self.state ^= s
return s
def main():
ptx = re.findall(r'^redmask{(\w+)}$', flag)[0].encode()
rsa = RSA.generate(1024)
oaep = PKCS1_OAEP.new(rsa)
lfsr = LFSR64(getRandomNBitInteger(64), 0xC936000000000000)
with open('output.txt', 'w') as f:
f.write(f"{lfsr.encrypt(ptx[:len(ptx)//2]).hex()}\n")
f.write(f"{oaep.encrypt(ptx[len(ptx)//2:]).hex()}\n")
f.write(f"{lfsr.encrypt(rsa.export_key('PEM')).hex()}\n")
f.close()
if __name__ == '__main__':
main()
c9bca96b3692b684627d2f3663515f662acae6
5321e066c8dc9fd994ab8466b35b06bc263b4b4789967f843d41ad3991485507c7c3bd5f6dcc90b6963795385a571e1cfd911995fb98f5d6cd5142bc28d7d704c216305c4c8a6672d63ff2fbdbc2ada80c02daff05dcd040e17196f6576c38ca34585d405c851b1dfdb57d34826261c05ece73403b983b636eb6021972186f67
c42df9728dbe3d02212ec05529edaee2957e0b2a2a63dcb4d6db86b5fb8ae51189bf23f7d93dccce6c65aa8083dfe2583caf3c052e814d39977ba7907d975e0bd92700a64ee2899428e470470c6b13be0b1ffc2112a50c07fb7961f3c794fb1f57455ffe017acda265467d4ee14e3b4772222b96c0f1659b3476734b3927393637360468929817e91cfc6c7e02474ceeed42fc06439e3acb0801b5aeda8d1adb9dddd20971d7638889ecb7759602debd7fe4adca6dff528c944c8735281519a61467999329eb65dc3ba23becf78fb0b1f5d9ccccfebdd3a3754652924c89649ad5fd3e2c024b1a41996e04e936b6dcc9aabebac45531c576c9d98942865329ac42549a144fee1aecb4f13a2f685281815e9b5146ec569a8eda03dfe30d34e1dcb6a5be146f1a5c81ad590f312cf307edc597364ee5cd58fd27c11867c106ec0713f0e4d8cff98db8254eae91ebfc65e04be3ca768b02ce3b9f9c263f7e187fa72d743209ce6ab58cbe4c7fde2b300629fa49112cf58a534764daeb52ac19adf8761a496b4fe1148d574cf7ff78091bcf4b1c14d896b73413755babe02c149d18e36426ffc23e3cce3621d69c943686221750ccab7b7ff76e05d52bc0c069217597dd827eb9811378c2aa76e530c0c6d71ee71fc4518e0ec6c8989ad248e2d26861ba00d768a8e9092dfcc2b215009972869e1987a3ea55b50cb8cf5db42185f338867d33917bc3bea048598db08352a803fae832fba7a94cac959b6a83bc265805247f827ed01bb68178ee9ef0c83e9b4fdd6340c553262175a0716dd8479f6c9be37c1b21239ea33982d92f97ba3d5164cfcc98d0e11544e8ce1cf1c6fa4b2f54992dc8caa0c6f0aefd67078f8ac2e19ebcb131ce806e43f71daad51e6f872bbe4c6d5f0aa8cee9a9bab6b228f0075934358d4990015ef1670544621796268d9e59c5affeea19ca2104f39d278d2f964b620975e536784cfc3741a0a3f0afc8f08dfea34c40c8ded494106946d093d6c74f2a0d807085101aa2bbe0d5b822f37a384dd720130bf1c3b17aa38e1e76d873d06cc6b9b545896ad1ade4b4b4c0499dd8daa1ab75d75633b349e08de5aef8aedbd1b881da3bec24dd42f2fe1acc2704203ca669154f6a7f0eec8bc9fca554a4d4941733388821a491d29852a48909080b392e74843b687a415f120e30f1ec03471b1c0e0732a897756642d9eacd6c4bc024532bd0683eaf0bc7100c72abd31acb20f99b5c
Solution
Jika diamati alur dari kode program, potongan flag pertama dienkripsi menggunakan Linear Feedback Shift Register (LFSR), yang pada kasus ini merupakan Weak Random Number Generator (RNG). Sementara potongan flag kedua dienkripsi menggunakan RSA dengan tambahan PKCS#1 OAEP. RSA key tersebut juga dienkripsi menggunakan LFSR dan dilampirkan pada attachment output.txt.
Seperti yang kita ketahui, RSA key memiliki format sebagai berikut.
-----BEGIN RSA PRIVATE KEY-----
<string base64>
-----END RSA PRIVATE KEY-----
Karena LFSR yang digunakan cukup kecil (64-bit), maka kita dapat mengetahui deretan beberapa bit output LFSR dengan melakukan xor terhadap string -----BEGIN RSA PRIVATE KEY----- (sebenarnya beberapa karakter saja cukup). Lakukan invert LFSR menggunakan $ \mathrm{taps} = \mathrm{0xC936000000000000} $ hingga kita menemukan initial state dari LFSR. Generate ulang LFSR menggunakan initial state dan $ \mathrm{taps} $ tersebut, lalu kita bisa decrypt potongan flag pertama dan RSA key. Setelah didapat RSA key, decrypt potongan flag kedua.
Implementation
#!/usr/bin/env python3
from Crypto.Cipher import PKCS1_OAEP
from deom import *
class LFSR64:
def __init__(self, state, taps):
self.mask = (1 << 64) - 1
self.state = state
self.taps = taps
def encrypt(self, m: bytes) -> bytes:
r = bytearray()
for b in m:
r.append(b ^ self._gene(8) ^ 0x69)
return bytes(r)
def _gene(self, n: int) -> int:
s = 0
for _ in range(n):
s ^= self._tick()
s <<= 1
s >>= 1
return s
def _tick(self) -> int:
r = self.state
self.state = (r << 1) & self.mask
i = (r & self.taps) & self.mask
s = 0
while i:
s ^= (i & 1)
i >>= 1
self.state ^= s
return s
out = open('../peserta/output.txt').read().strip().split()
c1 = bytes.fromhex(out[0])
c2 = bytes.fromhex(out[1])
c3 = bytes.fromhex(out[2])
randbs = xor(c3, b'-----BEGIN RSA PRIVATE KEY-----', b'\x69')
output = bin(int.from_bytes(randbs, 'big'))[2:]
output = list(map(int, list(output)))[:64]
length = len(output)
state = 0
taps = 0xC936000000000000
for i in range(length):
state |= output[i] << (length - 1 - i)
for _ in range(length + (len(c1) * 8)):
bit = state & 1
tmp = taps & (state >> 1)
while tmp:
bit ^= (tmp & 1)
tmp = tmp >> 1
state = (state >> 1) | (bit << (length-1))
lfsr = LFSR64(state, taps)
m1 = lfsr.encrypt(c1)
m3 = lfsr.encrypt(c3)
print(m3.decode())
rsa = RSA.import_key(m3)
oaep = PKCS1_OAEP.new(rsa)
m2 = oaep.decrypt(c2)
print('[*] Flag: redmask{\%s}' % (m1+m2).decode())
$ python3 solve.py
-----BEGIN RSA PRIVATE KEY-----
MIICXAIBAAKBgQDArTssW/ve2yhMSyKCyOYGBVtkmpsw56bmO4sTgCm3ifYUcgx7
xtRqDxmTBDepfX9bZjPjqoJmswXDX8Xz4OS0xML3NYHLdatDR3s09qylGLxR5BZr
ZihIeD77uOJmYullm+B7Mtxp20M+Qg8G6DsMZ/M9nfirzZ++L0wpCJGtnQIDAQAB
AoGAHwKiip4BWIRgT4CA55jAQMl9mfWyMuRNvdy+d7SBwlWqLUSP0soU/OmSPacI
8wv3l/UdNoVbuH4UAuENYeuDviGAe4qebAwCXJ90vsWpvzob48X0SL4Sqw2sri/c
vRS14FrplEhaB0RaM4/Lr0GDmAgpyIgqOkHW2A/uB0+nEacCQQDWVd/iCl1YkzQx
raM+qBcQvgDr0flciMF5VdMf6xfkaJsE/0q9Mlq0Vq/4QHmMl9j+WOk5SOFSYDAa
O4kkjRr/AkEA5iGJTi8++Fe9wF3JUgmGWmect6h/2MwfAD5340mug1mhJx7CL0wB
J6xTibFSQC3gbQJdLjGAerpgsKTdxZDDYwJAZptpuH6ZvWOLIxUrBz3U/PDY5Av7
Qm89n+aUUb1sDK5/N983WmeWwKqXR1MmXUX8XZcW35OiOptNq+FAgD0E5QJAPvUD
xDDmsDgIwDyoG9phOBBKbnAZcaz9+ioc0EBTDroRfUtL4naPhlP9kpjBIK+sSwYv
ibifJnQgiZLA3RCqcwJBALbtM8mWQ/B+MzlDQogxrcB2PbM0pvlp5WiFU3D/UlH6
yIRj/8+CafiPvaHf/Lk82kuCqxk2Rn/fEn62sA7CD/Y=
-----END RSA PRIVATE KEY-----
[*] Flag: redmask{plzz_use_s3cur3__R_N_G__nxtime_d1bd4ab}
Flag
redmask{plzz_use_s3cur3__R_N_G__nxtime_d1bd4ab}
poggers
Description
Author: deomkicer
Challenge
Diberikan dua attachment poggers yang merupakan ELF 64-bit LSB executable dan output.txt.
z28HADMcwc9AYjKmNiAyPLABws/PnxMyLGLCAHB3YmB1B6BTs0J0Vw==
Solution
File executable poggers sendiri merupakan binary golang, terdapat fungsi main_main ketika dilakukannya proses decompile menggunakan IDA. Input user diambil dari os.Args[1]. Untuk mempermudah proses decompile, gunakan binja + IDA + gdb (solusi dari @vidner, finalis yang berhasil mendapatkan first blood).
Ada 3 bagian utama yang menjadi fokus reverse alur program.
- Fungsi sus hanya ngeshuffle posisi karakter. Reverse sus dengan implementasi python:
def revSus(s):
v0 = s[len(s) / 2:][::-1]
v1 = s[:len(s) / 2][::-1]
return ''.join([i + j for i, j in zip(v0, v1)])
-
Gray code
x ^ (x >> 1). Reverse gray code dengan mengunakan librarylibnum.rev_grey_code. -
RotateLeft64->RotateRight64.
Implementation
#!/usr/bin/python
from base64 import b64decode
from libnum import n2s, rev_grey_code, s2n
from pwn import xor
def revSus(s):
v0 = s[len(s) / 2:][::-1]
v1 = s[:len(s) / 2][::-1]
return ''.join([i + j for i, j in zip(v0, v1)])
def rotateRight64(num, k):
b = bin(num)[2:].zfill(64)
return int(b[-(k % 64):] + b[:-(k % 64)], 2)
out = open('output.txt').read().strip()
out = xor(b64decode(out), '\x69')
out = [out[i:i + 8][::-1] for i in range(0, len(out), 8)]
out = [rotateRight64(s2n(i), 13) for i in out]
out = [n2s(rev_grey_code(i)) for i in out]
out = revSus(''.join(out))
print out
$ python solve.py
redmask{No_SAT_solv3rs_no_pr0bl3m}&&&&&&
Flag
redmask{No_SAT_solv3rs_no_pr0bl3m}