Cyber Apocalypse CTF 2021 writeup
4/19 ~ 24にて行われましたCyber Apocalypse CTF 2021のCryptoのwriteupです。
問題数が多くてよかったのですが、解けそうで解けない問題多くてもやもやしました。
問題名の横にある★の数はDifficultyです。
Result
Writeup
Warmup & Misc
Welcome 25pt ★
Join our Discord Server and the CA-2021 channels…
Discordに入っても全然flagが見つからない…。始まって1日かかっても分からなかったのですが、HackTheBoxのアカウントを作りdiscordのbotに認証させると色んなチャンネルに入れるようになりflagも見つかりました！
でもこのflagでいいの？とはなるflagでした。
CHTB{CA_CTF_i$_F*ing_EPIC}
Alien Camp 300pt ★
The Ministry of Galactic Defense now accepts human applicants for their specialised warrior unit, in exchange for their debt to be erased. We do not want to subject our people to this training and to be used as pawns in their little games. We need you to answer 500 of their questions to pass their test and take them down from the inside.
This challenge will raise 33 euros for a good cause.
dockerを起動させてncするとこんな感じです。
読めないです。うーーん。計算させる問題なんだろうけど、文字化けが分からない…。
slackに貼ってみるとなんと絵文字が！！
文字化けしてたのが絵文字と分かればchrすれば文字コードを入手できます。それと矢印先の数字と対応させて四則演算をすればOKです。ただここで足し引き算とかけ算の順序に気を付けて実装する必要があります。
- リストを作りまず最初の数字をappendします。
- 演算子が+なら数字をそのままappend
- 演算子が-なら数字に-1を掛けてappend
- 演算子が×ならリストの最後尾の数字をその数字と対応する数字の積に置き換える
- 最後にリストの総和を求める
先にかけ算を行って足し引き算のみの式にしようという感じです。
i=1 while(i<=500): print("Now :",i) r.recvuntil("Question " + str(i) + ":\n\n") question = r.recvline().decode() que = question.split() for j in range(0,len(que)): if que[j] == "?": print(que[j],end="") elif j%2 == 0: print(num[hel.index(ord(que[j]))]," ",end="") else: print(que[j]+" ",end="") print() ans = [0 for j in range(len(que)//2)] bef = "+" way = [] cnt = 1 #ansに対応する数字を格納していく。a - bの場合、[a,-b]と格納していき、最後にsum(ans)とすれば和が出る ans[0] = num[hel.index(ord(que[0]))] for ind in range(1,len(que),2): if que[ind] == "=": break if que[ind] == "*": #かけ算の場合、足し引き算より先に行わないといけない #先に積を導出し、掛けられる数が入ってたansのところを0に、掛ける数のとこを今求めた積を格納する # a + b * c * d の場合、[a,0,0,0] -> [a,b,0,0] -> [a,0,b*c,0] -> [a,0,0,b*c*d] -> sum(ans) となる temp = ans[cnt-1]*num[hel.index(ord(que[ind+1]))] ans[cnt-1] = 0 ans[cnt] = temp cnt += 1 else: #+ or - #足し引き算ならそのまま格納するだけでよい if que[ind] == "+": ans[cnt] = num[hel.index(ord(que[ind+1]))] cnt += 1 elif que[ind] == "-": ans[cnt] = -num[hel.index(ord(que[ind+1]))] cnt += 1 else: print("division") print(ans) ans = sum(ans)
500回は長かったなぁ
CHTB{3v3n_4l13n5_u53_3m0j15_t0_c0mmun1c4t3}
Crypto
Nintendo Base64 300pt ★
Aliens are trying to cause great misery for the human race by using our own cryptographic technology to encrypt all our games. Fortunately, the aliens haven't played CryptoHack so they're making several noob mistakes. Therefore they've given us a chance to recover our games and find their flags.
They've tried to scramble data on an N64 but don't seem to understand that encoding and ASCII art are not valid types of encryption!
This challenge will raise 33 euros for a good cause.
ファイル：output.txt
開いてみると綺麗ですね。
スペースを無くしてbase64 decodeしてみると後ろが==となりました。無限にdecodeしてb"CHTB{"が出るまで無限にdecodeして終わりです。
CHTB{3nc0d1ng_n0t_3qu4l_t0_3ncrypt10n}
PhaseStream1 300pt ★
The aliens are trying to build a secure cipher to encrypt all our games called "PhaseStream". They've heard that stream ciphers are pretty good. The aliens have learned of the XOR operation which is used to encrypt a plaintext with a key. They believe that XOR using a repeated 5-byte key is enough to build a strong stream cipher. Such silly aliens! Here's a flag they encrypted this way earlier. Can you decrypt it (hint: what's the flag format?)
2e313f2702184c5a0b1e321205550e03261b094d5c171f56011904
This challenge will raise 33 euros for a good cause.
これと同じです。
ångstromCTF 2021 writeup - Attack All Around
しかもこの問題と違ってmessageのどこかにflagがあるというわけではなく、flag以外余計な文字列は含まれていないので最初の5bytesは"CHTB{"となることが予想されます。それのxorをとると5bytesのkeyが求まるので後はそれを使って復号します。
CHTB{u51ng_kn0wn_pl41nt3xt}
PhaseStream2 300pt ★
The aliens have learned of a new concept called "security by obscurity". Fortunately for us they think it is a great idea and not a description of a common mistake. We've intercepted some alien comms and think they are XORing flags with a single-byte key and hiding the result inside 9999 lines of random data, Can you find the flag?
This challenge will raise 33 euros for a good cause.
ファイル：output.txt
1byteのkeyで、1つのflagと9999個のランダムデータをencryptした結果がoutput.txtです。
(keyの候補 = 256) × (10000行のデータ) = O(106) なのでまあbrute force可能です。各行をdecryptして"CHTB{"が含まれていたら終了です。
CHTB{n33dl3_1n_4_h4yst4ck}
PhaseStream3 300pt ★
The aliens have learned the stupidity of their misunderstanding of Kerckhoffs's principle. Now they're going to use a well-known stream cipher (AES in CTR mode) with a strong key. And they'll happily give us poor humans the source because they're so confident it's secure!
This challenge will raise 33 euros for a good cause.
ファイル：phasestream3.py, output.txt
AESのCTRモードで暗号化しているみたいです。CTRモードは初耳なのでこちらから勉強しました。
簡単に言えば、ナンスとカウンターをkeyによって暗号化した値と平文をxorしています。
平文と暗号文のペアがあれば「ナンスとカウンターをkeyによって暗号化した値」が分かります。今回はそれが分かります。
同じkeyでインスタンスを作ると同じナンスとカウンターが使われるので、「」内を求めてflagの暗号文をxorしたら終了です。
from Crypto.Util.number import * test_enc = "464851522838603926f4422a4ca6d81b02f351b454e6f968a324fcc77da30cf979eec57c8675de3bb92f6c21730607066226780a8d4539fcf67f9f5589d150a6c7867140b5a63de2971dc209f480c270882194f288167ed910b64cf627ea6392456fa1b648afd0b239b59652baedc595d4f87634cf7ec4262f8c9581d7f56dc6f836cfe696518ce434ef4616431d4d1b361c" flag_enc = "4b6f25623a2d3b3833a8405557e7e83257d360a054c2ea" test = b"No right of private conversation was enumerated in the Constitution. I don't suppose it occurred to anyone at the time that it could be prevented." #test=平文と、test_enc=暗号文の組み合わせが分かるのでenc(key) xor test = test_encからenc(key)を求める enc_key = long_to_bytes(bytes_to_long(test)^int(test_enc,16)) #flag長が46//2 = 23ということが分かる。enc(key)の上位23bytesとxorさせればOK print(long_to_bytes(bytes_to_long(enc_key[:23])^int(flag_enc,16)))
CHTB{r3u53d_k3Y_4TT4cK}
PhaseStream4 300pt ★★
The aliens saw us break PhaseStream 3 and have proposed a quick fix to protect their new cipher.
This challenge will raise 43 euros for a good cause.
ファイル：phasestream4.py, output.txt
前回と違って、平文と暗号文のペアが分かりません。
testquoteとflagの暗号文が一つずつあり、それぞれ96,85bytesです。「平文と暗号文のペア」が分からんくても解けるのか？とノートに数式いっぱい書いたけど分からず。
先頭5bytesがb"CHTB{"とすると、そこからenc_keyを求めてtestquoteを出すと「I alo」となります。「I alone ... 」なのかなとか思ってたけどそこから有力な情報を得ず…。英文になるようにtestquoteを決めてflagが意味ある文字列になればいいな、とか思ったけど人力じゃ無理でした。
次に前回の問題の平文について考えます。
No right of private conversation was enumerated in the Constitution. I don't suppose it occurred to anyone at the time that it could be prevented.
これはWhitfield Diffieの言葉(?)らしいです。
Diffieと言えばDiffie-Hellman鍵共有ですよね。3でDiffieなら4はHellmanの言葉を使っているのでは？とHellman quotesで検索するも何も出てこず…。この筋は違うと判断。
次にtestquoteが96bytes, 96文字ということに注目して身の回りに96文字の文章が無いのかと探してみると……
The aliens saw us break PhaseStream 3 and have proposed a quick fix to protect their new cipher.
あった。
早速それがtestquoteとしてenc_keyを求めてflagを出すと、意味ある文字列になりません。
え、これ違うのか。96文字でドンピシャだと思ったのに。問題文をrot13してみたり文字数を変えず色々試してみたのですが、そんな複雑なエスパー問題ではないだろうと考えなおします。
solves数が少ないわけではないので簡単に解けるのかなと思ってたのですが、問題文と暗号文の文字数が一緒だから関係あるのでは？から離れられませんでした。
数日悩み続け、一番最初のflagの先頭5bytesはb"CHTB{"であることからtestquoteの先頭5文字は"I alo"となることから調べていくと上手くいきました。
「quote I alo」と打つと予測で文章らしきものが出てきます。マザーテレサのお言葉でした。
I alone cannot change the world, but I can cast a stone across the water to create many ripples.
最初ヒットしたものは途中の"water"にsが付いており97文字でした。なのでflagが見えているんですが最後ぐちゃぐちゃした感じになりここでも悩みました。残り13文字が上手く復号されなかったので、その13文字を"Mother Teresa"と置けばいいのか？となりましたが違った…。その時に出ていたflagはこちらです。
CHTB{stream_ciphers_with_reused_keystreams_are_vulnerable_to_known_plain'1c;pcptr.>q
上手く復号されなかった部分は"plaintext"と続くのかなと予想します。flagがそうなら追加した"text"の部分からtestquoteはどうなるか確認したところ「to」(※アンダースコアは半角スペース)となり、s以降の文字列と一緒ではと考えsを消せば上手く復号されました。sが無いバージョンのquoteもあったのですが、他に解けた人はこのように解けたのか、はたまた97文字だからおかしいとして別のを探したのか気になります。
CHTB{stream_ciphers_with_reused_keystreams_are_vulnerable_to_known_plaintext_attacks}
SoulCrabber 300pt ★
Aliens heard of this cool newer language called Rust, and hoped the safety it offers could be used to improve their stream cipher.
This challenge will raise 33 euros for a good cause.
ファイル：main.rs, out.txt
Rustは全く触ったことがなく環境整備が難しそうだったので、Rust Playgroundを使いました。
main.rs を見ると、flagを読み込んで何かとxorして出力しているようです。その何かを求める必要がありそうですね。
get_rng関数では13371337をseedとして何かしらの整数を生成しているようです。結局この仕組みは分からないのですが、このくらいの解釈でも解けました。
ではどんな整数を生成しているのか確かめるために、flagと同じ長さになるように"A"を繋げそれをflagの代わりにして実行してみました。flagの長さはout.txtの長さから分かります。
fn main() -> std::io::Result<()> { let flag = "AAAAAAAAAAAAAAAAAAAAAAAAAAAAA"; let xored = rand_xor(flag.to_string()); println!("{}", xored); Ok(()) }
main.jsのmain関数だけ上記のように変更しました。すると、"19500187e1ba0b5bf3e27914c83f1ffd67123543ffc3ae4a4d22a9d54f" が得られました。
"A"29 xor (13371337をseedとして生成した整数) = 195...54f なので
(13371337をseedとして生成した整数) = "A"29 xor 195...54f となります。あとはこれと貰ったout.txtとxorして終了です。
CHTB{mem0ry_s4f3_crypt0_f41l}
SoulCrabber2 300pt ★★
Aliens realised that hard-coded values are bad, so added a little bit of entropy.
This challenge will raise 43 euros for a good cause.
ファイル：main.js, out.txt
先程は13371337をseedとしていたのに対し、今回はどうやらUNIX TIMEでseedを取っているようです。ここ2週間で作成したものだろうと高を括って解きました。
問題はRustで関数に引数を渡すやり方がいまいち分からなかったので、main関数で完結させました。
use rand::{Rng,SeedableRng}; use rand::rngs::StdRng; use std::fs; use std::io::Write; use std::time::SystemTime; fn main() -> std::io::Result<()> { let mut counter =0; while counter != 86400*14{ let mut rng = StdRng::seed_from_u64(1617537600+counter); let flag = "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"; let enc = flag.to_string(); let xored = enc .chars() .into_iter() .map(|c| format!("{:02x}", (c as u8 ^ rng.gen::<u8>()))) .collect::<Vec<String>>() .join(""); println!("{}", xored); counter += 1; } Ok(()) }
86400*14のbrute forceなので多少時間はかかりますが、回し切れますね。
CHTB{cl4551c_ch4ll3ng3_r3wr1tt3n_1n_ru5t}
RSA jam 325pt ★★
Even aliens have TLA agencies trying to apply rubber hose cryptanalysis.
This challenge will raise 43 euros for a good cause.
ファイル：rsajam.py
与えられたプログラムを読むと、RSAの公開鍵(e,n)に加え秘密鍵dが与えられます。φ(n)未満の与えられたd以外でme×d2 = m mod n となるd2を送るとflagがもらえるようです。
そもそも0以上φ(n)未満で秘密鍵となり得る自然数が複数存在するのか。フェルマーの小定理から、ap-1 = 1 mod p, aq-1 = 1 mod q (a< min(p-1,q-1) ) です。xがp-1とq-1の倍数とするとオイラーの定理より、ax = 1 mod nとなります。つまり、e×d2 = x + 1 (x = k×(p-1) = l×(q-1), k,lは自然数) となればよいです。
では、上記のの式に当てはまるd2を考えていきます。
e × d = 1 mod φ(n) であるので、e×d-1 = k×φ(n) (k : 自然数)と表せます。e, dは与えられるので、e×d-1を素因数分解して素数を上手く分けるとk × φ(n) という形に分けることが出来ます。
ではその上手く分けるためにはどうするかというと、素因数分解後の素数たちをbrute forceして試すんです。素数の個数の合計が20個以下ならまあ間に合います( O(220) 程度)。ビット全探査です。かなり大きい素数はほとんどの確率でφ(n)の方に含まれるので先に決め打ちしても問題ありません。
e×d-1 = a_1 × a_2 × ... × a_n とした時に、phi = a_x1 × a_x2 × ... × a_xm とおきます。phi = φ(n) であれば n - phi = n - φ(n) = p+q-1 となります。m = n - phi + 1 (= p + q) とおくと、n=p × q という情報もあるので解と係数の関係よりp,qを求めることが出来ます。
二次方程式 x2 - mx + n = 0 の解がp, qとなります。解の公式より m±√(m2 - 4 × 1 × n) / 2×1 が素数となればいいので、ルートの中身が平方数なのか判断すればOKです。求めた解p, qの積がnならnの素因数分解が出来ました。
次に、e×d2 = x + 1 (x = k×(p-1) = l×(q-1), k,lは自然数) となるd2を求めていきます。e×d = 1 + k×φ(n) と表せます。ここで、l = lcm(p-1,q-1)とすると、me×(d+l) = me×d + e×l = m×me×l mod n となります。lはp-1とq-1の倍数であるので、me×l = 1 mod nとなります。故に、d2 = d+l とすれば欲しいd以外の秘密鍵を手に入れられました(d+lがφ(n)を超える場合はd-lでもOKです)。
import gmpy2 import random import math e = 65537 pl =[2,2,3,3,5,5,7,11,11,13,191,199,1489] phi = 2954001204170914691805741860654963857940004074429377692284091070811401369951320958401069220899257193610366982095760499087321176610501426227559528834963391573119792751626794365037601107813476160364027477073371928090485550540475603624680000569693639581200408072914193394481017798545653296930496371873 d = 25279851828946689969935508637891642190361805428614897956944707979466882691402752252273969173866247553416847240691284721506378725185547104028957495800217551084649108905497165090047528206605038035320469604378521860671903204212263641356781239235920533291802966072966655090757438950541684952893977777198807710573 N = 123630001441211791699101815506417771377489862127836323215005247880779127747665261872791516882894729192469212567210262427681780651629370984012072785781572863755222453735206569087396934214192134882937330171191632058382828512367532999211413054935111652810223730835723518262117916443844727685713391668125094593189 for i in range(1<<len(pl)): temp = phi s = str(bin(i))[2:] s = "0"*(len(pl)-len(s)) + s #print("s",s) for j in range(len(pl)): if s[j] == "1": temp *= pl[j] M = N-temp+1 #print(M,N) rot, ch = gmpy2.iroot(M*M-4*N,2) if ch: print("find!") p = (M-int(rot))//2 q = (M+int(rot))//2 phi = (p-1)*(q-1) lc = (p-1) * (q-1) // math.gcd((p-1), (q-1)) print(d+lc) print(d+lc < phi) m = random.randrange(N) c = pow(m,e,N) m1 = pow(c,d+lc,N) print(m == m1)
e×d-1を出力した後はfactorDBで素因数分解したのでsolverらしきものは作ってはないです。素因数分解後、上のプログラムでd2を求めて手打ちで送って終了です。
CHTB{lambda_but_n0t_lam3_bda}
Problems
問題ファイルやsolverはこちらからどうぞ！
