ISITDTU CTF 2019 Write-up
はじめに
2019/06/29 ~ 2019/06/30に開催されたISITDTU CTFに個人で参加しました.
成績
69位(327チーム中)でした.
Welcome
Welcome [10pts, 263solves]
Welcome to our Discord
アプローチ:Discordに参加する
ISITDTU{Welcome_everyone_to_ISITDTUCTF}
Rev
Recovery [100pts, 79solves]
Could you help me recovery my number?
Note: The flag is not in flag format, please wrap it in format when you submit. ISITDTU{x, y, z, ...}
File: recovery
> file recovery.jar recovery.jar: Java archive data (JAR)
アプローチ:デコンパイル + Pre-order
ダウンロードしたjar
ファイルをデコンパイルします (JD-GUI
を使いました).
// [snip] private void btnSubmitActionPerformed(ActionEvent evt) { try { String txtInputS = this.txtInput.getText().trim(); String[] str = txtInputS.split(","); int[] input = new int[str.length]; for (int i = 0; i < str.length; i++) { input[i] = Integer.parseInt(str[i].trim()); } int[] s = { 9, 11, 33, 35, 38, 40, 44, 48, 61, 85, 89, 101, 106, 110, 135, 150, 159, 180, 188, 200, 201, 214, 241, 253, 268, 269, 275, 278, 285, 301, 301, 327, 356, 358, 363, 381, 396, 399, 413, 428, 434, 445, 449, 462, 471, 476, 481, 492, 496, 497, 509, 520, 526, 534, 540, 589, 599, 613, 621, 621, 623, 628, 634, 650, 652, 653, 658, 665, 679, 691, 708, 711, 716, 722, 752, 756, 764, 771, 773, 786, 807, 808, 826, 827, 836, 842, 856, 867, 875, 877, 879, 889, 892, 922, 946, 951, 965, 980, 993, 996 }; int[] l = { 35, 33, 44, 40, 38, 48, 11, 85, 89, 61, 110, 150, 159, 135, 188, 200, 180, 106, 101, 214, 268, 275, 269, 253, 241, 201, 9, 301, 301, 285, 327, 356, 363, 396, 413, 399, 445, 434, 462, 449, 428, 471, 481, 492, 496, 497, 476, 381, 358, 278, 534, 526, 520, 613, 599, 623, 621, 621, 589, 540, 628, 650, 653, 652, 665, 691, 679, 711, 756, 752, 722, 716, 807, 786, 773, 771, 826, 808, 827, 764, 856, 875, 867, 842, 836, 708, 879, 892, 889, 922, 877, 951, 946, 658, 980, 996, 993, 965, 634, 509 }; if (check(s, new CTF_Problem().getResultA(input))) { if (check(l, new CTF_Problem().getResultB(input))) { JOptionPane.showMessageDialog(this.rootPane, "Recovery successfull\nFlag is your solution"); } else { JOptionPane.showMessageDialog(this.rootPane, "Wrong answer! Try angain..."); } } else { JOptionPane.showMessageDialog(this.rootPane, "Wrong answer! Try angain..."); } } catch (Exception ex) { JOptionPane.showMessageDialog(this.rootPane, "Wrong answer! Try angain..."); } } // [snip]
コードを読むと入力値に対して何らかの処理(getResultA()
, getResultB()
)をした後,s
, l
と比較を行っていることが分かります.
次にgetResultA()
, getResultB()
について確認します.
// [snip] public int[] getResultA(int[] a) { CTF_Problem b = new CTF_Problem(); l = m = 0; for (int i = 0; i < arr1.length; i++) { b.insert(a[i]); } b.inOrder(root); return arr1; } public int[] getResultB(int[] a) { CTF_Problem b = new CTF_Problem(); l = m = 0; for (int i = 0; i < arr2.length; i++) { b.insert(a[i]); } b.postOrder(root); return arr2; } // [snip]
getResultA()
ではPre-order
からIn-order
への変換,getResultB()
ではPre-order
からPost-order
への変換を行っています.
したがって,s
, l
はそれぞれIn-order
, Post-order
であり,入力値としてPre-order
を与えればflag
を取得できることが分かります.
以下のページを参考にIn-order
, Post-order
からPre-order
を生成しました.
ISITDTU{509, 278, 9, 201, 101, 61, 11, 48, 38, 33, 35, 40, 44, 89, 85, 106, 180, 135, 110, 159, 150, 200, 188, 241, 214, 253, 269, 268, 275, 358, 356, 327, 285, 301, 301, 381, 363, 476, 471, 428, 399, 396, 413, 449, 434, 445, 462, 497, 496, 492, 481, 634, 628, 540, 520, 526, 534, 589, 621, 599, 613, 621, 623, 965, 658, 652, 650, 653, 946, 877, 708, 679, 665, 691, 836, 764, 716, 711, 722, 752, 756, 827, 808, 771, 773, 786, 807, 826, 842, 867, 856, 875, 922, 889, 879, 892, 951, 993, 980, 996}
Pytecode [100pts, 74solves]
File: Pytecode
> file pytecode pytecode: ASCII text
C0rr3ct func: 6 0 LOAD_CONST 1 ('Wow!!!You so best^_^') 3 PRINT_ITEM 4 PRINT_NEWLINE 5 LOAD_CONST 0 (None) 8 RETURN_VALUE Ch3cking func: 8 0 LOAD_CONST 1 (0) 3 STORE_FAST 1 (check) 9 6 LOAD_GLOBAL 0 (ord) 9 LOAD_FAST 0 (flag) 12 LOAD_CONST 1 (0) 15 BINARY_SUBSCR 16 CALL_FUNCTION 1 19 LOAD_CONST 2 (52) 22 BINARY_ADD 23 LOAD_GLOBAL 0 (ord) 26 LOAD_FAST 0 (flag) 29 LOAD_CONST 3 (-1) 32 BINARY_SUBSCR 33 CALL_FUNCTION 1 36 COMPARE_OP 3 (!=) 39 POP_JUMP_IF_TRUE 78 [snip]
アプローチ:dis (Python バイトコードの逆アセンブラ)のドキュメントを読む
flag
に関する処理をPythonっぽく書き換えると以下のようになります.
flag[:7] == 'ISITDTU' flag[9] == flag[14] flag[14] == flag[19] flag[19] == flag[24] flag[8] == '1' flag[8] == flag[16] (flag[16] == '1') flag[10:14] == 'd0nT' int(flag[18]) + int(flag[23]) + int(flag[28]) == 9 flag[18] == flag[28] flag[15] == 'L' ord(flag[17]) ^ -10 == -99 (flag[17] == 'k') ord(flag[20]) + 2 == ord(flag[27]) ord(flag[27]) < 123 ord(flag[20]) > 97 ord(flag[27]) % 100 == 0 (flag[27] == 'd', flag[20] == 'b') flag[25] == 'C' ord(flag[26]) % 2 == 0 ord(flag[26]) % 3 == 0 ord(flag[26]) % 4 == 0 (flag[26] == '0') int(flag[23]) == 3 (flag[23] == '3') flag[22] == lower(flag[13]) (flag[22] == 't') temp = 0 for i in flag: temp += ord(i) temp == 2441
この情報を元にflag
を復元するとISITDTU{1*d0nT*L1k3*b*t3*C0d3}
(*
は不明な文字) になります.
不明な文字を以下の情報(制約)を使って全探索します.
flag[9] == flag[14] flag[14] == flag[19] flag[19] == flag[24] temp = 0 for i in flag: temp += ord(i) temp == 2441
ISITDTU{1_d0nT_L1k3_b:t3_C0d3}
Programming
Do you like math? [100pts, 106solves]
nc 104.154.120.223 8083
> nc 104.154.120.223 8083 ##### ####### ##### # # # # # # # # ## # # # # # # # ##### ##### ###### ####### ##### # # # # # # # ##### # # # # # # # ####### ##### ####### ##### >>> 1127 Wrong!
アプローチ:頑張ってパースしてシグネチャで判定
何度かnc
すると次のことが分かります.
- 一桁または二桁の演算を行っている
- 演算は加算,減算,乗算のみ (除算はなし)
- 表示される文字は
0
~9
,+
,-
,*
,=
のみ
めちゃくちゃ面倒くさい
以下のようにして演算を行います.
ex.
表示される文字
# ##### # # # # # # # # # # # # ##### # # ####### ###### ####### # # # ##### # # # # # # #####
スペースで分割
# # # # # # # ####### # # # # # # ####### # # # # ##### # # # # ###### # # # ##### ##### #####
1行分の#
を数え,文字として連結させる (これをシグネチャとした)
#
のカウントだけだと6
,9
が同値だったりして面倒くさい
4: 12227110 *: 02272200 9: 52261250 =: 00505000
以下ソルバです.
#!/usr/bin/env python3 # -*- coding: utf-8 -*- from socket import * s = socket(AF_INET, SOCK_STREAM) s.connect(('104.154.120.223', 8083)) def parse(lines): index = [0] for i in range(len(lines[0])): space_check = True for j in range(8): if lines[j][i] == '#': space_check = False break if space_check: index.append(i) f = '' for i in range(len(index) - 1): if index[i] + 1 == index[i+1]: continue signature = '' for j in range(8): signature += str(lines[j][index[i]:index[i+1]].count('#')) print('signature: {}'.format(signature)) if signature == '32222230': f += '0' elif signature == '12211150': f += '1' elif signature == '52151170': f += '2' elif signature == '52151250': f += '3' elif signature == '12227110': f += '4' elif signature == '71161250': f += '5' elif signature == '52162250': f += '6' elif signature == '72111110': f += '7' elif signature == '52252250': f += '8' elif signature == '52261250': f += '9' elif signature == '00505000': f += '=' elif signature == '02272200': f += '*' elif signature == '00050000': f += '-' elif signature == '01151100': f += '+' return f for i in range(200): print(i) rec = s.recv(1024).decode('utf-8') temp = s.recv(1024).decode('utf-8') if 'ISI' in rec: print(rec) break lines = rec.split('\n')[1:-1] prob = parse(lines) print(rec) print(prob) result = str(eval(prob[:-1])).encode('utf_8') + b'\n' print(result) s.send(result) print('-'*50)
> python solve.py 0 signature: 52151170 signature: 52151250 signature: 02272200 signature: 12211150 signature: 71161250 signature: 00505000 ##### ##### # ####### # # # # # # ## # # # # # # # # ##### ##### ##### ####### # ###### # # # # # # ##### # # # # # # # # ####### ##### ##### ##### 23*15= b'345\n' -------------------------------------------------- [snip] -------------------------------------------------- 99 signature: 52151250 signature: 32222230 signature: 02272200 signature: 12211150 signature: 52261250 signature: 00505000 ##### ### # ##### # # # # # # ## # # # # # # # # # # # ##### ##### # # ####### # ###### # # # # # # # ##### # # # # # # # # # ##### ### ##### ##### 30*19= b'570\n' -------------------------------------------------- 100 Good job, this is your flag: ISITDTU{sub5cr1b3_b4_t4n_vl0g_4nd_p3wd13p13}
100問解くとflag
が降ってきます.
ISITDTU{sub5cr1b3_b4_t4n_vl0g_4nd_p3wd13p13}
balls [100pts, 76solves]
There are 12 balls, all of equal size, but only 11 are of equal weight, one fake ball is either lighter or heavier. Can you find the fake ball by using a balance scale only 3 times?
nc 34.68.81.63 6666
> nc 34.68.81.63 6666 ≡≡≡≡≡≡/\≡≡≡≡≡≡ /\ ││ /\ / \ ││ / \ ╚════╝ ││ ╚════╝ _ _ _ _ _ _ ││ _ _ _ _ _ _ (_) (_) (_) (_) (_) (_) ████ (_) (_) (_) (_) (_) (_) There are 12 balls, all of equal size, but only 11 are of equal weight, one fake ball is either lighter or heavier. Can you find the fake ball by using a balance scale only 3 times? Example weigh balls at position 1,2,3 vs 4,5,6: 1,2,3 4,5,6 Round 1 : Weighting 1: 1,2,3,4 5,6,7,8 The left is lighter than the right Weighting 2: 1,2,3,4 5,6,7,8 The left is lighter than the right Weighting 3: 1,2,3,4 5,6,7,8 The left is lighter than the right The fake ball is : 12 WRONG!!!!!! The fake ball is : 3
アプローチ:12 balls problemとかでググる
12個あるボールの中に1つだけ重さが異なるボールが混ざっているのではかりを3回だけ使ってどのボールがfake
なのか判定しましょうという問題.
いや、3回だけじゃ無理でしょと思ったので自力で考えずにググりました.
本当に3回で判定できてすごいな〜となりました.
以下めっちゃ汚いソルバです.
#!/usr/bin/env python3 # -*- coding: utf_8 -*- from socket import * s = socket(AF_INET, SOCK_STREAM) s.connect(('34.68.81.63', 6666)) def balls_round(): rec = s.recv(2048).decode('utf_8') fake = '' s.send('1,2,3,4 5,6,7,8\n'.encode('utf_8')) rec = s.recv(2048).decode('utf_8') print(rec) if 'equally' in rec: print('equally') rec = s.recv(2048).decode('utf_8') s.send('8,9 10,11\n'.encode('utf_8')) print(rec) rec = s.recv(2048).decode('utf_8') print(rec) if 'equally' in rec: print('equally') fake = '12' s.send('11 12\n'.encode('utf_8')) rec = s.recv(2048).decode('utf_8') print(rec) elif 'heavier' in rec: print('heavier') s.send('10 11\n'.encode('utf_8')) rec = s.recv(2048).decode('utf_8') print(rec) rec = s.recv(2048).decode('utf_8') print(rec) if 'equally' in rec: print('equally') fake = '9' elif 'heavier' in rec: print('heavier') fake = '11' elif 'lighter' in rec : print('lighter') fake = '10' elif 'lighter' in rec : print('lighter') s.send('10 11\n'.encode('utf_8')) rec = s.recv(2048).decode('utf_8') print(rec) rec = s.recv(2048).decode('utf_8') print(rec) if 'equally' in rec: print('equally') fake = '9' elif 'heavier' in rec: print('heavier') fake = '10' elif 'lighter' in rec : print('lighter') fake = '11' elif 'heavier' in rec: print('heavier') rec = s.recv(2048).decode('utf_8') s.send('1,2,5 3,6,9\n'.encode('utf_8')) print(rec) rec = s.recv(2048).decode('utf_8') print(rec) if 'equally' in rec: print('equally') s.send('7 8\n'.encode('utf_8')) rec = s.recv(2048).decode('utf_8') print(rec) rec = s.recv(2048).decode('utf_8') print(rec) if 'equally' in rec: print('equally') fake = '4' elif 'heavier' in rec: print('heavier') fake = '8' elif 'lighter' in rec : print('lighter') fake = '7' elif 'heavier' in rec: print('heavier') s.send('1 2\n'.encode('utf_8')) rec = s.recv(2048).decode('utf_8') print(rec) rec = s.recv(2048).decode('utf_8') print(rec) if 'equally' in rec: print('equally') fake = '6' elif 'heavier' in rec: print('heavier') fake = '1' elif 'lighter' in rec : print('lighter') fake = '2' elif 'lighter' in rec : print('lighter') s.send('5 9\n'.encode('utf_8')) rec = s.recv(2048).decode('utf_8') print(rec) rec = s.recv(2048).decode('utf_8') print(rec) if 'equally' in rec: print('equally') fake = '3' elif 'lighter' in rec : print('lighter') fake = '5' elif 'lighter' in rec : print('lighter') rec = s.recv(2048).decode('utf_8') s.send('5,6,1 7,2,9\n'.encode('utf_8')) print(rec) rec = s.recv(2048).decode('utf_8') print(rec) if 'equally' in rec: print('equally') s.send('3 4\n'.encode('utf_8')) rec = s.recv(2048).decode('utf_8') print(rec) rec = s.recv(2048).decode('utf_8') print(rec) if 'equally' in rec: print('equally') fake = '8' elif 'heavier' in rec: print('heavier') fake = '4' elif 'lighter' in rec : print('lighter') fake = '3' elif 'heavier' in rec: print('heavier') s.send('5 6\n'.encode('utf_8')) rec = s.recv(2048).decode('utf_8') print(rec) rec = s.recv(2048).decode('utf_8') print(rec) if 'equally' in rec: print('equally') fake = '2' elif 'heavier' in rec: print('heavier') fake = '5' elif 'lighter' in rec : print('lighter') fake = '6' elif 'lighter' in rec : print('lighter') s.send('1 9\n'.encode('utf_8')) rec = s.recv(2048).decode('utf_8') print(rec) rec = s.recv(2048).decode('utf_8') print(rec) if 'equally' in rec: print('equally') fake = '7' elif 'lighter' in rec : print('lighter') fake = '1' print(fake) s.send(fake.encode('utf_8') + b'\n') rec = s.recv(2048).decode('utf_8') print(rec) print('-----') rec = s.recv(2048).decode('utf_8') for i in range(51): print('Round: {}'.format(i)) if i == 50: rec = s.recv(2048).decode('utf_8') print(rec) break balls_round()
> python solve.py Round: 0 Both are equally heavy equally Weighting 2: The left is lighter than the right lighter Weighting 3: The left is heavier than the right The fake ball is : heavier 10 EXACTLY, The fake ball is 10 ----- [snip] ----- Round: 49 The left is heavier than the right heavier Weighting 2: Both are equally heavy equally Weighting 3: Both are equally heavy The fake ball is : equally 4 EXACTLY, The fake ball is 4 ----- Round: 50 ISITDTU{y0u_hav3_200iq!!!!}
50問解くとflag
が降ってきます.
ISITDTU{y0u_hav3_200iq!!!!}
Cryptography
Old story [239pts, 47solves]
This is an old story about wheat and chessboard, and it's easy, right?
File: Old_story (cipher.txt)file cipher.txt cipher.txt: ASCII text, with very long lines, with no line terminators
[524288, 4194304, 16384, 1024, 4194304, 32, 262144, 2097152, 4194304, 16777216, 70368744177664, 2251799813685248, 8192, 8388608, 8192, 4503599627370496, 16777216, 36028797018963968, 16384, 2199023255552, 67108864, 1048576, 2097152, 18014398509481984, 33554432, 68719476736, 4, 17179869184, 536870912, 549755813888, 262144, 4294967296, 16384, 128, 288230376151711744, 137438953472, 16777216, 36028797018963968, 1024, 4503599627370496, 16384, 68719476736, 262144, 4611686018427387904]
cipher.txt
を見ても何も分からないのでwheat and chessboard
とかでググります.
2の累乗とチェスボードが関係する問題だということが推測できます.
チェスボードは64マスなのでこれはbase64
だとエスパーできます(???).
以下ソルバです.
import math import string import base64 enc = [524288, 4194304, 16384, 1024, 4194304, 32, 262144, 2097152, 4194304, 16777216, 70368744177664, 2251799813685248, 8192, 8388608, 8192, 4503599627370496, 16777216, 36028797018963968, 16384, 2199023255552, 67108864, 1048576, 2097152, 18014398509481984, 33554432, 68719476736, 4, 17179869184, 536870912, 549755813888, 262144, 4294967296, 16384, 128, 288230376151711744, 137438953472, 16777216, 36028797018963968, 1024, 4503599627370496, 16384, 68719476736, 262144, 4611686018427387904] dec = [int(math.log(x,2)) for x in enc] b64 = string.ascii_uppercase + string.ascii_lowercase + string.digits + '+/' flag = ''.join([b64[x - 1] for x in dec]) print(base64.b64decode(flag))
ISITDTU{r1c3_che55b0ard_4nd_bs64}
シフトが1つずれているせいで時間を浪費した
Chaos [304pts, 45solves]
Could you help me solve this case? I have a tool but do not understand how it works.
nc 104.154.120.223 8085
> nc 104.154.120.223 8085 Your cipher key: Here is your cipher: 66/99/uu 22/ww/LL/TT 55/11/nn 66/44/zz 55/rr/AA/GG 77/kk/$$/hh 00/ff/<</hh 11/11/dd 55/ll/FF/LL 44/pp/~~/yy 66/jj/++/bb 88/vv/DD/==/)) 99/pp/**/tt 44/ii/BB/ZZ 66/ss/HH/&&/,, 11/pp/??/yy 22/zz/!!/tt 77/xx/KK/MM 99/kk/$$/hh 11/kk/VV/AA 33/oo/HH/__/^^ 44/uu/%%/ll 11/mm/FF/++/`` 44/ii/OO/KK 22/tt/@@/rr 55/dd/<</bb 44/ee/HH/QQ 00/yy/WW/TT 44/uu/CC/VV 55/qq/UU/DD 33/gg/$$/bb 11/mm/II/GG 44/tt/BB/II 99/kk/GG/))/~~ 11/uu/CC/??/?? 00/aa/^^/ee 33/bb/TT/JJ 11/hh/==/ll 44/ww/||/zz 00/vv/!!/yy 44/cc/YY/DD 55/dd/KK/YY 44/tt/HH/AA 99/mm/RR/CC 77/bb/XX/QQ 55/oo/>>/qq 66/ll/../aa 77/qq/==/zz 55/ii/II/&&/@@ 66/dd/JJ/EE 44/hh/||/ww 88/bb/EE/$$/** 11/rr/GG/LL 00/tt/**/rr 88/ee/OO/@@/-- 00/kk/MM/ZZ 77/cc/QQ/CC 99/xx/RR/PP 99/dd/&&/dd 88/ss/II/||/,, 88/dd/??/pp 77/uu/LL/HH 77/ff/OO/<</.. 99/kk/KK/))/++ WELCOME TO CHAOS TOOL: Description: This is a tool which helps you hide the content of the message Notes: - Message cannot contain whitespace characters - Message can use all characters including punctuation marks and number - Decrypt the above key to get the flag, len(key) = 64 - All punctuation marks use in plain key: ~`!@#$%^&*()_-+=<,>.?| - Key is not a meaningful sentence - Find the rule in this tool **FEATURES** <1> Encrypt message <2> Get the flag Your choice: 1 Enter your message: abc Here is your cipher: 33/aa/||/jj 22/bb/../bb 77/cc/^^/xx **FEATURES** <1> Encrypt message <2> Get the flag Your choice: 1 Enter your message: ABC Here is your cipher: 99/mm/AA/UU 22/kk/BB/HH 33/xx/CC/VV **FEATURES** <1> Encrypt message <2> Get the flag Your choice: 1 Enter your message: 0123 Here is your cipher: 00/99/uu 11/55/hh 22/88/qq 33/88/bb **FEATURES** <1> Encrypt message <2> Get the flag Your choice: 1 Enter your message: <>? Here is your cipher: 66/jj/HH/**/<< 00/zz/JJ/%%/>> 99/ff/OO/%%/??
アプローチ:変換ルールを見つけてGet the flag
以下が変換ルールです.
[a-z] a -> 33/aa/||/jj (スラッシュで区切った2つめ) [A-Z] A -> 99/mm/AA/UU (スラッシュで区切った3つめ) [0-9] 0 -> 00/99/uu (スラッシュで区切った1つめ) [記号] ? -> 99/ff/OO/%%/?? (スラッシュで区切った5つめ)
以下がソルバです.
#!/usr/bin/env python # -*- coding: utf-8 -*- import string from socket import * s = socket(AF_INET, SOCK_STREAM) s.connect(('104.154.120.223', 8085)) rec = s.recv(1024).decode('utf_8') rec = s.recv(2048).decode('utf_8') my_cipher = rec.split('\n')[0].split(' ')[4:] msg = '' for x in my_cipher: enc = x.split('/') if len(enc) == 4 and enc[-1][0] in string.ascii_lowercase: msg += enc[1][0] elif len(enc) == 4 and enc[-1][0] in string.ascii_uppercase: msg += enc[2][0] elif len(enc) == 3: msg += enc[0][0] else: msg += enc[-1][0] print(msg) s.send(b'2\n') rec = s.recv(2048).decode('utf_8') s.send(msg.encode('utf_8') + b'\n') rec = s.recv(2048).decode('utf_8') print(rec)
> python solve.py wz+3tUV8)KqORqV*JzPI|d4XjM0%|#GO+<hVB|,MSr?TOzZ`z$gmUcAGpRaMon^_ Good job! Here is your flag: ISITDTU{Hav3_y0u_had_a_h3adach3??_Forgive_me!^^}
ISITDTU{Hav3_y0u_had_a_h3adach3??_Forgive_me!^^}
これCryptoなのか?
decrypt to me [395pts, 42solves]
decrypt to me?????
File: decrypt_to_me
import binascii def generate_prg_bit(n): state = n while True: last_bit = state & 1 yield last_bit middle_bit = state >> len(bin(n)[2:])//2 & 1 state = (state >> 1) | ((last_bit ^ middle_bit) << (len(bin(n)[2:])-1)) flag = '###########' enc = "OKQI+f9R+tHEJJGcfko7Ahy2AuL9c8hgtYT2k9Ig0QyXUvsj1B9VIGUZVPAP2EVD8VmJBZbF9e17" flag_bin_text = bin(int(binascii.hexlify(flag), 16))[2:] prg = generate_prg_bit(len(flag_bin_text)) ctext = [] flag_bits = [int(i) for i in flag_bin_text] for i in range(len(flag_bits)): ctext.append(flag_bits[i] ^ next(prg)) ciphertext = '0b' + ''.join(map(str, ctext)) n = int(ciphertext, 2) print binascii.unhexlify('%x' % n).encode('base64')
アプローチ:全探索
適切なflag
をencrypt
するとOKQI+f9R+tHEJJGcfko7Ahy2AuL9c8hgtYT2k9Ig0QyXUvsj1B9VIGUZVPAP2EVD8VmJBZbF9e17
になるっぽいです.
encrypt
処理を読む限り,1つのbit
がencrypt
全体に影響を与えるような処理はされていないことが分かります.
つまり,1文字ずつflag
を探索していくことが可能です.
以下ソルバです.
#!/usr/bin/env python3 # -*- coding: utf-8 -*- import base64 import binascii import string from Crypto.Util.number import * def generate_prg_bit(n): state = n while True: last_bit = state & 1 yield last_bit middle_bit = state >> len(bin(n)[2:])//2 & 1 state = (state >> 1) | ((last_bit ^ middle_bit) << (len(bin(n)[2:])-1)) def encrypt(flag): flag_bin_text = bin(bytes_to_long(flag.encode('utf_8')))[2:] prg = generate_prg_bit(len(flag_bin_text)) ctext = [] flag_bits = [int(i) for i in flag_bin_text] for i in range(len(flag_bits)): ctext.append(flag_bits[i] ^ next(prg)) ciphertext = '0b' + ''.join(map(str, ctext)) n = int(ciphertext, 2) enc = base64.b64encode(long_to_bytes(n)).decode('utf_8') return enc def char_match(target, enc): count = 0 for t,e in zip(target, enc): if t == e: count += 1 else: break return count match_length = 10 flag = 'ISITDTU{' # length 57 (?) target = 'OKQI+f9R+tHEJJGcfko7Ahy2AuL9c8hgtYT2k9Ig0QyXUvsj1B9VIGUZVPAP2EVD8VmJBZbF9e17' search_range = string.ascii_letters + string.digits + '{}_!@' for i in range(47): max_length = match_length max_a = '' max_b = '' for a in search_range: for b in search_range: enc_result = encrypt(flag + a + b + '*' * (56-len(flag + a + b)) + '}') length = char_match(target, enc_result) if length > max_length: max_length = length max_a = a max_b = b flag += max_a match_length = max_length print(flag + max_b)
> python solve.py ISITDTU{El ISITDTU{Ena ISITDTU{Encr ISITDTU{Encrx ISITDTU{Encryp ISITDTU{Encrypt ISITDTU{Encrypt_ ISITDTU{Encrypt_X ISITDTU{Encrypt_X0 ISITDTU{Encrypt_X0p ISITDTU{Encrypt_X0rP ISITDTU{Encrypt_X0r_N ISITDTU{Encrypt_X0r_N0 ISITDTU{Encrypt_X0r_N0p ISITDTU{Encrypt_X0r_N0t_ ISITDTU{Encrypt_X0r_N0t_T ISITDTU{Encrypt_X0r_N0t_Us ISITDTU{Encrypt_X0r_N0t_Us3 ISITDTU{Encrypt_X0r_N0t_Us3_ ISITDTU{Encrypt_X0r_N0t_Us3_P ISITDTU{Encrypt_X0r_N0t_Us3_Ps ISITDTU{Encrypt_X0r_N0t_Us3_Psd ISITDTU{Encrypt_X0r_N0t_Us3_Psep ISITDTU{Encrypt_X0r_N0t_Us3_Pseud ISITDTU{Encrypt_X0r_N0t_Us3_Pseud0 ISITDTU{Encrypt_X0r_N0t_Us3_Pseud0P ISITDTU{Encrypt_X0r_N0t_Us3_Pseud0_R ISITDTU{Encrypt_X0r_N0t_Us3_Pseud0_Ra ISITDTU{Encrypt_X0r_N0t_Us3_Pseud0_Raa ISITDTU{Encrypt_X0r_N0t_Us3_Pseud0_Rand ISITDTU{Encrypt_X0r_N0t_Us3_Pseud0_Rand0 ISITDTU{Encrypt_X0r_N0t_Us3_Pseud0_Rand0a ISITDTU{Encrypt_X0r_N0t_Us3_Pseud0_Rand0m_ ISITDTU{Encrypt_X0r_N0t_Us3_Pseud0_Rand0m_D ISITDTU{Encrypt_X0r_N0t_Us3_Pseud0_Rand0m_Ga ISITDTU{Encrypt_X0r_N0t_Us3_Pseud0_Rand0m_Gen ISITDTU{Encrypt_X0r_N0t_Us3_Pseud0_Rand0m_Gend ISITDTU{Encrypt_X0r_N0t_Us3_Pseud0_Rand0m_Genep ISITDTU{Encrypt_X0r_N0t_Us3_Pseud0_Rand0m_Genera ISITDTU{Encrypt_X0r_N0t_Us3_Pseud0_Rand0m_Generat ISITDTU{Encrypt_X0r_N0t_Us3_Pseud0_Rand0m_Generat0 ISITDTU{Encrypt_X0r_N0t_Us3_Pseud0_Rand0m_Generat0r ISITDTU{Encrypt_X0r_N0t_Us3_Pseud0_Rand0m_Generat0r! ISITDTU{Encrypt_X0r_N0t_Us3_Pseud0_Rand0m_Generat0r!! ISITDTU{Encrypt_X0r_N0t_Us3_Pseud0_Rand0m_Generat0r!!! ISITDTU{Encrypt_X0r_N0t_Us3_Pseud0_Rand0m_Generat0r!!!! ISITDTU{Encrypt_X0r_N0t_Us3_Pseud0_Rand0m_Generat0r!!!!!
ISITDTU{Encrypt_X0r_N0t_Us3_Pseud0_Rand0m_Generat0r!!!!!}
多分想定解法とは違うと思います.
もっとスマートに解きたかった…
Thank you
Survey [10pts, 263solves]
Thank you for join with us, hope to see you next year, and so sorry about the server issue.
Survey
アプローチ:wgetでサクッと終わらせる (アンケートに答えない)
> wget https://forms.gle/v3eqi162QLeeBuse6 > grep 'ISITDTU{' ./v3eqi162QLeeBuse6 ,["ISITDTU{thank_you_for_your_feedback}",1,0,0,0]
ISITDTU{thank_you_for_your_feedback}
まとめ
- 最近チームで参加できていない
- Web, Pwn... (勉強します)
- 頭BabyなのでEasy RSAが解けない (Boneh Durfee Attackとか初めて聞いた(Wiener's Attackしか知らなかった)し,近似してからフェルマー法かけるのは思いつかなかった…)