hsctf 8 writeup
Result
Writeup
aptenodytes-forsteri 184pt
Here's a warmup cryptography challenge. Reverse the script, decrypt the output, submit the flag.
ファイル：aptenodytes-forsteri.py, output.txt
flag{}内が大文字アルファベットで、ROT18しているようです。ROT8して復元です。
意味わからない文字列かと思ったけど、キーボードの上段でした。
flag{QWERTYUIOP}
queen-of-the-hill 222pt
After finding a special key of the Hill, which contains a note to visit the Queen of the Hill, our brave Amanda begins her adventure to find the Queen of the Hill’s treasure. How shall she meet the Queen of the Hill? (a=0)
Cipher text: rtca{vbuhp_kaiq_gfj_nx_rda_ujw}
Encryption key:
16 25 8
14 19 5
15 17 3
実は前回のhsctfのcrypto問題、全完まであと少しでした。というのも唯一解けなかった「xkcd.com/2247」がflag出ていたのに見逃していました。
なんでこの話をしたのかというと、どちらもHill Cipherを使っているからです。前回の最終問題が、今回2問目で出てくる！？とかなりビビりました。
これを使って復号しました。
Hill Cipher - Decoder, Encoder, Solver - Online Calculator
flag{climb_your_way_to_the_top}
opisthocomus-hoazin 303pt
The plural of calculus is calculi.
ファイル： opisthocomus-hoazin.py, output.txt
flagを1文字ずつ65537とxorしているだけです。
e = 65537 ct = [65639, 65645, 65632, 65638, 65658, 65653, 65609, 65584, 65650, 65630, 65640, 65634, 65586, 65630, 65634, 65651, 65586, 65589, 65644, 65630, 65640, 65588, 65630, 65618, 65646, 65630, 65607, 65651, 65646, 65627, 65586, 65647, 65630, 65640, 65571, 65612, 65630, 65649, 65651, 65586, 65653, 65621, 65656, 65630, 65618, 65652, 65651, 65636, 65630, 65640, 65621, 65574, 65650, 65630, 65589, 65634, 65653, 65652, 65632, 65584, 65645, 65656, 65630, 65635, 65586, 65647, 65605, 65640, 65647, 65606, 65630, 65644, 65624, 65630, 65588, 65649, 65585, 65614, 65647, 65660] for c in ct: print(chr(e^c),end="") print()
flag{tH1s_ic3_cr34m_i5_So_FroZ3n_i"M_pr3tTy_Sure_iT's_4ctua1ly_b3nDinG_mY_5p0On}
regulus-satrapa 449pt
Do you like milk?
ファイル：regulus-satrapa.py, output.txt
Coppersmith's Attackかといつものももテクさんの記事を参考にsageを動かしましたが出来ず。
この記事のように、pの下位1bitを仮定してみてそれとqの下位1bitとかけ算した結果、nの下位1bitと合致するのか。合致したら2bit目を仮定して…を繰り返します。
Plaid CTF 2021 XORSA writeup - Attack All Around
pbar = (省略) #pの上位512bits qbar = (省略) #qの下位512bits n = (省略) e = 65537 c = (省略) sys.setrecursionlimit(100000) def multiply(p,q,n): #p,q,nは01の文字列 if len(p) == 512: print("512!!!") P = int(p,2) print(P) P += pbar*pow(2,512) if n%P == 0: print("factorize!!!!") print(P) Q = n//P phi = (P-1)*(Q-1) d = inverse(e,phi) m = pow(c,d,n) print(long_to_bytes(m)) return return x = len(p)+1 pp = "0"+p tmp_n = int(pp,2)*int(q,2) if bin(tmp_n)[-x:] == n[-x:]: multiply(pp,q,n) pp = "1"+p tmp_n = int(pp,2)*int(q,2) if bin(tmp_n)[-x:] == n[-x:]: multiply(pp,q,n) multiply("",bin(qbar)[2:],bin(n)[2:])
flag{H4lf_4nd_H4lf}
canis-lupus-familiaris-bernardus 457pt
Wait, why isn't it a species of bird this time?
nc canis-lupus-familiaris-bernardus.hsc.tf 1337
ファイル：canis-lupus-familiaris-bernardus.py
"JOUX"が含まれた文字列が送られてきたら"F", そうでないなら"T"を送ります。"F"の場合、その文字列をAESのCBCモードで暗号化した際のIVだけ渡されます。暗号文はもらえません。そして、IVをこちらで決めたもので復号し、復号文が"ABCDEFGHIKLMNPQRSTVWYZ"のみで構成されるようにしなければなりません。
これはbyte flipping attackです。
DawgCTF 2021 writeup - Attack All Around
次回の勉強会で使おうと思っていた攻撃手法が出てきてびっくりでした。以前出来なかった問題が、今回は解けて嬉しいです。
s, f = sock(HOST, PORT) for _ in range(40-7+2): read_until(f) for cnt in range(100): recv_m = read_until(f,"peptide? ").split() enc = recv_m[1] if "J" in recv_m[1] or "O" in recv_m[1] or "U" in recv_m[1] or "X" in recv_m[1]: print("F") s.send(b"F\n") print(read_until(f)) iv = read_until(f).split()[-1] print("iv:",iv) riv = "" for i in range(len(enc)): if enc[i] == "J": riv += iv[:2*i] t = ord("J")^ord("A")^int(iv[2*i:2*i+2],16) t = hex(t)[2:] if len(t) == 1: t = "0"+t riv += t + iv[2*i+2:] break if enc[i] == "O": riv += iv[:2*i] t = ord("O")^ord("A")^int(iv[2*i:2*i+2],16) t = hex(t)[2:] if len(t) == 1: t = "0"+t riv += t + iv[2*i+2:] break if enc[i] == "U": riv += iv[:2*i] t = ord("U")^ord("A")^int(iv[2*i:2*i+2],16) t = hex(t)[2:] if len(t) == 1: t = "0"+t riv += t + iv[2*i+2:] break if enc[i] == "X": riv += iv[:2*i] t = ord("U")^ord("A")^int(iv[2*i:2*i+2],16) t = hex(t)[2:] if len(t) == 1: t = "0"+t riv += t + iv[2*i+2:] break read_until(f,"use: ") print("modified iv:",riv) s.send(riv.encode()+b"\n") print(read_until(f)) else: print("T") s.send(b"T\n") print(read_until(f))
flag{WATCHING_PPL_GET_PEPTIDED_IS_A_VALID_PEPTIDE}
cyanocitta-cristata-cyanotephra 463pt
Only the ciphertext has changed from the original challenge.
The Blue Jay (Cyanocitta cristata) is a passerine bird in the family Corvidae, native to North America. It is resident through most of eastern and central United States and southern Canada, although western populations may be migratory. It breeds in both deciduous and coniferous forests, and is common near and in residential areas. It is predominately blue with a white chest and underparts, and a blue crest. It has a black, U-shaped collar around its neck and a black border behind the crest. Sexes are similar in size and plumage, and plumage does not vary throughout the year. Four subspecies of the Blue Jay are recognized.
ファイル：cyanocitta-cristata-cyanotephra.sage, output.txt
f(x,y)=c[0]*x^2+c[1]*y^2+c[2]*x*y+c[3]*x+c[4]*y+c[5]
これを解いていきましょう。xs, ys, solnは9種類分かっています。未知数がc[0~5]の6種類なので、6個の式が立てられれば求められます。
A = [ [xs0^2, ys0^2, xs0*ys0, xs0, ys0, 1], ... ] #6×6 正方行列 C = [c[0], c[1], c[2], c[3], c[4], c[5] ] #縦ベクトル B = [soln[0], soln[1], soln[2], soln[3], soln[4], soln[5] ] #縦ベクトル A × C = B A_inv × A × C = A_inv × B C = A_inv × B
上の式よりCが求められました。よって与えられたa, bからf(a,b)を求め、与えられた暗号文とxorしたらflagが復元されました。
enc = [(与えられたxs, ys, solnをそのままコピペ)] A = Matrix([[enc[0][0]^2,enc[0][1]^2,enc[0][0]*enc[0][1],enc[0][0],enc[0][1],1], [enc[1][0]^2,enc[1][1]^2,enc[1][0]*enc[1][1],enc[1][0],enc[1][1],1], [enc[2][0]^2,enc[2][1]^2,enc[2][0]*enc[2][1],enc[2][0],enc[2][1],1],[enc[3][0]^2,enc[3][1]^2,enc[3][0]*enc[3][1],enc[3][0],enc[3][1],1],[enc[4][0]^2,enc[4][1]^2,enc[4][0]*enc[4][1],enc[4][0],enc[4][1],1],[enc[5][0]^2,enc[5][1]^2,enc[5][0]*enc[5][1],enc[5][0],enc[5][1],1]]) B = Matrix([[enc[0][2]],[enc[1][2]],[enc[2][2]],[enc[3][2]],[enc[4][2]],[enc[5][2]]]) print((A^-1)*B) # Cとなる
from Crypto.Util.number import * c = [15323988390216276549, 1211184093130083857, 5875327950550733875, 13889881931964042512, 14473158623602872631, 3300675726605068946] def f(x,y): return c[0]*x*x+c[1]*y*y+c[2]*x*y+c[3]*x+c[4]*y+c[5] a,b = 966671014274, 431366307057 x = f(a,b) enc = (省略) #与えられた暗号文 print(x) print(long_to_bytes(enc^x))
flag{:monkaSTEER::monkaSTEER::monkaSTEER::monkaSTEER::monkaSTEER ::monkaSTEER::monkaSTEER::monkaSTEER::monkaSTEER:}
regulus-regulus 466pt
Anhinga anhinga
nc regulus-regulus.hsc.tf 1337
これと全く同じです。
Cyber Apocalypse CTF 2021 writeup - Attack All Around
flag{r3gulus_regu1us_regUlus_regulu5_regUlus_Regulus_reguLus_regulns_reGulus_ r3gulus_regu|us}
cyanocitta-cristata-cyanotephra-but-fixed 466pt
Only the ciphertext has changed from the original challenge.
The Blue Jay (Cyanocitta cristata) is a passerine bird in the family Corvidae, native to North America. It is resident through most of eastern and central United States and southern Canada, although western populations may be migratory. It breeds in both deciduous and coniferous forests, and is common near and in residential areas. It is predominately blue with a white chest and underparts, and a blue crest. It has a black, U-shaped collar around its neck and a black border behind the crest. Sexes are similar in size and plumage, and plumage does not vary throughout the year. Four subspecies of the Blue Jay are recognized.
ファイル：cyanocitta-cristata-cyanotephra.sage, output.txt
but-fixedとありますが、cyanocitta-cristata-cyanotephraと同じ解法です。
先程の問題はflagが長すぎてもらった暗号文をlong_to_bytesするとほとんどflagが見えてしまう現象がありました。しかも同じ文字列が続いていたのでそこからエスパーして当てた人もいそう。それを無くしたのでしょう。
flag{d8smdsx01a0}
agelaius-phoeniceus 479pt
What's with the bird themed challenges?
ファイル：agelaius-phoeniceus.py, output.txt
与えられたファイルの16行目で出力された配列をoutsとします。
A = [[outs[0~99]], [outs[1~100], ... , outs[99~198] ] #100×100 正方行列 x = [g.s[0], g.s[1], ... , g.s[99] ] #縦ベクトル、未知数 B = [outs[100], ous[101], ..., outs[199] ] #縦ベクトル Ax = B (mod n)
上式のように表すことができます。
このサイトが参考になりすぎる！
https://pc1.math.gakushuin.ac.jp/~shin/html-files/Algebra_Introduction/2016/06.pdf
まずAの余因子行列A' とやらを求めます。逆行列A_invの場合、A×A_inv=Eとなります。余因子行列の場合、A×A' =(det A)Eとなります。なので逆行列を求めて、それをAの行列式倍すれば余因子行列となります。
cA'×B = x mod n ※c = (det A)^-1 mod n
これで未知数xの縦ベクトルが求められました。ここでxがプログラム上のg.sと一致します。
g.sとg.coをセットしたら200回g.next()を実行させ、与えられた暗号文とg.next()をxorさせたらflagが復元されました。
from Crypto.Util.number import * def Next(s,c,n): tmp = 0 for i in range(100): tmp += s[i]*c[i] tmp %= n s.append(tmp) return s[0], s[1:] f = open("output.txt") a = f.readlines() tmp = a[0].split(",") val = [] for i in range(len(tmp)-1): val.append(int(tmp[i][1:])) val.append(int(tmp[-1][1:-2])) det = (省略) #sageを使って求める n = 18446744073709551629 c = inverse(det,n) det_n = det%n f = open("inv.txt") #Aの逆行列が入っている A_inv = [] a = f.readlines() for t in a: x = t[1:-2].split() tmp = [] for y in x: tmp.append(int(y)*det_n) A_inv.append(tmp) A = mat E = [] for i in range(100): temp = [] for j in range(100): tmp = 0 for k in range(100): tmp += A[i][k]*A_inv[j][k] tmp %= n temp.append(tmp) E.append(temp) print(E) B = [] for i in range(100,200): B.append(val[i]) L = [] for i in range(100): tmp = 0 for j in range(100): tmp += A_inv[i][j]*B[j] L.append(tmp) C = [] for l in L: C.append((c*l)) S = [val[i] for i in range(100)] for i in range(200): g, S = Next(S,C,n) print(i) assert g == val[i] enc = (省略) lf = len(enc)//2 k = "" for i in range(lf): g, S = Next(S,C,n) k += hex(g)[2:].zfill(16) for i in range(0,len(enc),2): flag = int(enc[i:i+2],16)^int(k[i:i+2],16) print(chr(flag),end="") print()
flag{if_i_had_a_nickel_4or_ev3ry_st0re_h3re_1n_town_with_a_fu11_suit_of_armor_0ut_ in_front_i_would_have_two_nickl3s_wh1ch_isn't_a_l0t_but_it's_weird_that_we_h4ve_tw0}
bucephala-albeola 487pt
⬛
nc bucephala-albeola.hsc.tf 1337
なぜ解けたか未だに分からない問題です。
keyを送るとenc(flag, key)を返してくれます。"a"~"z"を一文字ずつ送ると以下の事に気付きました。
key: a enc(flag,key): 74 83 64 95 95 54 53 84 56 95 54 53 54 86 54 83 54 67 54 83 54 74 54 95 84 63 54 64 53 key: b enc(flag,key): 47 56 37 68 68 27 26 57 29 68 27 26 27 59 27 56 27 40 27 56 27 47 27 68 57 36 27 37 26 key: c enc(flag,key): 85 94 75 106 106 65 64 95 67 106 65 64 65 97 65 94 65 78 65 94 65 85 65 106 95 74 65 75 64 key: d enc(flag,key): 83 92 73 104 104 63 62 93 65 104 63 62 63 95 63 92 63 76 63 92 63 83 63 104 93 72 63 73 62 key: e enc(flag,key): 86 95 76 107 107 66 65 96 68 107 66 65 66 98 66 95 66 79 66 95 66 86 66 107 96 75 66 76 65 key: f enc(flag,key): 64 73 54 85 85 44 43 74 46 85 44 43 44 76 44 73 44 57 44 73 44 64 44 85 74 53 44 54 43 key: g enc(flag,key): 77 86 67 98 98 57 56 87 59 98 57 56 57 89 57 86 57 70 57 86 57 77 57 98 87 66 57 67 56 key: h enc(flag,key): 76 85 66 97 97 56 55 86 58 97 56 55 56 88 56 85 56 69 56 85 56 76 56 97 86 65 56 66 55 key: i enc(flag,key): 44 53 34 65 65 24 23 54 26 65 24 23 24 56 24 53 24 37 24 53 24 44 24 65 54 33 24 34 23 key: j enc(flag,key): 44 53 34 65 65 24 23 54 26 65 24 23 24 56 24 53 24 37 24 53 24 44 24 65 54 33 24 34 23 key: k enc(flag,key): 75 84 65 96 96 55 54 85 57 96 55 54 55 87 55 84 55 68 55 84 55 75 55 96 85 64 55 65 54 key: l enc(flag,key): 73 82 63 94 94 53 52 83 55 94 53 52 53 85 53 82 53 66 53 82 53 73 53 94 83 62 53 63 52 key: m enc(flag,key): 55 64 45 76 76 35 34 65 37 76 35 34 35 67 35 64 35 48 35 64 35 55 35 76 65 44 35 45 34 key: n enc(flag,key): 43 52 33 64 64 23 22 53 25 64 23 22 23 55 23 52 23 36 23 52 23 43 23 64 53 32 23 33 22 key: o enc(flag,key): 54 63 44 75 75 34 33 64 36 75 34 33 34 66 34 63 34 47 34 63 34 54 34 75 64 43 34 44 33 key: p enc(flag,key): 57 66 47 78 78 37 36 67 39 78 37 36 37 69 37 66 37 50 37 66 37 57 37 78 67 46 37 47 36 key: q enc(flag,key): 66 75 56 87 87 46 45 76 48 87 46 45 46 78 46 75 46 59 46 75 46 66 46 87 76 55 46 56 45 key: r enc(flag,key): 63 72 53 84 84 43 42 73 45 84 43 42 43 75 43 72 43 56 43 72 43 63 43 84 73 52 43 53 42 key: s enc(flag,key): 56 65 46 77 77 36 35 66 38 77 36 35 36 68 36 65 36 49 36 65 36 56 36 77 66 45 36 46 35 key: t enc(flag,key): 53 62 43 74 74 33 32 63 35 74 33 32 33 65 33 62 33 46 33 62 33 53 33 74 63 42 33 43 32 key: u enc(flag,key): 46 55 36 67 67 26 25 56 28 67 26 25 26 58 26 55 26 39 26 55 26 46 26 67 56 35 26 36 25 key: v enc(flag,key): 84 93 74 105 105 64 63 94 66 105 64 63 64 96 64 93 64 77 64 93 64 84 64 105 94 73 64 74 63 key: w enc(flag,key): 65 74 55 86 86 45 44 75 47 86 45 44 45 77 45 74 45 58 45 74 45 65 45 86 75 54 45 55 44 key: x enc(flag,key): 67 76 57 88 88 47 46 77 49 88 47 46 47 79 47 76 47 60 47 76 47 67 47 88 77 56 47 57 46 key: y enc(flag,key): 87 96 77 108 108 67 66 97 69 108 67 66 67 99 67 96 67 80 67 96 67 87 67 108 97 76 67 77 66 key: z enc(flag,key): 45 54 35 66 66 25 24 55 27 66 25 24 25 57 25 54 25 38 25 54 25 45 25 66 55 34 25 35 24
- "i", "j"1文字の時は全く同じ暗号文となる。
- 29個の整数が送られてくるが、25種類の1個目に注目すると、数値が5×5のような形になる(ex. 43~47, 53~57, ... ,93~97)
問題文の四角形も考慮し、これではないかとエスパー。
上の例の場合、数値順に並べそのkeyを当てはめると、ncする度に異なりますがこんなような感じになります。
nizub tomsp rfwqx lakhg dvcey
この5×5の表は、29の送られてくる数値を並べると全て同じ並びになります。
ここでenc(flag, key)を考えます。keyとflagの値によってこの値が決まると考えた時、flagが固定なので毎回変わる上の5×5の表はランダムでflagに依存しないと考えます。
では、enc関数にflagはどう影響しているのでしょうか。ここで、上の5×5の表の開始位置(上の例では"n")が異なることに注目します。key=nの時の1つ目の数値が、なぜ"11"スタートではなく"43"なのでしょう。
ここで、5×5の表の開始位置も5×5の形になることを見つけます。flagの1文字がこの開始位置を決定しているとエスパーします。つまりflagを1文字ずつ見ていった場合、それが"n"だったら5×5の表の開始位置が最も左上になります。反対に"y"だったら5×5の表の開始位置が最も右下になります。
自分でも説明が良く分かっていないのですが、これで提出したらcorrectとなりました。こんな単語あるんだ。
フロクシノーシナイヒリピリフィケイション - Wikipedia
flag{floccinaucinihilipilification}
Problems&Solver
【ご報告】生きています
大学院復学してもう3ヶ月近く経って、気付いたらすぐ学生終わってしまうのではと焦っています。良ければ読んでください
学業
研究生活
留学時に行っていた研究の続きを主軸としてやっています。
加えて、研究室の後輩の研究を手伝ったり勉強会に参加したりと、幅広くネットワークセキュリティを学んでいます。
研究室同期が卒業し年下の学生がほとんどなのですが、みんな頭が良くてついていくので必死です。改めて良い環境だなと感じるこの頃です。
その他
競技プログラミング
競技プログラミングのコンテストにAtCoderというものがあり、ランクを上げたいと精進していました。無事誕生日にランクが上がり、今は少しお休み中です。
その時の記録です。よろしければ見てください！
CTF
Capture The Flagというコンピュータセキュリティコンテストというものがあり、m1z0r3という大学のチームで活動しています。これがまたハマってしまい、土日はほとんどCTFのコンテストに出て問題を解くのに潰しています。
他の人と情報をやり取りする時に情報を暗号化するのですが、その暗号化の方式がずさんだと情報が漏洩してしまいます。その暗号を解く問題を担当しており、情報系の謎解きみたいな感じで熱中してます。
今年度また強い新入生が加入してくれて、刺激になっております。後輩には負けまい、と暗号学やプログラミングを学んでいます！
スポーツ
ボウリング
実は緊急事態宣言前に少しやってました。
久しぶりに投げたら、なんと1ゲーム目でノーミス2ダボの210。「俺ボウリング上手くね？」と思ったのも束の間、その後はブランクを感じさせる素晴らしい投球から抜け出せません。
帰ったら、家の少し固めの食器棚がを開けられないほどの筋肉痛が襲ってきました…。ようやく投げた後2日間で筋肉痛が来なくなった頃、緊急事態宣言となり休んでおります。
また、緊急事態宣言が明けたら少しずつ投げようかと思っています。
その他
体の変化
体重の維持が難しい
今までそれなりに運動をしていたようで、やらなくなった途端順調に肥えてきました。
元の体重までは7kg近くもあるので諦めているのですが、少しは落としたいと思いダイエットもどきをしております。楽して痩せたい。
散歩や軽い筋トレもしているのですが、最近の楽しみは週1のキャッチボール。ボウリングしなくなったのでなんか代わりにやろうと始めたのですが、最近梅雨のせいで中止になることが多く、将来は金持ちになって室内練習場でも立てようかと薄く考えております。
さらに酒弱に
ビール一杯も乾かぬ内に顔が真っ赤になる人でしたが、いまやビール一杯飲んだら水をかなり飲まないと次の日頭ガンガンになってしまうほどになりました。原因究明中です。
趣味(?)
巨人戦毎試合TV観戦
昔はプロ野球が放送されている時間に家にいることは少なかったのですが、今は巨人戦の時間に合わせた生活スタイルになりました。なんとか阪神ヤクルトをまくってくれ！
ドラゴンクエスト
スマホのアプリでやっています。いずれは全ての世界を救いたいですね。Ⅻが楽しみです。
今はⅦをやっているのですが、長くて全然終わらない…。
出会い
無。求。
さいごに
また3ヶ月後くらいに生存報告するので、また読んでくれると幸いです。
BCACTF v2.0 writeup
Result
今までで一番良い成績だったと思います！！
Writeup
crypto
Easy RSA 50pt
As part of his CTF101 class, Gerald needs to find the plaintext that his teacher encrypted. Can you help him do his homework? ( It's definetely not cheating ;) )
ファイル：enc.txt
p: 251867251891350186672194341006245222227 q: 31930326592276723738691137862727489059 n: 8042203610790038807880567941309789150434698028856480378667442108515166114393 e: 65537 ct: 5247423021825776603604142516096226410262448370078349840555269847582407192135
素因数分解されているので、普通に秘密鍵求めて復号するだけです。
bcactf{RSA_IS_EASY_AFTER_ALL}
Cipher Mishap 75pt
My Caeser-loving friend decided to send me a text file, but before sending it, his sister, who loves Caps Lock, tampered with the file. Can you help me find out what my friend sent me? Note: the answer must be wrapped in bcactf{}
ファイル：text.txt
126-Y, 113-N, 122-N, 130-N, 117-N, 107-N, 137, 114-N, 127-Y, 137, 113-Y, 104-N, 131-N, 110-N, 137, 105-Y, 110-N, 110-N, 121-Y, 137, 131-Y, 114-N, 112-N, 110-N, 121-N, 110-N, 125-N, 110-N, 137, 114-Y, 121-N, 126-N, 127-N, 110-N, 104-N, 107-N
137がアンダースコアっぽいと気付き、色々試すと8進数であることが分かったのでASCII変換。
VKRXOG_LW_KDYH_EHHQ_YLJHQHUH_LQVWHDG
問題文よりCaesarが使われているはずなので試すとROT23で意味ある文になる。
SHOULD_IT_HAVE_BEEN_VIGENERE_INSTEAD
"-Y", "-N" はYが大文字でNが小文字とエスパー。
def ROT23(enc): ret = "" for s in enc: if ord("A") <= ord(s) <= ord("Z"): x = ord(s)-ord("A")-3 if x < 0: x += 26 ret += chr(ord("A")+x) else: ret += s return ret f = open("text.txt") a = f.readline().split() print(a) enc = "" for i in a: enc += chr(int(i[:3],8)) print(enc) rot_enc = ROT23(enc) print(rot_enc) flag = "bcactf{" for i in range(len(a)): if len(a[i]) < 4: flag += rot_enc[i] else: if "N" in a[i]: flag += rot_enc[i].lower() else: flag += rot_enc[i] flag += "}" print(flag)
自分がやったのはROT23に気付いただけです。他は全てチームメイトが見つけました！
bcactf{Should_iT_Have_BeeN_Vigenere_Instead}
Sailing Thru Decryption 75pt
I seem to have lost something while I was sailing to France. I know it was one of my pets, but I can't seem to remember his name. Could you help me remember it?
ファイル：image.png
これの正体はこちらから。
picoGym cryptography writeup - Attack All Around
一番最後の行を読むと、「thekeyisfhskdn」-> 「the key is fhskdn」となります。「fhskdn」ってなんやねんと調べますが特に分からず。残った上の5行は、正解を言うと国際信号旗です。最後の行がそうなら、他も同じですよね。普通はそう考えます。
しかし、私はそこでモールス信号ではないかと道を外れます。Sailingからそうではないかと…。モールス信号なら途中で空白があるはずなのですが、これにはありません。ここで何度も右往左往します。
はい、ほんとは01を表しているのでそれに沿ってASCII変換すると、
gjsmws{1x_o1k_x4pr_l3y4jn?}
となります。これはチームメイトがやってくれました。その時私は何をしていたかというと、散歩がてら進撃の巨人とトモダチゲームの最新刊を買いに行ってました。ひどい先輩です。
うちに着いて進捗を見て、Vigenere暗号だと気付きcorrect。どうも、ゴール前で寝転がってボールが来たのでシュートだけ決める、チームからは絶対嫌われる選手です。
Vigenere暗号のkeyは「fhskdn」です。CyberChefで復号しました。
bcactf{1s_h1s_n4me_g3r4rd?}
Slightly Harder RSA 75pt
Gerald's homework is getting trickier. He isn't being given the primes anymore. Help him find the plaintext!
ファイル：enc.txt
n = 947358141650877977744217194496965988823475109838113032726009 e= 65537 ct=811950322931973288295794871117780672242424164631309902559564
nがfactorDBなどで素因数分解可能です。
bcactf{rsa_factoring}
Little e 100pt
Gerald's favorite prime is 3 and made it his public exponent; he keeps insisting that it's secure. Help me prove him wrong.
ファイル：encrypted.txt
N: 17260541145579198891286838820507756585494408484294770862002805660577661138753926064444981930310528890773266098356882517290033235056654103412024620204547445159627671127518965960486480229617902782023368077819854820837387791591683428592246121552228695417314295153721144499366280389254552597040315734269703314601367296670296596449184388246232676724558126845148454433428619114310396032130452938580427564701080866025573039407415733982384144637567337164211240182263026767455207192185903776322079215198832973810587735067694801737731617941390472537291532113711292822595269219795255224521641891049508289784761579371125213474439 e: 3 ct: 1112413624683819960899152482895461211039349964898672381675850025556800617245120168928400758297834676330400246617472191750627367991315450127361583383350639760738254818244740474313061192563860605923503717
me < nのパターンです。Low Public Exponent Attackですね。
bcactf{R54_N0T_50_S3CUR3_33}
RSAtrix 1 125pt
RSA, RSA, RSA. After so many RSA problems, they all start to look the same. But what looks different? Matrices! After a lot of detailed R&D, we're proud to present RSAtrix, the world's first* matrix RSA system!
ファイル：rt1.sage, enc.txt
出ましたsage。以下の難しそうなコードをsagemathで出力させると、5×5の行列で要素が0か1のものが出てきました
R = Zmod(n)
MS = MatrixSpace(R, 5, 5)
s = PermutationGroupElement('(1,4)(2,3,5)')
P = MS(s.matrix())
"""
[0 0 0 1 0]
[0 0 1 0 0]
[0 0 0 0 1]
[1 0 0 0 0]
[0 1 0 0 0]
"""
これを平文m倍して、nでの剰余となるので、enc.txtにある0でない要素はRSA暗号の暗号文cに該当します。p, qが分かっているので復号は簡単ですね。
bcactf{just-rsa-with-matrices-9385dax}
FNES 1 150pt
My friend developed this encryption service, and he's been trying to get us all to use it. Sure, it's convenient and easy to use, and it allows you to send encrypted messages easily, and...
Well, I want to get control of his service so I can monitor all the messages! I think he's hidden some features and files behind a secret admin passphrase. Can you help me access those hidden files?
nc crypto.bcactf.com 49153
ファイル：fnes1.py
fnes1.pyを見るとARC4という初耳の暗号を使っています。まずはそれについて調べました。
https://www2.nict.go.jp/csri/plan/H26-symposium/files/3-1.pdf
keyによって擬似乱数を生成して、平文とxorしたのが暗号文になるという理解です。「CTF ARC4 writeup」などでググりましたが、「ARC4は最初の512bytesを捨てないといけない」という脆弱性があるということでしたが理解できず、その問題のsolves数が5とかだったので諦めました。
fnes1.pyのtempkeyを定義しているところに注目します。
tempkey = SHA.new(int(key + int(time.time() / 10)).to_bytes(64, 'big')).digest()[0:16] cipher = ARC4.new(tempkey)
keyは毎回同じ値でUNIXTIMEの整数部分を10で割った値と足しています。ん？
これは10秒毎にその値が変わります。つまり10秒以内に2回ncすれば、tempkeyが同じになるので生成する擬似乱数も同じになります。
目的はtarget_query="Open sesame... Flag please!"の暗号文を作り復号させることです。"flg!"が平文に含まれていると暗号化してくれないので"0"を送り暗号文をもらい"0"でxorして擬似乱数を得ます。そしてtarget_queryとxorしたのを渡すとflagがもらえました。
HOST, PORT = "crypto.bcactf.com", 49153 s, f = sock(HOST, PORT) for _ in range(12): read_until(f) key = "Open sesame... Flag please!" #for i in range(len(key)): read_until(f) read_until(f,">>> ") s.send(b"E\n") read_until(f) read_until(f,">>> ") enc = "0"*len(key) s.send(enc.encode()+b"\n") read_until(f) ct = read_until(f).strip() s.close() s, f = sock(HOST, PORT) print(ct) assert len(ct) == len(key)*2 pt = "" for i in range(0,len(ct),2): x = int(ct[i:i+2],16)^ord("0")^ord(key[i//2]) x = hex(x)[2:] if len(x) == 1: x = "0" + x pt += x for _ in range(12): read_until(f) read_until(f) read_until(f,">>> ") s.send(b"D\n") read_until(f) read_until(f,">>> ") s.send(pt.encode()+b"\n") while True: print(read_until(f))
bcactf{why-would-you-attack-your-FNES????-4x35rcg}
RSAtrix 2 200pt
Sure, you saw our first prototype, but you could obviously see it was just RSA slapped on a permutation matrix. Will you still be able to decode our messages if we conjugate our generator first?
ファイル：rt2.sage, enc.txt
RSAtrix 1と比べてCという行列が出てきました。チームメイトが解けた時に教えてくれたのですが、Cはランダムに要素を決めていると思いきや、seed(1)としているので毎回同じになります。なのでGがわかりその逆行列が求められるので、以下の式のようになります(やったのはチームメイトで自分は何もやっていない)。
M^e = (mI)^e * G^e M^e * (G^e)^-1 = (mI)^e
これでRSAtrix 1のenc.txtのような、要素が0となんか大きい値=暗号文cが得られ、復号したらflagとなりました。
bcactf{permutation-conjugation-magic-3x876oeu}
Rainbow Passage 225pt
I'm pretty sure my friend has been communicating with the trickster god by beaming encrypted message at rainbows every time it rains. I've intercepted one of his messages along with its plaintext; can you help me figure out the password he uses so I can talk to the shape shifter myself?
To get the flag, wrap the password in bcactf{...}.
ファイル：rp.py, message.txt, enc.txt
まず、暗号化のアルゴリズムを理解するのに苦労します。
- パスワードを2文字ずつに分ける ASCII変換->2進数16bitsにして文字列として保存。今回パスワードが32文字なので16個の文字列が出来る。
- 平文を16文字ずつ分ける。暗号文の上位1byteは、上の16個の文字列の各0番目の文字に注目する。16個の文字列の0番目の文字列の0番目の文字が1なら平文の0番目をxorする(最初は0とxor)。
- 次に、16個の文字列の1番目の文字列の0番目の文字が1なら平文の1番目とxorする。 暗号文の上位2byte目は、上の16個の文字列の各1番目の文字に注目する。やり方は先と同様。
- 以上を繰り返す。
enc.txtの上位2bytes"0074"を例にとって考えます。"00"の方は、16個の文字列の0番目は必ず0なので、どれともxorしていません。一方、"74"の方はmessage.txtの"When sunlight st"の内いくつかをxorすると"74"になりました。こんな感じです。
解法として、bit全探査を行います。"When sunlight st"の内、どれを選べば0x74になるのでしょう。16文字で選ぶ/選ばないの通り数は、216 = 65536なので全探査の時間はそこまでかかりません。ちなみにこの場合、512通り考えられます。
では、この512通りを絞っていきます。"When sunlight st"の内、何番目を選べば0x74になるのかという組み合わせを記憶します(これが512通りあります)。その内正しい組み合わせは、次の16文字"rikes raindrops "でもenc.txtの上位18byte目と一致するはずです。さらに、次の16文字でも上位34byte目と一致します。これを繰り返していくと、正しい組み合わせが一意に定まります。
f = open("message.txt") mes = f.readline().strip() print(mes) f = open("enc.txt") enc = f.readline().strip() print(enc) s = [] for block in range(16): for i in tqdm(range(2**16)): t = bin(i)[2:] while len(t) < 16: t = "0"+t check = True #print(enc[2*j+2*block:2*j+2+2*block]) for j in range(0,len(mes)-16,16): #print(enc[2*j+2*block:2*j+2+2*block]) x = 0 for k in range(16): if j+k >= len(mes): break if t[k] == "1": x ^= ord(mes[j+k]) x = hex(x)[2:] if len(x) == 1: x = "0" + x if enc[2*j+2*block:2*j+2+2*block] != x: check = False break #else: # print(i) if check: s.append(i) print("find! :",i) break
ここで、"find! : {i}" と出るiはパスワードのASCII変換ではなく、ASCII変換したx bit目を上から見た時の数値になります。例えば、2回目に出る"find! : {i}"は、i=61305ですが、下の図の2bit目を上から見た状態です。
0111001101111001 0111001101110100 0110010101101101 0010110101101111 0110011000101101 0110110001101001 0110111001100101 0110000101110010 0010110101100101 0111000101110101 0110000101110100 0110100101101111 0110111001110011 0010110100110010 0011011100110011 0110010001100101
これをうまく変換させるとパスワードが手に入り、bcactf{}で括って提出しました。
bcactf{system-of-linear-equations-273de}
FNES 2 375pt
After FNES got cracked, my friend enlisted his ex-girlfriend to help him improve his service. She majored in cryptography, so it should theoretically be quite a bit better now. Unless she installed a backdoor, that is...
nc crypto.bcactf.com 49154
ファイル：fnes2.py
はい、Padding Oracle Attackですね。
Padding Oracle Attack 分かりやすく解説したい - Attack All Around
今回はEncryption Attackを使って、"Open sesame... Flag please!"の暗号文を作っていきます。やり方は上記のサイトを参考にしてください。
bcactf{high-priestess-of-the-temple-of-apollo-49b7x}
binex
BCA Mart 75pt
After the pandemic hit, everybody closed up shop and moved online. Not wanting to be left behind, BCA MART is launching its own digital presence. Shop BCA MART from the comfort of your own home today!
nc bin.bcactf.com 49153
ファイル：bca-mart.c, bca-mart
C言語のint型オーバーフローを使ってFlagを買います。
#include <stdio.h> #include <stdlib.h> int main() { int money = 15,amt=10000; while (1) { int tmp; tmp = 100*amt; if(tmp < money) { printf("%d\n",amt); break; } amt++; } return 0; }
ここで出力された値の文だけFlagを買えばオーバーフローしてflagが表示されます。
bcactf{bca_store??_wdym_ive_never_heard_of_that_one_before}
Honors ABCs 75pt
Here at BCA, we don't deal with normal classes. Everything is at the honors level or above! Let's start by learning about the alphabet.
And by learning, we obviously mean testing. Don't cheat!
nc bin.bcactf.com 49155
ファイル：honors-abcs.c, honors_abcs
int型変数gradeをバッファオーバーフローを利用して値を書き換えます。本来gdb等を利用してアドレスを求めて…とかになると思うのですが、そんなの分かんないんで長さを変えてって上手くいくときを狙います。最初の文字を0とするのが必須ですね。
HOST, PORT = "bin.bcactf.com", 49155 test = "0"*40 while True: test += "z" s, f = sock(HOST, PORT) for _ in range(11): read_until(f) read_until(f,"Answer for 1: ") s.send((test+"999").encode()+b"\n") print(test) recv_m = read_until(f).strip() print(recv_m) if "How" in recv_m: while True: print(read_until(f)) s.close()
AP ABCs 100pt
Oh wow, they put a freshman in AP ABCs? Never thought I'd see this happen. Anyways, good luck, and make sure to not cheat on your AP test!
nc bin.bcactf.com 49154
ファイル：ap-abcs.c, ap-abcs
終わった後に解けたんですが、Honors ABCsの時と同様に長さを変えてってscore変数を0x73434241にしたいです。これがリトルエンディアンだと気付かずb"sCBA"と送っていました。いや問題名から"ABCs"となることに気付けよ！！！
HOST, PORT = "bin.bcactf.com", 49154 test = "0" while True: s, f = sock(HOST, PORT) for _ in range(46): read_until(f) print(read_until(f,"Answer for 1: ")) s.send((test+"ABCs").encode()+b"\n") for _ in range(2): read_until(f) print(test) recv_m = read_until(f).strip() print(recv_m) if "tsk" in recv_m: while True: print(read_until(f)) test += "0" s.close()
rev
Digitally Encrypted 1 75pt
Gerald has just learned about this program called Digital which allows him to create circuits. Gerald wants to send messages to his friend, also named Gerald, but doesn't want Gerald (a third one) to know what they are saying. Gerald, therefore, built this encryption circuit to prevent Gerald from reading his messages to Gerald.
ファイル：circuit_1.dig, encrypted.txt
以下のサイトのREADME.mdにあるDownloadボタンでアプリを入手します。チームメイトが教えてくれました。
GitHub - hneemann/Digital: A digital logic designer and circuit simulator.
自作ブロック暗号ですね。keyとxorするだけでkeyの値も分かっているので、暗号文とkeyをxorして終了です。
from Crypto.Util.number import * enc = [0xB6A46EE913B33E19, 0xBCA67BD510B43632, 0xA4B56AFE13AC1A1E, 0xBDAA7FE602E4775E, 0xEDF63AB850E67010] key = 0xD4C70F8A67D5456D for i in enc: t = key^i print(long_to_bytes(t).decode(),end="") print()
bcactf{that_was_pretty_simple1239152735}
Digitally Encrypted 2 150pt
Gerald and Gerald have just learned that Gerald has cracked their previous cypher. Gerald scolds Gerald, saying that he shouldn't have given away the key. Gerald, therefore, decides to create a new cypher, hopefully one that Gerald can't crack.
ファイル：circuit_2.dig, Block.dig, encrypted.txt
今度の自作ブロック暗号は、平文とkeyによって暗号化しているようです。その具体的な方法がBlock.digに記載されています。keyの値も今回は非公開です。
まず、40bitsのkeyをkey1, key2に分けます。ともに32bitsで、key1はkeyの下位32bits, key2はkeyの上位32bitsとなります。灰色で薄く[0-31]とあり、最初は上位32bitsの事かと思いましたが、逆のようでした。
後は以下の式の通りです。
pt1 = 平文下位32bits, pt2 = 平文上位32bits
ct1 = 暗号文下位32bits, ct2 = 暗号文上位32bits
ct1 = pt2 xor not(key1 xor pt1)
ct2 = pt1 xor not(ct1 xor key2)
= pt1 xor not( (pt2 xor not(key1 xor pt1) xor key2)
not()はbit反転です。pythonでは~があるようですが、~4 = -5となりよくわからなかったので自作しました。
def rev_bit_32(x): x = bin(x)[2:] while len(x) < 32: x = "0"+x ret = "" for i in range(len(x)): if x[i] == "1": ret += "0" else: ret += "1" return int(ret,2)
平文の最初7文字は"bcactf{"であることに注目します。pt2 = long_to_bytes(b"bcac"), pt1 = long_to_bytes("tf{?") となります。?は何かしらの1文字です。この?をbruteforceしていきます。
pt1, 2, ct1, 2が分かっているのでkey1, 2が求められます。key1, 2は24bits共有しているのでそうなるものをbruteforceします。今回は一意に決まったのでよかったです！ key1, 2が求まったら、暗号文から平文を復元します。
from Crypto.Util.number import * def rev_bit_32(x): x = bin(x)[2:] while len(x) < 32: x = "0"+x ret = "" for i in range(len(x)): if x[i] == "1": ret += "0" else: ret += "1" return int(ret,2) def decoded(key1,key2,enc): e1 = int(enc[:8],16) e2 = int(enc[8:],16) tmp = rev_bit_32(key2^e1) pt1 = tmp^e2 tmp = rev_bit_32(pt1^key1) pt2 = e1^tmp return (long_to_bytes(pt1) + long_to_bytes(pt2)).decode() f = open("encrypted.txt") a = f.readline().split() print(a) ptab = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz_{}" ct2 = int(a[0][:8],16) ct1 = int(a[0][8:],16) for p1 in ptab: plain = "bcactf{"+p1 plain = bin(bytes_to_long(plain.encode()))[2:] while len(plain) < 64: plain = "0"+plain pt1 = int(plain[32:],2) pt2 = int(plain[:32],2) tmp = ct1^pt2 tmp = rev_bit_32(tmp) key1 = tmp^pt1 tmp = ct2^pt1 tmp = rev_bit_32(tmp) key2 = ct1^tmp k1 = bin(key1)[2:] while len(k1) < 32: k1 = "0" + k1 k2 = bin(key2)[2:] while len(k2) < 32: k2 = "0" + k2 if k1[:24] == k2[-24:]: print(key1,key2) break #decode for enc in a: e1 = int(enc[8:],16) e2 = int(enc[:8],16) tmp = rev_bit_32(e1^key2) pt1 = tmp^e2 tmp = rev_bit_32(pt1^key1) pt2 = tmp^e1 pt = pow(2,32)*pt2+pt1 print(long_to_bytes(pt).decode(),end="") print()
bcactf{x0r5_4nD_NXoR5_aNd_NnX0r5_0r_xOr}
Problems&Solver
solved by Teammates
自分は解けずにチームメイトが解いたcrypto問です。
-
- RSAtrix 3
- RSAtrix 4
- RSAtrix 5
とくにRSAtrix 5解けたのすごいなぁ。
ICHSA CTF 2021 writeup
今回のwriteupは以前の記事を多用します。ご了承ください。
Result
writeup
Crime Cloud 150pt
I got a notification from my cloud storage provider that they added strong OTP "protection" to their service.
They want 10,000 BTC for a CrimeCloud decryptor.
I think they should have named themselves CrimeSomware those thiefs!
Now I can't read my precious data anymore :-(
My H@ck3r friend was able to recover their server-side source code but he said OTP is "prefectly-secure" so I should give up.
Maybe u have an idea how to beat those CrimeLords?
Connect: nc crime.ichsa.ctf.today 8008
Note
Flag contains only lower ASCII characters and underscore. Regex it should obey ICHSA_CTF{[a-z_]+} (perl syntax).
ファイル：source.py
picoCTF 2021でも出たこの問題と全く同じですね。ただ途中にあるrand(32)のせいで、まあまあ上手くいかないです。上手くいくと長さが95になるのでそうなるまでグルグル回します。
picoCTF 2021 writeup - Attack All Around
HOST, PORT = "crime.ichsa.ctf.today", 8008 s, f = sock(HOST, PORT) for _ in range(3): read_until(f) flag = "ICHSA_CTF{" candi = "abcdefghijklmnopqrstuvwxyz_}" while True: ans = "" for c1 in candi: read_until(f,"Your input: ") mes = flag + c1 s.send(mes.encode()+b"\n") m = read_until(f).strip() read_until(f) m = base64.b64decode(m.encode()) if len(m) == 95: print("update!") ans_len = len(m) ans = c1 flag += ans print(flag) if "}" in ans: break
ICHSA_CTF{d0n7_7ruzt_DeF4uL7_V4lu3z}
Baby Homework 150pt
My teacher gave some homework in crypto. HELP!!!!!!
Connect: nc baby_homework.ichsa.ctf.today 8010
ファイル：best_crypto_service.py
以下が初耳でした。
from Crypto.Cipher.AES import AESCipher AESCipher(os.environ.get('KEY')).encrypt(padding(data))
上のサイトより、このモジュールはデフォルトでECBモードと分かりました。flagの先頭16文字を特定するため、暗号文の第一ブロックと第二ブロックが一致するよう頑張ります。
HeroCTF v3 writeup - Attack All Around
またしても以前のサイトで申し訳ないですが、これと同じ方法でflagを出します。下のsolverでは、"0"が15文字+(一文字brute force)+"0"が15文字を送ります。(一文字brute force)がflagの先頭文字と一致すると暗号文の1, 2ブロック目が等しくなります。
HOST, PORT = "baby_homework.ichsa.ctf.today", 8010 flag = "" while True: isfin = True for i in range(48,126): print(i,chr(i)) s, f = sock(HOST, PORT) read_until(f) mes = "0"*(16-(len(flag)%16)-1) + flag + chr(i) + "0"*(16-(len(flag)%16)-1) s.send(mes.encode()+b"\n") m = read_until(f).strip() s.close() if m[32:64] == m[96:128]: isfin = False flag += chr(i) print(flag,len(flag)) break if isfin: break print("ICHSA_CTF{"+flag+"}")
最後変なpadding入るので注意です。
ICHSA_CTF{d0n7_7ruzt_DeF4uL7_V4lu3z}
Poodle 1 200pt
I lost my beloved poodle :(
did you see it?
maybe the oracle will be able to find it... can you talk with her for me? please?
Connect: nc poodle1.ichsa.ctf.today 8003
ファイル：poodle1.py
これはpadding oracle attackですね。1はDecryption Attackなのでしょう。こちらのサイトをcheck!
Padding Oracle Attack 分かりやすく解説したい - Attack All Around
def modifyXor(d): if len(d) == 0: return "" x = len(d)//2 + 1 ret = "" for i in range(0,len(d),2): #print("xor",x,x-1-(i//2)) t = int(d[i:i+2],16)^x^(x-1-(i//2)) t = hex(t)[2:] if len(t) == 1: t = "0"+t ret += t #print("ret:",ret) return ret #HOSTはIPアドレスでも可 HOST, PORT = "poodle1.ichsa.ctf.today", 8003 s, f = sock(HOST, PORT) for _ in range(5): read_until(f) enc = read_until(f).strip() print("enc:",enc) for _ in range(5): read_until(f) d2 = "" dec2 = "" for j in range(16): print(j) hen = True for i in range(256): read_until(f) read_until(f,">> ") h = hex(i)[2:] #print("h:",h) if len(h) == 1: h = "0"+h print("h:",h) mes = enc[:32] + "00"*(15-j)+ h + modifyXor(d2) + enc[64:] #print("mes:",mes) assert len(mes) == 96 s.send(mes.encode()+b"\n") recv_m = read_until(f).strip() print(recv_m) if "mmm" in recv_m: hen = False print("Find!") d2 = h + d2 t = i^(j+1) t = hex(t)[2:] if len(t) == 1: t = "0"+t dec2 = t + dec2 break if hen: print("okashii") break p2 = long_to_bytes(int(dec2,16)^int(enc[32:64],16)) print(p2) d1 = "" dec1 = "" for j in range(16): print(j) hen = True for i in range(256): read_until(f) read_until(f,">> ") h = hex(i)[2:] #print("h:",h) if len(h) == 1: h = "0"+h print("h:",h) mes = "00"*(15-j)+ h + modifyXor(d1) + enc[32:64] #print("mes:",mes) assert len(mes) == 64 s.send(mes.encode()+b"\n") recv_m = read_until(f).strip() print(recv_m) if "mmm" in recv_m: hen = False print("Find!") d1 = h + d1 t = i^(j+1) t = hex(t)[2:] if len(t) == 1: t = "0"+t dec1 = t + dec1 break if hen: print("okashii") break p1 = long_to_bytes(int(dec1,16)^int(enc[:32],16)) print(p1) print(p1+p2)
ICHSA_CTF{I_d0nt_like_oracl3s}
Poodle 2 300pt
I lost my poodle again :(:(:(
let's try the oracle again?
Connect: nc poodle2.ichsa.ctf.today 8004
ファイル：poodle2.py
こちらはEncryption Attackですね。cをkeyでdecryptした値を求めてb"givemetheflag"とxorしたのを暗号文にします。
d1 = "" dec1 = "" for j in range(16): print(j) hen = True for i in range(256): read_until(f) read_until(f,">> ") h = hex(i)[2:] #print("h:",h) if len(h) == 1: h = "0"+h print("h:",h) mes = "00"*(15-j)+ h + modifyXor(d1) + enc[32:64] #print("mes:",mes) assert len(mes) == 64 s.send(mes.encode()+b"\n") recv_m = read_until(f).strip() print(recv_m) if "mmm" in recv_m: hen = False print("Find!") d1 = h + d1 t = i^(j+1) t = hex(t)[2:] if len(t) == 1: t = "0"+t dec1 = t + dec1 break if hen: print("okashii") break m = b"givemetheflag\x03\x03\x03" c = hex(int(dec1,16)^bytes_to_long(m))[2:] assert len(c) <= 32 while len(c) < 32: c = "0" + c c += "00"*16 read_until(f) read_until(f,">> ") s.send(c.encode()+b"\n") while True: print(read_until(f))
ICHSA_CTF{y3s_y0u_c4n_als0_encrypt_in_tha7_w4y_a660a2}
Unsolved
Pikatchu's Fault 100pt
I have a pretty weird girlfriend, she gave me a device to decrypt her secret messages to me. She said not to worry it is an efficient RSA implementation using CRT - whatever.
One time my pikatchu got an uncommon cold and sneezed exacty when I fed her secret message to the decryptor. I got unreadable nonsense as a result I suspect it's my pikatchu's fault for having an electric sneeze and it confused the decryptor. My confidence about it raised after I tried to decrypt again and got a readable message.
I wonder though if it is possible to get the private key from that faulty message.
N: 14428106165822100311240179104702593030922229606910261061860621459798477042443217675708638511393783602097391544907229222395222465303690975922805833664159517707002845392996861764206707180372733989400577838887924912395532925065643238637812097531657082837158436848594708309238918390308191361234059534178077141595873018313112575974600539522798755895311426362091301356794727864093165846318233065617022292712839240223002241134094765005135404901074586741323378531189871102865921045940469715763216120732916020528427859371641401521785824628585853094123501351577248220567930583676467206786442597142305655569749177107891502253803
e: 65537
M: 4c6f766520616e64206b69737365732c206d697373696e6720796f7521000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f202122232425262728292a2b2c2d2e2f303132333435363738393a3b3c3d3e3f404142434445464748494a4b4c4d4e4f505152535455565758595a5b5c5d5e5f606162636465666768696a6b6c6d6e6f707172737475767778797a7b7c7d7e7f808182838485868788898a8b8c8d8e8f909192939495969798999a9b9c9d9e9fa0a1a2a3a4a5a6a7a8a9aaabacadaeafb0b1b2b3b4b5b6b7b8b9babbbcbdbebfc0c1c2c3c4c5c6c7c8c9cacbcccdcecfd0d1d2d3d4d5d6d7d8d9dadbdcdddedfe0e1e2
M': 1a36d7ecad4b18bc765ff0e3d3ecde7cae84bf1cc445a6fdcb48c335d9d3a043817fc014d55bfad94b51eb522b4ff719d33f012afe1498efafe660b97d1cb806d4ff7985a40a14f9bec9d93e2eb20f3820423ba0e34302adc82156673fa164822779174e9b7a84a417873358d1d774ccdfdb1f36de6aa8249b00184aac2feb003782f16fb3f5d7b113387989f662062452793bbaad87014b1ebd4a020342a11a19d95f4d3b29dd5449c57ea0fd3b881542a7b8b0bdbc9dcb7b19337f40e723439365dc29625cb775e91aef886d79d1403725c5aefa21b3d69f8cacbbbafb8b35c86822113e71bd272ca7cdf68da0ab397c658cb6cc14225732bc07726155ecd1
gcd(M'-M, N) で素因数分解できることは分かりました。ただそれ以降は分からず…。
Problem&Solver
zh3r0 CTF v2 writeup
先日、TEAM NACS 第17回公演「マスタ―ピース～傑作を君に～」を拝聴しました。いやあ、面白い。大泉洋＝面白い俳優 → 水曜どうでしょう面白すぎる → TEAM NACS 面白い → 舞台観てみたい、となり今回この舞台をストリーミング配信で観ました。リーダーのカーテンコールにモーレツに感動した。皆さんも是非。
CTF中にこの配信があり、気になって仕方なかったよという話です。
Result
Writeup
今回、m1z0r3新入生の方がすごくてcrypto問題を結構解いてくれました！しかも自分が苦手な問題をやってくれたので何とも良いチームプレイでした！
それらも勉強せねば。
- Chaos
Twist and Shout はこちらから。その新入生が解いてくれました！ zh3r0 CTF 2021 writeUp - HackMD
alice_bob_dave
Alice and Bob are sending their flags to Dave. But sadly Dave lost the modulus :( Try to retrive the flag!
ファイル：chall.py, out.txt
公開鍵e, 暗号文ct_a, ct_b, 秘密鍵d_a, d_bが分かっていてn_a (=pq), n_b (=pr)が分からないという鬼畜。これが一番簡単なのか…。
e×d_a = k×φ(n_a)+1 = k×(p-1)×(q-1)+1
e×d_b = l×φ(n_b)+1 = l×(p-1)×(r-1)+1
より、GCD(e×d_a+1, e×d_b+1) = (p-1)×kとなります。このGCDした値を因数分解して、kと(p-1)に分ける組み合わせを全探査します。(p-1)に分けた方に1を足して1024bitsの素数となればOKです。因数の組み合わせが20個以内であればそんなに時間かかりませんね。
pが求まったらそこから頑張ってq, rを求めてもいいのですが(上と同じやり方で)、pをモジュールとしてやったらflag出てきましたやったね。
from Crypto.Util.number import * ct_a= ct_b= d_a= d_b= e=65537 import math c = math.gcd(e*d_a-1,e*d_b-1) #c = k*(p-1) print(c) # cを素因数分解したやつがpp pp = [ 2,2,3,3,1543,36097,1014259,17275267,33878479,64555363525704839503363,13843294374590501153575359748767274126053352729479537741977678154837940367725830968854964957283527886754718756686680847922782086222027205796563115693252960446483090290176656020345895604792952692850026400036720222060460108513404092975304800801154763470020377] import sympy for i in range(pow(2,len(pp))): cc = bin(i)[2:] while len(cc) < len(pp): cc = "0" + cc np = 1 for j in range(len(cc)): if cc[j] == "1": np*=pp[j] if sympy.isprime(np+1) and len(bin(np+1)[2:]) == 1024: print("Found!") p = np+1 #p = 177279130816191665059944783286411855023035031289227941571673915784074353287733189099688126318264113305321082059619767094038966996649561164342515779196140056547333435193040798074799909334916510316728847254833619137382153503950749154356946058670079132324988450725735937306884337410304401871741381990982764516163177279130816191665059944783286411855023035031289227941571673915784074353287733189099688126318264113305321082059619767094038966996649561164342515779196140056547333435193040798074799909334916510316728847254833619137382153503950749154356946058670079132324988450725735937306884337410304401871741381990982764516163 m1 = pow(ct_a,d_a,p) m2 = pow(ct_b,d_b,p) print(long_to_bytes(m1)) print(long_to_bytes(m2))
zh3r0{GCD_c0m3s_70_R3sCue_3742986}
1n_jection
COVID: exists
vaccine jokes: challenge_name
ファイル：challenge.py
from secret import flag def nk2n(nk): l = len(nk) if l==1: return nk[0] elif l==2: i,j = nk return ((i+j)*(i+j+1))//2 +j return nk2n([nk2n(nk[:l-l//2]), nk2n(nk[l-l//2:])]) print(nk2n(flag)) #2597749519984520018193538914972744028780767067373210633843441892910830749749277631182596420937027368405416666234869030284255514216592219508067528406889067888675964979055810441575553504341722797908073355991646423732420612775191216409926513346494355434293682149298585
まず、nk2n(x, y) = 259...585 になったことが分かります。elif l==2: を見てみると、 ( (i+j)×(i+j+1) )//2 +j = 259...585 ということが分かり、i, j が x, yに該当します。
enc = ( (i+j)×(i+j+1) )//2 +j
2×enc = ( (i+j)×(i+j+1) ) +2×j
2×enc ≃ (i+j)2
と強引な近似式を立てます。
x2 < 2×enc となる最大の自然数xを見つけ、2×enc - (x+1)x が 2×j となるのでj求め。x-jからiを出します。あとは、見つけたi, jをencとして共に128以下になるまで再帰的に計算させます。128以下としたのはASCII文字だろうという想定です。
感覚でnk2nの逆関数書いたら出来たという感じです。もっと理論的なwriteupありそう。最大の自然数としてうまくいったのも正直よく分かっていない。
def inv_nk2n(enc,dep): if enc < 128: print(chr(enc)) return e,_ = gmpy2.iroot(2*enc,2) #e = i+jになっていたらいいな e = int(e) while True: j = (2*enc-(e*(e+1)))//2 if j < 0: e -= 1 continue e1,_ = gmpy2.iroot(2*enc-2*j,2) #e1 = i+jのはず。e=e1ならちゃんと求められている if e == e1: i = e-j assert ((i+j)*(i+j+1))//2 +j == enc break e -= 1 if i < 128: print(chr(i),end="") print(chr(j),end="") return elif j < 128: #print(chr(j),end="") inv_nk2n(i,dep+1) print(chr(j),end="") else: inv_nk2n(i,dep+1) inv_nk2n(j,dep+1)
zh3r0{wh0_th0ugh7_b1j3c710n5_fr0m_nk_t0_n_c0uld_b3_s00000_c0000000l!}
b00tleg
Source? Gotta comply to Indian CTFs' crypto standards
nc crypto.zh3r0.cf 1111
これ本当にだるかった。
暗号文が渡されてそれがどんな暗号化をしているかは教えてくれないが、任意の16進数は暗号化してくれるoracleがあります。そして、渡された暗号文に対する平文が分かったら答えてねといった問題が8問もありました。
Q1-1
Level: 1, encrypted flag: 69666d6d70217870736d6522214d667574216866752168706a6f68 [1] Encrypt [2] Submit level flag >>> 1 message in hex:00 01 [1] Encrypt [2] Submit level flag >>> 1 message in hex:01 02 [1] Encrypt [2] Submit level flag >>> 1 message in hex:0f 10 [1] Encrypt [2] Submit level flag >>> 1 message in hex:0102030405 0203040506
と1byteごと1足した値が返ってきます。なので貰った暗号文を1byteごと1減らして出せばOKです。
[1] Encrypt [2] Submit level flag >>> 2 flag in hex:68656c6c6f20776f726c6421204c6574732067657420676f696e67 Correct
Q1-2
Level: 1, encrypted flag: 167536933462626657495469026094356252520425094567558410085605026028734973776349984140755605180214900 [1] Encrypt [2] Submit level flag >>> 1 message in hex:00 0 [1] Encrypt [2] Submit level flag >>> 1 message in hex:10 16 [1] Encrypt [2] Submit level flag >>> 1 message in hex:1000 4096
hex -> dec だけのようですね。貰った暗号文をhex()でOKです。
[1] Encrypt [2] Submit level flag >>> 2 flag in hex:4e6f7468696e672066616e63792c206a757374207374616e646172642062797465735f746f5f696e74 Correct
Q2
Level: 2, encrypted flag: 0082288254783f5b78d033d03fd03382287854c1e88928d054d0ccc1d0541be889c1d0331d89 [1] Encrypt [2] Submit level flag >>> 1 message in hex:00 f2 [1] Encrypt [2] Submit level flag >>> 1 message in hex:01 8d [1] Encrypt [2] Submit level flag >>> 1 message in hex:02 a9
これだけじゃ一切分からなかったのですが、下のですぐに分かりました。
[1] Encrypt [2] Submit level flag >>> 1 message in hex:0101 8d8d
00~ffが別の1byteとマッピングしているようですね。換字式暗号のよう。00~ffを暗号化させて対応表を作成し復号します。
このあたりから繋ぎ直す度に暗号文が変わっていきました。
[1] Encrypt [2] Submit level flag >>> 2 flag in hex:6d6f6e6f20737562737469747574696f6e73206172656e742074686174206372656174697665 Correct
このあたりから繋ぎ直す度に暗号文が変わっていきました。そして暗号文が変わっても平文は毎回一定ということが分かり、ASCII変換すると意味のある文字列になりました。早く気付け…
Q3
Level: 3, encrypted flag: c46b9613f603197b6d8d7ce39bc6ada752de6bff165924dfe5c3b90c00c792ea4775b0602d93a6cfc9652cf090b3 [1] Encrypt [2] Submit level flag >>> 1 message in hex:00 ef [1] Encrypt [2] Submit level flag >>> 1 message in hex:01 a6 [1] Encrypt [2] Submit level flag >>> 1 message in hex:0101 a693 [1] Encrypt [2] Submit level flag >>> 1 message in hex:0102 a6c7 [1] Encrypt [2] Submit level flag >>> 1 message in hex:02 2d [1] Encrypt [2] Submit level flag >>> 1 message in hex:0201 2d93
これまた換字式暗号のようですが、"0101"を送っても同じ1byteが2回続くわけではなさそう。ただ、i byte目かによって変わる換字式暗号のだろう。2byte目を"01"にしたら1byte目に依存せず"93"となりました。
なので、暗号文の上位1byteと一致するまで00~ffを暗号化してもらい、"(一致した1byte)+00~ff" で暗号化してもらい、暗号文の上位2byteと一致するか確かめ、"(一致した2byte)+00~ff" で…を繰り返します。
[1] Encrypt [2] Submit level flag >>> 2 flag in hex:6372656174696e6720646966666572656e7420737562737469747574696f6e7320666f7220656163682063686172 Correct
Q4
Level: 4, encrypted flag: 83c492da5a071252f030f87c4424db86a7cd110f5b1eaec1fc7935eb5f073d2c3631caab94de551071f35dc3b5ba93e2680c44dc670d8cdc0560e43caebb620cf77fc1a060121059471ab7b7da9a [1] Encrypt [2] Submit level flag >>> 1 message in hex:00 c43c [1] Encrypt [2] Submit level flag >>> 1 message in hex:00 dc24 [1] Encrypt [2] Submit level flag >>> 1 message in hex:00 38c8 [1] Encrypt [2] Submit level flag >>> 1 message in hex:00 8e72 [1] Encrypt [2] Submit level flag >>> 1 message in hex:00 14ec [1] Encrypt [2] Submit level flag >>> 1 message in hex:00 a45c [1] Encrypt [2] Submit level flag >>> 1 message in hex:00 847c [1] Encrypt [2] Submit level flag >>> 1 message in hex:0001 b05058a9 [1] Encrypt [2] Submit level flag >>> 1 message in hex:0001 7a867e83
なんの方法も思いつきません。1byteの平文が2byteの暗号文になっていて、2倍の関係はずっと成り立つくらいです。
無心で"00"を暗号化していると…
[1] Encrypt [2] Submit level flag >>> 1 message in hex:00 11ef [1] Encrypt [2] Submit level flag >>> 1 message in hex:00 12ee [1] Encrypt [2] Submit level flag >>> 1 message in hex:00 11ef
と同じ暗号文になる時があった。もしかして、"00"の暗号文は256通りあってだから1byte平文→2bytes暗号文か？となりました。
00~ffまで100回ほど暗号化してもらって、貰った暗号文と一致しているかチェックして平文を復号させていきます。256通りもあるので、何回も暗号化してもらっても貰った暗号文と一致しない箇所があるかもしれませんが、平文は意味ある文字列になるので最後はエスパー出来るだろう。
47xy616420xy6861xyxy796fxyxy66696775726564206fxyxy2074686520696e7661xyxyxy6e74 G?ad ?ha??yo??figured o?? the inva???nt
予想当たってそう。
Glad, figured out になるのだろう。最後の単語なんだろう。
ここで2日目の夜を迎えます。僕はお休みですがPCには頑張ってもらいます。夜通しグルグルさせたら復号できました。
[1] Encrypt [2] Submit level flag >>> 2 flag in hex:476c6164207468617420796f752066696775726564206f75742074686520696e76617269616e74 Correct
Glad that you figured out the invariant
実際、"00"の暗号文256個を全て出すのにかかる暗号化試行回数の期待値はいくつなのだろう。
Q5
Level: 5, encrypted flag: 21632f60371e637d646719633361371d6e38257c0c7f7d727e1d6e7d7c781c747d767f007271256705633c76724962326b63497238697b4967337c780763cdc8ef69065d0517 [1] Encrypt [2] Submit level flag >>> 1 message in hex:00 2d1d7371522d4207101c [1] Encrypt [2] Submit level flag >>> 1 message in hex:01 77d092631876f707d06a [1] Encrypt [2] Submit level flag >>> 1 message in hex:02 01d479285c03ca8ee440 [1] Encrypt [2] Submit level flag >>> 1 message in hex:0001 ed22e53735ed2323ded2 [1] Encrypt [2] Submit level flag >>> 1 message in hex:000102 3d6c2d55f63d6d2fbc4b [1] Encrypt [2] Submit level flag >>> 1 message in hex:00010203 3b5742e8213b5640eb2d [1] Encrypt [2] Submit level flag >>> 1 message in hex:0001020304 5a77fc8bd45a76fe88d0 [1] Encrypt [2] Submit level flag >>> 1 message in hex:000102030405 228a9f15b82739069578228b9d16bc
5bytesまで暗号文の長さは10bytesと変わらず、6bytes送ると15bytesになりました。初めは5bytes -> 10bytesなのでQ5と変わらないのかと思いましたが、6bytes(10bytesでも) -> 15bytesで断念。なんか余計な5bytesがあるな。
[1] Encrypt [2] Submit level flag >>> 1 message in hex:00010203040506070809 4b3f92695d4e389762504b3e906a59 [1] Encrypt [2] Submit level flag >>> 1 message in hex:00010203040506070809 6c5fd82ec26958dd25cf6c5eda2dc6 [1] Encrypt [2] Submit level flag >>> 1 message in hex:00010203040506070809 22f1249dd427f62196d922f0269ed0
またもや無心oracle attackをしていると、いずれも0~2, 20~22文字目が一致している & 3, 23文字目の差の絶対値が1という共通点を発見。
[1] Encrypt [2] Submit level flag >>> 1 message in hex:000102030405060708090001020304 ba7470d81abf7375d317ba7470d81aba7572db1e
この0~9, 20~29文字が等しい暗号文を送ると、暗号文の0~9, 20~29が等しくなりました。
XORだ！！！！
下位5bytesは乱数で、それと平文5bytesずつXORしているよう。平文長が5の倍数出ない場合は乱数でパディングしているよう。
貰った暗号文の下位5bytesと他でXORすると文章が出てきました。後ろ3bytesはパディングのようですね。
Here we append the key with your shit, please dont tell anyone\x90\xcd\xf8
後ろ3bytesをカットして提出でcorrect
[1] Encrypt [2] Submit level flag >>> 2 flag in hex:4865726520776520617070656e6420746865206b6579207769746820796f757220736869742c20706c6561736520646f6e742074656c6c20616e796f6e65 Correct
Q6
次の問題が出るまでちょっと待たされる
Level: 6, encrypted flag: 136384619054339654698475609187854339113882435852470452229300074212198483311645305554174498023573137797735886243473558340482613861649177748126144672869929906606346385500823906944622319359965197258529068372012245196075373073203790506545107848221246609729715492848444591450621341939920310444052818596797750926038 [1] Encrypt [2] Submit level flag >>> 1 message in hex:00 0 [1] Encrypt [2] Submit level flag >>> 1 message in hex:01 1 [1] Encrypt [2] Submit level flag >>> 1 message in hex:02 8 [1] Encrypt [2] Submit level flag >>> 1 message in hex:03 27
Q5, 6の疲労からまだ難しいのがどんどん来るのだろうと思ったら、ただの3乗やんけ！とウッキウキで暗号文の3乗根を取ってみる。無い。キレる。
どんな暗号文を送っても3乗になるだけ…となっていたのですが、大きい数字を送ると3乗根はありませんでした。e=3, N=unknownのRSA暗号のよう。
m3 > N となるmを送り、m3 - c (=m3 mod N)からNの倍数が手に入ります。これは先程の新入生が教えてくれました。自分は気付かず二分探索で求めようと…。
素因数分解してみると、1024bitsの素数が1つだけありました。色々検証した結果、c = m3 mod p (p:prime) と断定。ed = 1 mod (p-1) でdを求め、cd mod pで意味ある文字列になりました。
[1] Encrypt [2] Submit level flag >>> 2 flag in hex:43756265206d6f64756c6f207072696d652c20616e7920677565737365732077686174206d6967687420626520636f6d696e67206e6578743f Correct
Q7
Level: 7, encrypted flag: 108613801296595507842842562285901639870700128823984221118522899150125891850980318127085910315828915486703595963395705206816199002398854310898276932839241255030719759005865491552890311738885862387404277721909188630301200138952557304529868842692309573491972932743859389182753896383477285635296983981909565573190 [1] Encrypt [2] Submit level flag >>> 1 message in hex:00 0 [1] Encrypt [2] Submit level flag >>> 1 message in hex:01 1 [1] Encrypt [2] Submit level flag >>> 1 message in hex:02 170141183460469231731687303715884105728
今度も何乗もしていそう。"02"の時、かなり大きい値となっていますが、2進数にする進数にすると
>>> c = 170141183460469231731687303715884105728 >>> bin(c) '0b10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000'
ここから、eの値が求められます。この場合128bitsあるのでe=127ですね。
先と同様に、me > nとなる平文を送ってその差分からnが分かります。Q6でもやればよかったのですが、GCD(m1e - c1, m2e - c2)でよりnがわかりやすいです。今回もn=p (p:prime)でした。
[1] Encrypt [2] Submit level flag >>> 2 flag in hex:7a683372307b31375f61316e375f6d7563685f6275375f315f346d5f73306d333768316e675f30665f345f6372797037346e346c7935375f6d7935336c667d Correct Shh, you got the flag already
もうもらっているとあるので、出てきた平文をASCII変換するとflagでした
zh3r0{17_a1n7_much_bu7_1_4m_s0m37h1ng_0f_4_cryp74n4ly57_my53lf}
Problems & Solver
Padding Oracle Attack 分かりやすく解説したい
Padding Oracle Attack, AESを使うCTF問題で一番難しいのではないのでしょうか。僕もこれがあるせいでAES問題に強い苦手意識がありました。僕と同じような方も、この記事で得意になってくれると嬉しいです！Padding Oracle Attackが理解できると、どんなAES問題も強気で解きにいけると思います！
AESとは
いつもの。
ブロック暗号の代表格ですね。あまり言うと違うよとお叱りを受けそうなのですが、DESに脆弱性が発見されてからAESが主流となり推奨されているといった感じです。
ブロック暗号とは、平文をN文字ずつ分けそれぞれ暗号化するような感じです。AESでは16文字ごと分けています。その暗号化の方式はいくつかあり、AESではECB, CBC, CFBモードなどがあります。
AESのCBCモードとは
暗号化
平文を16文字ずつに分け、各ブロックをkeyというバイト列によって暗号化します。自分の理解ではkeyの値を知っていたとしてもどのように暗号化されるかは分からないです。pythonのpycryptodomeモジュールでは簡単にできますが、まあできないもんとしていても大丈夫だと思います。
keyとは別にivというバイト列も用意します。平文の第1ブロックをivとxorし、その値をkeyによって暗号化したのが暗号文の第1ブロックになります。続いて、平文の第2ブロックとivではなく暗号文の第1ブロックとxorしたのをkeyによって暗号化したのが暗号文の第2ブロックとなります。
以降は [平文の第kブロック] xor [暗号文の第k-1ブロック] -> (key) -> [暗号文の第kブロック] となります。
これがAESのCBCモードです。CTFでは他にECBモードが良く使われます。ECBは平文をただkeyによって暗号化するだけなので、同じ平文ブロックがあると同じ暗号文ブロックになるという欠点があります。その点、CBCモードは前の暗号文ブロック(もしくはiv)とxorするので、同じ平文ブロックがあっても異なる暗号文ブロックになります。
復号
復号方式は、暗号化方式の手順を逆にしたものです。
まず第1暗号文ブロックをkeyによってdecryptし、ivとxorしたのが第1平文ブロックです。以降はkeyによってdecryptするのは同じですが、xorするのはその一つ前の暗号文ブロックとです。
CBCモードの暗号化/復号方式はこんな感じです。不慣れな方はじっくり勉強しましょう！
CBCモードのCTF問題で、Padding Oracle Attackを使わないものですが、これが分かるとよりこの攻撃が理解しやすくなると思います！
ångstromCTF 2021 writeup - Attack All Around
Padding方式 PKCS #7とは
AESでは、ある平文を暗号化する際に平文を16文字ずつ分けますが、その平文の長さが16の倍数でない時はどうなるのでしょうか。答えは平文の後ろに詰め物をして強引に16の倍数にします。この詰め物をパディングといいます。
ではPKCS #7がどのようにパディングしているかというと、パディングしている長さを値としてパディングします。はい、よく分からないですよね。具体例を出しましょう。
b"0123456789abcde" という平文を暗号化したいと思います。長さが15なので16の倍数にするには1つパディングする必要があります。その場合、PKCS #7方式では「b"0123456789abcde\x01"」となります。1つパディングするのでb"\x01"が1つあります。
では、b"0123456789abcd" という平文を暗号化したい場合のパディングは、どうなるのでしょうか。答えは「b"0123456789abcd\x02\x02"」です。2つパディングするのでb"\x02"が2つあります。
こんな感じで、3個のパディングはb"\x03\x03\x03", 11個パディングするにはb"0x0b"×11となります。このようにパディングがどれだけされているかがパディング値で分かるようになっています。これでどこまでが平文でどれが詰め物かが分かるようになりますね。
pythonのpycryptodomeでは、Crypto.Cipher モジュールにpad関数が実装されています。pad(byte列, 1ブロックの長さ(=基本16) )とするとPKCS #7方式でパディングしてくれます。style = で指定するパターンもあります。
加えて、unpad関数も実装されています。pad関数と同様に、unpad(byte列, 16)でパディングを消してくれます。ここで重要なのが、unpad関数は第一引数のbyte列がこのPKCS #7方式でパディングしていない場合、エラーを吐きます。まず一番後ろの1byteを見て、b"\x01" ~ b"\x10"でないならエラー吐きますし、そうであってもその長さ分同じものが続いていないとエラーを吐きます。
エラーを吐く例
- b"abcdefghijklmnop"
- b"abcdefghijklmno\x02"
- b"abcdefghijkl\x04\x04\x03\x03"
- b"abcdefghijkl\x04\x03\x04\x04"
エラーを吐かない例
- b"abcdefghijklmn\x02\x02"
- b"abcdefghijklmnop" + b"\x10"×16
- b"abcdefghijklm\x03\x02\x01" -> パディングが1つとして扱われる
このunpad関数でのパディングが上手くいかなかった時のエラー、これを通信相手に教えてしまうとPadding Oracle Attackが出来てしまう環境となってしまいます。次の節で具体的に解説していきます！
用意した自作サーバ
GitHub - ksbowler/PaddingOracleAttack
こちらのgithubにも載せていますが、公開サーバーだけ載せますね。
import socketserver import socket, os from Crypto.Cipher import AES from Crypto.Util.Padding import pad,unpad from binascii import unhexlify, hexlify from secret import FLAG, MSG import base64 key = os.urandom(16) iv = os.urandom(16) def encrypt_data(data): pt = pad(data.encode(),16,style='pkcs7') cipher = AES.new(key, AES.MODE_CBC,iv) enc = cipher.encrypt(pt) return enc.hex() def decrypt_data(encryptedParams): assert len(encryptedParams) >= 32 IV = encryptedParams[:32] data = encryptedParams[32:] cipher = AES.new(key, AES.MODE_CBC,unhexlify(IV)) paddedParams = cipher.decrypt( unhexlify(data)) pt = unpad(paddedParams,16,style='pkcs7') return pt def send_msg(s, msg): enc = msg.encode() s.send(enc) def main(s): wlcm_msg = "Welcome to practice for Padding Oracle Attack\n" send_msg(s, wlcm_msg) msg = base64.b64encode(MSG.encode()).decode() send_msg(s, "Guest ciphertext: " + encrypt_data(msg)+'\n') IV = hexlify(iv).decode() send_msg(s, "IV : "+IV+"\n") while True: #任意の暗号文を復号できる send_msg(s, 'What ciphertext do you want to decrypt? (hex): ') ct = s.recv(4096).decode().strip() try: check = decrypt_data(ct) send_msg(s, "check you can login\n") #print("check :",check) except Exception as e: send_msg(s, str(e) + '\n') continue try: pt = base64.b64decode(check).decode() if pt[:25] == MSG[:25]: send_msg(s, "You can login!\n") if pt[25:] == "admin": clear_msg = "OK! You are admin! Here is flag\n" send_msg(s, clear_msg) send_msg(s, FLAG+"\n") else: guest_msg = "However, because you are not admin, we can not send you flag\n" send_msg(s, guest_msg) else: invalid_msg = "We can not recognize your input for our service\n" send_msg(s, invalid_msg) except Exception as e: send_msg(s, str(e) + '\n') class TaskHandler(socketserver.BaseRequestHandler): def handle(self): main(self.request) if __name__ == '__main__': socketserver.ThreadingTCPServer.allow_reuse_address = True server = socketserver.ThreadingTCPServer(('0.0.0.0', 3000), TaskHandler) server.serve_forever()
流れとしては、
- 変数MSGにある文字列をbase64で暗号化し、AESのCBCモードで暗号化したものが送られる。
- この暗号化に使われたIVが送られる。
- 任意の文字列を復号してくれる。IVも自身で決められる。
3-a. 復号時に失敗すると、エラー文が送られる。
3-b. 復号しbase64decodeしたものと、変数MSGの前25文字と比較する。
3-b-1. 合致し且つ残りが"admin"だとflagがゲット。 (目標はここ)
3-b-2. 合致するが残りが"admin"でないと、loginできないと言われる。
3-b-3. 合致しないと認識できないと言われる。
この3-aが脆弱性なんです。次節で説明していきますね。
平文を手に入れる Decryption Attack
それでは本題の攻撃アルゴリズムについて書いていきます。
Padding Oracle Attackを簡単に言うと、暗号文ブロックc_iをkeyによってdecryptionした値Dec(c_i)が分かれば、そこから貰った暗号文ブロックc(i-1)とxorすれば平文ブロックp_iが分かるし、任意の平文ブロックp_iに対する暗号文ブロックc(i-1)をxorすることで作成できます。だからDec(c_i)を求めようという感じです。
githubにも載せているスライドに合わせて進めていきます。
この問題の目的は上記の3-b-1になることです。そのためにはまず、変数MSGがどんな文字列が分からないといけません。変数MSGがbase64 encodeされた値がCBCモードで暗号化されています。その暗号文から元の平文を求めていくのがDecryption Attackです。
まずは、平文の最終ブロックを求めていきます。今回は暗号文が16進数で96桁なので3blocksあります。なのでp3を求めていきます。
p3 = Dec(c3) xor c2 という式で復号されます。ここでDecとはkeyによって復号された値です。p3を求める前にこのDec(c3)を求めます(スライドではc2となっています)。
本問のサーバは復号文は教えてくれませんし、Dec(c3)の値も教えてくれません。しかし、復号時にPaddingがきちんとされてないとエラー文を送ってくれます。それを使ってDec(c3)を求めます。
c2の16bytesを全てb"\x00"にして送ります。理由は後述します。そこから最後1byteを0x00から0xffまで全て試します。そうすると、一回だけPadding incorrectと出ない時があります。復号されたp3の最後1byteがb"\x01"となった時ですね。そうなった時に何を送ったかを覚えておきます。例えばそれが"f6"だったとします。そうなると、Dec(c3)の最後1byteが、0xf6 xor 0x01 = 0xf7であることが分かります！
次に、Dec(c3)の最後2byte目を求めます。次はp3の最後2byteをb"\x02\x02"となるようにしたいです。まず、p3の下位1byteをb"\x02"にするには、0xf7 xor 0x02 = 0xf5をc2の下位1byteとします。そして、c2の下位2byte目を0x00から0xffまで全て試して、padding incorrectが出ないものを見つけます。先と同様にDec(c3)の2byte目を求めます。
ここまで来るとお分かりでしょうが、次はDec(c3)の下位3byte目を求めます。下位2bytesをb"\x03\x03"になるようc2の下位2bytesを調整し、c3の下位3byte目をbrute forceします。
これを繰り返していくと、Dec(c3)の16bytes全て求めることが出来ます。そこからp3は簡単に分かります。1. で貰ったMSGの暗号文と求めたDec(c3)より、p3 = Dec(c3) xor c2の式に当てはめるとp3が求められましたね。
本問では、以下のような平文となりました。
m = b'PWd1ZXN0\x08\x08\x08\x08\x08\x08\x08\x08'
base64decodeすると、"=guest"となりました。文字列になったことから正しく動作していることが分かりますね。
先程少し触れた「c2の16bytesを全てb"\x00"にする」理由ですが、もらったc2の上位15bytesをそのまま使うとpadding incorrectと言われない時が二回ある可能性があります。平文のpaddingとごっちゃになってしまう場合に注意です。
p3が求められたので、次はp2を求めていきます。サーバに送る暗号文はIVとc1, c2とし、c3は送りません。c2を最終ブロックとすることで、p2のpaddingがどうか先程と同じようにしてDec(c2)→p2を求めていきます。
以上を繰り返して、平文全てを求めます。平文の先頭ブロックを求める時はIVを変えていきます。やり方は上のと変わりません。
b'bTF6MHIzX2xvZ2luX3NlcnZpY2U6IElEPWd1ZXN0\x08\x08\x08\x08\x08\x08\x08\x08'
base64 decode : b'm1z0r3_login_service: ID=guest'
IDがguestではloginできませんね。adminにしてloginできるように、Encryption Attackを行いましょう。
任意の平文に対する暗号文を手に入れる Encryption Attack
Decryption Attackは複雑で難しいと思いますが、これが理解できればEncryption Attackは大して難しくありません。やっていることはDecryption Attackとさほど変わりません。
Encryption Attackは、padding incorrectを教えてくれる時に、復号したら欲しい平文となる暗号文を作ることが出来る攻撃です。
本問では、b'm1z0r3_login_service: ID=admin'をbase64 encodeした平文、つまり「b'bTF6MHIzX2xvZ2luX3NlcnZpY2U6IElEPWFkbWlu\x08\x08\x08\x08\x08\x08\x08\x08'」が欲しいです。これの暗号文を作っていきましょう。
Encryption Attackの手順は、初めにDecryption Attackと同じようにDec(c_i)を求めます。c3はMSGの暗号文と変える必要はありません。そのDec(c3)を求めたら、b'PWFkbWlu\x08\x08\x08\x08\x08\x08\x08\x08'とxorした値をc2とします。c2とDec(c3)をxorしたらこの欲しい平文になりますよね。
では、次にこの新しいc2のDec(c2)を求めるためにc1をいじくります。Decryption Attackと同じようにしてOKです。Dec(c2)が求まったら、欲しい平文の後ろから2つ目とブロックとxorしてそれをc1とします。同じようにしてIVも求めます。
IVとc1~c3を送ると、それが欲しい平文と復号されるので、adminとしてloginが出来てflagが手に入りました！
m1z0r3{Padding_Oracle_Attack_is_so_difficult}
おわりに
githubにsolver.pyと公開サーバのserver.pyと作問者しか見られないsecret.py, そして解説資料のpdfを載せています。そちらもご覧ください。
GitHub - ksbowler/PaddingOracleAttack
Padding Oracle Attackを使う問題は多くはないですが、理解できるとほとんどのAES問題は解けると思います。はじめにも書きましたが、私もこれがあるからAES問題は好きではなかったのですが、分かると楽しくなりました！
crypto問題面白いけど実生活に活きることあるのだろうか、と考えながらCTFを解いているこの頃…。解けると楽しいんだよなぁ。でもタスクもある…。と苛まれている次第です。ご査収ください。
参考文献
- Padding Oracle AttackによるCBC modeの暗号文解読と改ざん - security etc...
この文献を理解できるようになるまでしばらくかかりました。この記事でより早く理解できたということがあると嬉しいです！
cpawCTF level3 Common World ○○○○○○の定理じゃないの？
ちょっと納得いかなかったので共有。
問題文
Cpaw君は,以下の公開鍵を用いて暗号化された暗号文Cを受け取りました．しかしCpaw君は秘密鍵を忘れてしまいました.Cpaw君のために暗号文を解読してあげましょう.
(e, N) = (11, 236934049743116267137999082243372631809789567482083918717832642810097363305512293474568071369055296264199854438630820352634325357252399203160052660683745421710174826323192475870497319105418435646820494864987787286941817224659073497212768480618387152477878449603008187097148599534206055318807657902493850180695091646575878916531742076951110529004783428260456713315007812112632429296257313525506207087475539303737022587194108436132757979273391594299137176227924904126161234005321583720836733205639052615538054399452669637400105028428545751844036229657412844469034970807562336527158965779903175305550570647732255961850364080642984562893392375273054434538280546913977098212083374336482279710348958536764229803743404325258229707314844255917497531735251105389366176228741806064378293682890877558325834873371615135474627913981994123692172918524625407966731238257519603614744577)
暗号文: 80265690974140286785447882525076768851800986505783169077080797677035805215248640465159446426193422263912423067392651719120282968933314718780685629466284745121303594495759721471318134122366715904
これは…？
フラグは以下のシンタックスです.
cpaw{復号した値}
※復号した値はそのままで良いですが，実は意味があります，余力がある人は考えてみてください.
「これは…？」をクリックするとhint.txtが貰える。
Cpaw君は自力では解けないのでRSA暗号のプロに尋ねるとヒントをくれました. (e, N) = (13, 236934049743116267137999082243372631809789567482083918717832642810097363305512293474568071369055296264199854438630820352634325357252399203160052660683745421710174826323192475870497319105418435646820494864987787286941817224659073497212768480618387152477878449603008187097148599534206055318807657902493850180695091646575878916531742076951110529004783428260456713315007812112632429296257313525506207087475539303737022587194108436132757979273391594299137176227924904126161234005321583720836733205639052615538054399452669637400105028428545751844036229657412844469034970807562336527158965779903175305550570647732255961850364080642984562893392375273054434538280546913977098212083374336482279710348958536764229803743404325258229707314844255917497531735251105389366176228741806064378293682890877558325834873371615135474627913981994123692172918524625407966731238257519603614744577) 暗号文: 14451037575679461333658489727928902053807202350950440400755535465672646289383249206721118279217195146247129636809289035793102103248547070620691905918862697416910065303500798664102685376006097589955370023822867897020714767877873664
クレーム
解法はCommon Modulus Attackをやるらしい。
e1=11, e2 = 13とすると、e1×6+e2×(-5)=1となる。問題文にある暗号文をc1, hint.txtにある方をc2とすると、m = c16 × c2-5 mod n で求まるとのこと。me1×6+e2×(-5) = m1 となりますからね。
ただCommon Modulus Attackが成立する条件は、「同じnと異なるeで同じ平文mを暗号化してはいけない」だ。hint.txtには同じ平文をeで暗号化したとは一言も言ってない。これをエスパーしろというのは酷では？
まあ、level2までのCrypto問題もそこまで難しい問題ではなかったから比較的簡単なCMAを扱ったというのは分からんでもないが、ちょっとなぁ。問題名も確かに…。うーん。
別解？
クレームをつけた理由として、Common Modulus Attackを使わずに解いたからがあげられる。
カーマイケルの定理を使った。この記事がわかりやすい。
p - 1 ≡ 0 (mod e) のときの RSA 復号方法 | y011d4.log
そもそもnは素因数分解可能でありそれで簡単に解けるかと思いきや、eとφ(n)が互いに素でない。Seccon Beginnersでも同様の問題があり、それを引っ張り出してきた。どうでもいいけど毎回beginnerのスペルが怪しい。engineerやpioneerにつられてbegineerと書きたくなる。
SECCON Beginners CTF 2021 Crypto writeup - Attack All Around
ここで腹が立ったのが、φ(n)がe2=13の倍数でもあったこと。hint.txtの暗号文を復号すれば何かヒントがもらえると思い込んでいたのでつらかった。
L = 3φ(n)/e とすれば後は記事通り。2じゃダメだった。
e=11なので11種類の平文が出てくる。かなり短い平文を発見したので提出したらcorrectだった。
from Crypto.Util.number import * import math n = (中略) p = pow(2,607)-1 assert n%p == 0 q = n//p e = 11 c = (中略) phi = (((p-1)*(q-1))//(math.gcd(p-1,q-1))) # カーマイケルの定理 d = inverse(e,phi//e) m = pow(c,d,n) L = pow(3,phi//e,n) for i in range(e): mm = (pow(L,i)*m)%n print("cpaw{"+str(mm)+"}") # Common Modulus Attack ee = 13 cc = (中略) s1 = 6 s2 = -5 cc_inv = inverse(cc,n) M = (pow(c,s1,n)*pow(cc_inv,-s2,n))%n print("cpaw{"+str(M)+"}")
cpaw{424311244315114354}
これが何かの意味を持つとのことで16進数ぽいとエスパーしたが11がある時点でダメ。これらしい。
"RSAISEASY"となるようだが、カーマイケルの定理を使っている時点でどこがEASYやとまた怒る。
これだけ言ってますが、常設CTFには感謝してます。良い勉強になっています。
