I played Defenit CTF 2020 as a member of zer0pts. This was an amazing competition. I enjoyed it a lot.
Challenge attachments and solution scripts are available from here
- [Crypto] Double Message
- [Crypto] Hash ChungDol
- [Forensics] What Browse do I use
- [rev] child encrypter
- [rev] Lord Fool Song Remix
- [rev] MixMix
- [rev] Mom's Touch
[Crypto] Double Message
We're given the double.sage and the output.txt.
from Crypto.PublicKey import RSA from hashlib import md5 import binascii nBitSize = 2048 e = 3 Flag = b'XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX' # censored key = RSA.generate(nBitSize) M1 = Flag + md5(Flag).digest() M2 = Flag + md5(b'One more time!' + Flag).digest() M1 = int(binascii.hexlify(M1),16) M2 = int(binascii.hexlify(M2),16) C1 = Integer(pow(M1,e,key.n)) C2 = Integer(pow(M2,e,key.n)) with open('out.txt','w') as f: f.write('n = ' + hex(key.n)+'\n') f.write('C1 = '+ hex(C1)+'\n') f.write('C2 = ' + hex(C2)+'\n')
Apparently, it seems to be Coppersmith's Short Pad Attack + Franklin-Reiter's Related Message Attack. I borrowed the script from this writeup .
e = 3 PRxy.<x,y> = PolynomialRing(Zmod(n)) PRx.<xn> = PolynomialRing(Zmod(n)) PRZZ.<xz,yz> = PolynomialRing(Zmod(n)) g1 = x**e - C1 g2 = (x + y)**e - C2 q1 = g1.change_ring(PRZZ) q2 = g2.change_ring(PRZZ) h = q2.resultant(q1) # need to switch to univariate polynomial ring # because .small_roots is implemented only for univariate h = h.univariate_polynomial() # x is hopefully eliminated h = h.change_ring(PRx).subs(y=xn) h = h.monic() roots = h.small_roots(X=2**127, beta=0.3) assert roots, "Failed1" diff = roots[0] x = PRx.gen() # otherwise write xn g1 = x**e - C1 g2 = (x + diff)**e - C2 # gcd while g2: g1, g2 = g2, g1 % g2 g = g1.monic() assert g.degree() == 1, "Failed 2" # g = xn - msg msg = -g[0] print(msg)
[Crypto] Hash ChungDol
server.py
#!/usr/bin/python3 from Crypto.Random.random import getrandbits from base64 import b64decode, b64encode from Crypto.Util.number import long_to_bytes, bytes_to_long from secret import flag BITS = 220 def shift(n,i): n1=(n<<i)%0x800 n2=(n>>(11-i)) return n1^n2 def PIE(i, A, B, C): if i<16: return (A&B)|((~A)&C) return (A&B)|(B&C)|(C&A) def pie(j): if(j<16): return j elif(j==16): return 0 elif(j==17): return 4 elif(j==18): return 8 elif(j==19): return 12 elif(j==20): return 1 elif(j==21): return 5 elif(j==22): return 9 elif(j==23): return 13 elif(j==24): return 2 elif(j==25): return 6 elif(j==26): return 10 elif(j==27): return 14 elif(j==28): return 3 elif(j==29): return 7 elif(j==30): return 11 else: return 15 def HashGenerate(value): n = 3 s = [3]*16 + [7]*16 Q = [0]*36 m = [0]*16 X = [] for i in range(0,20): X.insert(0, value&0x7ff) value >>=11 for i in range(-3, 1, 1): Q[n+i]=X[i+3] for i in range(0,16): m[i]=X[i+4] for i in range(0, 32): Q[n+i+1]=shift(( (Q[n+i-3] + PIE(i,Q[n+i],Q[n+i-1],Q[n+i-2]) + m[pie(i)])%0x800 ), s[i]) Y = [] for i in range(0,4): Y.append((Q[n+i-3] + Q[32+i])%0x800) Y[1]=(Y[0]<<33)^(Y[1]<<22) Y[0]=Y[2]<<11 Y[1]^=Y[0]^Y[3] return Y[1] def challenge(): goal = HashGenerate(getrandbits(BITS)) print("Hash : %s [0/5]" % hex(goal)) answer = [] for i in range(1, 6): data = b64decode(input("data : ")) value = bytes_to_long(data) result = HashGenerate(value) if (result!= goal) or (value in answer): exit(0) answer.append(value) print("Hash : %s [%d/5]" % (hex(goal), i)) print("\nGood!\n") if __name__ == '__main__': print("Can you make a hash like this?\n") stage = 1 while stage <= 10: print("============================================") print(" Stage %d" % stage) print("============================================") try: challenge() stage+=1 except: print("Nop") exit(0) print(flag)
Our task is to find 5 value pairs that yield the same hash value. @mitsu proposed a method that makes almost of Q[i] to 0. Using this method, we can fix the least 33bit of the hash value. So I brute-forced the remaining 11bit to find the collision.
In fact, as this algorithm assumes to get the 220-bit long value at most, value a and a | (1 << 220) yields the same result.
solve.py
def crack(h): n = 3 for t in range(1 << 11): tt = (t << 33) | (h & ((1 << 33) - 1)) value = tt << (220 - 44) x = value Q = [0]*36 m = [0]*16 X = [] for i in range(0,20): X.insert(0, value&0x7ff) value >>=11 for i in range(-3, 1, 1): Q[n+i]=X[i+3] for i in range(0,16): m[i]=X[i+4] for i in range(0, 4): P = PIE(i, Q[n+i], Q[n+i-1], Q[n+i-2]) m[i] = 0x800 - P - Q[n+i-3] while m[i] < 0: m[i] += 0x800 x |= (m[i] << (165 - 11 * i)) h2 = HashGenerate(x) if h2 == h: return x from ptrlib import * from Crypto.Random.random import getrandbits from base64 import b64decode, b64encode from Crypto.Util.number import long_to_bytes, bytes_to_long sock = Socket("hash-chungdol.ctf.defenit.kr", 8960) for _ in range(10): h = int(sock.recvlineafter("Hash : ").split(b" ")[0], 16) r = crack(h) for i in range(1, 6): exploit = r | (i << 220) sock.sendlineafter("data : ", b64encode(long_to_bytes(exploit))) print(sock.recvline()) print(sock.recvline()) sock.interactive()
[Forensics] What Browse do I use
We're given some huge Evidence files. Its format is EWF/Expert Witness/EnCase image file format. I've never seen the format, however, it can be mounted with ewftool. Then it exploded its size to 30GiB . This file can also be mounted with kpartx in this time.
Now we can see the windows file system. As our purpose is to find out the version of the user's default browser, I checked NTUSER.DAT and saw the value of HKEY_CURRENT_USER\Software\Microsoft\Windows\Shell\Associations\UrlAssociations\http\UserChoice\Progid. Then it turned out the user used google chrome.
To get the version of chrome was easy, just see in the C:\Program Files (x86)\Google\Chrome.
[rev] child encrypter
We're given the ELF file and ciphertext.txt. After some observation, it turned out that the ELF file works like the following.
from Crypto.Cipher import AES import os key = open("key", "rb").read() plaintext = open("plaintext", "rb").read() nonce = os.urandom(16) c.srand(key[0]) xorkey = None ciphertext = [] for i in range(len(plaintext)): if i % 16 == 0: nonce = nonce[:15] + bytes([c.rand() % 10]) xorkey = AES.new(key=key, mode=AES.MODE_ECB).encrypt(nonce) ciphertext.append( xorkey[i % 16] ^ plaintext[i] ) with open("cihpertext", "wb") as f: f.write(ciphertext)
It is similar to the CTR_MODE but the last byte is determined by rand() % 10. This means that the variation of the key is just 10. So this challenge could be reduced to a multi-time pad challenge.
[rev] Lord Fool Song Remix
The reversing part was done by @ptr-yudai. I received the python emulated version of the binary.
def encrypt(name, slen): bits = [] for c in name + b'\x00' * (9-len(name)): for i in range(8): bits.append((c >> (7-i)) & 1) memory = [ bits[0:23][::-1] + [0] * (slen - 23), bits[23:23+24][::-1] + [0] * (slen - 24), bits[23+24:23+24+25][::-1] + [0] * (slen - 25) ] for i in range(0, slen - 23): memory[0][23+i] = memory[0][i] ^ memory[0][i+5] for i in range(0, slen - 24): memory[1][24+i] = memory[1][i] ^ memory[1][i+4] ^ memory[1][i+1] ^ memory[1][i+3] for i in range(0, slen - 25): memory[2][25+i] = memory[2][i] ^ memory[2][i+3] output = [] for i in range(slen): output.append( ((memory[2][i] ^ memory[0][i]) & memory[1][i]) ^ memory[2][i] ) return output length = 20 name = b"abcd123" enc = encrypt(name, length*10) for i in range(length): snd = 0 for j in range(10): snd |= enc[i*10 + j] snd <<= 1 print(snd >> 1, end=" ") print()
just do the boring stuff with z3.
def solve(piyo): slen = len(piyo) bits = [BitVec("bitvec{}".format(i), 1) for i in range(72)] memory = [ bits[0:23][::-1] + [0] * (slen - 23), bits[23:23+24][::-1] + [0] * (slen - 24), bits[23+24:23+24+25][::-1] + [0] * (slen - 25) ] for i in range(0, slen - 23): memory[0][23+i] = memory[0][i] ^ memory[0][i+5] for i in range(0, slen - 24): memory[1][24+i] = memory[1][i] ^ memory[1][i+4] ^ memory[1][i+1] ^ memory[1][i+3] for i in range(0, slen - 25): memory[2][25+i] = memory[2][i] ^ memory[2][i+3] output = [] solver = Solver() for i in range(len(piyo)): solver.add( ((memory[2][i] ^ memory[0][i]) & memory[1][i]) ^ memory[2][i] == piyo[i] ) m = solver.check() if m == sat: print("sat") m = solver.model() p = '' flag = [] for b in bits: p += str(m[b].as_long()) if len(p) == 8: flag.append(chr(int(p, 2))) p = '' print("".join(flag)) else: print("unsat") outputs = [] xs = [int(x) for x in "638 1004 829 320 666 526 593 247 940 790 1023 75 240 42 1012 326 447 261 882 881".split(" ")] for x in xs: outputs += [int(b) for b in "{:010b}".format(x)] print(len(outputs)) solve(outputs)
[rev] MixMix
the binary shuffle and replace the input with the RC4-like algorithm. I collected shuffle indices and replace values using the following gdb script.
import gdb gdb.execute("file ./mixmix") gdb.execute("start < input") piebase = int(gdb.execute("piebase", to_string=True).strip().split(" = ")[1], 16) data = 'mogutakomogumogutakomogudefenitc' print(data) gdb.execute("b *0x{:0x}".format(piebase+ 0xECA)) offsets = [] bits = [] for _ in range(256): gdb.execute("continue") offset = int(gdb.execute("print $rdx", to_string=True).strip().split(" = ")[1]) offsets.append(offset) bit = int(gdb.execute("print $rcx", to_string=True).strip().split(" = ")[1]) bits.append(bit) gdb.execute("b *0x{:0x}".format(piebase+ 0x102A)) gdb.execute("b *0x{:0x}".format(piebase+ 0x105B)) swapindex = [] bitvalues = [] for _ in range(256): gdb.execute("continue") offset = int(gdb.execute("print $rdx", to_string=True).strip().split(" = ")[1]) swapindex.append(offset) gdb.execute("continue") offset = int(gdb.execute("print $rdx", to_string=True).strip().split(" = ")[1]) bitvalues.append(offset) gdb.execute("b *0x{:0x}".format(piebase+ 0x1123)) mogo_offsets = [] vs = [] for _ in range(256): gdb.execute("continue") offset = int(gdb.execute("print $rdx", to_string=True).strip().split(" = ")[1]) mogo_offsets.append(offset) gdb.execute("step") v = int(gdb.execute("print $rdx", to_string=True).strip().split(" = ")[1]) vs.append(v) gdb.execute("b *0x{:0x}".format(piebase+0x0F64)) mogo_read_offsets = [] read_vs = [] for _ in range(256): gdb.execute("continue") offset = int(gdb.execute("print $rdx", to_string=True).strip().split(" = ")[1]) mogo_read_offsets.append(offset) gdb.execute("step") v = int(gdb.execute("print $rdx", to_string=True).strip().split(" = ")[1]) read_vs.append(v) gdb.execute("b *0x{:0x}".format(piebase+0x0D8b)) mini_values = [] vx = [] for _ in range(len(data)): gdb.execute("continue") v = int(gdb.execute("print $rsi", to_string=True).strip().split(" = ")[1]) mini_values.append(v) v2 = int(gdb.execute("print $rcx", to_string=True).strip().split(" = ")[1]) vx.append(v2) print(offsets) print(bits) print(swapindex) print(bitvalues) print(mogo_offsets) print(vs) print(mogo_read_offsets) print(read_vs) print(mini_values) print(vx)
After getting the indices, applying the reverse assignments.
shuffle_2 = [164, 144, 464, 928, 96, 856, 580, 268, 556, 180, 244, 392, 468, 200, 544, 936, 776, 316, 524, 932, 412, 172, 688, 676, 444, 572, 796, 76, 652, 692, 380, 408, 916, 356, 84, 360, 188, 68, 312, 388, 340, 88, 816, 44, 512, 264, 20, 184, 52, 0, 372, 520, 168, 740, 236, 568, 252, 260, 644, 552, 852, 548, 292, 420, 72, 1004, 884, 136, 768, 248, 240, 304, 344, 272, 792, 564, 256, 680, 708, 80, 620, 760, 976, 744, 480, 4, 864, 592, 944, 320, 952, 948, 696, 124, 452, 472, 428, 284, 752, 832, 204, 64, 720, 872, 348, 440, 588, 28, 560, 220, 432, 608, 56, 764, 176, 784, 148, 972, 496, 92, 504, 880, 488, 860, 436, 772, 684, 48, 8, 476, 844, 416, 368, 960, 920, 484, 868, 280, 352, 36, 120, 824, 24, 212, 376, 828, 532, 712, 808, 996, 780, 448, 276, 1008, 60, 152, 700, 100, 508, 308, 756, 364, 648, 328, 116, 612, 748, 216, 528, 456, 956, 704, 224, 660, 716, 736, 636, 1016, 132, 604, 128, 788, 576, 672, 196, 904, 668, 848, 840, 888, 724, 896, 300, 584, 540, 912, 980, 876, 424, 404, 624, 208, 596, 992, 836, 640, 232, 160, 500, 516, 396, 332, 336, 12, 800, 656, 140, 112, 296, 156, 228, 812, 968, 32, 288, 908, 536, 732, 460, 1012, 728, 16, 892, 820, 104, 492, 192, 600, 400, 940, 984, 40, 108, 1000, 988, 632, 924, 324, 964, 900, 1020, 628, 616, 804, 384, 664] bit_shuffle = [72, 84, 4, 156, 136, 56, 148, 44, 168, 180, 24, 220, 200, 152, 212, 140, 20, 40, 68, 8, 76, 52, 64, 60, 240, 248, 100, 252, 232, 0, 244, 32, 120, 104, 88, 112, 92, 116, 80, 124, 196, 208, 164, 192, 172, 216, 160, 204, 144, 28, 184, 132, 188, 16, 176, 128, 12, 108, 228, 48, 236, 96, 224, 36, 328, 340, 260, 412, 392, 312, 404, 300, 424, 436, 280, 476, 456, 408, 468, 396, 276, 296, 324, 264, 332, 308, 320, 316, 496, 504, 356, 508, 488, 256, 500, 288, 376, 360, 344, 368, 348, 372, 336, 380, 452, 464, 420, 448, 428, 472, 416, 460, 400, 284, 440, 388, 444, 272, 432, 384, 268, 364, 484, 304, 492, 352, 480, 292, 584, 596, 516, 668, 648, 568, 660, 556, 680, 692, 536, 732, 712, 664, 724, 652, 532, 552, 580, 520, 588, 564, 576, 572, 752, 760, 612, 764, 744, 512, 756, 544, 632, 616, 600, 624, 604, 628, 592, 636, 708, 720, 676, 704, 684, 728, 672, 716, 656, 540, 696, 644, 700, 528, 688, 640, 524, 620, 740, 560, 748, 608, 736, 548, 840, 852, 772, 924, 904, 824, 916, 812, 936, 948, 792, 988, 968, 920, 980, 908, 788, 808, 836, 776, 844, 820, 832, 828, 1008, 1016, 868, 1020, 1000, 768, 1012, 800, 888, 872, 856, 880, 860, 884, 848, 892, 964, 976, 932, 960, 940, 984, 928, 972, 912, 796, 952, 900, 956, 784, 944, 896, 780, 876, 996, 816, 1004, 864, 992, 804] bit_pick = [28, 24, 20, 16, 12, 8, 4, 0, 60, 56, 52, 48, 44, 40, 36, 32, 92, 88, 84, 80, 76, 72, 68, 64, 124, 120, 116, 112, 108, 104, 100, 96, 156, 152, 148, 144, 140, 136, 132, 128, 188, 184, 180, 176, 172, 168, 164, 160, 220, 216, 212, 208, 204, 200, 196, 192, 252, 248, 244, 240, 236, 232, 228, 224, 284, 280, 276, 272, 268, 264, 260, 256, 316, 312, 308, 304, 300, 296, 292, 288, 348, 344, 340, 336, 332, 328, 324, 320, 380, 376, 372, 368, 364, 360, 356, 352, 412, 408, 404, 400, 396, 392, 388, 384, 444, 440, 436, 432, 428, 424, 420, 416, 476, 472, 468, 464, 460, 456, 452, 448, 508, 504, 500, 496, 492, 488, 484, 480, 540, 536, 532, 528, 524, 520, 516, 512, 572, 568, 564, 560, 556, 552, 548, 544, 604, 600, 596, 592, 588, 584, 580, 576, 636, 632, 628, 624, 620, 616, 612, 608, 668, 664, 660, 656, 652, 648, 644, 640, 700, 696, 692, 688, 684, 680, 676, 672, 732, 728, 724, 720, 716, 712, 708, 704, 764, 760, 756, 752, 748, 744, 740, 736, 796, 792, 788, 784, 780, 776, 772, 768, 828, 824, 820, 816, 812, 808, 804, 800, 860, 856, 852, 848, 844, 840, 836, 832, 892, 888, 884, 880, 876, 872, 868, 864, 924, 920, 916, 912, 908, 904, 900, 896, 956, 952, 948, 944, 940, 936, 932, 928, 988, 984, 980, 976, 972, 968, 964, 960, 1020, 1016, 1012, 1008, 1004, 1000, 996, 992] xorbuf = [247, 162, 130, 73, 139, 252, 234, 40, 142, 146, 75, 134, 81, 115, 215, 169, 165, 169, 56, 234, 105, 163, 139, 231, 172, 23, 9, 106, 139, 191, 253, 21] encrypted = open("flag_mixed", "rb").read() xoredx = [] xored = '' for i in range(len(encrypted)): x = xorbuf[i] ^ encrypted[i] xoredx.append(x) xored += "{:08b}".format(x)[::-1] print(xoredx) bitbuf = [None for _ in range(256)] for i, b in enumerate(xored): index = bit_pick[i] // 4 bitbuf[index] = b print(bitbuf) shuffled = [None for _ in range(256)] for i, b in enumerate(bitbuf): index = bit_shuffle[i] // 4 shuffled[index] = b plainbits = [None for _ in range(256)] for i, b in enumerate(shuffled): index = shuffle_2[i] // 4 plainbits[index] = b print(plainbits) flag = "" for i in range(0, len(plainbits), 8): flag += chr(int("".join(plainbits[i:i+8])[::-1], 2)) print(flag)
[rev] Mom's Touch
import gdb gdb.execute("b main") gdb.execute("b *0x8048800") gdb.execute("run < piyo2") flag = '' for _ in range(0x49): # ecx1 = int(gdb.execute("print $ecx", to_string=True).split(" ")[2]) # ecx2 = int(gdb.execute("print $ecx", to_string=True).split(" ")[2]) # ecx3 = int(gdb.execute("print $ecx", to_string=True).split(" ")[2]) mask1 = int(gdb.execute("x/w $bp*4 + 0x80492AC", to_string=True).split("\t")[1]) mask2 = int(gdb.execute("x/w $eax*4 + 0x80492AC", to_string=True).split("\t")[1]) cmpto = int(gdb.execute("x/w $esi*4 + 0x8049144", to_string=True).split("\t")[1]) gdb.execute("step") gdb.execute("step") gdb.execute("step") gdb.execute("step") gdb.execute("set $ZF = 6") gdb.execute("set $eflags |= (1 << $ZF)") flag += chr(mask1 ^ mask2 ^ cmpto) print(flag) gdb.execute("continue") gdb.execute("quit")
