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}
