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はある論文を読んだとのことですが、「この論文を完全に理解できるほど賢くなかった」と言ってます。いやこの問題解けるんだから充分賢いよ。