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しか知らなかった)し，近似してからフェルマー法かけるのは思いつかなかった…)
