SECCON Beginners CTF 2021 Crypto writeup
Beginnerの範囲が広い。
Result
Writeup
simple_RSA
忘れない内に
$ tar -zvxf xxx.tar.gz
e=3と小さいです。me < n であるLow Public Exponent Attackだろうとエスパーし、cのe乗根を取るとあったのであとはlong_to_bytesして終了です。
import gmpy2 from Crypto.Util.number import * n = (中略) e = 3 c = (中略) m,ch = gmpy2.iroot(c,3) assert ch print(long_to_bytes(int(m)))
ctf4b{0,1,10,11...It's_so_annoying.___I'm_done}
Logical_SEESAW
We have an innovative seesaw!
ファイル：Logical_SEESAW.tar.gz
flag[i]=0なら、key[i]がなんであろうと0になります。16回行って毎回0になっているところはflag[i] = 0, そうでないならflag[i] = 1として最後long_to_bytesすればOKです。
cipher = (中略) cip = [[] for _ in range(len(cipher[0]))] for j in range(len(cipher)): for i in range(len(cipher[j])): cip[i].append(cipher[j][i]) m = "" for c in cip: if c.count("1") > 0: m += "1" else: m += "0" print(long_to_bytes(int(m,2)))
ctf4b{Sh3_54w_4_SEESAW,_5h3_54id_50}
GFM
Github Flavored Markdown
Google Facebook Microsoft
And...?
ファイル：gfm.tar.gz
enc = key × M × key (全て行列)であり、enc, keyが与えられているのであとはsageに逆行列や行列積を計算させればOKです。行列積なので掛ける順番に気を付けましょう。
key × M × key = enc key × M × key × key_inv = enc × key_inv key × M = enc × key_inv key_inv × key × M = key_inv × enc × key_inv M = key_inv × enc × key_inv
SIZE = 8 p = random_prime(2^128) MS = MatrixSpace(GF(p), SIZE) M = copy(MS.zero()) key = matrix( (中略) ) enc = matrix( (中略) ) key_inv = key.inverse() d = enc*key_inv p = 331941721759386740446055265418196301559 m = key_inv*d for i in range(8): for j in range(8): print(chr(m[i,j]%p),end="")
ctf4b{d1d_y0u_pl4y_w1th_m4tr1x_4nd_g4l0is_f1eld?}
Imaginary
虚数は好きですか？
接続方法: nc imaginary.quals.beginners.seccon.jp 1337
ファイル：app.py
AESのECBモードなのである平文に対して毎回同じ暗号文になります。
pythonの辞書型に対して、"1337i" in self.numbersがtrueになるのは、self.numbersのkeyに"1337i"が含まれている必要があります。
しかし、このサーバは"(自然数) + (自然数)i"とself.numbersのkeyを決めるので、「1337i"」の暗号文は簡単に作れそうですが、「"1337i"」の暗号文は無理そうです。なので、ちょうど「"」で平文ブロックが終わるものと、「1337i"」から始まる平文ブロックを暗号化してもらい、あとはそれら二つを合成して、「{xxx "1337i": xxx}」となる暗号文を生成します。
具体的には、step1を「1337i"」から始まる平文ブロックの暗号文を得る、step2を「"」で終わる平文ブロックの暗号文を得るとすると、
step1
re = 123, im = 456 をsaveする
re = 1, im = 1337 をsaveする
Export
step2
re = 1234, im = 4567 をsaveする
re = 1, im = 1337 をsaveする
Export
となります。あとはstep2で得られた暗号文の先頭64bytesとstep1で得られた暗号文の64bytes以降を足したものをImportすればflagが手に入ります。
json.loadsとかでエラー吐かないように平文を気を付けないといけなかったのが難しいですね。
ctf4b{yeah_you_are_a_member_of_imaginary_number_club}
Field_trip
Someone is getting ready for a field trip.
ファイル：Field_trip.tar.gz
先に言うと、チームメイトが惜しいところまで解いて自分が修正してみたら、終了1分前flagが手に入りましたあぶね～～～～～。
Merkle-Hellman knapsack暗号であろうと目を付け、ググるとこのサイトが。
PlaidCTF CTF 2015: Lazy - うさぎ小屋
このサイトに載っているsolver丸パクリです。細かい手法は一切分かりません。
本当のBeginnersはこのソースコードみてナップザック暗号だ！となるのすら難しいと思います。経験がものを言いますね。
b = pub_key n = len(b) c = 1010137180395931262752398681857488526009620802401167859543237801022630704004744078316133982172587856565491470015404484864890095896964409269987597733836611756 MULTIPLIER = 100 B = matrix(ZZ, n + 1, n + 1) B.set_block(0, 0, MULTIPLIER * matrix(n, 1, b)) B.set_block(n, 0, MULTIPLIER * matrix([ - c ])) B.set_block(0, 1, 2 * identity_matrix(n)) B.set_block(n, 1, matrix([ -1 ] * n)) #print '[*] basis: B =', B # LLL algorithm for x in B.LLL(): if x[0] == 0 and all(x_i in [-1, +1] for x_i in x[1 :]): print('[*] found: x =', x) # decode x m = 0 flag = "" for x_i in (x[1 :]): m *= 2 m += int(x_i == +1) print('[*] plaintext: m =', m) while m > 0: flag += chr(m%256) m //=256 print(flag[::-1])
チームメイトはこのサイトを参考にしてsolverを作ったとのことですが、私はある程度自分でやってしまい、それが原因で上手くいきませんでした。まずはsolverパクろう(教訓)
終了5分前、どうやっても復号できないとチームメイトからslackが来て、その復号文を2進数にして逆順にするとflagが出てきた！急いでsubmitしようとしたらloginしろと言われ焦る。これほどブラウザにパスワードを記憶させててよかったことはありませんでした(笑)
ctf4b{Y35!_I_ju5t_n33d3d_th353_num63r5!}
p-8RSA
It looks someone is encrypting it with RSA.
ファイル：p-8RSA.tar.gz
これ本当にbeginnerか？？？
まず、qを素数生成して8ずつ小さくしていき、それが素数且つe=17とφ(n)が互いに素でないなら鍵生成を終了します。
後半部分はともかく、とりあえず素因数分解します。factorDBでは上手くいきませんでしたが、自作のフェルマー法で素因数分解できました。
さあ、eとφ(n)が互いに素でない場合はどうしましょう。とりあえずググって見つけたサイトのアルゴリズムをそのままパクるとflagが出ました。
RSA Risk: When e and PHI share the same factor
これはgoogle力がものを言いました。phi = φ(n)/eとすると、gphi mod N != 1となるgを見つけ、d = e^-1 mod phiとなるdを使って、m = cd mod N を計算します。適切なgだと、gmが元の平文になるとのことです。gはbrute forceします。eとφ(n)が互いに素ではないと、違う平文でも同じ暗号文になってしまうので、得られた平文もどきから頑張って元の平文を手に入れるようなイメージしか湧きませんでした。
def algo1(p,q,e,gg): phi = ((p-1)*(q-1))//e while True: ge = pow(gg,phi,p*q) if ge != 1: return ge gg += 1 n = (中略) e = 17 c = (中略) tmp, ch = gmpy2.iroot(n,2) tmp = int(tmp)-1 #tmpが最初偶数だったため while True: if n%tmp == 0: p = tmp q = n//p print(p) print(q) assert n==p*q phi = ((p-1)*(q-1))//e d = inverse(17,phi) print("d:",d) m = pow(c,d,n) l = 1 fin = True while fin: mm = m*l mes = long_to_bytes(mm%n) if b"ctf4b" in mes: print(mes) fin = False l *= algo1(p,q,e,l) l %= n tmp -= 2
ctf4b{4r3_y0u_up5id3_d0wn?_Fr0m_6310w?_0r_60th?}
picoGym cryptography writeup
常設CTFは本当にありがたい。
picoCTF 2021で出題された問題のwriteupはこちらから
picoCTF 2021 writeup - Attack All Around
- Mod 26 10pt
- Mind your Ps and Qs 20pt
- Easy Peasy 40pt
- New Caesar 60pt
- Mini RSA 70pt
- Dachshund Attacks 80pt
- No Padding, No Problem 90pt
- It's Not My Fault 1 100pt
- Play Nice 110pt
- Double DES 120pt
- Compress and Attack 130pt
- Scrambled: RSA 140pt
- It is my Birthday 2 170pt
- Pixelated 200pt
- New Vignere 300pt
は上のサイトから見てください！
今回は問題文、与えられたファイルなど省略しています。ご了承ください。
こちらから参照していただければ！
- solved
- The Numbers 50pt
- Easy1 100pt
- 13 100pt
- caesar 100pt
- spelling-quiz 100pt
- XtraORdinary 150pt
- triple-secure 150pt
- la cifra de 200pt
- Tapping 200pt
- Flags 200pt
- Mr-Worldwide 200pt
- rsa-pop-quiz 200pt
- college-rowing-team 250pt
- waves over lambda 300pt
- miniRSA 300pt
- b00tl3gRSA2 400pt
- AES-ABC 400pt
- b00tl3gRSA3 450pt
- john_pollard 500pt
- unsolved
solved
The Numbers 50pt
1 -> A, 2 -> B, ... 26 -> Z と変換すればOKです。
PICOCTF{THENUMBERSMASON}
Easy1 100pt
table.txtはVigenere暗号の変換表のようですね。
decoder ↓ CyberChef
picoCTF{CRYPTOISFUN}
13 100pt
rot13ですね。13文字アルファベットをシフトさせます。
picoCTF{not_too_bad_of_a_problem}
caesar 100pt
もらったciphertextをrot13しても文章にはなりません。自分でrot1~25を作り、文章になるやつを探します。
def rotate(enc,cnt): x = ord("a") ret = "" for i in range(len(enc)): c = ord(enc[i]) n = c-x ret += chr(((n+cnt)%26)+x) return ret enc = "gvswwmrkxlivyfmgsrhnrisegl" for i in range(26): dec = rotate(enc,i) print("picoCTF{"+dec+"}")
picoCTF{gvswwmrkxlivyfmgsrhnrisegl}
picoCTF{hwtxxnslymjwzgnhtsiosjtfhm}
picoCTF{ixuyyotmznkxahoiutjptkugin}
picoCTF{jyvzzpunaolybipjvukqulvhjo}
picoCTF{kzwaaqvobpmzcjqkwvlrvmwikp}
picoCTF{laxbbrwpcqnadkrlxwmswnxjlq}
picoCTF{mbyccsxqdrobelsmyxntxoykmr}
picoCTF{nczddtyrespcfmtnzyouypzlns}
picoCTF{odaeeuzsftqdgnuoazpvzqamot}
picoCTF{pebffvatgurehovpbaqwarbnpu}
picoCTF{qfcggwbuhvsfipwqcbrxbscoqv}
picoCTF{rgdhhxcviwtgjqxrdcsyctdprw}
picoCTF{sheiiydwjxuhkrysedtzdueqsx}
picoCTF{tifjjzexkyvilsztfeuaevfrty}
picoCTF{ujgkkafylzwjmtaugfvbfwgsuz}
picoCTF{vkhllbgzmaxknubvhgwcgxhtva}
picoCTF{wlimmchanbylovcwihxdhyiuwb}
picoCTF{xmjnndiboczmpwdxjiyeizjvxc}
picoCTF{ynkooejcpdanqxeykjzfjakwyd}
picoCTF{zolppfkdqeboryfzlkagkblxze}
picoCTF{apmqqglerfcpszgamlbhlcmyaf}
picoCTF{bqnrrhmfsgdqtahbnmcimdnzbg}
picoCTF{crossingtherubicondjneoach}
picoCTF{dspttjohuifsvcjdpoekofpbdi}
picoCTF{etquukpivjgtwdkeqpflpgqcej}
picoCTF{furvvlqjwkhuxelfrqgmqhrdfk}
picoCTF{crossingtherubicondjneoach}
spelling-quiz 100pt
alphabet = list('abcdefghijklmnopqrstuvwxyz') random.shuffle(shuffled := alphabet[:]) dictionary = dict(zip(alphabet, shuffled))
これから小文字アルファベットを別の小文字アルファベットに変換しているようです。要は換字式暗号ですね。study-guideをquipquipに投げ変換してもらいます。全部投げると多いと怒られる(フリーズする)ので、適度に入れます。"h"の頻度が少ないので気をつけてください。
それから対応表を作ってflag.txtのを復号する。
picoCTF{perhaps_the_dog_jumped_over_was_just_tired}
XtraORdinary 150pt
この問題面白かった。
まずflagとkeyをxorし、その後random_strs[0~9]とxorを最大(28 + 26 + 24 + 22 + 1)回行います。しかし、同じものをk回xorしたとしても、k%2回xorした値と等しくなります。xorの特性ですね。もし、aとrandom_str[0]が2k回xorしてたら、計算結果はaと同値です。2k+1回だったら1回xorしたのと同値です。つまり、random_strsの1つに対して、それとxorするかしないかの2通りしかなく、random_strsにはb"ever"が多く同一のを無視すると5種類しかないので、25 = 32通り試して上手くいくのを探します。
32通り試した後、出てくるのはflagとkeyのxorした値だけで、これでは上手くいったか、32通りの内どれが答えか分かりません。そこで、flag形式のb"picoCTF{"とxorさせます。keyの長さは分かりませんが、flagよりも短く長さを越えたら最初に戻るというようなrotateがされているので、keyの長さが7以下であれば解けそうです。この問題は他にヒントが無いのでkey長は7以下で一周して周期が分かるように設定されているはずとエスパーします。
ct = "57657535570c1e1c612b3468106a18492140662d2f5967442a2960684d28017931617b1f3637" ct = long_to_bytes(int(ct,16)) rev = [b'break it', b'ever',b'and you will never', b'is absolutely impenetrable', b'my encryption method'] for i in tqdm(range(32)): for j in range(5): if i & (1 << j): ct = decrypt(ct, rev[j]) flag = b"picoCTF{" print(i) k = b"" key = [] for j in range(8): tmp = ct[j]^flag[j] print(tmp) if tmp in key: print("plural key!") key.append(tmp) k += long_to_bytes(tmp)
65 102 114 105 99 97 33 65
となる時がありました。エスパー通り、keyの周期が見えました。
picoCTF{w41t_s0_1_d1dnt_1nv3nt_x0r???}
triple-secure 150pt
n1, n2, n3の内二つ選んで最大公約数を取るとp, q, rになり素因数分解ができいつものRSA方式に落とし込めます。
nxの秘密鍵をdxとすると、暗号化とは逆にd3->d2->d1の順で復号すればOKです。
p = math.gcd(n1,n2) r = math.gcd(n3,n2) q = math.gcd(n1,n3) phi1 = (p-1)*(q-1) phi2 = (p-1)*(r-1) phi3 = (r-1)*(q-1) d1 = inverse(e,phi1) d2 = inverse(e,phi2) d3 = inverse(e,phi3) c = pow(c,d3,q*r) c = pow(c,d2,p*r) c = pow(c,d1,q*p) print(long_to_bytes(c))
picoCTF{1_gu3ss_tr1pl3_rs4_1snt_tr1pl3_s3cur3!!!!!!}
la cifra de 200pt
ncして得られる暗号文はどうやら換字式暗号のようです。全く読めない英文ならほぼ間違いなく換字式暗号です。quipquipに投げて終了です。と思ったら復号されない。
flagになりそうな"pohzCZK{m311a50_0x_a1rn3x3_h1ah3x6kp60egf}"の部分が全くもってうまく復号されません。"pohzCZK"が"picoCTF"になるならzで矛盾します。
dcodeのcipher identifier など使いましたが分からず、結局他の方のwriteupを見ました。
picoCTF 2019 la cifra de - Points: 200 - Qiita
vigenere暗号なんて分かるか！！！とも思いましたが、"pohzCZK"が"picoCTF"になることから1, 5文字目は平文と暗号文が変わらないことから4文字keyのvigenereとエスパーできる方もいるかもしれませんね。
picoCTF{b311a50_0r_v1gn3r3_c1ph3r6fe60eaa}
Tapping 200pt
ncしてもらえる暗号文は明らかにモールス信号ですね。初めての方はこういうものかと覚えてください。CyerChefなどのMorse Decoderに任せましょう。
PICOCTF{M0RS3C0D31SFUN1261438181}
Flags 200pt
一度m1z0r3の勉強会でやったことある問題でした。
問題画像には正方形の旗があり、1つの旗が1文字になり"{"の文字より前の7文字は"PICOCTF"となりそうです。
「alphabet flag」と画像検索すると一発です。code flagというものらしいですね。大体のサイトではここまで復号できると思います。
"PICOCTF{F?AG?AND?TUFF}"
LとSが入るのだろうと提出してみるとincorrect。ちょっと悩んでみると、leetでは？となった。
数字のflag codeでいいものはありませんでした。エスパー能力向上問題ですね。
PICOCTF{F1AG5AND5TUFF}
Mr-Worldwide 200pt
もらったmessage.txtを見ると、どうやら座標のようですね。
google map検索でこのまま検索するとその座標が表す位置にピンを置いてくれます。
座標を全て調べた結果がこちらです。
- Nakanocho, Kamigyo Ward, Kyoto, 602-0958
- Odesa, Odessa Oblast, Ukraine, 65000
- Dayton, OH 45402, United States
- Hoca Paşa, 34110 Fatih/İstanbul, Turkey
- Hazza' Bin Zayed the First St - Al Manhal - Abu Dhabi - United Arab Emirates
- 50480 Kuala Lumpur, Federal Territory of Kuala Lumpur, Malaysia
- _
- Kirkos, Addis Ababa, Ethiopia
- Av Nueva Loja, Loja, Ecuador
- Martelaarsgracht 5, 1012 TN Amsterdam, Netherlands
- 188 vida activa, Sleepy Hollow, NY 10591, United States
- Kodiak, AK 99615, United States
- Faculty Of Engineering, Al Azaritah WA Ash Shatebi, Qism Bab Sharqi, Alexandria Governorate, Egypt
ここから都市名か国名かの頭文字を抜き取ってflagにするんだろうけど、探すの面倒だな…。でも何度やってもincorrect。大文字にしてなかったりそもそも抜き取るアルファベットが違うあんどあり、諦めて他の方のwriteupをみました。解く方向性は分かったからいいよね。
picoCTF{KODIAK_ALASKA}
rsa-pop-quiz 200pt
server connect問題かと思いきや同じ問題を解くわけじゃないので、別にターミナル開いてそこでpythonなど起動させ計算させましょう。ただ、このserverは時間が経つと切れてしまうので気を付けてください。繋ぎ直しても問題が変わることはないのでどこかにメモしておきましょう。
- p, qからnを求める。計算：n = p×q
- p, nからqを求める。計算：q = n/p (pythonだとn//p)
- nからp, qを求める。計算：しないで"N"を送る。次の問題に進んでくれる。
- p, qからφ(n)を求める。計算：φ(n) = (p-1)×(q-1)
- plaintext, e, nからciphertextを求める。計算：ciphertext = pow(plaintext, e, n)
- ciphertext, e, nからplaintextを求める。計算：しないで"N"を送る。次の問題に進んでくれる。
- p, q, eからdを求める。計算：d = inverse(e,(p-1)×(q-1) )
- p, ciphertext, e, nからplaintextを求める。計算：q = n//p, d = inverse(e,(p-1)×(q-1) ), plaintext = pow(ciphertext, d, n)
最後まで解くと以下のような文章が送られてきます。
If you convert the last plaintext to a hex number, then ascii, you'll find what you need! ;)
最後に求めたplaintextをlong_to_bytesするとflagになりました。
picoCTF{wA8_th4t$_ill3aGal..ode01e4bb}
college-rowing-team 250pt
この問題、Håstad's broadcast attackを使う問題です。初めてこの攻撃を扱う問題に触れました(自分で作ったことはあるけれど)。
この攻撃は中国剰余定理を用いてme を求めていきます。必要なのは公開鍵eの値と同じ数だけ異なるnがあり、暗号化する平文mとeは同値である必要があります。
今回はe=3です。そして、flagの暗号文が3つあると成立します。
flag<n より flag3 < n1n2n3
flag3 > max(n1,n2,n3)
ここでn1で割ると余りがc1、n2で割ると余りがc2、n3で割ると余りがc3となる整数xを求めていきます。また、元々の暗号化方式より、xはflag3にも当てはまります。中国剰余定理では、n1n2n3以下ではこの解は1つしかありません。先の式で flag3 < n1n2n3 ということが分かっています。なので、このxを求めたらflag3と同値で3乗根を取れば平文となります。
flag3 < n1n2n3 となる必要があるので、異なるnがe個必要なんです。
中国剰余定理はsympyで実装されています。
今回はflagの他に3つの文章の暗号文が3つずつ渡されています。この12個の暗号文の内、3つがflagの暗号文なのでbrute forceして見つけていきます。
from sympy.ntheory.modular import * import itertools import gmpy2 from Crypto.Util.number import * f = open("encrypted-message.txt") a = f.readlines() n_list = [] c_list = [] for i in range(0,len(a),4): n_list.append(int(a[i].split()[-1])) c_list.append(int(a[i+2].split()[-1])) tmp = [i for i in range(len(n_list))] for lis in itertools.combinations(tmp,3): # 0~11の内3つ選ぶのをbrute force candi = list(lis) m3,n = crt([n_list[candi[0]],n_list[candi[1]],n_list[candi[2]]],[c_list[candi[0]],c_list[candi[1]],c_list[candi[2]]]) #中国剰余定理 m, ch = gmpy2.iroot(int(m3),3) # 3乗根が存在するか確認 if ch: print(long_to_bytes(int(m))) #存在したら出力。flagと他の文章も出力される。
picoCTF{1_gu3ss_p30pl3_p4d_m3ss4g3s_f0r_4_r34s0n}
waves over lambda 300pt
今度は換字式暗号でした、良かった。quipquipに投げましょう。
frequency_is_c_over_lambda_agflcgtyue
miniRSA 300pt
このレベルが300pt!?となりました。e=3と小さく、me < nであるようなので、暗号文cの3乗根とってlong_to_bytesすればOKです。
import gmpy2 from Crypto.Util.number import * f = open("ciphertext") a = f.readlines() n = int(a[1].split()[-1]) e = 3 c = int(a[-1].split()[-1]) m, ch = gmpy2.iroot(c,3) assert ch print(long_to_bytes(int(m)))
picoCTF{n33d_a_lArg3r_e_d0cd6eae}
b00tl3gRSA2 400pt
eがいつもの65537に比べ非常に大きいです。これはWiener's Attackですね。eが大きいと相対的にdが小さくなることで求められる攻撃ですが、細かい仕組みは未だに理解していません。eが大きいと出来る攻撃程度の理解でも良いと思います(自分の保身のため)。
AES-ABC 400pt
AESのECBモードで暗号化しています。それについて学びましょう。
このwikiにも
ECBモードの欠点は、同じ鍵を用いた場合には、同じ平文ブロックを暗号化した結果の暗号文ブロックが常に同じとなることである。このため、データのパターンを隠蔽することができない。メッセージの機密性の保持には向かず、暗号化プロトコルにおける使用は推奨されない。同じ入力に対して常に同じ出力を返すことから、ECBモードは反射攻撃に対しても脆弱である。
ECBモードにおいてデータのパターンがどの程度残されるかを、ビットマップ画像の暗号化を用いて説明する。各々のピクセルの色情報を暗号化しても、暗号化処理後の画像にはピクセルごとの色情報のパターンが残留している。
とあるように、画像をECBモードで暗号化してもうっすら見えてしまうという欠点があります(wikiでのペンギンの絵、分かりやすい)。今回はそれを使います、つまり復号する必要はありません。
aes-abc.pyを見ると、16bytes毎読み取り一つ前のblockの値と足して25616 を越えるならそれで割った余りとするようにしていきます。なので、solverではその逆を行い復元していきます。
solverが上手くいかなかったのでこちらを参考にしました。
f = open("body.enc.ppm","rb") a0 = f.readline() a1 = f.readline() a2 = f.readline() header = a0 + a1 + a2 #ppmファイルは最初3行がheaderとなり必要な値 block = [] while True: data = int.from_bytes(f.read(16),"big") #16bytesずつ読み込む if data == 0: break block.append(long_to_bytes(data)) blocks = [] blocks.append(block[0]) for i in range(1,len(block)): if i%10000 == 0: print(i) t = block[i] t = bytes_to_long(t) t1 = bytes_to_long(block[i-1]) ans = (t-t1) if ans < 0: ans += UMAX ans = long_to_bytes(ans) while len(ans) % 16 != 0: ans = b"\0" + ans blocks.append(ans) ct = b"".join(blocks) with open("flag.ppm","wb") as fw: fw.write(header) fw.write(ct)
picoCTF{d0Nt_r0ll_yoUr_0wN_aES}
b00tl3gRSA3 450pt
今度はeの値が普通ですが、nが簡単に素因数分解できました。しかし素数が3つ以上あるmultiple primes RSAですね。細かいことはオイラーの定理を用いて考えるのですが、ざっくり言うとφ(n) = (素数1 - 1)×(素数2 - 1) × ... ×(素数k - 1) です。あとはいつも通りに秘密鍵dを求めて終了です。
phi = 1 for pp in p: phi *= (pp-1) #pというリストにnの素因数を入れている d = inverse(e,phi) m = pow(c,d,n) print(long_to_bytes(m))
john_pollard 500pt
証明書と言えばopenssl。opensslと言えばコマンドが難しい。
$ openssl x509 -text -in cert -noout
Certificate:
Data:
Version: 1 (0x0)
Serial Number: 12345 (0x3039)
Signature Algorithm: md2WithRSAEncryption
Issuer: CN = PicoCTF
Validity
Not Before: Jul 8 07:21:18 2019 GMT
Not After : Jun 26 17:34:38 2019 GMT
Subject: OU = PicoCTF, O = PicoCTF, L = PicoCTF, ST = PicoCTF, C = US, CN = PicoCTF
Subject Public Key Info:
Public Key Algorithm: rsaEncryption
RSA Public-Key: (53 bit)
Modulus: 4966306421059967 (0x11a4d45212b17f)
Exponent: 65537 (0x10001)
Signature Algorithm: md2WithRSAEncryption
07:6a:5d:61:32:c1:9e:05:bd:eb:77:f3:aa:fb:bb:83:82:eb:
9e:a2:93:af:0c:2f:3a:e2:1a:e9:74:6b:9b:82:d8:ef:fe:1a:
c8:b2:98:7b:16:dc:4c:d8:1e:2b:92:4c:80:78:85:7b:d3:cc:
b7:d4:72:29:94:22:eb:bb:11:5d:b2:9a:af:7c:6b:cb:b0:2c:
a7:91:87:ec:63:bd:22:e8:8f:dd:38:0e:a5:e1:0a:bf:35:d9:
a4:3c:3c:7b:79:da:8e:4f:fc:ca:e2:38:67:45:a7:de:6e:a2:
6e:71:71:47:f0:09:3e:1b:a0:12:35:15:a1:29:f1:59:25:35:
a3:e4:2a:32:4c:c2:2e:b4:b5:3d:94:38:93:5e:78:37:ac:35:
35:06:15:e0:d3:87:a2:d6:3b:c0:7f:45:2b:b6:97:8e:03:a8:
d4:c9:e0:8b:68:a0:c5:45:ba:ce:9b:7e:71:23:bf:6b:db:cc:
8e:f2:78:35:50:0c:d3:45:c9:6f:90:e4:6d:6f:c2:cc:c7:0e:
de:fa:f7:48:9e:d0:46:a9:fe:d3:db:93:cb:9f:f3:32:70:63:
cf:bc:d5:f2:22:c4:f3:be:f6:3f:31:75:c9:1e:70:2a:a4:8e:
43:96:ac:33:6d:11:f3:ab:5e:bf:4b:55:8b:bf:38:38:3e:c1:
25:9a:fd:5f
真ん中付近にある”Modulus: 4966306421059967”を素因数分解してヒントの通りにflagを作ればOKです。
picoCTF{73176001,67867967}
unsolved
- corrupt-key-1
以下のコマンドで秘密鍵を確認できる。
$ openssl rsa -text < private.key
RSA Private-Key: (1024 bit, 2 primes)
modulus:
00:b8:cb:1c:ca:99:b6:ac:41:87:6c:18:84:57:32:
a5:cb:fc:87:5d:f3:46:ee:90:02:ce:60:85:08:b5:
fc:f6:b6:0a:5a:c7:72:2a:2d:64:ef:74:e1:44:3a:
33:8e:70:a7:3e:63:a3:03:f3:ac:9a:df:19:85:95:
69:9f:6e:9f:30:c0:09:d2:19:c7:d9:8c:4e:c8:42:
03:61:08:34:02:9c:79:56:7e:fc:08:f6:6b:4b:c3:
f5:64:bf:b5:71:54:6a:06:b7:e4:8f:b3:5b:b9:cc:
ea:9a:2c:d4:43:49:f8:29:24:20:78:df:a6:4d:52:
59:27:bf:d5:5d:09:9c:02:4f
publicExponent: 65537 (0x10001)
privateExponent: 0
prime1:
00:e7:00:56:8f:f5:06:bd:58:92:af:92:59:21:25:
e0:6c:be:9b:d4:5d:fe:af:e9:31:a3:33:c1:34:63:
02:3d:4f:00:00:00:00:00:00:00:00:00:00:00:00:
00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
00:00:00:00:00
prime2: 0
exponent1: 0
exponent2: 0
coefficient: 0
writing RSA key
-----BEGIN RSA PRIVATE KEY-----
MIHeAgEAAoGBALjLHMqZtqxBh2wYhFcypcv8h13zRu6QAs5ghQi1/Pa2ClrHciot
ZO904UQ6M45wpz5jowPzrJrfGYWVaZ9unzDACdIZx9mMTshCA2EINAKceVZ+/Aj2
a0vD9WS/tXFUaga35I+zW7nM6pos1ENJ+CkkIHjfpk1SWSe/1V0JnAJPAgMBAAEC
AQACQQDnAFaP9Qa9WJKvklkhJeBsvpvUXf6v6TGjM8E0YwI9TwAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAgEAAgEAAgEAAgEA
-----END RSA PRIVATE KEY-----
nと素数pの上位半分bitsが分かるので、Coppersmithの定理を使うのだろう。ももテクさんの記事を丸パクリしたけど出来ない。となると分からない。
SageMathを使ってCoppersmith's Attackをやってみる - ももいろテクノロジー
- corrupt-key-2
- Clouds
Cloudsはwriteupありましたが理解できず。writerはある論文を読んだとのことですが、「この論文を完全に理解できるほど賢くなかった」と言ってます。いやこの問題解けるんだから充分賢いよ。
AtCoder 入水しました！
初めて色変記事というものを書いていきます。多くの方に読んでもらえたらと思っています！特に入水を目指している方向けになればいいなと思っています！
では、今までのことをつらつら書いていきます。最初は競プロをするまでのことを書くので、始めてからを知りたい方は読み飛ばして下さい。
AtCoderを始める前
高校生まで
プログラミングの「プ」の字も知らない。パソコンと言えば親に隠れてゲームの攻略法(ワザップとか)を調べる手段に過ぎない。それか情報の授業で触る程度。
今や中学生高校生がAtCoderをやっているのが珍しくなく、自分よりも全然rateが高い方を見るとすげえなぁって言葉しか出ない。例えまだ入水していない学生さんでもやってるだけですごいと本当に思う。
大学学部生時代 プログラミングと出会う
1年次に初めてプログラミングというものを知る。最初はC言語で、Hello worldってどの目線で言ってんねん、for文ってなんやと思っていました。プログラミングって新しそうっていう薄っぺらい知識から親は知らないだろうと話してみたら、なんと親父が知っていた。高校生の時も勉強を父から教わっていて、大学生になってもそれは変わらずC言語を教えてもらっていました(参考にならなくてすみません)。それから授業の中でも好きな方になっていきました。
2年次に挫折を味わう。Java言語の授業に遭遇するのである。オブジェクト指向ってなんやねん！！！そしてソフトウェア開発？的なグループワークでチェスを作る課題が一切分からず、他のチームメイトが99%行い自分は何もできないんだと悟る。
他にも2年次にはアルゴリズムの授業があり、ソートについてや最短経路探索、幅優先深さ優先などなど競プロにかなり役立つものばかりでしたが、当時の私はそんなに理解できていませんでした。
3年次は好転します。C言語の授業で競プロのようなオンラインジャッジシステムにグループで提出しろというのが毎週ありました。3人グループで自分以外女子、しかも二人とも可愛い。頑張らないわけがありません。積極的に課題に取り組み好感度爆上げ作戦を実行します。おかげでプログラミングの経験値は稼げました(他は察しろ)。
4年次、今の研究室に配属するとみんなpythonを使っていました。授業でpythonを扱ったことが無いので、なんでみんな知っているのか&よく使われているんだ、と壁を感じました。少し勉強したら使い方も分かり、今では本当によく使っています。でも、4年生になりたての時は授業で使ったことない言語を普通に使いこなしている先輩&同期が遠く見えました。
AtCoderを始めてみた
そんなこんなで大学院生になりました。やっと競プロを始めます。
競プロを始める前のプログラミングとの関わりとしては
といった感じです。
これからは下の図に沿って書いていきます。
灰色期
昨年度同期みんなpythonを知っていてビビり散らかした経験から、他にも言語学んでおかねばとフリーランスの友達にどんな言語を学ぶと将来活きるか聞いたところ、golangとかいいかもねと言われ勉強します。ただ勉強するだけじゃつまらない上にできているかどうか分からないので、競技プログラミングをチュートリアルとしようと思いアカウントを作りました。コンテストには出ず、過去問をいくつか解いていました。灰色ではなく黒色期ですね(笑)
そこから問題を解いていくうちに、実際に自分はどれだけできるのだろうと気になりコンテストに2回出ます。最初はまさかのAGC。よく知らないまま参加したのでいつもより難しすぎる！！！となります。ただ初めて出たのでrateは少し上がります。2回目はちゃんとABCに出ます。その時の記憶が無いのですが、なんと1100パフォ。提出履歴観たらpythonで出してる。GO言語の勉強どこ行った(おそらくいい成績出したくて慣れてるpythonでやったのでしょう)。
そこから留学準備の為半年間お休みします。この時期のTOEFL勉強きつかった。よかったらその時の記事もあるので読んでみてください。
復帰後はGO言語でコンテストには出て、特にこれといって精進はしていなかったです。競プロのための勉強はしたくなかった…。1ヶ月しかいなかった留学中もやっており、その期間で入茶しました。
茶色期
帰国後、一番の転機が訪れます。研究室の新入生に黄coderがいたのです。茶色になりたてからするととても遠い存在ではありますが、彼に教えてもらう気満々でいたことは確かです。そして、緑coderもいました。彼とはいいライバルが続いております。
まだGO言語を使っており、灰色期に比べ反省や復習をよくした記憶です。挑んだけど解けなかった問題であったり、どうしてもO(N), O(N logN)に落とし込めない問題など、実装はともかくACへのプロセスは理解するようにしていました。それもこれも彼の指導ですね。
そしてコンテストもよほどのことが無い限り参加していました。上級者が身近にいるのは本当にありがたく、未熟者からすると解説を読んでも分からない近いできないということはよくありました。また解説にはないやりやすい方法など彼に聞いて教えてもらっていました。
一度、ABC-Eまでコンテスト中に解け、終了後FもACできた時がありました。5月過ぎの伸びているところです。それから緑にならいけるのでは？とモチベーションが上がりました。
そして、とうとう親父も競プロを始めました。親父はc++を使っており、同じアルゴリズムでもc++の方が断然速いことを目の当たりにした結果、GO言語を学びたいという初心を捨てrateを上げたいと目標を変えます。c++に完全移行した日あたりで入緑しました。
入緑後、即停滞期
この時期の停滞期は妥当と思っていました。まだまだ不慣れなc++の扱いであったり、緑になる目標が達成されたので上を目指す意識が低かったです。それでも色落ちした時は悔しかったですね。
ここらへんの時期から彼や、他の競プロerの勧めもあり、ちゃんと精進するようになりました。よく使っていたのはこのサイトですね。
レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】 - Qiita
夏休み中や、ちょっと空いた時など解いていました。ワーシャルフロイド法やUnion-find、いもす法など知らないアルゴリズムが多かったので勉強になりました。今までろくに勉強してなかった分ですね。
また、競プロ用のアカウント(@ks37814026)を作って多くの競プロerの方と繋がれるようにしました。その方たちが詰まったところや良い問題などを共有して下さるので、勉強するのに困らなかったです！ 今もそのアカウントは続けているのですが、CTFの宣伝が多いですね(笑)
そして、精進の成果が出てきたのは肌寒くなった頃でした。
入水できるかも期
ある程度のアルゴリズムを覚え実装もできるようになると、だんだんrateが上がってきました。ABCではDが安定して解けるようになり自信も付いてきました。また、この時期からARCの頻度も増えてきてよく参加していました。ABCよりrateが上がる確率や幅が大きいことが多かったのでできるだけ出るようにしてました(ダメだった時の影響も大きいけど)。なので、ABC-Dが解けそうになってきた方はARCをお勧めします！
また速解きができるよう、スニペットが載っているサイトをブックマークしていました。他にも自作のライブラリなどを持っていると実装がすぐできると思います！特に数学的な問題はgoogleに頼る方がいいですね。
「1000000007 で割ったあまり」の求め方を総特集！ 〜 逆元から離散対数まで 〜 - Qiita
AtCoder 版！マスター・オブ・整数 (素因数分解編) - Qiita
巡回セールスマン問題をビットDPで解く (C++) - Qoosky
中には素因数は何種類あるか？って問題で2つ目のサイトをそのままコピペして最後だけ変えれば即ACという時もありました。コンテスト中は理解は後回しで、終わってから理解でも良いのかなと思っています(ペナ吐いたら考え物だけど)。
あと有難かったものとして、解けなかった問題の類題を彼が教えてくれる時がありました。リベンジという面でモチベにもなりますし純粋に経験値を多く得られます。上級者の知り合いを作るのが一番良い手かもしれません。
この時期はコンテスト参加すればほぼ毎回highestを更新していました。
partenderさんのAtCoder Beginner Contest 190での成績：1963位
— ありす (@ks37814026) 2021年1月30日
パフォーマンス：1188相当
レーティング：1050→1065 (+15) :)
Highestを更新しました！#AtCoder #ABC190 https://t.co/EpVKYHQONm
8連続highest更新!! 紅蓮華効果(?)
partenderさんのキャディプログラミングコンテスト2021(AtCoder Beginner Contest 193)での成績：1127位
— ありす (@ks37814026) 2021年2月27日
パフォーマンス：1439相当
レーティング：1111→1148 (+37) :)
Highestを更新しました！#AtCoder #キャディプログラミングコンテスト2021(ABC193) https://t.co/fKeHmd4awn
入水近し！！！
この頃、鬼滅の刃は全く知らないのですがコンテスト前に紅蓮華を聞いて強くなれる理由を知ってました！(笑) しかし入水目前でまたしても停滞期が…
第二停滞期
この頃の心の叫びです。
入水の夢を見ると現実を思い知らされる pic.twitter.com/tlx8oocjUs
— ありす (@ks37814026) 2021年3月14日
最近冷えてばかりなので温まりたい…
— ありす (@ks37814026) 2021年3月20日
色変前はよくあること、水パフォが全く出ないってことはないからいずれなるだろう、と思うようにしました。rateは下がってはいたのですが、大きく下がりはしなかったのでまだよかったです。
しかし、状況打破のためにこのようなことを始めました。
後輩が1日1CTFをやっているのにあやかって
— ありす (@ks37814026) 2021年3月15日
1日1CTF correctと1atcoder ACを毎日の目標にします。
これは今でも続けています。思い立った時にやるよりかは、毎日少しでも競プロに触れることでアルゴリズムや実装法など忘れにくくなります。毎日時間を取るのは難しいですが、実装しなくても問題を考えることが重要だと思います。おそらくこのレベルになると、頭に浮かんだ方法を考える方が、それを実装する世にも遥かに難しいからです。私は毎日家に引きこもっているので時間は簡単に作れるのですが、そうでない方で停滞している方は是非やってみてください！
最近はこれをよくやっています。★4,5あたりは解けなくて解説を読むことが多いですが、よくある解法を頭に落とし込めるのは良い経験になります。
その結果もあって、週末二つのコンテスト(ABC, ARC)で150以上も上がり入水できました！ この日は誕生日でもあったのでWでお祝いでした！
個人的なコンテストの挑み方
コンテスト前
- ルーティンを大事にする。コンテスト中は音楽を聴きながらやっているのですが、好きな音楽を最初にかける。紅蓮華効果は絶大だった(rate下がったらやめた)。
- エディタの準備を怠らない。提出する時にそのコンテスト用のディレクトリにすぐアクセスできるようにしておく。
- 好きなものを食べる！(揚げ物食べた日の調子はすごくいい)
コンテスト中
- 時間的計算量をまず考える。N=105 だったらO(N), O(N logN)で解けるからその方法を考える。N = 1018ならO(1)で解ける。などなど
- Nosubを考えない。考えると集中できなくなる。
コンテスト後
- twitterで他の方の解説や解法を確認する
さいごに
ここまで読んでくださった方、ありがとうございます。もしよろしければ是非感想をリプなりしていただけると嬉しいです。色変記事書くのは初めてなので、こういった情報もあると良いよなどあれば是非教えてください！
入水が目標だったので入青は今のところあまり考えてないのですが、もっとモチベが上がれば頑張ってみようと思います。入青出来た際にはまた記事を書こうと思うので読んでいただければと思います！
dctf 2021 writeup
初心者用といいながら、ちゃんと難しいCTFでした。
Result
Writeup
Misc
Encrypted the flag 100pt
Decrypted flag is not in exact format.
ファイル： EncryptedTheFlagIHave.png
5文字目と最後の文字(記号？)が"{}" に対応してそうです。このフォントを調べていくとこれがヒットしました。「alphabet font」でググって、根気強く探して見つかりました。
Languages in Star Wars - Wikipedia
dctf{mastercodebreaker}
Dragon 100pt
Hiding in plain sight.
ファイル：dragon.png
背景の白色部分に白文字が隠されているのか…？と色々調べましたが、各色を透過させたら出てきました。
WEBブラウザ上で簡単に透過PNG画像を作成できるツール | 無料で画像を加工できるサイト PEKO STEP
dctf{N0w_Y0u_s3e_m3}
Don't let it run 100pt
PDF documents can contain unusual objects within.
ファイル：dragon.pdf
PDFを開いてプロパティを確認しますが特には分からず。困った時はstringsコマンド。
$ strings dragon.pdf (中略) /Type /Action /S /JavaScript /JS <766172205F3078346163393D5B2736363361435968594B272C273971776147474F272C276C6F67272C273150744366746D272C27313036387552596D7154272C27646374667B7064665F316E6A33637433647D272C273736383537376A6868736272272C2737313733343268417A4F4F51272C27373232353133504158436268272C2738333339383950514B697469272C27313434373836335256636E546F272C2731323533353356746B585547275D3B2866756E6374696F6E285F30783362316636622C5F3078316164386237297B766172205F30783536366565323D5F3078353334373B7768696C652821215B5D297B7472797B766172205F30783237353061353D7061727365496E74285F307835363665653228307831366529292B2D7061727365496E74285F307835363665653228307831366429292B7061727365496E74285F307835363665653228307831366329292B2D7061727365496E74285F307835363665653228307831373329292A2D7061727365496E74285F307835363665653228307831373129292B7061727365496E74285F307835363665653228307831373229292A2D7061727365496E74285F307835363665653228307831366129292B7061727365496E74285F307835363665653228307831366629292A7061727365496E74285F307835363665653228307831373529292B2D7061727365496E74285F307835363665653228307831373029293B6966285F30783237353061353D3D3D5F307831616438623729627265616B3B656C7365205F30783362316636625B2770757368275D285F30783362316636625B277368696674275D2829293B7D6361746368285F3078353736346134297B5F30783362316636625B2770757368275D285F30783362316636625B277368696674275D2829293B7D7D7D285F3078346163392C3078386439376629293B66756E6374696F6E205F30786128297B766172205F30783363366432303D5F3078353334373B636F6E736F6C655B5F3078336336643230283078313734295D285F307833633664323028307831366229293B7D76617220613D27626B706F646E746A636F7073796D6C78656977686F6E7374796B787372707A79272C623D2765787262737071717573746E7A717269756C697A70656565787771736F666D77273B5F30786228612C62293B66756E6374696F6E205F307835333437285F30783337646533352C5F3078313961633236297B5F30783337646533353D5F30783337646533352D30783136613B766172205F30783461633965613D5F3078346163395B5F30783337646533355D3B72657475726E205F30783461633965613B7D66756E6374696F6E205F307862285F30783339623365652C5F3078666165353433297B766172205F30783235393932333D5F30783339623365652B5F30786661653534333B5F30786128293B7D0A> endobj (中略)
変な16進数ありますね。でかい数字はとりあえずlong_to_bytes()
>>> x = 0x766172205F3078346163393D5B2736363361435968594B272C273971776147474F272C276C6F67272C273150744366746D272C27313036387552596D7154272C27646374667B7064665F316E6A33637433647D272C273736383537376A6868736272272C2737313733343268417A4F4F51272C27373232353133504158436268272C2738333339383950514B697469272C27313434373836335256636E546F272C2731323533353356746B585547275D3B2866756E6374696F6E285F30783362316636622C5F3078316164386237297B766172205F30783536366565323D5F3078353334373B7768696C652821215B5D297B7472797B766172205F30783237353061353D7061727365496E74285F307835363665653228307831366529292B2D7061727365496E74285F307835363665653228307831366429292B7061727365496E74285F307835363665653228307831366329292B2D7061727365496E74285F307835363665653228307831373329292A2D7061727365496E74285F307835363665653228307831373129292B7061727365496E74285F307835363665653228307831373229292A2D7061727365496E74285F307835363665653228307831366129292B7061727365496E74285F307835363665653228307831366629292A7061727365496E74285F307835363665653228307831373529292B2D7061727365496E74285F307835363665653228307831373029293B6966285F30783237353061353D3D3D5F307831616438623729627265616B3B656C7365205F30783362316636625B2770757368275D285F30783362316636625B277368696674275D2829293B7D6361746368285F3078353736346134297B5F30783362316636625B2770757368275D285F30783362316636625B277368696674275D2829293B7D7D7D285F3078346163392C3078386439376629293B66756E6374696F6E205F30786128297B766172205F30783363366432303D5F3078353334373B636F6E736F6C655B5F3078336336643230283078313734295D285F307833633664323028307831366229293B7D76617220613D27626B706F646E746A636F7073796D6C78656977686F6E7374796B787372707A79272C623D2765787262737071717573746E7A717269756C697A70656565787771736F666D77273B5F30786228612C62293B66756E6374696F6E205F307835333437285F30783337646533352C5F3078313961633236297B5F30783337646533353D5F30783337646533352D30783136613B766172205F30783461633965613D5F3078346163395B5F30783337646533355D3B72657475726E205F30783461633965613B7D66756E6374696F6E205F307862285F30783339623365652C5F3078666165353433297B766172205F30783235393932333D5F30783339623365652B5F30786661653534333B5F30786128293B7D0A
>>> long_to_bytes(x)
b"var _0x4ac9=['663aCYhYK','9qwaGGO','log','1PtCftm','1068uRYmqT','dctf{pdf_1nj3ct3d}','768577jhhsbr','717342hAzOOQ','722513PAXCbh','833989PQKiti','1447863RVcnTo','125353VtkXUG'];(function(_0x3b1f6b,_0x1ad8b7){var _0x566ee2=_0x5347;while(!![]){try{var _0x2750a5=parseInt(_0x566ee2(0x16e))+-parseInt(_0x566ee2(0x16d))+parseInt(_0x566ee2(0x16c))+-parseInt(_0x566ee2(0x173))*-parseInt(_0x566ee2(0x171))+parseInt(_0x566ee2(0x172))*-parseInt(_0x566ee2(0x16a))+parseInt(_0x566ee2(0x16f))*parseInt(_0x566ee2(0x175))+-parseInt(_0x566ee2(0x170));if(_0x2750a5===_0x1ad8b7)break;else _0x3b1f6b['push'](_0x3b1f6b['shift']());}catch(_0x5764a4){_0x3b1f6b['push'](_0x3b1f6b['shift']());}}}(_0x4ac9,0x8d97f));function _0xa(){var _0x3c6d20=_0x5347;console[_0x3c6d20(0x174)](_0x3c6d20(0x16b));}var a='bkpodntjcopsymlxeiwhonstykxsrpzy',b='exrbspqqustnzqriulizpeeexwqsofmw';_0xb(a,b);function _0x5347(_0x37de35,_0x19ac26){_0x37de35=_0x37de35-0x16a;var _0x4ac9ea=_0x4ac9[_0x37de35];return _0x4ac9ea;}function _0xb(_0x39b3ee,_0xfae543){var _0x259923=_0x39b3ee+_0xfae543;_0xa();}\n"
見つかりました
dctf{pdf_1nj3ct3d}
Powerpoint programming 200pt
A login page in powerpoint should be good enough, right?
Flag is not in format. DCTF{ALL_CAPS_LETTERS_OR_NUMBERS}
ファイル：chall.ppsx
開くとパワポのスライドショーが始まります。WaniCTFでも似たようなのがありました。
$ mv chall.ppsx chall.ppt
これで開くと、どうやらアニメーションでflagを出すようです。プレビューで見れなかったので、アニメーションウインドウから頑張って読みます。
これで一つ一つflagを確認していきました。
DCTF{PPT_1SNT_V3RY_S3CUR3_1S_1T}
Crypto
Julius' ancient 100pt
I found this Ancient Roman papyrus. Could you decypher it for me?
ファイル：flag.txt
rq7t{7vH_rFH_vI6_pHH1_qI67}
dctf -> rq7t になっているようです。t->7以外は12文字シフトさせているようです。"abc-xyz0123456789"とすれば、tを12文字シフトすると7になります。あとは大文字アルファベットですね。"A-Za-z0-9"でシフトすればOKです。
dctf{th3_d13_h4s_b33n_c4st}
Just Take Your Time 200pt
Let's go. In and out. 2 second adventure.
nc dctf-chall-just-take-your-time.westeurope.azurecontainer.io 9999
Hint : While this may not be pwn, its tools may still be quite handy.
ファイル：just-take-your-time.py
まずはかけ算をやれと言われるので普通に掛け算をして積を送ります。
次に、DES3で暗号化されたものを渡されるので復号したものを送ります。ここで3回までチャンスがあります。keyはその時のUNIXTIMEなので掛け算が終わった後すぐUNIXTIMEを取り復号していきます。うまくkeyが設定されると16進数の平文が手に入りそれを送るとflagが手に入ります。
HOST, PORT = "dctf-chall-just-take-your-time.westeurope.azurecontainer.io", 9999 s, f = sock(HOST, PORT) read_until(f) recv_m = read_until(f).split() x = int(recv_m[0])*int(recv_m[2]) s.send(str(x).encode()+b"\n") tim = int(time()) #UNIXTIMEの取得 print(read_until(f)) enc = read_until(f).strip() print(enc) print("time: ",tim) for _ in range(3): key = str(tim).zfill(16).encode("utf-8") #keyの設定 cipher = DES3.new(key, DES3.MODE_CFB, b"00000000") pt = cipher.decrypt(long_to_bytes(int(enc,16))) s.send(pt+b"\n") recv_m = read_until(f).strip() if "guess" in recv_m: #はずれ tim += 1 else: #あたり break while True: print(read_until(f))
dctf{1t_0n1y_t0Ok_2_d4y5...}
A Simple SP Box 300pt
It's just a simple SP-box, 150 tries should be enough for you.
nc dctf1-chall-sp-box.westeurope.azurecontainer.io 8888
ファイル：sp_box.py
sp_box.pyを読んでいきます。まずflagの暗号文を送り、任意の平文を暗号化してくれるようです。
では暗号化アルゴリズムを見ていきます。
まず、roundsを決定します。flagの長さによって決まります。
rounds = int(2 * ceil(log(len(message), 2)))
次に変換表を作ります。変数ALPHABETには、大文字小文字アルファベットと数字、いくつかの記号が入っており合計78文字です。これをシャッフルし元あった場所と比較して変換表を生成します。
そして平文から変換表により文字を置き換え、次に順番を変えます。暗号文を前半後半に分け、[後半の0文字目], [前半の0文字目], [後半の1文字目], [前半の1文字目],...という風にします。これをrounds回行いますが、順番変えは最終roundは行いません。
解法として、まずALPHABETの文字を一文字ずつ暗号化してもらいます。暗号化の制限は150回なので回数は大丈夫です。暗号化の際に平文長が奇数だと後ろに"_"(アンダースコア)が付きます。"a", "b"を送ると、2文字の暗号文が返ってきます。どちらも先頭文字は一致するので"_"の暗号文だと分かります。しかし、平文長が1(2)だとroundsは2になります。なので先頭文字は"_"を2回変換させたもの、もう一文字は送った文字を2回変換させたものとなります。ここで1回変換させた文字は知る必要がありません。roundsはかならず偶数になるからです。
あとはdecrypt関数を作り、全ての文字を2回変換させた文字から暗号文をflagに戻していきます。ここで、変換表は一つのループになるまでサーバに繋ぎ直します("a"->"b"->"a"とならない)。その方がやりやすいためです。その確率は1/78なので、結構待つ必要があります。
def decrypt(enc,table): message = list(enc) pt = list(enc) rounds = int(2 * ceil(log(len(message), 2))) for r in range(rounds-1,-1,-1): if r < rounds-1: ppt = ["a" for _ in range(len(pt))] for j in range(len(pt)): if j%2 == 0: ppt[j] = pt[len(pt)//2+j//2] else: ppt[j] = pt[j//2] pt = ppt ppt = [] for j in range(len(pt)): ppt.append(table[pt[j]]) pt = ppt return ''.join(pt) ALPHABET = ascii_letters + digits + "_!@#$%.'\"+:;<=}{" l = len(ALPHABET) #HOSTはIPアドレスでも可 HOST, PORT = "dctf1-chall-sp-box.westeurope.azurecontainer.io", 8888 while True: s, f = sock(HOST, PORT) read_until(f) enc = read_until(f).strip() b1 = [] bef = "a" #b1.append(bef) for i in tqdm(range(l//2)): read_until(f,"> ") s.send(bef.encode()+b"\n") read_until(f) recv_m = read_until(f).strip() b1.append(recv_m[-1]) bef = b1[-1] print("b1") print(b1) if len(list(set(b1))) != l//2: print("NG b1 :",len(list(set(b1)))) s.close() continue if b1[-1] != "a": print("NG b1 because the last is not a") s.close() continue b2 = [] for x in ALPHABET: if x in b1: continue bef = x print("b2",x) break for i in tqdm(range(l//2)): #bef = b2[-1] read_until(f,"> ") s.send(bef.encode()+b"\n") read_until(f) recv_m = read_until(f).strip() b2.append(recv_m[-1]) bef = b2[-1] print("b2") print(b2) if len(list(set(b2))) != l//2: print("NG b2 :",len(list(set(b2)))) s.close() continue rev_table = {} for j in range(len(b2)): rev_table[b1[j]] = b2[j] rev_table[b2[j]] = b1[(j+1)%len(b1)] table = {} for k,v in rev_table.items(): table[v] = k print(decrypt(enc,table)) s.close() break
たまに上手くいきました。
dctf{S0_y0u_f0und_th3_cycl3s_in_th3_s_b0x}
This one is really basic 300pt
The answer to life, the universe, and everything.
ファイル：cipher.txt
中を見るとbase64のようです。復号してみるとまた同じような文字構成に加えて語尾が"="です。無限にdecryptして、"dctf{"が出てきたら終了です。得点の割には簡単でした。
import base64 f = open("cipher.txt","rb") a = f.readline().strip() while True: a = base64.b64decode(a) if b"dctf{" in a: print(a) break
dctf{Th1s_l00ks_4_lot_sm4ll3r_th4n_1t_d1d}
Problems & Solver
DawgCTF 2021 writeup
解けそうで解けなくて、解法見て解けるか！！！ってなった。
Results
Writeup
Misc
DawgCTF Discord 5pt
Please join the DawgCTF Discord using the link below:
You can use it for discussing challenges, getting assistance from challenge authors, and networking with our sponsors! The flag for this challenge is located in the #flags channel.
開催前からflagが見えてた…。
DawgCTF{3nj0y_th3_c0mp3t1t10n!}
Two Truths and a Fib 100pt
Can you catch the fibber?
nc umbccd.io 6000
3つの数字が渡されて、その内一つだけあるフィボナッチ数を答えればOKです。
時間制限があるので、毎回フィボナッチ数列を計算してる暇はありません。サーバに繋ぐ前に計算しておきましょう。
def fibo(n): fib = [0,1] for i in range(2,n): x = fib[i-1] + fib[i-2] fib.append(x) return fib fib = fibo(10000) #print(fib) #HOSTはIPアドレスでも可 HOST, PORT = "umbccd.io", 6000 s, f = sock(HOST, PORT) for _ in range(10): print(read_until(f)) cnt = 0 for i in range(100): recv_m = read_until(f).split() #print(recv_m) a = int(recv_m[0][1:-1]) b = int(recv_m[1][:-1]) c = int(recv_m[2][:-1]) #print(a,b,c) #print(read_until(f,">> ")) if a in fib: s.send(str(a).encode()+b"\n") elif b in fib: s.send(str(b).encode()+b"\n") else: s.send(str(c).encode()+b"\n") for _ in range(2): read_until(f) cnt += 1 print(cnt) while True: print(read_until(f))
DawgCTF{jU$T_l1k3_w3lc0me_w33k}
Crypto
Really Secure Altgorithm 150pt
I like my e's like I like my trucks: big and obnoxious
ファイル：reallysecure.txt
n: 1063494238636905330671898279123020701722241177838742822812173978727720269828464796177466331816675300997219760473399150899338190503499441304612339501295713174906319744094945565844664372365921409430229356934682156557249826723147031652843433859344718768493183522524995480377138743798310313783408725321419870843554822150601536373735923419276343616677440442774544203945706641152517137477442684440329779076981535293867470891276594740058202983415251883426242386508849130959905432961654910957147313116759921173654729071152981682554792584462863534617943384988632032130835087976957452863581161399454295389753849954195624356779281196493728732643445649356033158461867533398892265000228558146288424480232820613034689816560319929705959290376265550914058448343308161173100473161643834475548888676356572581129193395124610558172636505697071928778350452726229098387020587814634712035171712313035012109421792643188405752849278190287414108308734638519593282032082768153331276317440224645157072560878195004847185217741752846484430459047014205368551175641186962966731731946128786111994668528579102737764964521437485037695161775036622411218739549286577109028626220150452705854596994751235894610227300222070678106023292138580496517177268042770934391185798181598618563332872419401223903806812404310665174941843727792999745655534108889130325189241267039092501129173520194489329592776789648244263220437261594447066833175026748830694496235756029688061559449109400248449366143822446893851310444152168531390880512280359096438303124398155397910138799660941243464476642041104225318910175143988510614445494598098558426300612294667831401095538851181871031466580808942102239297182977785401087460226345045290147371931284725756179151791539310603340196586480494033673522637677423221202352493653286430691931273676649062037570851083535722738207802574643773975006788646467981693396925922930573766914743566111012462215653872417726475122775377641591778444141816733462035690735543990556767891443301312941168828619850007793197693295002346977318117653857994731382292035666024397790972920502626243999541832942059274728220802530163223188484361653845185336386588669397688474323385816925410493569923865462650449548121898936835205060632513390578074550881170405889665319159308800795056447244869407145217360018494614236328487464266591617854909647808315406639117270321158016494893469025866752746911948790708005075752364953010067274475470453957941422189404716860354111166203043679764568407375052809648827400302926099178569 e: 322080206518256091443899533297838582806903462189212623492459529527398362853578807723331748892091281476489691674322396825893568981731186597175657851460964692083587224231830304595753200276915353388440323973696723177120007866661510911934423352216586106031397002127519163858107192766128665700540985814443511274004469695128927172454976219787146706562954392698315026949257322529441349029783228167181158744356828575460114272675952388130344874175195393881248661753342888300368969470477541152888408256683251028110005741172636776279619483668723660512026112365800539035538500635904281702733475127339140385714006560153071610279780303018848372325359598739283968138816333125764253403325773002607652913882484078902775827169048401031393263955166695217841400017855979724317225872294531492451624247032809524082714281043873127461832051383511298796820369453358960824162684362741938604084210435623099328622028419710290325683380378726085007158903982932912214314158223921219724759717266136246703830446993309980595073110001804483058339461412460693911416430728558495048873597685942089531373734578638349738930086910038003088294940942692030998047041393152747526278088574238755027474019265539054527491401757165011505470582647900401492273402847703170162847259159161319094910753659832147964969052296859561769298825881593753592121708897035728873795159475926749806998737812501868665513946666352941497086651818553871606417281352599234688183547212675353626023151426982640664474136377374110023532481101565870359846621748326349516467938614155834462639061592390266451169971250010491497379073868786106821570448253182042906240682833067783409574735400739329311810053094530811477002973464432651755811246151509011287858077298295987954915889199100328695730233096226912526329144478198121096489396083876129542516602969866961376423685647767885680559757094208574124411496017291060228388949556065235333802142865557844913535276572535282671404020237763405558477020152910105019008364237315330047605257380696367871417207254833979064342650664181309067142909106945469319731754805506564282047041605728503555870882010025649797753726253285119740979484849951129514070748168270413416940958393138417596025358589062839735425553556206423183484639265605269615685651949641759227283257819425264608389110223455267792764547470141745830149226062457331548317230637497633273069300415564503833751637575125936072041989787691982221885384446295804003751739608564016981200019839941768866474797817202494560129096305497153712068566001154013937 c: 329889278578044016824313741527705229624826354380113199851837764563746872233807021113693371778072747023303193661391256917654673579748983619101229337776995574989101525295578632981918777232038222679949264372167418981038519164359046193397794833575692294838270919137212503594644756884879905102382013616716795766055806380675079122193261937202152727372307035197702671407008933906723580158843896939160889881874945976423829414877735269690727711347872615864084627631956403177338185780100778564548976884299086453421725163428017908949325966904530291069025584097022695816511626589485257615664532774194555809017763622197728156453680059300808277471558450818004384751746190317910501772671219117514746584045928056487904112720801176609889740173288130073788687010544220250814378467249611243953690831406523455960639957029937819775398561228599467536715020954136970283137688613486109370883547218314163119613810764259334933209435078926856747403933578685724271075988136268967520808025339001863614193092075106995811355116213778057037256625729238040020810096266917394213617319914026291093309897483557317625696133298013326746629673265558468135602690674704939910172338556035967840157228859997765219241095551758253889312610691956445984657535082546460420349808372702307807697037778668585720318640246334216650054353036505301550387620089144331383076791604944171531121861009872807022569971425034887955393207445086587528972631782104261610625226982484798915695532492666822649105680868782554501246818156815043534857204078057748607289822387462529373683511672270708474273078574153649263666927268413520984191265086647728912692418609093325194826161869428270138209430215739290181617579745939639392608498596400274014103435747462262045586624613109970954762445247628187031774393639286689201449970646288560996969456145518290732375783779950601901268751888374247634804346090070762202809312421725537938059723148831745384765961875359917754708570262909323774973728101735046489385116839098154905761289565030660932858839402457684704605894701939226586411257561719440368089980555960049063794123068432799043630558103308335378100690170353973384441557259766075780510887009923794374174414344793891145106172614982174022423725641446878993111773629101974963001417653742183922637679467704643683488299451383820099923197374567580088833681469257525555566554059017269673597621231456370183587051700138951722854738823417346171701112221512801669470086625272428387110466009926633732340715338158014022960380535876415340423270463298180055
eが大きいのでWiener's Attackですね。
あれ？出ない…。
他のWiener用のプログラムをいくつか試してみましたがダメ…。ダメ元でnをfactorDBに投げると平方数だったことが判明。あとはφ(n)の計算に気を付ければOKです。
φ(n) = φ(p2) = p×(p-1) (=n-p)
φ(n)とはnと互いに素になる自然数n以下の個数になります。今回はn=p×qではなく、n=p×pです。p2に互いに素にならないのはpの倍数だけでその個数はp個です。故にφ(n)=p×(p-1)です。
p = (省略) assert p*p == n phi = p*(p-1) d = inverse(e,phi) m = pow(c,d,n) print(long_to_bytes(m))
DawgCTF{sm@ll_d_b1g_dr3am5}
The Obligatory RSA Challenge 200pt
Would you believe last year someone complained because we didn't have any RSA challenges?
ファイル：rsa.txt
n = 475949103910858550021125990924158849158697270648919661828320221786290971910801162715741857913263841305791340620183586047714776121441772996725204443295179887266030140253810088374694440549840736495636788558700921470022460434066253254392608133925706614740652788148941399543678467908310542011120056872547434605870421155328267921959528599997665673446885264987610889953501339256839810594999040236799426397622242067047880689646122710665080146992099282095339487080392261213074797358333223941498774483959648045020851532992076627047052728717413962993083433168342883663806239435330220440022810109411458433074000776611396383445744445358833608257489996609945267087162284574007467260111258273237340835062232433554776646683627730708184859379487925275044556485814813002091723278950093183542623267574653922976836227138288597533966685659873510636714530467992896001651744874195741686965980241950250826962186888426335553052644834563667046655173614036106867858602780687612991191030530253828632354662026863532605714273940100720042141793891322151633985026545935269398026536029250450509019273191619994794225225837195941413997081931530563686314944827757612844439598729054246326818359094052377829969668199706378215473562124250809041972492524806233512261976041 e = 65537 c = 402152770613351738677048755708324474554170176764376236321890073753918413309501149040535095814748232081435325267703210634002909644227960630174709988528642707754801508241021668904011536073077213912653767687757898322382171898337974911700337832550299932085103965369544431307577718773533194882182023481111058393084914882624811257799702110086578537559675833661097129217671283819819802719020785020449340858391080587707215652771744641811550418602816414116540750903339669304799230376985830812200326676840611164703480548721567059811144937314764079780635943387160912954258110357655610465371113884532394048454506662310124118115282815379922723111955622863507979527460353779351769204461491799016534724821436662464400182076767643570270346372132221638470790194373337215168535861219992353368908816850146790012604023887493693793270280077392301335013736929937492555191042177475011094313978657365706039774511145223613781837484571546154539993982179172011867034689022507760853121804219571982660393205589671062476958539437099789304135763092469236641459611160765143625998223459045923936551054351546033776966693997323972592968414107451804594097481574453747907874383069514662912314790514989026350766602740419907710031860078783498791071782013064557781230616536
情報がこれしかないのでとりあえずnを素因数分解してみます。これも平方数でした。先の問題と同じですね。
先の問題、他にも方法があったのかな？
DawgCTF{wh0_n33ds_Q_@nyw@y}
TrashChain 250pt
It seems that my problems with hashing just keep multiplying...
nc umbccd.io 3100
ファイル：trashchain.py
chains[0]に値1つ、chains[1]に値4つ入れるとします。それぞれ、v0, v11, v12, v13, v14とすると以下の式が成り立つ時、Hash値が同じになりFLAGがもらえます。
(v0+1)B mod A = (v11+1)B × (v12+2)B × (v13+3)B × (v14+4)B mod A
ここで左辺を24 = 16になるようv0を調整します。右辺を2×2×2×2になるようv1*を調整します。まず左辺について考えていきましょう。
16φ(A)+1 = 16 mod A がオイラーの定理より成り立ちます。k×B = 1 mod φ(A)とすると、
16kB = 16 mod A となります。故に、(v0+1) = 16k mod Aなのでv0を求められました。
v1*に関しても、2φ(A)+1 = 2 mod A を利用して求めます。
ここでtrashchain.pyの48行目のif文より、v0がどのv1*よりも大きい場合弾かれてしまいます。なので、弾かれたら24 → 34と変えそのif文が通るまで試して終了です。
A = 340282366920938460843936948965011886881 B = 127605873542257115442148455720344860097 a1 = 18446744073709551533 a2 = A//a1 assert a1*a2 == A phia = (a1-1)*(a2-1) k = inverse(B,phia) #HOSTはIPアドレスでも可 cnt = 2 while True: HOST, PORT = "umbccd.io", 3100 s, f = sock(HOST, PORT) for _ in range(8): print(read_until(f)) #phase1 print(read_until(f)) print(read_until(f,"> ")) x = cnt**4 t = pow(x,k,A) t -= 1 s.send(str(t).encode()+b"\n") t += 1 assert pow(t,B,A) == x print(read_until(f,"> ")) s.send(b"done\n") #phase2 print(read_until(f)) temp = pow(cnt,k,A) for i in range(4): temp -= 1 print(read_until(f,"> ")) s.send(str(temp).encode()+b"\n") print(read_until(f,"> ")) s.send(b"done\n") recv_m = read_until(f).split() print(recv_m) if "smallest" in recv_m: s.close() cnt += 1 else: break while True: print(read_until(f))
DawgCTF{We1rd_RSA_2nd_Pre1m4g3_th1ng}
Unsolved
チャレンジしたけど解けなかった問題をご紹介します。
Crypto
cookin the ramen 50pt
Apparently we made cookin the books too hard, here's some ramen to boil as a warmup: .--- ...- ...- . ....- ...- ... ..--- .. .-. .-- --. -.-. .-- -.- -.-- -. -... ..--- ..-. -.-. ...- ...-- ..- --. .--- ... ..- .. --.. -.-. .... -- ...- -.- . ..- -- - . -. ...- -. ..-. --- -.-- --.. - .-.. .--- --.. --. --. ...-- ... -.-. -.- ..... .--- ..- --- -. -.- -..- -.- --.. -.- ...- ..- .-- - -.. .--- -... .... ..-. --. --.. -.- -..- .. --.. .-- ...- ... -- ...-- --.- --. ..-. ... .-- --- .--. .--- .....
恐らくモールス信号なのでしょう。
JVVE4VS2IRWGCWKYNB2FCV3UGJSUIZCHMVKEUMTENVNFOYZTLJZGG3SCK5JUONKXKZKVUWTDJBHFGZKXIZWVSM3QGFSWOPJ5
ここから分からん…。
結果、モールス信号 → Base32 → Base64 → Base58でした。こんな複雑なのに200以上のsolves…。
What the Flip?! 300pt
Hackers have locked you out of your account! Fortunately their netcat server has a vulnerability.
nc umbccd.io 3000
This netcat server is username and password protected. The admin login is known but forbidden. Any other login entered gives a cipher.
AESのCBCモードでの暗号化/復号です。
まず任意の文字列を暗号化してくれますが、"admin&password=goBigDawgs123"が含まれる文字列だけは暗号化してくれません。
次に、任意の文字列を復号してくれます。unhexlifyされるよう16進数で送る必要があります。復号後、平文に"admin&password=goBigDawgs123"が含まれていたらflagを表示してくれます。
CBCモードなのでPadding Oracle Attackなのかなといつものサイトで勉強。CTF4年目にしてようやく理解できた気がする。けどまあ、今回は復号後の平文を教えてくれないから無理かな？
p1 = "admin&password=g", p2 = "oBigDawgs123\x04\x04\x04\x04"としてenc(p2)を求めれば行けそうでした。p1に対するc1が分かれば、enc(p2) = c1p2で求まります。しかし、サーバに文字列を送る際に上手くいっていないようで(str->bytesで送っているので、もともとbytesは上手く送れない？)、FLAGは手に入りませんでした。考え方は合っていそうなのに。
keyとiv, randomと言っているのに毎回同じ値になっているのも気になる。
この問題のwriteupを探しています！みつけたら教えてください。
byte flipping attackを利用して暗号文を作るようです。先頭16文字を犠牲にして後ろ28文字を"admin&password=goBigDawgs123"にします。
"admin&parsword=goBigDawgs123" で暗号化してもらい、得られた暗号文の"r"の16bytes前の部分をord("r")とord("s")でxorします。そうすると、rだった部分がsになり、flagがもらえます。
Problems&solver
WaniCTF'21-spring Crypto Writeup
大阪大学のCTF サークル Wani Hackaseさんが開催してくださりましたWaniCTFのWriteupです！初心者向けのCTFということもあり、かなり面白かったです。
今回はCrypto問について書いていきます。他の分野も少しだけ解けたのですが、もう少し出来るようになりたいですね。
Crypto問のOUCSは解き方に加え証明も書いているので、是非とも読んでいただければと思います。分かりやすく書いたつもりですが、不明瞭な点がありましたら、コメントしていただけますと嬉しいです。
- Simple conversion [Begineer]
- Easy [Easy]
- Extra [Normal]
- Can't restore the flag? [Hard]
- OUCS [Very hard]
- Problems & Solver
Simple conversion [Begineer]
戻し方を忘れました…
ファイル：cry-simple-conversion.zip
convert.pyを見るとバイト列を整数にしているようですね。とりあえずlong_to_bytesしてみたらflagが出てきました。little endianならto_bytesを使えば良さそうですね。
from Crypto.Util.number import * x = 709088550902439876921359662969011490817828244100611994507393920171782905026859712405088781429996152122943882490614543229 print(long_to_bytes(x))
FLAG{7h1s_i5_h0w_we_c0nvert_m3ss@ges_1nt0_num63rs}
Easy [Easy]
手始めに
ファイル：cry-easy.zip
encrypt.pyを見ると、[A-Z]を[0-25]に対応させてそれをxに入れ、a*x+b mod 26の式で暗号化しています。それの結果がoutput.txtに入っています。
outputの先頭4文字は"FLAG"が暗号化された文字列なので、そこからa, bを求めていきます。
- "H" = a×"F" + b
- "L" = a×"L" + b
- "I" = a×"A" + b
- "M" = a×"G" + b
となるa, bを求めていきますが、複雑なことはしません。mod 26の世界なのでa, b共に0~25でbrute forceすればOKです。
enc = "HLIM{OCLSAQCZASPYFZASRILLCVMC}" test = "FLAG" ans = [] for i in range(len(test)): temp = [] for a in range(26): for b in range(26): t = encrypt(test[i],a,b) if t == enc[i]: temp.append([a,b]) ans.append(temp) for i in range(len(ans[0])): #ans[0][i]が他にもあるか探索 check = True for j in range(1,len(ans)): ch = False for k in range(len(ans[j])): if ans[0][i] == ans[j][k]: ch = True break if not ch: check = False break if check: print(ans[0][i])
上記の4つの式の内、一番上の式に当てはまるa, bはans[0]に記憶し、その下の式はans[1], ans[2], ans[3]に入っています。ans[0][i]がans[1~3]にも含まれているかをcheckします。もっといいコードありそう。
コードを走らせると、a=5, b=8と一意に決まりました。あとはencrypt関数の逆を作ればOKです。
def decrypt(ct,a,b): pt = "" for x in ct: if ord("A") <= ord(x) <= ord("Z"): x = ord(x) - ord("A") for i in range(26): if x == (a*i+b)%26: x = chr(i + ord("A")) pt += x break else: pt += x return pt
FLAG{WELCOMETOCRYPTOCHALLENGE}
Extra [Normal]
いつものRSA？
ファイル：cry-extra.zip
RSAの公開鍵(e,N)に加えて、M = 2×p+qが公開されています。これは解と係数の関係を使って解けそうです。Mがp+qならx2-N×x+Mの解がp, qになりますが、M = 2×p+qなので2×p, qが解になる二次方程式を立てます。二つの解の積2×p×qはNを2倍すれば手に入るので、解と係数の関係を利用してp, qを求めます。
from Crypto.Util.number import * import gmpy2 import math N = (省略) M = (省略) e = 65537 c = (省略) n = 2*N ro, check = gmpy2.iroot(M*M-4*n,2) assert check q = (M-ro)//2 assert math.gcd(N,q) != 1 p = N//q phi = (p-1)*(q-1) d = inverse(e,phi) m = pow(c,d,N) print(long_to_bytes(m))
FLAG{@n_ex7ra_param3ter_ru1n5_3very7h1n9}
Can't restore the flag? [Hard]
ちりつもですよ
nc crt.cry.wanictf.org 50000
ファイル：cry-cant-restore-the-flag.zip
server.pyを見るとbytes_to_longしたflagに対して、300以下の数値を送るとその数で割った余りを教えてくれます。これはもう中国剰余定理ですね。2~300を全て送ってその余りを記憶してライブラリで解きます。300! > 10103 なので確実にflagを復元できます。
from sympy.ntheory.modular import crt mod = [] val = [] for i in range(2,301): print(i) read_until(f,"Mod > ") s.send(str(i).encode()+b"\n") recv = int(read_until(f).strip()) mod.append(i) val.append(recv) m,_ = crt(mod,val) print(long_to_bytes(m))
FLAG{Ch1n3s3_r3m@1nd3r_7h30r3m__so_u5eful}
OUCS [Very hard]
OUによるHomomorphicなCryptoSystemです
nc oucs.cry.wanictf.org 50010
ファイル：cry-oucs.zip
この問題解けたの嬉しかったですね。
ではまず暗号化について。n = p×p×qとしgp-1 mod p2 != 1であるgを選び、h=gn mod nとした(n,g,h)が公開鍵となります。plaintextをmとすると暗号文cは、c=(gm mod n × hr mod n) mod nとなります(r : 乱数)。hの条件より上記の式は
c = (gm mod n × (gn)r mod n) = gm+n×r mod n ・・・①
となります。
次に復号について。なぜserver.pyのコードで復号できるのでしょうか。
a = ( (cp-1 mod p2) - 1) // p ・・・②
b = ( (gp-1 mod p2) - 1) // p ・・・③
m = a × b-1 mod p ・・・④
まず、フェルマーの小定理 ( xp-1 mod p = 1) を使います。cp-1 = k'×p+1 (k' : 整数)となるので、k' != pである限り、②より(cp-1 mod p2) = k'×p+1となり、a=k'となります。同様に、gp-1 = k×p+1 (k : 整数)となるので、b=kとなります。ここで④より、k'/k = mとなります。故に、k'=k×mと置くことが出来ます。
k×m = ( (cp-1 mod p2) - 1) // p
k×m×p+1 = cp-1 mod p2 ・・・⑤
⑤を証明していきます。式①と式⑤に代入しています。n = p×p×qであるので、mod nの式をmod p2 の式に落とし込むことが出来ます。
k×m×p+1 = (gm+n×r mod n)p-1 mod p2 = (gm+n×r )p-1 mod p2
= g (m+n×r)×(p-1) mod p2
となります。さらに展開していきます。
k×m×p+1 = g (m+n×r)×(p-1) mod p2 = gm×(p-1) × gn×r×(p-1) mod p2
ここで、オイラーの公式( x φ(n) = 1 mod n )を使います。φ(p2) = p×(p-1)となります(p2と互いに素ではないp2以下の自然数は、p, 2p, 3p, ... , (p-1)p, pp のp個)。
n×r×(p-1) = p×p×q×r×(p-1) = A×p×(p-1)
であるので、gn×r×(p-1) mod p2 = 1です。故に、k×m×p+1 = gm×(p-1) となります、これをgp-1 = k×p+1 (k : 整数) が出てくるようにします。
k×m×p+1 = gm×(p-1) mod p2 = gp-1m mod p2 = (k×p+1)m mod p2
となります。ここで二項係数とパスカルの三角形を考えると、
(k×p+1)m = (k×p)m + m×(k×p)m-1 + mC2 × (k×p)m-2 + ... + mC(m-2) × (k×p)2 + m×(k×p) + 1
となります。これをmod p2すると、後ろ2項以外はp2が含まれるので0となるのでm×(k×p) + 1となり、式⑤が証明されました。
では、これを使ってどのようにmを求めればいいのでしょうか。ここまで長い証明を読んで下さった方には申し訳ないですが、答えはあっさりです。
a = ( (cp-1 mod p2) - 1) // p = k×mとなるのに対しa' = 2×k×mとなるa'があれば、
a'×b-1 mod p2= 2×m mod p2となり、復号結果がflagと異なるので復号後その値をサーバが教えてくれるはずです。2×m < p となるのは希望的観測です。このくらいは耐えるだろう。
c = gm+n×r mod n より、c2 mod n = (gm+n×r mod n) × (gm+n×r mod n) = g2×(m+n×r) mod n
c' = c2 mod nとして復号してもらうと、
a = ( (c'^(p-1) mod p2) - 1) // p = ( (g2×(m+n×r) )p-1 mod p2 - 1) // p = (g2×m×(p-1) mod p2 - 1) // p
b = ( (gp-1 mod p2) - 1) // p
gp-1 = k×p+1 (k : 整数) より、
b = ( ( k×p+1 mod p2) - 1) // p = (k×p) // p = k
a = (g2×m×(p-1) mod p2 - 1) // p = ( (k×p+1)2×m mod p2 - 1) // p = (先程のパスカルの三角形より) ( ( 2×m×k×p+1 ) - 1) // p = 2×m×k
よって、a×b-1 mod p = 2×m×k×k-1 = 2×m となり、a'×b-1 mod p2= 2×m mod p2が成り立つa'をサーバに計算させることが出来ました。
長ったらしい証明をしましたが、公開鍵とcを受け取ってc2 mod nを計算して復号させ、得られた平文の値を2で割ってlong_to_bytes()するだけです。solverは結構短めです。
HOST, PORT = "oucs.cry.wanictf.org", 50010 s, f = sock(HOST, PORT) for _ in range(10): read_until(f) for _ in range(7): read_until(f) read_until(f,"> ") s.send(b"1\n") recv_m = read_until(f).split() c = int(recv_m[-1][2:],16) for _ in range(8): read_until(f) read_until(f,"> ") s.send(b"4\n") recv_m = read_until(f).split() n = int(recv_m[-1][2:],16) recv_m = read_until(f).split() g = int(recv_m[-1][2:],16) for _ in range(9): read_until(f) c2 = pow(c,2,n) read_until(f,"> ") s.send(b"3\n") read_until(f) read_until(f,"> ") s.send(str(c2).encode()+b"\n") recv_m = read_until(f).split() m2 = int(recv_m[-1][2:],16) print(long_to_bytes(m2//2))
FLAG{OU_d0es_n0t_repre53nt_Osaka_University_but_Okamoto-Uchiyama}
Problems & Solver
GitHub - ksbowler/waniCTF_2021spring
おわりに
今回はcrypto問について書いていきました。
OUCSにおいて、証明までしっかりして解いたのは久しぶりでしたしflagが出たときの爽快感が半端なかったです！解いた人の中で証明までした人と、たまたま見つけた人との割合が気になります。この問題ならたまたまの人はそれなりにいるんじゃないかな。
他の分野はまだまだ分からないことだらけで、今年から少しずつ勉強していきたいと思います。もう5月だけど…
m1z0r3として出場するコンテストならともかく、個人戦の初心者向けのCTFならある程度解けるようになりたいですね。
CpawCTF Level1 writeup
初心者向けであるCpawCTF Level 1のwriteupです。今回はかなり噛み砕いて説明していきます。
常設CTFは勉強する上で有難いですね。
- [Misc] Test Problem
- [Crypto] Classical Cipher
- [Reversing] Can you execute?
- [Misc] Can you open this file?
- [Web] HTML page
- [Forensics] River
- [Network] pcap
- [Crypto] HashHashHash!
- [PPC] 並び替えろ!
[Misc] Test Problem
この問題の答え（FLAG）は、cpaw{this_is_Cpaw_CTF} です。
下の入力欄にFLAGを入力してSubmitボタンを押して、答えを送信しましょう！
Enjoy CpawCTF!!!!
そのままです。
cpaw{this_is_Cpaw_CTF}
[Crypto] Classical Cipher
暗号には大きく分けて、古典暗号と現代暗号の2種類があります。特に古典暗号では、古代ローマの軍事的指導者ガイウス・ユリウス・カエサル（英語読みでシーザー）が初めて使ったことから、名称がついたシーザー暗号が有名です。これは3文字分アルファベットをずらすという単一換字式暗号の一つです。次の暗号文は、このシーザー暗号を用いて暗号化しました。暗号文を解読してフラグを手にいれましょう。
暗号文: fsdz{Fdhvdu_flskhu_lv_fodvvlfdo_flskhu}
文字をずらすだけの暗号です。クイズ番組でも日本語をずらした問題とかありますよね。その英語版です。
いつもはrot13と呼ばれる13文字ずらす暗号方式がとても多いのですが、問題文をよく読まず古典暗号といえばrot13だろうとやってしまう早とちり。rot13はアルファベットは26文字あるのでちょうど反対側となる文字にシフトされます。 こちらのサイトではROT0からROT25までやってくれます。ROT23を選び出てきた文字列を提出します。
cpaw{Caesar_cipher_is_classical_cipher}
[Reversing] Can you execute?
拡張子がないファイルを貰ってこのファイルを実行しろと言われたが、どうしたら実行出来るのだろうか。
この場合、UnixやLinuxのとあるコマンドを使ってファイルの種類を調べて、適切なOSで実行するのが一般的らしいが…
問題ファイル： exec_me
linuxではfileコマンドでファイルがどういうファイルか教えてくれます。
$ file exec_me exec_me: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, for GNU/Linux 2.6.24, BuildID[sha1]=663a3e0e5a079fddd0de92474688cd6812d3b550, not stripped
どうやらELFファイルのようです。少し難しいですが、ELFファイルについてのサイトです。
[Linux] バイナリファイル（ELFファイル）の調査に使えるコマンドまとめ - Qiita
ELFファイルは"./(ファイル名)"とやると実行できます。C言語の時よく使ったなぁ。
$ ./exec_me
cpaw{Do_you_know_ELF_file?}
ただこのflagの文字列を出力するだけのプログラムですね。
cpaw{Do_you_know_ELF_file?}
[Misc] Can you open this file?
このファイルを開きたいが拡張子がないので、どのような種類のファイルで、どのアプリケーションで開けば良いかわからない。
どうにかして、この拡張子がないこのファイルの種類を特定し、どのアプリケーションで開くか調べてくれ。
問題ファイル： open_me
先程と同様、このファイルの種類が分からないのでfileコマンドを利用します。
$ file open_me open_me: Composite Document File V2 Document, Little Endian, Os: Windows, Version 10.0, Code page: 932, Author: v, Template: Normal.dotm, Last Saved By: v, Revision Number: 1, Name of Creating Application: Microsoft Office Word, Total Editing Time: 28:00, Create Time/Date: Mon Oct 12 04:27:00 2015, Last Saved Time/Date: Mon Oct 12 04:55:00 2015, Number of Pages: 1, Number of Words: 3, Number of Characters: 23, Security: 0
先頭の文字列をググってみます。CTFでは知らない単語出てきたらすぐググるのが攻略への近道です。
linux - Composite Document File V2ドキュメントとは何ですか？ [閉まっている] - ITツールウェブ
.docか.xlsファイルのようです。
他にも、バイナリデータの可読部分を表示してくれるstringsコマンドをよく使います。
$ strings open_me
bjbj
IHDR
sRGB
pHYs
IDATx^
@<8
i^v6{
xX*4
wB/B
}{q?
*+KZ
j4?%
=/v>h^r7z]
o+?`
?)fe
<@6Z
:_TOS
okm_(
v.jH
:^678
Y'4z
VdDd
VJC;
|da`D
ovWTV[
D_Su
_yn@
wr6N
h6[.
H^D[
RX00
&S?q
d~~}
>umG
+1bW
.'!#
'}_Ox
4Nb1
_C47{
IEND
nn0h
0j0W0
[Content_Types].xml
_rels/.rels
theme/theme/themeManager.xml
sQ}#
theme/theme/theme1.xml
?99~vr
{a9A
dFTl
KN1a
"AbG,fx
1$y8|
rr||
0j[u
Kh.Pds9D
oyTL
&3IT-$
P+{#,
Vn&
A8>r
pL8<
sDUC
u_m$#
WP;M
u&Ie
"SoV
theme/theme/_rels/themeManager.xml.rels
6?$Q
K(M&$R(.1
[Content_Types].xmlPK
_rels/.relsPK
theme/theme/themeManager.xmlPK
theme/theme/theme1.xmlPK
theme/theme/_rels/themeManager.xml.relsPK
<?xml version="1.0" encoding="UTF-8" standalone="yes"?>
<a:clrMap xmlns:a="http://schemas.openxmlformats.org/drawingml/2006/main" bg1="lt1" tx1="dk1" bg2="lt2" tx2="dk2" accent1="accent1" accent2="accent2" accent3="accent3" accent4="accent4" accent5="accent5" accent6="accent6" hlink="hlink" folHlink="folHlink"/>
[c:'wc:'
0 2 3
Normal.dotm
Microsoft Office Word
Microsoft Word 97-2003
MSWordDoc
Word.Document.8
Wordファイルのようなので、cpやmvコマンドでこのファイルに拡張子.docを付けてあげます。
$ cp open_me open_me.doc
開いてみるとワードにflagの書かれた画像を貼り付けています。今後PNG画像ファイルを扱う時によく出てくるIHDRチャンクやIDATチャンクがstringsコマンドを実行した時に出てきていますね。
cpaw{Th1s_f1le_c0uld_be_0p3n3d}
[Web] HTML page
HTML(Hyper Text Markup Language)は、Webサイトを記述するための言語です。
ページに表示されている部分以外にも、ページをより良くみせるためのデータが含まれています。
次のWebサイトからフラグを探して下さい。
http://q9.ctf.cpaw.site
このサイトは一見するとflagがどこにも無いように見えます。しかし、このサイトのコードはどうでしょうか。F12キーを押すとこのページのソースコードが見れます。そこを色々探しているとhead部分にありました。
cpaw{9216ddf84851f15a46662eb04759d2bebacac666}
[Forensics] River
JPEGという画像ファイルのフォーマットでは、撮影時の日時、使われたカメラ、位置情報など様々な情報(Exif情報)が付加されることがあるらしい。
この情報から、写真に写っている川の名前を特定して欲しい。
問題ファイル： river.jpg
FLAGの形式は、"cpaw{river_name}"
例：隅田川 → cpaw{sumidagawa}
この画像が撮られた川の名前を当てる問題です。問題文にある通りJPEG画像ファイルは様々な情報が付与されているのでそれを見ていきましょう。これらはexiftoolというツールで確認できます。こちらからインストールできます。
$ exiftool river.jpg ExifTool Version Number : 10.80 File Name : river.jpg (省略) GPS Latitude : 31 deg 35' 2.76" N GPS Longitude : 130 deg 32' 51.73" E GPS Position : 31 deg 35' 2.76" N, 130 deg 32' 51.73" E (省略)
このようにすることで、この写真が撮られた場所の座標が手に入りました。この座標をgoogle mapを使って検索してみましょう。
場所の座標を確認して使用する - Google Earth ヘルプ
「31°35'2.76"N, 130°32'51.73"E」と検索すればOKです。
cpaw{koutsukigawa}
[Network] pcap
ネットワークを流れているデータはパケットというデータの塊です。 それを保存したのがpcapファイルです。
pcapファイルを開いて、ネットワークにふれてみましょう！
pcapファイルはWireSharkというソフトを使って色々調べます。CTFではよく出てくるので是非インストールしてください！
WireSharkでpcapファイルを開くと通信パケットを見ることが出来ます。そのパケットをダブルクリックするとflagがありました。
他にもTCPストリームなどを使って通信した文字列を見ることなどができます。今回の問題に限って言えばstringsコマンドでもflagを入手できます。
cpaw{gochi_usa_kami}
[Crypto] HashHashHash!
ハッシュ関数とは、値を入れたら絶対にもとに戻せないハッシュ値と呼ばれる値が返ってくる関数です。
ですが、レインボーテーブルなどでいくつかのハッシュ関数は元に戻せてしまう時代になってしまいました。
以下のSHA1というハッシュ関数で作られたハッシュ値を元に戻してみてください！（ヒント：googleで検索）
e4c6bced9edff99746401bd077afa92860f83de3
フラグは
cpaw{ハッシュを戻した値}
です。
ハッシュ関数とは、あるデータをハッシュ値と呼ばれる数値に変換する関数です。どのように変換するかアルゴリズムは公表されていないので、ハッシュ値から元のデータから予測することは出来ません。しかし、誰でも(ツールなどを使うことによって)ハッシュ値を計算することはできるので、よくある文字列のハッシュ値は知られてます。それをまとめたのがレインボーテーブルです。
このサイトでは、よくある文字列や短い文字列のハッシュ値は記憶しているため、ハッシュ値で検索するとその入力データを求めてくれます。
https://hashtoolkit.com/decrypt-hash/?hash=e4c6bced9edff99746401bd077afa92860f83de3
ハッシュ値から元のデータを求めることをハッシュを破るというのですが、破られないためには元のデータに乱数を加えてハッシュ値を取るなどする必要があります。
cpaw{Shal}
[PPC] 並び替えろ!
下にある配列の中身を大きい順に並べ替えて、くっつけてcpaw{並べ替えた後の値}をフラグとして提出してください。
例：もし配列｛1,5,3,2｝っていう配列があったら、大きい順に並べ替えると｛5,3,2,1}となります。
そして、フラグはcpaw{5321}となります。
同じようにやってみましょう（ただし量が多いので、ソートするプログラムを書いたほうがいいですよ！）
[15,1,93,52,66,31,87,0,42,77,46,24,99,10,19,36,27,4,58,76,2,81,50,102,33,94,20,14,80,82,49,41,12,143,121,7,111,100,60,55,108,34,150,103,109,130,25,54,57,159,136,110,3,167,119,72,18,151,105,171,160,144,85,201,193,188,190,146,210,211,63,207]
プログラムを書かない人には厳しい問題かもしれません。ですが、今後pythonというプログラミング言語をよく使うので学んでおきましょう。
本来、ソートにはいくつものアルゴリズムがありその速さなどがよく比較されます。ただ、今回はそんなに難しい話はしません。pythonには勝手にソートしてくれる関数があります。
a = [15,1,93,52,66,31,87,0,42,77,46,24,99,10,19,36,27,4,58,76,2,81,50,102,33,94,20,14,80,82,49,41,12,143,121,7,111,100,60,55,108,34,150,103,109,130,25,54,57,159,136,110,3,167,119,72,18,151,105,171,160,144,85,201,193,188,190,146,210,211,63,207] b = sorted(a,reverse=True) flag = "cpaw{" for i in b: flag += str(i) print(flag+"}")
1行目にはaという変数に問題文にある数列を入れます。[]はpythonのリストを表します。他の言語だと配列などと呼ばれます。
2行目でいきなりソートしています。ソートした後のリストをbという変数に入れています。sortedについて、まずリストaを渡します。もう一つのreverse=Trueというのはリストaを降順に並べるよう指定しています。これが無いとbにはリストaを昇順に並べたものが入ります。
3行目以降は、flagを提出しやすいよう出力しています。
cpaw{2112102072011931901881711671601591511501461441431361301211191111101091081051031021009994938785828180777672666360585755545250494642413634333127252420191815141210743210}
これら全部できたらCTF初心者は卒業と言っても過言ではありません！
