この大会は2017/9/24 0:30(JST)～2017/9/25 0:30(JST)に開催されました。
今回もチームで参戦。結果は全問制覇の3600点で、212チーム中6位でした。
自分で解けた問題をWriteupとして書いておきます。
IMAGEREV (200)
RGBの値をASCIIコードとして結合(3バイト)。それに対して、暗号化してその結果、64バイトになる。暗号化処理の内容は復号するコードにすることがかなり難しい。
そこでencrypted.txtを見ると、64バイトごとに同じようなデータが多数あるので、RとGとBの値はすべて同じであると推定して、256パターンの総当たりで復元する。
またピクセルの数はデータの長さから7371。素因数分解し、その組み合わせの積を考慮して、画像の幅と高さをいろいろと試してみる。
7371 = 3^4 * 7 * 13
結果は幅が351の時にフラグが書かれた画像に復元することができた。そのときのコードは次の通り。
from PIL import Image def bin_return(dec): return(str(format(dec,'b'))) def bin_8bit(dec): return(str(format(dec,'08b'))) def convert_32bit(dec): return(str(format(dec,'032b'))) def convert_64bit(dec): return(str(format(dec,'064b'))) def hex_return(dec): return expand(hex(dec).replace('0x','').replace('L','')) def dec_return_bin(bin_string): return(int(bin_string,2)) def dec_return_hex(hex_string): return(int(hex_string,16)) def some_LP(l,n): l1=[] j=0 k=n while k<len(l)+1: l1.append(l[j:k]) j=k k+=n return(l1) def rotate_right(bit_string,n): bit_list = list(bit_string) count=0 while count <= n-1: list_main=list(bit_list) var_0=list_main.pop(-1) list_main=list([var_0]+list_main) bit_list=list(list_main) count+=1 return(''.join(list_main)) def shift_right(bit_string,n): bit_list=list(bit_string) count=0 while count <= n-1: bit_list.pop(-1) count+=1 front_append=['0']*n return(''.join(front_append+bit_list)) def addition(input_set): value=0 for i in range(len(input_set)): value+=input_set[i] mod_32 = 4294967296 return(value%mod_32) def str_xor(s1,s2): return ''.join([str(int(i)^int(j)) for i,j in zip(s1,s2)]) def str_and(s1,s2): return ''.join([str(int(i)&int(j)) for i,j in zip(s1,s2)]) def str_not(s): return ''.join([str(int(i)^1) for i in s]) def not_and_and_xor(x,y,z): return(str_xor(str_and(x,y),str_and(str_not(x),z))) def and_and_and_xor_xor(x,y,z): return(str_xor(str_xor(str_and(x,y),str_and(x,z)),str_and(y,z))) def some_e0(x): return(str_xor(str_xor(rotate_right(x,2),rotate_right(x,13)),rotate_right(x,22))) def some_e1(x): return(str_xor(str_xor(rotate_right(x,6),rotate_right(x,11)),rotate_right(x,25))) def some_s0(x): return(str_xor(str_xor(rotate_right(x,7),rotate_right(x,18)),shift_right(x,3))) def some_s1(x): return(str_xor(str_xor(rotate_right(x,17),rotate_right(x,19)),shift_right(x,10))) def expand(s): return '0'*(8-len(s))+s def get_pixels_list(filename): im = Image.open(filename) return list(im.getdata()) def data_encrypted(list_of_pixels): data = '' for i in list_of_pixels: d = ''.join([chr(j) for j in i]) d = encryption(d) data += ''.join(d) print len(data) return data def message_pad(bit_list): pad_one = bit_list + '1' pad_len = len(pad_one) k=0 while ((pad_len+k)-448)%512 != 0: k+=1 back_append_0 = '0'*k back_append_1 = convert_64bit(len(bit_list)) return(pad_one+back_append_0+back_append_1) def message_bit_return(string_input): bit_list=[] for i in range(len(string_input)): bit_list.append(bin_8bit(ord(string_input[i]))) return(''.join(bit_list)) def message_pre_pro(input_string): bit_main = message_bit_return(input_string) return(message_pad(bit_main)) def message_parsing(input_string): return(some_LP(message_pre_pro(input_string),32)) def message_schedule(index,w_t): new_word = convert_32bit(addition([int(some_s1(w_t[index-2]),2),int(w_t[index-7],2),int(some_s0(w_t[index-15]),2),int(w_t[index-16],2)])) return(new_word) initial=['6a09e667','bb67ae85','3c6ef372','a54ff53a','510e527f','9b05688c','1f83d9ab','5be0cd19'] values=['428a2f98','71374491','b5c0fbcf','e9b5dba5','3956c25b','59f111f1','923f82a4','ab1c5ed5','d807aa98','12835b01','243185be','550c7dc3','72be5d74','80deb1fe','9bdc06a7','c19bf174','e49b69c1','efbe4786','0fc19dc6','240ca1cc','2de92c6f','4a7484aa','5cb0a9dc','76f988da','983e5152','a831c66d','b00327c8','bf597fc7','c6e00bf3','d5a79147','06ca6351','14292967','27b70a85','2e1b2138','4d2c6dfc','53380d13','650a7354','766a0abb','81c2c92e','92722c85','a2bfe8a1','a81a664b','c24b8b70','c76c51a3','d192e819','d6990624','f40e3585','106aa070','19a4c116','1e376c08','2748774c','34b0bcb5','391c0cb3','4ed8aa4a','5b9cca4f','682e6ff3','748f82ee','78a5636f','84c87814','8cc70208','90befffa','a4506ceb','bef9a3f7','c67178f2'] def encryption(input_string): w_t=message_parsing(input_string) a=convert_32bit(dec_return_hex(initial[0])) b=convert_32bit(dec_return_hex(initial[1])) c=convert_32bit(dec_return_hex(initial[2])) d=convert_32bit(dec_return_hex(initial[3])) e=convert_32bit(dec_return_hex(initial[4])) f=convert_32bit(dec_return_hex(initial[5])) g=convert_32bit(dec_return_hex(initial[6])) h=convert_32bit(dec_return_hex(initial[7])) for i in range(0,64): if i <= 15: t_1=addition([int(h,2),int(some_e1(e),2),int(not_and_and_xor(e,f,g),2),int(values[i],16),int(w_t[i],2)]) t_2=addition([int(some_e0(a),2),int(and_and_and_xor_xor(a,b,c),2)]) h=g g=f f=e e=addition([int(d,2),t_1]) d=c c=b b=a a=addition([t_1,t_2]) a=convert_32bit(a) e=convert_32bit(e) if i > 15: w_t.append(message_schedule(i,w_t)) t_1=addition([int(h,2),int(some_e1(e),2),int(not_and_and_xor(e,f,g),2),int(values[i],16),int(w_t[i],2)]) t_2=addition([int(some_e0(a),2),int(and_and_and_xor_xor(a,b,c),2)]) h=g g=f f=e e=addition([int(d,2),t_1]) d=c c=b b=a a=addition([t_1,t_2]) a=convert_32bit(a) e=convert_32bit(e) value_0 = addition([dec_return_hex(initial[0]),int(a,2)]) value_1 = addition([dec_return_hex(initial[1]),int(b,2)]) value_2 = addition([dec_return_hex(initial[2]),int(c,2)]) value_3 = addition([dec_return_hex(initial[3]),int(d,2)]) value_4 = addition([dec_return_hex(initial[4]),int(e,2)]) value_5 = addition([dec_return_hex(initial[5]),int(f,2)]) value_6 = addition([dec_return_hex(initial[6]),int(g,2)]) value_7 = addition([dec_return_hex(initial[7]),int(h,2)]) value = (hex_return(value_0),hex_return(value_1),hex_return(value_2),hex_return(value_3),hex_return(value_4),hex_return(value_5),hex_return(value_6),hex_return(value_7)) return(value) def get_string(d): remain = d s = '' for i in range(3): code = remain / (256 ** (2 - i)) s += chr(code) remain = remain % (256 ** (2 - i)) return s with open('encrypted.txt', 'r') as f: data = f.read() e = [] for i in range(256): val = i + i*256 + i*256*256 s = get_string(val) e.append(''.join(encryption(s))) width = 351 height = 7371 / width img = Image.new('RGB', (width, height), (255, 255, 255)) for i in range(0, len(data), 64): pixel_data = data[i:i+64] color_code = e.index(pixel_data) x = (i / 64) % width y = (i / 64) / width img.putpixel((x, y), (color_code, color_code, color_code)) img.save('flag.png')
$ echo -n 'CTF{d4mm17_y0u_f0und_my_h1dd3n_5h4_h45h}' | sha256sum d66f0a384abd48764b5caecb3e204c88746661c3d7f25471d79ac265c59c9085 -
d66f0a384abd48764b5caecb3e204c88746661c3d7f25471d79ac265c59c9085
COMPLEX-RSA (200)
公開鍵が2つと暗号ファイルが渡される。2回別の鍵で暗号化しているので、それを復号する問題。
$ openssl rsa -pubin -text < pubkey1 Public-Key: (1026 bit) Modulus: 03:15:4c:a2:cd:44:39:ad:97:e0:38:7a:51:4c:97: bf:21:0c:f7:5f:3b:cf:26:25:94:68:3b:b5:3c:e6: 99:48:12:df:6a:19:55:c4:4f:9f:12:e9:9c:2a:69: 8c:b9:7f:0e:47:e8:e8:d1:48:a7:f3:47:2d:2b:4d: e2:54:10:ad:f2:1e:49:8b:b9:b4:66:5a:0c:66:d8: d2:66:ff:20:63:7e:ac:f2:71:8d:9a:59:c1:c4:a3: cf:02:2f:0b:f2:8d:53:89:d5:86:41:f3:dd:99:4e: f2:ff:fa:4b:70:d3:d3:98:e9:48:42:00:f8:77:93: 06:10:13:a8:ed:07:2c:d7:7f Exponent: 37507589401 (0x8bba06519) writing RSA key -----BEGIN PUBLIC KEY----- MIGhMA0GCSqGSIb3DQEBAQUAA4GPADCBiwKBgQMVTKLNRDmtl+A4elFMl78hDPdf O88mJZRoO7U85plIEt9qGVXET58S6ZwqaYy5fw5H6OjRSKfzRy0rTeJUEK3yHkmL ubRmWgxm2NJm/yBjfqzycY2aWcHEo88CLwvyjVOJ1YZB892ZTvL/+ktw09OY6UhC APh3kwYQE6jtByzXfwIFCLugZRk= -----END PUBLIC KEY----- yoshinori@yoshinori-virtual-machine:/mnt/hgfs/Shared$ openssl rsa -pubin -text < pubkey2 Public-Key: (1026 bit) Modulus: 03:15:4c:a2:cd:44:39:ad:97:e0:38:7a:51:4c:97: bf:21:0c:f7:5f:3b:cf:26:25:94:68:3b:b5:3c:e6: 99:48:12:df:6a:19:55:c4:4f:9f:12:e9:9c:2a:69: 8c:b9:7f:0e:47:e8:e8:d1:48:a7:f3:47:2d:2b:4d: e2:54:10:ad:f2:1e:49:8b:b9:b4:66:5a:0c:66:d8: d2:66:ff:20:63:7e:ac:f2:71:8d:9a:59:c1:c4:a3: cf:02:2f:0b:f2:8d:53:89:d5:86:41:f3:dd:99:4e: f2:ff:fa:4b:70:d3:d3:98:e9:48:42:00:f8:77:93: 06:10:13:a8:ed:07:2c:d7:7f Exponent: 1a:1b:48:c3:a6:ce:4a:6a:f6:e3:cb:78:c5:5f:ac: 7f:59:29:6f:41:bb:11:e5:8a:30:1f:b8:d2:f3:c4: 7e:bb:15:fa:3e:68:e9:f7:7f:8c:52:39:3b:e2:22: 17:5d:e4:a7:bc:55:d9:9d:51:80:1b:5a:1d:be:72: dd:6e:ff:ae:52:39:f3:a4:48:d3:e9:ef:5a:a1:c9: 54:5e:1a:38:49:18:9b:e6:3c:49:fe:3b:94:92:54: d4:20:d9:81:76:77:a7:db:4a:d1:f3:f5:df:99:b3: 25:7d:d6:04:c5:72:ce:e2:5e:43:c2:69:43:cf:d1: 64:91:80:3b writing RSA key -----BEGIN PUBLIC KEY----- MIIBGjANBgkqhkiG9w0BAQEFAAOCAQcAMIIBAgKBgQMVTKLNRDmtl+A4elFMl78h DPdfO88mJZRoO7U85plIEt9qGVXET58S6ZwqaYy5fw5H6OjRSKfzRy0rTeJUEK3y HkmLubRmWgxm2NJm/yBjfqzycY2aWcHEo88CLwvyjVOJ1YZB892ZTvL/+ktw09OY 6UhCAPh3kwYQE6jtByzXfwJ8GhtIw6bOSmr248t4xV+sf1kpb0G7EeWKMB+40vPE frsV+j5o6fd/jFI5O+IiF13kp7xV2Z1RgBtaHb5y3W7/rlI586RI0+nvWqHJVF4a OEkYm+Y8Sf47lJJU1CDZgXZ3p9tK0fP135mzJX3WBMVyzuJeQ8JpQ8/RZJGAOw== -----END PUBLIC KEY-----
nの値が同じで、eの値はそれぞれ次の通り。
n = 0x03154ca2cd4439ad97e0387a514c97bf210cf75f3bcf262594683bb53ce6994812df6a1955c44f9f12e99c2a698cb97f0e47e8e8d148a7f3472d2b4de25410adf21e498bb9b4665a0c66d8d266ff20637eacf2718d9a59c1c4a3cf022f0bf28d5389d58641f3dd994ef2fffa4b70d3d398e9484200f87793061013a8ed072cd77f e1 = 0x8bba06519 e2 = 0x1a1b48c3a6ce4a6af6e3cb78c55fac7f59296f41bb11e58a301fb8d2f3c47ebb15fa3e68e9f77f8c52393be222175de4a7bc55d99d51801b5a1dbe72dd6effae5239f3a448d3e9ef5aa1c9545e1a3849189be63c49fe3b949254d420d9817677a7db4ad1f3f5df99b3257dd604c572cee25e43c26943cfd16491803b
c1 = pow(m, e1, n) c = pow(c1, e2, n) → c = pow(m, e1*e2, n)
Wiener's attackで復号する。
from fractions import Fraction def egcd(a, b): x,y, u,v = 0,1, 1,0 while a != 0: q, r = b//a, b%a m, n = x-u*q, y-v*q b,a, x,y, u,v = a,r, u,v, m,n gcd = b return gcd, x, y def decrypt(p, q, e, c): n = p * q phi = (p - 1) * (q - 1) gcd, a, b = egcd(e, phi) d = a pt = pow(c, d, n) return hex(pt)[2:-1].decode('hex') def continued_fractions(n,e): cf = [0] while e != 0: cf.append(int(n/e)) N = n n = e e = N%e return cf def calcKD(cf): kd = list() for i in range(1,len(cf)+1): tmp = Fraction(0) for j in cf[1:i][::-1]: tmp = 1/(tmp+j) kd.append((tmp.numerator,tmp.denominator)) return kd def int_sqrt(n): def f(prev): while True: m = (prev + n/prev)/2 if m >= prev: return prev prev = m return f(n) def calcPQ(a,b): if a*a < 4*b or a < 0: return None c = int_sqrt(a*a-4*b) p = (a + c) /2 q = (a - c) /2 if p + q == a and p * q == b: return (p,q) else: return None def wiener(n,e): kd = calcKD(continued_fractions(n,e)) for (k,d) in kd: if k == 0: continue if (e*d-1) % k != 0: continue phin = (e*d-1) / k if phin >= n: continue ans = calcPQ(n-phin+1,n) if ans is None: continue return (ans[0],ans[1]) n = 0x03154ca2cd4439ad97e0387a514c97bf210cf75f3bcf262594683bb53ce6994812df6a1955c44f9f12e99c2a698cb97f0e47e8e8d148a7f3472d2b4de25410adf21e498bb9b4665a0c66d8d266ff20637eacf2718d9a59c1c4a3cf022f0bf28d5389d58641f3dd994ef2fffa4b70d3d398e9484200f87793061013a8ed072cd77f e1 = 0x8bba06519 e2 = 0x1a1b48c3a6ce4a6af6e3cb78c55fac7f59296f41bb11e58a301fb8d2f3c47ebb15fa3e68e9f77f8c52393be222175de4a7bc55d99d51801b5a1dbe72dd6effae5239f3a448d3e9ef5aa1c9545e1a3849189be63c49fe3b949254d420d9817677a7db4ad1f3f5df99b3257dd604c572cee25e43c26943cfd16491803b e = e1 * e2 p, q = wiener(n, e) with open('flag.enc', 'rb') as f: c = int(f.read().encode('hex'), 16) flag = decrypt(p, q, e, c) print flag
実行結果は CTF{c0n6r47zzz_y0u_f0und_0ur_h1dd3n_w13n3r!!}
$ echo -n 'CTF{c0n6r47zzz_y0u_f0und_0ur_h1dd3n_w13n3r!!}' | sha256sum c0081b21d2c1d3f581914be8bc4ce98158b9eafbcf68dda83f6eddae99d4b1e2 -
c0081b21d2c1d3f581914be8bc4ce98158b9eafbcf68dda83f6eddae99d4b1e2
STEREOTYPES (300)
$ openssl rsa -pubin -text < pubkey Public-Key: (2048 bit) Modulus: 00:87:ae:91:10:c6:f2:df:9a:d5:a7:47:c9:c2:5b: 60:57:6a:c2:bf:17:76:00:2d:4e:5d:ba:17:72:ae: a0:b8:70:34:94:29:9c:f8:51:38:be:84:bf:2d:9f: 4f:88:79:5e:9c:cd:63:45:4f:df:55:32:57:da:09: 5a:0d:ea:cd:44:6f:d9:a9:4d:90:e4:06:d3:86:1c: c7:4e:cb:5c:a1:1c:6e:ce:b3:fd:0b:13:bc:23:26: 7f:9f:14:ef:20:19:3e:61:02:70:3c:c3:b3:fd:f7: a7:f3:e7:20:3b:9d:43:4e:c9:66:d9:04:ab:d8:0b: 68:37:3f:fb:87:f3:b4:06:ff:53:af:8b:9f:85:48: dd:3a:da:63:4e:06:f0:87:ed:4a:d5:98:cd:a1:75: 20:02:45:e0:b5:ec:d4:5e:83:11:60:ef:7e:c0:b9: 32:7a:28:18:70:97:1e:c7:0d:63:2e:ed:79:a2:1d: a6:35:18:77:b9:46:dd:54:b2:eb:a1:6d:ad:7b:f5: d2:11:73:d1:5b:22:3a:4c:58:12:c6:8c:e9:41:4f: 3f:ba:bf:03:ee:d2:8f:fc:65:64:6d:4f:32:81:cc: 6a:fe:8d:21:c1:45:27:ef:50:dd:0d:50:d6:58:99: 69:5b:53:c6:b6:37:4c:ec:05:e3:81:53:ca:65:e8: 73:f1 Exponent: 7 (0x7) writing RSA key -----BEGIN PUBLIC KEY----- MIIBIDANBgkqhkiG9w0BAQEFAAOCAQ0AMIIBCAKCAQEAh66REMby35rVp0fJwltg V2rCvxd2AC1OXboXcq6guHA0lCmc+FE4voS/LZ9PiHlenM1jRU/fVTJX2glaDerN RG/ZqU2Q5AbThhzHTstcoRxuzrP9CxO8IyZ/nxTvIBk+YQJwPMOz/fen8+cgO51D Tslm2QSr2AtoNz/7h/O0Bv9Tr4ufhUjdOtpjTgbwh+1K1ZjNoXUgAkXgtezUXoMR YO9+wLkyeigYcJcexw1jLu15oh2mNRh3uUbdVLLroW2te/XSEXPRWyI6TFgSxozp QU8/ur8D7tKP/GVkbU8ygcxq/o0hwUUn71DdDVDWWJlpW1PGtjdM7AXjgVPKZehz 8QIBBw== -----END PUBLIC KEY-----
n = 0x0087ae9110c6f2df9ad5a747c9c25b60576ac2bf1776002d4e5dba1772aea0b8703494299cf85138be84bf2d9f4f88795e9ccd63454fdf553257da095a0deacd446fd9a94d90e406d3861cc74ecb5ca11c6eceb3fd0b13bc23267f9f14ef20193e6102703cc3b3fdf7a7f3e7203b9d434ec966d904abd80b68373ffb87f3b406ff53af8b9f8548dd3ada634e06f087ed4ad598cda175200245e0b5ecd45e831160ef7ec0b9327a281870971ec70d632eed79a21da6351877b946dd54b2eba16dad7bf5d21173d15b223a4c5812c68ce9414f3fbabf03eed28ffc65646d4f3281cc6afe8d21c14527ef50dd0d50d65899695b53c6b6374cec05e38153ca65e873f1 e = 7
平文は末尾以外わかっているので、Coppersmith's Attackを実行。
# coppersmith_attack.sage n = 0x0087ae9110c6f2df9ad5a747c9c25b60576ac2bf1776002d4e5dba1772aea0b8703494299cf85138be84bf2d9f4f88795e9ccd63454fdf553257da095a0deacd446fd9a94d90e406d3861cc74ecb5ca11c6eceb3fd0b13bc23267f9f14ef20193e6102703cc3b3fdf7a7f3e7203b9d434ec966d904abd80b68373ffb87f3b406ff53af8b9f8548dd3ada634e06f087ed4ad598cda175200245e0b5ecd45e831160ef7ec0b9327a281870971ec70d632eed79a21da6351877b946dd54b2eba16dad7bf5d21173d15b223a4c5812c68ce9414f3fbabf03eed28ffc65646d4f3281cc6afe8d21c14527ef50dd0d50d65899695b53c6b6374cec05e38153ca65e873f1 e = 7 with open('ciphertext', 'rb') as f: c = int(f.read().encode('hex'), 16) with open('plaintext', 'r') as f: m0 = f.read() m0 = int(m0.replace('X', '\x00').encode('hex'), 16) kbits = 15 * 8 PR.<x> = PolynomialRing(Zmod(n)) f = (m0 + x)^e - c x0 = f.small_roots(X=2^kbits, beta=1)[0] plaintext = ('%x' % (m0 + x0)).decode('hex') print plaintext
復号結果は次の通り。
Welcome to BackdoorCTF17. Just one advice Never ignore the challenge names, they provides the maximum hint. Okay now let's leave the boring stuff apart i know you are eagerly waiting to gain some points So here it is : CTF{y0u_607_17}
$ echo -n 'CTF{y0u_607_17}' | sha256sum 229eab315f374015ad0e8a0374b6df89a2510538a305cbd2b88df81eb05349a6 -
229eab315f374015ad0e8a0374b6df89a2510538a305cbd2b88df81eb05349a6
