【IRON CTF】Write Up
はじめに
2024年の10月5日から10月6日にわたって24時間で開催されたIRON CTFのWrite up です．
1671ptで，169位でした．
問題リスト
Dantig's Puzzle - Crypto
Game of Hunt - Forensics
このほか，別の方のWrite upを参考にして，後日解いてみた問題に関する記事も書く予定です．
Write ups
Dantig's Puzzle - Crypto
問題文
Dantzig was on a trip with his friends and one day, they decided to play a game or atleast, it's easier version. He would think of a string and the others have to find it based on the clues he gives them.
- The knapsack list contains 8 numbers, with 1 and 2 as the first two numbers and the subsequent numbers are formed by adding one to the sum of all the numbers before.
- The value of m=257 and n is something less than 257
- The encrypted string is - [538, 619, 944, 831, 360, 531, 468, 971, 635, 593, 655, 425, 1068, 530, 1068, 360, 706, 1068, 299, 619, 670, 1068, 891, 425, 670, 1068, 371, 670, 732, 531, 1068, 484, 372, 635, 371, 372, 237, 237, 1007]
Can you find the string Dantzig was thinking of?
Flag Format: ironCTF{this_is_fake}
Author: p3rplex3d
解法
「Dantzig」，「Knapsack」などの単語でググると「ナップザック暗号」が関連しているとわかります．
復号には公開鍵である
wikiの記述と問題文を照らし合わせると
-
n(=8) - 「Knapsack list」が超増加列
w - 秘密鍵
q = 257 m
であると推測できます．
秘密鍵である
これを実装します．
def gen_cdash(c, rinv, q):
cdash = []
for ci in c:
cdash.append((ci * rinv) % q)
return cdash
def decrypt(w, cdash, n):
message = []
for s in cdash:
S = 0
for i in range(n-1, -1, -1):
if s >= w[i]:
s = s - w[i]
S = S | (1 << (n - 1 - i))
message.append(S)
return message
# knapsack list 超増加列
w = [1, 2, 4, 8, 16, 32, 64, 128]
# 秘密鍵 q
q = 257
# n: 8ビットの平文を暗号化する
n = 8
# 暗号文
c = [538, 619, 944, 831, 360, 531, 468, 971, 635, 593, 655, 425, 1068, 530, 1068, 360, 706, 1068, 299, 619, 670, 1068, 891, 425, 670, 1068, 371, 670, 732, 531, 1068, 484, 372, 635, 371, 372, 237, 237, 1007]
# rの候補を全て試す
for r in range(1, q):
rinv = pow(r, -1, q)
cdash = gen_cdash(c, rinv, q)
message = decrypt(w, cdash, n)
# 得られた文字列のうち，asciiで読み取れるものを出力する
if all([0x00 <= m <= 0x7f for m in message]):
print(''.join([chr(m) for m in message]))
得られた平文をasciiで変換すると，flagが得られました．
ironCTF{M4th_&_C5_ar3_7h3_b3sT_c0Mb0!!}
Game of Hunt - Forensics
問題文
A Cryptic Voyage
Author: tasarmays
また，upsidedown.txtというテキストファイルが与えられます．
00000000 00000000 00000000 00000001 01000001 ...
upsidedown.txtでは，二進文字列がスペース区切りで羅列されています．ファイル名である「upsidedown」という単語をヒントに，このリストを反転して表示してみます．二進数のままだとみずらいので16進数に変換しています．
s = []
with open("upsidedown.txt", "r") as f:
s = f.read().split(" ")
s = [int(i, 2) for i in s]
s_hex = [hex(i) for i in s]
print(s_hex[::-1][:5])
これを実行すると
['0x50', '0x4b', '0x3', '0x4', '0xa']
となります．
0x50，0x4b，0x03，... というバイト列は，zipファイルの冒頭のバイト列と一致します．
バイト列をファイルに書き込み，upsidedown.zipとして保存します．
s = []
with open("upsidedown.txt", "r") as f:
s = f.read().split(" ")
with open("upsidedown.zip", "wb") as f:
f.write(bytes(reversed(s)))
得られたファイルをunzipすると，ilovepdfs/というディレクトリに入った大量のpdfが得られます．
$ ls -r ilovepdfs/
document_99.pdf document_88.pdf document_77.pdf document_66.pdf document_55.pdf document_44.pdf document_33.pdf document_22.pdf document_11.pdf
document_98.pdf document_87.pdf document_76.pdf document_65.pdf document_54.pdf document_43.pdf document_32.pdf document_21.pdf document_100.pdf
document_97.pdf document_86.pdf document_75.pdf document_64.pdf document_53.pdf document_42.pdf document_31.pdf document_20.pdf document_10.pdf
document_96.pdf document_85.pdf document_74.pdf document_63.pdf document_52.pdf document_41.pdf document_30.pdf document_2.pdf document_1.pdf
document_95.pdf document_84.pdf document_73.pdf document_62.pdf document_51.pdf document_40.pdf document_3.pdf document_19.pdf
document_94.pdf document_83.pdf document_72.pdf document_61.pdf document_50.pdf document_4.pdf document_29.pdf document_18.pdf
document_93.pdf document_82.pdf document_71.pdf document_60.pdf document_5.pdf document_39.pdf document_28.pdf document_17.pdf
document_92.pdf document_81.pdf document_70.pdf document_6.pdf document_49.pdf document_38.pdf document_27.pdf document_16.pdf
document_91.pdf document_80.pdf document_7.pdf document_59.pdf document_48.pdf document_37.pdf document_26.pdf document_15.pdf
document_90.pdf document_8.pdf document_69.pdf document_58.pdf document_47.pdf document_36.pdf document_25.pdf document_14.pdf
document_9.pdf document_79.pdf document_68.pdf document_57.pdf document_46.pdf document_35.pdf document_24.pdf document_13.pdf
document_89.pdf document_78.pdf document_67.pdf document_56.pdf document_45.pdf document_34.pdf document_23.pdf document_12.pdf
大半のpdfは次のような意味のないものです．
すべてのファイルに目を通すと，document_83.pdfに次の手がかりが含まれていることがわかります．
こちらのWrite upによると，pdf2txtというコマンドを使うと便利なようです．
$ find . -type f -name "*.pdf" | xargs -I {} pdf2txt {}
実行結果(抜粋)
This is PDF document 82
How do you feel now, find the hidden esolang :)
++++++++++[>+>+++>+++++++>++++++++++<<<<-]>>>>+++++.++++++++
+.---.-.<---.+++++++++++++++++.--------------.>+++++++++++++.<+++++++++++++++++
++.>------------.+++++
+.<++++++.++.>---.<++++.------.>++.<+++++++++.---.------.+++++++.+
++.+++++.---------.>-.
+.+++++++++.
This is PDF document 84
brainf*ckのソースコードが与えられています．これを実行するとflagが得られました．自分はオンラインコンパイラを使用しました．
++++++++++[>+>+++>+++++++>++++++++++<<<<-]>>>>+++++.++++++++
+.---.-.<---.+++++++++++++++++.--------------.>+++++++++++++.<+++++++++++++++++
++.>------------.+++++
+.<++++++.++.>---.<++++.------.>++.<+++++++++.---.------.+++++++.+
++.+++++.---------.>-.
+.+++++++++.
実行結果:
ironCTF{You_are_the_finest}
Discussion