Attack All Around

今やCTFと競プロばかりだが、トビタテ生のアメリカ留学やTOEFL奮闘記

m1z0r3CTF 2021 作問しました

今年もm1z0r3CTFの季節になりました。
今年が最後ということで、性格の悪さを存分に発揮した問題を作りました。

githubにプログラムファイルを載せていますが、サーバ問題に関しては皆さんローカルで動かしていただきたいです。その中でsecret.pyなどが入っていますが見ないで解いてください…。見てはいけないファイルに関してはreadme.txtなどに書いてあるので、そちらを先に読んでください！



Challenge


github : GitHub - ksbowler/m1z0r3CTF_2021: m1z0r3CTF 2021 problem files


15Prime (warmup)

Prime numbers are prime in this problem.
ファイル：15prime.zip (chal.py, output.txt)


Long Island (easy)

Have you ever heard of a Japanese comedian named Long Island?
ファイル：Long_Island.zip (chal.py, output.txt)


1024Prime (medium)

nc 127.0.0.1 5000 ファイル：1024prime.zip (server.py)


SqUArE (hard)

□■
ファイル：challengeS.zip (outputS.txt, chalS.py)


解説は1週間後に掲載します！

Buckeye CTF Defective RSA writeup


Challenge

I use whatever exponent I want
ファイル：chall.py

from Crypto.Util.number import getPrime, inverse, bytes_to_long

e = 1440

p = getPrime(1024)
q = getPrime(1024)
n = p * q

flag = b"buckeye{???????????????????????????????}"
c = pow(bytes_to_long(flag), e, n)

print(f"e = {e}")
print(f"p = {p}")
print(f"q = {q}")
print(f"c = {c}")

# e = 1440
# p = 108625855303776649594296217762606721187040584561417095690198042179830062402629658962879350820293908057921799564638749647771368411506723288839177992685299661714871016652680397728777113391224594324895682408827010145323030026082761062500181476560183634668138131801648343275565223565977246710777427583719180083291
# q = 124798714298572197477112002336936373035171283115049515725599555617056486296944840825233421484520319540831045007911288562132502591989600480131168074514155585416785836380683166987568696042676261271645077182221098718286132972014887153999243085898461063988679608552066508889401992413931814407841256822078696283307
# c = 4293606144359418817736495518573956045055950439046955515371898146152322502185230451389572608386931924257325505819171116011649046442643872945953560994241654388422410626170474919026755694736722826526735721078136605822710062385234124626978157043892554030381907741335072033672799019807449664770833149118405216955508166023135740085638364296590030244412603570120626455502803633568769117033633691251863952272305904666711949672819104143350385792786745943339525077987002410804383449669449479498326161988207955152893663022347871373738691699497135077946326510254675142300512375907387958624047470418647049735737979399600182827754



How to solve

まず e=1440ということで、p-1, q-1と互いに素ではないのでいつも通りの復号ができません。eを素因数分解すると、25 × 32 × 5 となります。次の3ステップで復号していきます。


c = c1 ^ 32 (=2^5) mod n
c1 = c2 ^ 9 (=3^2) mod n
c2 = m^5 mod n


Step 1

c = c1 ^ 32 mod n となるc1を以下のアルゴリズムで求めます。

ct ← c
for 0,5,1 :
  [ct = c1'^2 mod n となるc1'を求める] : ①
  ct ← c1'
c1 ← ct

①の部分はRabin暗号で求められます。Rabin暗号ではp, qがともに4で割ると余りが3になるものが条件ですが、今回はこれに合致しています。

f:id:partender810:20211027133536p:plain
Rabin暗号　復号方式

出典：Rabin cryptosystem - Wikipedia

上図のように復号していきます。c = c1'^2 mod n となるc1'は4通り考えられます。その4通りのc1'において、c1' = c1''^2 mod n となるc1''を求めます。これを繰り返すと 45 通りのc1が出てきそうですが、重複しているものや上図のr1~r4を2乗しても元に戻らないものなどを削ると3通りにまでc1の候補を減らすことができます。


Step 2

Step1で求めたc1を使って、c1 = c2 ^ 9 mod n となるc2を求めます。

ここで、9はp-1, q-1ともに互いに素なのでいつものRSAのように復号可能です。


Step 3

Step2で求めたc2を使って、c2 = c3 ^ 5 mod n となるc3を求めます。このc3は求めたいmに該当します。

5はp-1の約数ですが、その二乗の25はp-1の約数ではありません。また、q-1は5で割り切れません。以上より、カーマイケルの定理が利用できます。


p - 1 ≡ 0 (mod e) のときの RSA 復号方法 | y011d4.log


このサイトをそのまま使います。e=5と置き換えれば復号可能です。c2の候補3つを全て復号してみたら、flagのような形の平文が出力されました。

from Crypto.Util.number import *
import math
import gmpy2


e = 1440
p = 108625855303776649594296217762606721187040584561417095690198042179830062402629658962879350820293908057921799564638749647771368411506723288839177992685299661714871016652680397728777113391224594324895682408827010145323030026082761062500181476560183634668138131801648343275565223565977246710777427583719180083291
q = 124798714298572197477112002336936373035171283115049515725599555617056486296944840825233421484520319540831045007911288562132502591989600480131168074514155585416785836380683166987568696042676261271645077182221098718286132972014887153999243085898461063988679608552066508889401992413931814407841256822078696283307
c = 4293606144359418817736495518573956045055950439046955515371898146152322502185230451389572608386931924257325505819171116011649046442643872945953560994241654388422410626170474919026755694736722826526735721078136605822710062385234124626978157043892554030381907741335072033672799019807449664770833149118405216955508166023135740085638364296590030244412603570120626455502803633568769117033633691251863952272305904666711949672819104143350385792786745943339525077987002410804383449669449479498326161988207955152893663022347871373738691699497135077946326510254675142300512375907387958624047470418647049735737979399600182827754
n = p*q

#step1
g,yp,yq = gmpy2.gcdext(p,q)
yp = int(yp)
yq = int(yq)
assert p*yp+q*yq == 1
c_list = [c]
for _ in range(5):
    next_c_list = []
    print("="*30)
    for ct in c_list:
        mp = pow(ct,(p+1)//4,p)
        mq = pow(ct,(q+1)//4,q)
        r1 = (yp*p*mq+yq*q*mp)%n
        r2 = n-r1
        r3 = (yp*p*mq-yq*q*mp)%n
        r4 = n-r2
        
        if (r1**2)%n == ct: next_c_list.append(r1)
        
        if (r2**2)%n == ct: next_c_list.append(r2)
        
        if (r3**2)%n == ct: next_c_list.append(r3)
        
        if (r4**2)%n == ct: next_c_list.append(r4)
        

    c_list = list(set(next_c_list))
print(c_list,len(c_list))

#step2
e1 = 9
phi = (p-1)*(q-1)
d1 = inverse(e1,phi)
next_c_list = []
for ct in c_list:
    m = pow(ct,d1,n)
    next_c_list.append(m)
c_list = list(set(next_c_list))

#step3
phi //= 10
d = inverse(5,phi)
for k in range(2,5):
    L = pow(k,phi,n)
    for i in range(5):
        for ct in c_list:
            m = (pow(ct,d,n)*pow(L,i,n))%n
            print()
            print(long_to_bytes(m))


buckeye{r0ots_0f_uN1Ty_w0rk_f0r_th1s???}



DeconstruCT.F 2021 Cryptography writeup

初めて全部の問題を紹介できる記事になったと思います。



Writeup


RSA-1

I have a lot of big numbers. Here, have a few!
ファイル：big_numbers.txt

nが小さいので素因数分解可能です。いつものように復号して終わりです。

from Crypto.Util.number import *


p,q = 4655885807254867892895911581,5051525354555657585960616263
phi = (p-1)*(q-1)
d = inverse(e,phi)
m = pow(c,d,n)
print(long_to_bytes(m))


dsc{t00_much_m4th_8898}



RSA-2

Hey I heard you have a supercomputer at home. This is taking too long to compute on my computer. Could you take a look on yours? I'm sure its a lot more precise than mine is, and faster too!
ファイル：supercomputer_food

e=3 と小さいのとnに比べてcがかなり小さいので、Low public exponent attackを考えます。gmpy2で調べたらcの3乗根が存在したので予想通りです。

import gmpy2
from Crypto.Util.number import *
e = 3
c = (中略)
n = (中略) 
m,ch = gmpy2.iroot(c,e)
print(long_to_bytes(int(m)))


dsc{t0-m355-w1th-m4th-t4k35-4-l0t-0f-sp1n3}



RSA-3

Alright, this is the big leagues. You have someone's Public Key. This isn't unusual, if you want to send someone an encrypted message, you have to have thier public key. Your job is to evaluate this public key, and obtain the value of the secret exponent or decryption exponent (The value of "d" in an RSA encryption).
Wrap the number that you find with dsc{}!
ファイル：mykey.pub

苦手な公開鍵ファイル形式です。値を得るにはどうしたらいいか調べるのに時間がかかり、やっと見つけました。

$ openssl rsa -noout -text -inform PEM -in mykey.pub -pubin
RSA Public-Key: (2049 bit)
Modulus:
    01:fb:7e:02:ec:6b:a1:1d:b8:4b:1e:eb:3d:a2:a0:
    9f:1d:1e:4d:d9:ee:96:96:75:db:f8:c3:f9:a8:26:
    d8:f5:f6:e3:a1:69:a0:56:a2:93:46:ef:19:bf:cd:
    4a:8e:39:50:e7:7d:68:73:cc:78:b5:fd:07:e2:4c:
    ae:3e:39:e0:00:8d:14:8d:67:44:70:d9:cd:5b:2e:
    c4:ae:72:73:77:05:bc:8c:6a:d9:4a:98:fb:05:97:
    bd:7a:83:dd:a3:79:75:ea:59:d3:0d:00:b1:4e:79:
    bf:d5:81:7e:72:b0:35:12:4e:f0:21:01:b9:4b:47:
    e0:b9:31:9e:6e:2c:0b:5f:bf:6a:54:57:02:46:f0:
    9c:71:24:0a:86:2b:89:89:98:ca:d0:c3:ab:59:89:
    67:9b:c3:b9:d7:cb:70:d1:95:2e:68:58:60:b4:56:
    81:27:24:c8:d3:86:8d:e6:84:d9:17:78:32:b8:f0:
    d9:f0:c0:93:a7:bc:18:a0:9e:02:bd:c3:8d:95:4a:
    68:6c:0a:92:67:5f:d5:22:a0:f1:95:83:36:62:8e:
    a1:d7:4d:70:1b:35:bf:8e:e7:2c:83:ef:0d:a7:e5:
    7e:e2:f1:d7:69:22:e9:cf:a0:ce:84:0e:d3:64:80:
    28:cf:32:fe:e0:8e:52:7c:bd:25:cf:37:d7:49:00:
    7c:09
Exponent:
    01:1e:f0:5c:01:b3:6f:f6:fe:c8:fd:98:9e:68:a8:
    d9:c4:47:25:23:90:17:8c:0f:e2:81:07:16:e2:cc:
    fb:b8:73:f2:b7:4f:f9:69:7e:53:18:49:2b:7d:13:
    ac:f6:b7:a7:23:0e:c9:4e:45:de:a3:db:80:ae:e6:
    c4:21:ca:78:ee:0e:37:e3:a7:60:e6:2d:2d:9b:16:
    d4:cc:5f:cf:cf:3d:c9:24:6a:b2:82:68:5b:56:72:
    25:30:ff:77:23:09:b6:55:43:8c:b9:34:9f:7c:ad:
    35:35:d9:b2:ca:c0:bb:c7:2d:0e:b9:d1:db:f8:6b:
    73:52:fe:34:1f:6a:dc:4d:ee:95:a8:fb:95:d2:95:
    58:e6:a8:af:9e:33:de:04:a9:79:4d:5b:31:af:06:
    f2:55:77:63:fb:58:63:87:6a:70:73:67:d4:65:8d:
    4b:65:40:21:c9:ba:f1:2b:ff:5d:d8:b7:19:7a:27:
    54:2b:c2:16:57:dd:b3:80:4f:c0:61:b3:43:b1:bc:
    2b:b8:b4:7d:d6:23:bd:0d:31:07:f7:dc:f4:38:88:
    cc:8f:fc:67:22:46:3f:91:bf:23:e6:50:9d:20:84:
    ec:53:c5:71:01:dc:e4:c7:4e:48:21:ae:78:b7:aa:
    36:fb:6b:d7:29:87:d0:81:2c:23:79:74:41:cb:08:
    20:95

eが大きいので、Wiener's Attackです。問題文より、秘密鍵の値がflagになるようです。


dsc{63933136978362426184143019464489956595164295762618713567671020 219205380524818295685880471894474718733401405378107694338783830291 64089236876209147584435733}



The Conspiracy

There was once a sailor who travelled to many countries. He was a quirky old man. He said many many things, and most of what he said never made sense to anyone. He considered himself ahead of his time, and said that the people of his time were unworthy of his wisdom. Soon he was lost to the ages, but his diary wasn't. Are you worthy of decoding his wisdom?
ファイル：diary.txt

diary.txtの中身はいかにもbase64です。復号するとこのようになりました。

dsc{(-18.05572729282756, 178.45700143131674),(19.028282857505392, 103.14426071207107),(42.536705991266146, 1.4930344612276933),(38.5893697217354, 68.81632523058967),_,(50.851518948206795, 4.360180853581986),(7.671863538453386, 36.83726095698952),_,(38.619506740587035, 34.85512642711004),(47.42806157123545, 18.998421101903602),(30.19387158353921, 31.12496611612573),_,(-0.23177559426111558, -78.5033963083949),(-12.85446936733455, 132.79262433883298),(44.424231252577435, 24.350241166279226),(24.8195647413923, 120.97236754005058),(18.584456974403487, -72.31812189614772)}

座標の形をしているので、google mapで調べます。Fiji, Laos, Andorra, ... と続くので座標が示す国名の頭文字を繋げるとflagになりそうです。次はGかと思ったら、Tajikistanでびっくりしましたが…。

あとは、小文字指定を教えてほしかった。


dcs{flat_be_the_earth}



Code Decode

Around 5 years ago, I made this killer program that encodes the string into a cyphertext. The unique feature of this program is that for the same exact plaintext, it generates a different cyphertext every time you run the program. Yesterday I was nosing around in some old stuff and found an encrypted message!
2njlgkma2bv1i0v}22lv19vuo19va2bvl2{-5x
Sadly I realized the I lost the decryption program. I have the encryption program though. Do you think you can help me out and decrypt this message for me?
ファイル：cypher.txt, encrypter.py, encrypted_text.txt

encrypter.pyのcreate_encryption関数を見ると、平文を別の文字に変えているようです。その対応表はcypher.txtに書かれています。どの対応表を使っているかはキー(?)のようなもので区別され、暗号文の先頭3文字と残りは最後に書かれています。

暗号文より、キーは"2nj-5x"であることが分かります。あとは、対応表通りに元に戻せばOKです。

def create_encryption(character_key):
    charstring = "abcdefghijklmnopqrstuvwxyz1234567890 _+{}-,.:"
    final_encryption = {}
    for i, j in zip(charstring, character_key):
        final_encryption[i] = j
    return final_encryption

dic = {(中略)}

enc = "2njlgkma2bv1i0v}22lv19vuo19va2bvl2{-5x"
for k,v in dic.items():
        #print(k,v)
        if k[:3] == enc[:3]:
                print(k,v)
                final_encryption = create_encryption(v)
                ct = enc[3:-3]
                print(final_encryption)
                for c in ct:
                        for a,b in final_encryption.items():
                                if c == b: print(a,end="")
                print()


dsc{y0u_4r3_g00d_4t_wh4t_y0u_d0}



Stars and Shapes

This might be a difficult question, but I'm sure you can do it with your eyes closed.
ファイル：stars_and_shapes.gif

gifファイルを分解します。IrfanViewやオンラインツールなど使ってください。

GIF画像を分解する方法5選。分解可能なソフトとWebサイトを紹介 | Offers Magazine


f:id:partender810:20211007212114p:plain
分解結果


一枚の画像とflagの1文字が対応してそうです。なんだこの図形が書かれたりなかったり…。問題文を読むと、目を閉じれば解ける…？


点字だ！


下の2つだけが付いている点字は、"_"(アンダースコア)ではなく"-"(ハイフン)であるのに気付くのに時間がかかり、何度もincorrectを出してしまいました。


dsc{d0-y0u-th1nk-h3-s4w-us7132}



Doe, a deer

Mark, a very gifted musician, is suddenly missing after his music class. He is said to have been upset after turning in his assignment. He had worked very hard on it, it was his first original. Here, you can see his work. I'm sure you can find him, he wouldn't have gone far.
ファイル：Doe_a_deer.pdf, tune_700.mp3

この問題は解けませんでした…。


pdfにあるのは、mp3の音源の楽譜でしょう。楽譜が暗号文になる暗号化方式があったような…。

google先生が、solfa cipherだと教えてくれました。

Solfa Cipher Secrets

ただdecoderの使い方が分からずタイムアップ。Solfa Cipher: の欄に <音階><数字> を入れればいいのでしょうが、音階はともかく数字が分からない。数字は何拍子目かに該当するのでしょうが、よくわからない…。



まず、Solfa keyはこのようにします。

f:id:partender810:20211007213408p:plain

次に、音符の形で何拍子目かを特定できます。形によって音を長くする短くするは分かっていたのですが、五線譜のどこに黒丸があるか音階にしか注目していませんでした…。

二分音符は長さ4つ分、四分音符は長さ2つ分、八分音符は長さ1つ分、音符の右に小さい点がある場合は長さ+1です。

f:id:partender810:20211007213859p:plain
左から順に、四分音符、四分音符(点付き)、八分音符、二分音符

このマークは2つ分待て、という意味です。

f:id:partender810:20211007220511p:plain
四分休符というらしい

ここで、音階は日本の「ドレミファソラシ」が「D, R, M, F, S, L, T」になり、数字の部分は1~4の中で何拍子目にその音が始まるかが入ります。

なので、最初は"R1"となり、二分音符なので4つ伸ばすと1→2→3→4→1と1に戻るので、次は"M1"となります。その次は2つ分伸ばすので"F3"となります。これを続けて全ての音符を復号させます。

f:id:partender810:20211007221949p:plain
復号結果

これで出てきた文字をdsc{}で括ればいいのかと思ったら、もう一ひねりありました。

tune_700.mp3をstringsコマンド叩いて見ると、最後の行にgoogle driveのURLが載っているのでアクセスします。そうすると、PDFがダウンロードされますがパスワードがかかっています。solfa cipherでの平文をぶち込むと開くことができ、そこにflagがありました。


dsc{b3tt3r-b3-h0m3-f0r-d1nn3r}



Tamil CTF 2021 crypto writeup

平日開催だったのですが、思わずやってしまいました。前回のCTFのwriteup見たいなとCTFtimeを開いたのが敗因です…。おかげで平日にやるべきことをどんどん後回しにしています。

今回のCTF、最後に時間を延長することになってそのおかげで追加で1問解けたのですが、その後FLAGをtwitterに載せる人がいて強制終了となりました。本当に良くない。



Result


f:id:partender810:20210929124240p:plain
良かったと思う


f:id:partender810:20210929204320p:plain
あと2問は難しすぎる



Writeup


Triple Dimple Easy Squish 200pt

The Author is addicted to reels , find out what he is doing!!
ファイル：chall

challを見ると、ciphertext, key, ivがあります。keyは24バイトでivは8バイトでした。慣れてる方は8バイトのivでピンと来るかもしれません。ピンと来なかった私は、とりあえずAESだろう、keyが読める文字だな、筆者はリールが好きとのことだからivを繰り返して16バイトにするのかな？と色々考えていました。しかし、どのAES暗号のモードを使ってもダメ…。


問題名より、Triple DES に気付けるかどうかの問題でした。DESはIVを8バイトにしがちなのか…。

from Crypto.Cipher import DES3
from Crypto.Util.number import *
f = open("chall")
a = f.readlines()
ct = a[0].split()[-1]
key = a[1].split()[-1]
iv = a[2].split()[-1]
ct = long_to_bytes(int(ct,16))
key = long_to_bytes(int(key,16))
iv = long_to_bytes(int(iv,16))
cipher = DES3.new(key, DES3.MODE_CBC,iv)
print(cipher.decrypt(ct))
print()
cipher = DES3.new(key, DES3.MODE_CFB,iv)
print(cipher.decrypt(ct))
print()
cipher = DES3.new(key, DES3.MODE_OFB,iv)
print(cipher.decrypt(ct))
print()

OFBモードでうまくいきました。


TamilCTF{Triplee_DES_iss_quitee_samee_as_DES_isnt_it???}



PJ-JP 238pt

You know something Pj and Jp are friends and CTF contributers... go ahead
ファイル：pj_jp.txt

いつもvimでファイルを見ているのですが、今回catで見たのでファイルの下の方の文字にすぐ気付けました。

最後にある、"jp", "pj"を2進数に変換すればOKです。8文字毎に空白が2つあることや、8文字毎の先頭が毎回"jp"であることから推測できると思います。"jp"を0, "pj"を1としてASCIIコードとすればOKです。

f = open("pj_jp.txt")
a = f.readlines()
enc = a[-3].split()

for i in range(0,len(enc),8):
    temp = enc[i:i+8]
    val = 0
    val = ""
    for j in range(len(temp)):
        if temp[j] == "pj": val += "1"
        else: val += "0"
    print(chr(int(val,2)),end="")
print()


TamilCTF{wh4t_th3_b!4ry}



AEXOR 293pt

The title itself enough ig?
ファイル：data.txt, enc.py

正直この問題はあまり納得いっていないです。

Triple Dimple Easy Squishと同様、data.txtを見るとciphertext, key, ivがあります。ivが16バイトであることや問題名からAES暗号でしょう。enc.pyでAESであることは分かりますがモードは分かりません。


問題は、encです。encはgetkey関数とgetsubkey関数で取得したバイト列を1バイト毎XORしています。getkey関数で得られたバイト列はkeyとなり、暗号化時に使われています。getsubkeyはそのkeyの部分文字列であろう、だからrep_keyという変数名(repeat)なのだろうと推測。どのバイト列が部分文字列ならうまくいくかすべて検証しましたが、どれもうまくいかず…。


結局、data.txtの最後にあった"okay"がgetsubkey関数で得られた文字列とのこと。Discordで質問したらよくdata.txtを見ろと言われました。元から"okay"には気付いていましたが、まさかこれがという感じです。しかも、別にkeyの部分文字列ではないです。うーん…

from Crypto.Util.number import *
from Crypto.Cipher import AES
ct = "68e934aa25be2c5f1674e101b31c25672400d69f9cf910a9f64071cea79f2de01d01bcf140105e5f7a3db66fffe64694"
enc = "030e150a0b0415110618111c001b0d1c"
iv = "1cb7942bf4ae14947150f9f196f92b2c"
ct = long_to_bytes(int(ct,16))
iv = long_to_bytes(int(iv,16))
ok = "okay"
key = b""
for i in range(0,len(enc),2):
    v = int(enc[i:i+2],16)^ord(ok[(i//2)%4])
    key += long_to_bytes(v)

cipher = AES.new(key,AES.MODE_CBC,iv)
flag = cipher.decrypt(ct)
if b"Tamil" in flag: print("CBC",flag)
cipher = AES.new(key,AES.MODE_CFB,iv)
flag = cipher.decrypt(ct)
if b"Tamil" in flag: print("CFB",flag)
cipher = AES.new(key,AES.MODE_OFB,iv)
flag = cipher.decrypt(ct)
if b"Tamil" in flag: print("OFB",flag)
cipher = AES.new(key,AES.MODE_OPENPGP,iv)
flag = cipher.decrypt(ct)
if b"Tamil" in flag: print("OPENPGP",flag)
cipher = AES.new(key,AES.MODE_EAX,iv)
flag = cipher.decrypt(ct)
if b"Tamil" in flag: print("EAX",flag)
cipher = AES.new(key,AES.MODE_GCM,iv)
flag = cipher.decrypt(ct)
if b"Tamil" in flag: print("GCM",flag)

CBCモードでした。


TamilCTF{AESS+XORR_issss_W3irdd_Combinationn???}



Secret Sharing 294pt

Jo , Pj and Shamir communicating with each other in group, jo ask for a flag, Shamir send's junk of data, did you decrypt this data?
ファイル：file

問題名をググると、「Shamirの秘密分散法」がヒットします。以下のサイトが分かりやすかったです。

Shamir's Secret Sharing Step-By-Step - Qvault


つまり、f(x) = a_n × xn + a_(n-1) × xn-1 + ... + a_1 × x + a_0 mod p という式があり、a_0が秘匿情報、つまりFLAGとなります。f(1) ~ f(5)の値が与えられています。また、required_sharesが2であることから、上記の式のnが2ではないかとエスパーします。


f(x) = a1*x+a0 mod p  (a0 = flag)

f(1) = a1+a0 = shares[0] mod p
f(2) = 2*a1+a0 = shares[1] mod p

よって
a1 = f(2) - f(1) = shares[1] - shares[0] mod p
flag = a0 = f(1) - a1 mod p
import base64
from Crypto.Util.number import *

p = b"AQAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAEp"
p = bytes_to_long(base64.b64decode(p))

rs = 2

shares = [b"MEwx7cz+C01rL8H0Hhz2EIgHjWYXVcL81uITmRha674=",b"YJhj22+ntS1s80CT9b6Y7ayc52baTFGNRpPUyLxtaf8=",b"kOSVyRJRXw1utr8zzWA7ytEyQWedQuAdtkWV+GB/6EA=",b"wTDHtrT7CO1wej3TpQHep/XHm2hgOW6uJfdXKASSZoE=",b"8Xz5pFekss1yPbxzfKOBhRpc9WkjL/0+lakYV6ik5MI="]

#f(1) = a1+a0 mod p
#f(2) = 2*a1+a0    mod p
f1 = bytes_to_long(base64.b64decode(shares[0]))
f2 = bytes_to_long(base64.b64decode(shares[1]))
a1 = (f2-f1)%p
flag = (f1-a1)%p
print(long_to_bytes(flag))


TamilCTF{S3cr3eT_4lg0RitHm}



Break The RSA 296pt

Megan Foxx sent a mssg regarding her age..Did you decrypt message only using public keys?
Note: the flag is seprated by two parts
Name+age enc Second one Rsa
ファイル：message.enc, message.pub

この問題もあまり好みではありませんでした…。


1. 1つ目の暗号

公開鍵が、「BEGING PUBLIC KEY」と少し変です。ちゃんとしたものではないのでしょう。問題文より、どうやらRSA暗号ではないようです。


作問者に聞くと、Meganの年齢が重要だと言っていました。Megan Foxxという人が実在しているとは思わず放置していました。調べてみると35歳でした。なんと、megan35 という符号化処理があるんですね。調べてみると、base64でencodeされた文字列を別の文字に置き換える処理がmegan35のようです。


weird_encodings · GitHub

このソースコードを参考にして自作megan32 decodeプログラムを作りました。decode時にpaddingが合わないと出てきたので最後の文字だけのけると、URLエンコードされた文字列となりASCII文字列にするとこのような文章が得られました。

Congrats You Got it !
n = 667
d = 1027
e = 3
decrypt it


message.encの1行目の整数たちをこの値で復号すると、flagの前半部分が得られました。

import base64
from Crypto.Util.number import *
import urllib.parse

megan35 = b"3GHIJKLMNOPQRSTUb=cdefghijklmnopWXYZ/12+406789VaqrstuvwxyzABCDEF5"
b = b"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/="
dec_dict = dict(zip(megan35, b))

# megan 35 decode
enc = b"bwDVjxOXnMR1RZGjlxe1RZGMlxb1RZG0nHesRHesRceqbgy1RZ31Rub1RZ3wSZm1RJK/OdNqOdSJOdNqRd3sSseqbge1RZ31Rub1RZ3tOdGGjLfZm+1qnHesRL1u="
dec = b""
for e in enc:
    v = dec_dict[e]
    dec += long_to_bytes(v)
msg = base64.b64decode(dec[:-1])
print(urllib.parse.unquote(msg.decode()))


# decode RSA

n = 667
d = 1027
e = 3

ct = [408,217,382,380,416,613,408,162,604,9,537,146,280]
for c in ct:
    m = pow(c,d,n)
    print(chr(m),end="")
print()



TamilCTF{y0u_


2. 2つ目の暗号

DownUnder CTFでもあったPKCS#1方式のRSAです。モジュール使って公開鍵を見てみると、nの値がそこまで大きくなかったのでfactorDBに入れると素因数分解できました。復号したのですが、なんか変な文字列に…。

b'\x02\x90\xa9\x14\x93l\xe2\x9f\x8a?-\xa1\xf4\x01b\xbbD\xa8\x00br34k3d}\n'

後ろの方にギリギリ読めそうな文字列がありました。いつかのCTFで復号したらこれと似た文字列が出てきたことがありました。その時は、m1, m2が得られてm2をlong_to_bytesするとこのように後ろの方に読める文字列があり、答えはlong_to_bytes(m1+m2)でした。

今回もこんな感じになるのだろうと思っていたのですが、1つ目の暗号は綺麗にもう出ています。これからどうするんだと悩んでいたら、作問者からそのまま読めるとこ引っ付ければいいよと言われます。


公式writeupではopensslでやると綺麗になるそうですが、なんかもやっとしています。

from Crypto.Cipher import PKCS1_OAEP
from Crypto.PublicKey import RSA
from Crypto.Util.number import *
import base64
b2 = b"MDgwDQYJKoZIhvcNAQEBBQADJwAwJAIdDVZLl4+dIzUElY7ti3RDcyge0UGLKfHs+oCT2M8CAwEAAQ=="
v2 = base64.b64decode(b2)
cipher = RSA.importKey(v2)
print(cipher)
# RsaKey(n=359567260516027240236814314071842368703501656647819140843316303878351, e=65537)

# nを素因数分解すると、p,q= 17963604736595708916714953362445519,20016431322579245244930631426505729
p,q= 17963604736595708916714953362445519,20016431322579245244930631426505729
n = 359567260516027240236814314071842368703501656647819140843316303878351
assert n == p*q
e = 65537
ct2 = b"C1qKLBtrUwLkebPf+JKX6ie1bKEdUGmzkYwBJWQ="
ct2 = bytes_to_long(base64.b64decode(ct2))
phi = (p-1)*(q-1)
d = inverse(e,phi)
m = pow(ct2,d,n)
print(long_to_bytes(m))


TamilCTF{y0u_br34k3d}



Code Book of Bases 482pt

Blocks and Blocks of data in Cipher Books
ファイル：cipher, key

keyに書いてあるものが読みにくかったので、fileコマンド叩くと見慣れないものが出てきました。

$ file key
key: ISO-8859 text


これでutf-8に変換できました。

不正なマルチバイト文字ですと表示された時の対処法 - Qiita

$ iconv -f sjis -t utf8 key
ﾓ]tﾗMuﾓ]tﾓ]5ﾓ]uﾗM5ﾓ]uﾓ]4ﾓ]tﾓM5ﾓ]tﾗ]5ﾓ]tﾗM5ﾓ]tﾗ]4ﾓ]tﾓMuﾓ]uﾓ]4ﾓ]tﾓ]tﾓMuﾓMtﾓMuﾓM4ﾓMuﾓMtﾓMuﾓM5ﾓMtﾓM5


バイナリデータとして読み込んでみると、なんとなく周期がありそうで、5バイト毎のようです。

b'\xef\xbe\x93]t'
b'\xef\xbe\x97Mu'
b'\xef\xbe\x93]t'
b'\xef\xbe\x93]5'
b'\xef\xbe\x93]u'
(以下略)


2進数で見てみましょう。

1110111110111110100100110101110101110100
1110111110111110100101110100110101110101
1110111110111110100100110101110101110100
1110111110111110100100110101110100110101
1110111110111110100100110101110101110101
(以下略)


21, 27, 33, 37bit目以外は毎回同じです。ここの部分だけ抜き取ってみると、ASCIIコードのようです。ここのエスパー要素ちょっと強め？

b'keytamilctf2021!'


どうやらkeyが得られたようです。問題名よりブロック暗号のようなので、IVの要らないAESのECBモードでcipherにあった暗号文らしきbase64encodeを復号してみたら、FLAGになりました。


TamilCTF{bL0ckS_ar3_Br34kabL3!!}



Bases 485pt

Its going to complex as usual, but if you know random bases very well it wouldn't be. Play with them
ファイル：cipher.txt

時間延長のおかげで解けた問題です。作問者にめっちゃDM送りました。

どうやら65536がヒントだぞと教えてもらったのですが、問題名より65536進数にするのかと思いやってみるがうまくいかず…。

結局、base65536 → base91 → base62 → base32 → base85とdecodeすればFLAGになりました。base65536は初耳です。情弱には難しいです…。


復号ツールはこちらです。
base65536 : Base65536 Decoding Tool Online Free
base91 : Base91 Encoding - Base 91 Online Decoder, Encoder, Translator
残り : CyberChef


TamilCTF{B4s3_C1ph3r_4r3_re4lly_c00l!!}



Vai Raja Vai 984pt

Karthick(you) and Panda are friends.. You have a unique power to see the future and panda knows the gambling world . Panda is in debt of 10 lakhs to Rande(a local gangster) as one of his gambling incident went wrong. Use your ability to help panda. As his fate depends on your ability and time.
nc 3.99.48.161 8002
ファイル：vai_raja_rai_client

crypto要素はそれほどなく、reversing問のような気がします。reversingにしてもそれほど難しいわけではなく、コスパがいい問題でした。


Ghidraに与えられたファイルを突っ込んでみると、乱数を生成しておりシードはそのプログラムが実行された時のUNIXTIMEです。

順序としては、mod 7の乱数を6回生成し、その合計値を配列に格納すること50回行います。その配列の値を50個すべて当てればFLAGがもらえます。

そのアルゴリズムをそのまんま自分でも作ります。ここでシードは現在のUNIXTIMEから10足した値にします。自分で実行してから10秒後にncすると、シードが同じ値になるので、実行したプログラムでの配列の値をそのまま送ればFLAGがもらえます。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main(void) {
    unsigned int nowtime = (unsigned int) time( NULL );
    srand(nowtime+10);
    int a,b,x;
    a = 0;
    b = 1;
    int val[53];
    while(b < 301) {
        if(b%6 == 0) {
            val[b/6-1] = a;
            a = 0;
            x = rand();
            a += x%7;
        } else {
            x = rand();
            a += x%7;
        }
        b++;
    }
    for(int i=0;i<53;i++) {
        printf("%d %d\n",i,val[i]);
    }
    printf("%u\n",nowtime+10);
}


TamilCTF{Af73r_m4nY_1nt3r3st1ng_tuRn_0f_3v3nts_R4nd3_tri3s_t0_k1ll_k4rth1ck_ but_k4rth1ck_g0t_s4v3d_by_KumAru_uh_K0kki_kumAru_uh}



Problems&solver

GitHub - ksbowler/TamilCTF_2021

DownUnderCTF 2021 writeup

久しぶりに満足する結果となりました！

今回は珍しくcrypto以外もちょこっと解けました。


DownUnderCTF 2021





Result


f:id:partender810:20210926191424p:plain
2000点いきたかった



Writeup


misc


The introduction

Are you ready to start your journey?
nc pwn-2021.duc.tf 31906

ncしてテキトーに名前を打ってしばらくすると、本当にハッカーか？と聞かれ、yesと答えるとflagが手に入ります。


DUCTF{w3lc0m3_70_7h3_duc7f_7hund3rd0m3_h4ck3r}



Discord

How about you visit our help page? You know what they say when you need 'help' discord is there for support :)

request-supportチャンネルにありました。最近のDiscord問題、本当にflagの場所が分からない…。


このチャンネルは、のちにめちゃくちゃ使います。チケットを発行すると、スタッフに質問できるようになります。どうなっているんだろう。


DUCTF{if_you_are_having_challenge_issues_come_here_pls}



General Skills Quiz

QUIZ TIME! Just answer the questions. Pretty easy right?
nc pwn-2021.duc.tf 31905

クイズを解いていくわけですが、30秒以内ということで手作業では間に合いません。

1) 1+1=? : 2
2) 16進数を10進数に : int("xxxx",16)
3) ASCIIコードに : ord(xx)
4) URLをASCIIに : urllib.parse.unquote("")
5) base64 decode : base64.b64decode(b"xxxx")
6) base64 encode : base64.b64encode(b"xxx")
7) rot13 : codecs("","rot-13")
8) rot13 : codecs("","rot-13")
9) 2進数を10進数に : int("xxxx",2)
10) 10進数を2進数に : bin(xx,2) "0b"を付ける
11) 世界一のCTFは？ : "DUCTF"

4), 10) で苦労しました。


DUCTF{you_aced_the_quiz!_have_a_gold_star_champion}



rabbit

Can you find Babushka's missing vodka? It's buried pretty deep, like 1000 steps, deep.
ファイル：flag.txt

中身を見るとバイナリデータのよう。fileコマンドを叩くと

$ file flag.txt
flag.txt: bzip2 compressed data, block size = 900k

となり、拡張子が違うことが分かります。拡張子を".bz2"にして解凍しても、またバイナリデータとなりました。問題文にあるように、約1000回くらい解凍しないといけないようなのでプログラムを書いたのですが、途中でbzip2以外の拡張子も使わないといけないことが分かりました。


調べたところ、「.bz2, .xz, .gz, .zip」の4種類が使われているだろうということで、subprocessモジュールを使って解凍していきます。fileコマンドを叩いて、その結果で拡張子をmvコマンドで変えて、該当コマンドで解凍する流れです。zipファイルの時はややこしいのですが、解凍するとflag.txtと勝手に名前が決まっていますので、そこだけ注意しましょう。

import subprocess as sp

meirei = 0
# 0 : bz2
# 1 : xz
# 2 : gz
# 3 : unzip


for i in range(2000):
    print(i)
    if meirei == 0:
        sp.call(["bzip2","-d","temp.bz2"])
        #proc = sp.run("file temp", shell=True, stdout=sp.PIPE)
    elif meirei == 1:
        sp.call(["xz","-dv","temp.xz"])
    elif meirei == 2:
        sp.call(["gzip","-d","temp.gz"])
    elif meirei == 3:
        sp.call(["unzip","temp.zip"])
        sp.call(["mv","flag.txt","temp"])
        
    proc = sp.run("file temp", shell=True, stdout=sp.PIPE)
    if b"bzip2" in proc.stdout:
        sp.call(["mv","temp","temp.bz2"])
        meirei = 0
    elif b"XZ" in proc.stdout:
        sp.call(["mv","temp","temp.xz"])
        meirei = 1
    elif b"gzip" in proc.stdout:
        sp.call(["mv","temp","temp.gz"])
        meirei = 2
    elif b"Zip" in proc.stdout:
        sp.call(["mv","temp","temp.zip"])
        meirei = 3
    else:
        break


DUCTF{babushkas_v0dka_was_h3r3}




web


Cowboy World

I heard this is the coolest site for cowboys and can you find a way in?
https://web-cowboy-world-54f063db.chal-2021.duc.tf
Hint : https://www.youtube.com/watch?v=fn3KWM1kuAw

指定されたサイトに行くと、SQL injectionのようなログイン画面が出てきます。しかしusernameが分からない…。adminではないよう。

ヒントからrobots.txtだと推測。

# pls no look

User-Agent: regular_cowboys
Disallow: /sad.eml

URLの後ろに/sad.emlを付けると、emailをDLしました。

MIME-Version: 1.0
Date: Sun, 18 Jul 2021 20:48:32 +1000
Message-ID: <CAOXXCfPcb9Odey1va2xW=paWmwgrQoYFu9ayBUznwLr-FuD9Gw@mail.gmail.com>
Subject: :'(
From: DownUnder CTF <contact.downunderctf@gmail.com>
To: sadcowboys@everyone.com
Content-Type: multipart/alternative; boundary="0000000000000f998405c7639019"

--0000000000000f998405c7639019
Content-Type: text/plain; charset="UTF-8"

Everyone says 'yeee hawwwww'

but never 'hawwwww yeee'

:'(

thats why a 'sadcowboy' is only allowed to go into our website

--0000000000000f998405c7639019
Content-Type: text/html; charset="UTF-8"

<div dir="ltr">Everyone says &#39;yeee hawwwww&#39;<br><br>but never &#39;hawwwww yeee&#39;<br><br>:&#39;(<br><br>thats why a &#39;sadcowboy&#39; is only allowed to go into our website<br></div>

後ろの方に、「'sadcowboy'じゃないとウェブサイトに入れない」とあるので、usernameを'sadcowboy'にすれば良さそう。

password = ' OR 1=1 -- でログインできました。


DUCTF{haww_yeeee_downunderctf?}




reversing


nostring

This binary contains a free flag. No strings attached, seriously!
ファイル：nostrings

ghidraなどで解析すると、入力された文字列がflagの部分文字列かつ"D"から始まっているとcorrectと出ます。

Pythonからシェルコマンドを実行！subprocessでサブプロセスを実行する方法まとめ | DevelopersIO

このサイトで実行ファイルに引数を渡して、結果を得ます。

import subprocess as sp
import string
cmd = "./nostrings"
inp = b""

while True:
    for c in range(30,128):
    #print(c)
        v = chr(c)
        res = sp.run(cmd,shell=True,input=inp+v.encode()+b"\n",stdout = sp.PIPE)
        if b"correct" in res.stdout:
            print(v)
            #x = input("OK?> ")
            #if x == "n": continue
            inp += v.encode()
            print(inp)
            break


DUCTF{stringent_strings_string}




crypto


Substitution Cipher I

Just a simple substitution cipher to get started...
ファイル：substitution-cipher-i.sage, output.txt

flagの一文字ずつをordした値をxとすると、f = 13x2 + 3x + 7を計算し、chr(f)した値がoutput.txtに書かれます。

xを30から128くらいでbrute forceしてfを計算し、output.txtの文字をordした値と合致するか確認しflagを復元します。

msg = "REDACTED"
flag = ""
for c in msg:
    x = ord(c)
    for i in range(128):
        if x == 13*i*i+3*i+7:
            flag += chr(i)
            break
print(flag)


DUCTF{sh0uld'v3_us3d_r0t_13}



Substitution Cipher II

That's an interesting looking substitution cipher...
ファイル：substitution-cipher-ii.sage, output.txt

Iとは違い、数式fが分かりません。CHARSETが47文字なので、その中で計算が行われています。

「f = P.random_element(6)」はランダムに係数を決める6次式をfに格納します。6次式なので係数が7個必要です。brute forceするには477 = 1012 なので厳しいです。

ここで、mod 47での行列演算で係数を求めます。最初の6文字と最後の文字は"DUCTF{", "}"と分かっています。CHARSETでのindexはそれぞれ0~6なので、これらがfで計算されると[1,20,35,33,42,14,41]となることが分かります。

A = 7×7の正方行列。A_ij : pow(i,j,47)が格納。x^j 
B = 長さ7のvector。[1,20,35,33,42,14,41]
C = 係数
A×C = B
C = A_inv×B
n = 47
P.<x> = PolynomialRing(GF(n))

A = matrix(P, [[0, 0, 0, 0, 0, 0, 1],[1, 1, 1, 1, 1, 1, 1],[17, 32, 16, 8, 4, 2, 1],[24, 8, 34, 27, 9, 3, 1],[7, 37, 21, 17, 16, 4, 1],[21, 23, 14, 31, 25, 5, 1],[32, 21, 27, 28, 36, 6, 1]])
B = vector(P,[1,20,35,33,42,14,41])
Ainv = A.inverse()
print(Ainv*B) #[41, 15, 40, 9, 28, 27, 1]

from string import ascii_lowercase, digits
CHARSET = "DUCTF{}_!?'" + ascii_lowercase + digits
n = len(CHARSET)

x = [41, 15, 40, 9, 28, 27, 1]

def calc(val):
    ret = 0
    for i in range(7):
        ret += x[i]*pow(val,6-i)
    return ret%47

enc = "Ujyw5dnFofaou0au3nx3Cn84"
part_flag = "DUCTF{"
ct = ""
for p in part_flag:
    ct += CHARSET[calc(CHARSET.index(p))]
print(ct,enc[:6])

for i in range(len(enc)):
    candi = ""
    for c in CHARSET:
        if enc[i] == CHARSET[calc(CHARSET.index(c))]: candi += c
    print(i,candi,len(candi))

candiが複数になることもあり、長さが2,3のが一つずつありました。計6種類のflagが出てきたので全て提出してみたところ、一つだけ通りました。


DUCTF{go0d_0l'_l4gr4ng3}



Break Me!

AES encryption challenge.
nc pwn-2021.duc.tf 31914
ファイル：aes-ecb.py

flag + 任意のメッセージ + key が暗号化されます。ECBモードの同じ平文ブロックは同じ暗号文ブロックになるという脆弱性を利用します。任意のメッセージを調整して求めたい平文を特定するのですが、この形ではflagを直接求めることはできません。なので、keyを求めます。


任意のメッセージの長さを変えていくと、16文字にしたら暗号文の長さが変わったので、key長は16の倍数であることを踏まえるとflag長も16の倍数であることが分かります。そこから任意のメッセージを調整していって、keyを1バイトごと求めます。

任意のメッセージ = "0"×15+[1バイトbrute force]+"0"×15 とすると、"0"×15+[1バイトbrute force]がiブロック目になり、"0"×15+[keyの先頭1バイト]がその次のブロックになります。i, i+1ブロックが合致した時、keyの先頭1バイトが分かります。2バイト目以降は"0"の個数を減らして求めます。

kt = b''
for i in range(10,16):
    print("i =",i)
    for x in range(30,128):
        if x%10 == 0: print(x)
        read_until(f)
        sen = kt + long_to_bytes(x)
        #print(x,sen)
        sen = b"0"*(16-len(sen)) + sen + b"0"*(16-len(sen))
        if x == 130:
            print(sen)
        s.send(sen+b"\n")
        enc1 = read_until(f).strip()
        #print(x,enc1)
        try:
            enc = base64.b64decode(enc1.encode())
        except:
            print(enc1)
        
        e1 = enc[-48:-32]
        e2 = enc[-32:-16]
        #print(e1,e2)
        if e1 == e2:
            for j in range(0,len(enc),16):
                print(enc[j:j+16]," ",end="")
            print()
            print(f"Find! {i}th key chara")
            kt += long_to_bytes(x)
            print(kt)
            print(sen)
            break
read_until(f)
s.send(b"test\n")
enc = read_until(f).strip()
enc = base64.b64decode(enc.encode())
key = kt
cipher = AES.new(key, AES.MODE_ECB)
flag = cipher.decrypt(enc)
print(flag)


DUCTF{ECB_M0DE_K3YP4D_D474_L34k}



treasure

You and two friends have spent the past year playing an ARG that promises valuable treasures to the first team to find three secret shares scattered around the world. At long last, you have found all three and are ready to combine the shares to figure out where the treasure is. Of course, being the greedy individual you are, you plan to use your cryptography skills to deceive your friends into thinking that the treasure is in the middle of no where...
nc pwn-2021.duc.tf 31901
ファイル：treasure.py

FAKE_COORDSをlong_to_bytesすると、b'-31.95187912224053, 115.85957308693384' となります。この座標の形になっていれば関数is_coordsでFalseが返ることはありません。


この問題は2回ncする必要があります。1回目ではREAL_COORDSを求めます。

もらったshares[0]の値をそのままrun_combinerに送ると、返り値はsecret = REAL_COORDSとなります。

s1 = r1r2s mod p , s = RC
s2 = r1r1r2s mod p
s3 = r1r2r2s mod p

secret = s1^3 / s2s3 = s mod p

しかしshare[0]をそのまま送ると、仲間に宝物の座標がばれてしまうのでダメなようです。ゆえにもう一度ncします。


二回目の接続では、treasure.pyの45行目のif文を通るようshare[0]の値に1加えた値を送り座標の形にならないようにします。

次にもう一度run_combiner関数が呼ばれるので、今度はそこで返り値がFAKE_COORDSになるようにyour shareの値を計算します。

s = RC
s1 = share[0]*k = kr1r2s mod p とする
secret = (k^3)*s mod p
secret = FC となってほしいので
FC = (k^3)*RC mod p
FC/RC = k^3 mod p

d = inverse(3,p)
k = pow(FC*inverse(RC,p),d,p)

このように整数kを求め、share[0]と掛けた値をyour shareとします。そうすることで、返り値がFAKE_COORDSとなりflagがもらえました。


DUCTF{m4yb3_th3_r34L_tr34sur3_w4s_th3_fr13nDs_w3_m4d3_al0ng_Th3_W4y.......}



Secuchat

"With end-to-end encryption facilitated by military-grade RSA2048-OAEP and user-generated AES-256-CBC keys, rest assured that Secuchat has your conversations and secrets obscured from prying eyes."
Shame their DB got dumped. See if you can glean anything.
ファイル：secuchat.db

この問題は、先ほどのdiscordでいろいろ聞いて何とか解けました。しかも日本語が少し話せる方だったので、スムーズに色々聞くことができました。

与えられたデータベースの中身はこんな感じです。

sqlite> .schema Conversation
CREATE TABLE Conversation (
        id INTEGER PRIMARY KEY AUTOINCREMENT,
        initiator TEXT,
        peer TEXT,
        initial_parameters INTEGER,
        FOREIGN KEY (initiator) REFERENCES User(username),
        FOREIGN KEY (peer) REFERENCES User(username),
        FOREIGN KEY (initial_parameters) REFERENCES Parameters(id),
        UNIQUE(initiator, peer)
    );

sqlite> .schema Message
CREATE TABLE Message (
        conversation INTEGER,
        timestamp INTEGER,
        from_initiator BOOL,
        next_parameters INTEGER,
        encrypted_message BLOB,
        FOREIGN KEY (conversation) REFERENCES Conversation(id),
        FOREIGN KEY (next_parameters) REFERENCES Parameters(id)
    );

sqlite> .schema Parameters
CREATE TABLE Parameters (
        id INTEGER PRIMARY KEY AUTOINCREMENT,
        encrypted_aes_key_for_initiator BLOB,
        encrypted_aes_key_for_peer BLOB,
        iv BLOB
    );

sqlite> .schema User
CREATE TABLE User (
        username TEXT PRIMARY KEY,
        rsa_key BLOB
    );

Conversationテーブルでは誰と誰が会話するのか、Messageテーブルは実際の通信内容、ParametersではAES暗号についての情報、Userはrsaの鍵が入っています。


1. rsa_keyを取得

AESのkeyは暗号化されているようなので、まずはrsaの方を見ていきます。RSA2048-OAEPでピンときた方は問題ないですが、そうでなかった私はrsa_keyに入っているバイナリデータの意味が全然分かりませんでした。

RSA公開鍵のファイル形式とfingerprint - Qiita

このサイトで、PKCS#1方式ではないか？と予想がつきました。

from Crypto.PublicKey import RSA
keyPub = RSA.importKey(dat)
e = keyPub.e
n = keyPub.n

これで取得できます。


2. 素因数分解できるか確認

rsa_keyはUserテーブルにたくさんあります。どれもnは2048ビットなのでそのまま素因数分解はできないとは思ったのですが、共通素数があるのでは？とエスパー。全ペアを確認したところ唯一共通素数を使っているペアがいました。hortonashleyとeriksaundersでした。


3. encrypted_aes_key_for_xxx とは

AES-256-CBCを使ったと問題文にあります。encrypted_aes_key_for_xxx (initiator, peer どちらも)を見ると256バイトでした。AES-256-CBCは256ビットのキーを使うので、何かしらの暗号化により256バイトになったと考えます。ここでRSAと組み合わせていることを考えると、AESのキーをRSAで暗号化したのでは？と推測できます。

  1. で素因数分解できたので秘密鍵が二つ手に入ります。encrypted_aes_key_for_xxxをすべて復号してみて32バイトになるのを探していきます。

ここで一つ問題があって、RSA2048-OAEPで暗号化しているので普段と同じように復号しても上手くいきません。モジュールを使います。

key_h = RSA.construct((p*q,65537,d1,p,q))
cipher1 = PKCS1_OAEP.new(key_h)
msg1 = cipher1.decrypt(para[1])


4. encrypted_message とは

Messageテーブルにあるencrypted_messageは暗号化される前のAESキーを使ってCBCモードで暗号化した文だと考えます。

  1. で復号して32バイトになったキーで、全てのencrypted_messageを復号します。ivはParametersにあるものをそのまま使います。

その中で唯一、"DUCTF"が含まれる平文がありました。


DUCTF{pr1m1t1v35, p4dd1ng, m0d35- wait, 3n7r0py?!}



m1z0r3 Crypro CTF 2021 解説

今回、かなりエスパー要素強かったと思います。来年はできるだけ抑えようと頑張ります。

問題はこちらから：m1z0r3 Crypro CTF 2021 問題＆ヒント - Attack All Around

解説やsolverはこちらから：m1z0r3CryproCTF_2021/Answer at master · ksbowler/m1z0r3CryproCTF_2021 · GitHub

以降では、裏話やこの問題を採用した経緯などを話していきます。



Solve Me 100pt

サマーウォーズを初めて見た時は暗号の「あ」の字すら知らなかったのですが、QuizKnockのYouTubeを見つけてRSA暗号だったのか！と作問に至りました。


www.youtube.com


eでsplitして暗号文cと公開鍵nになるのは初見じゃきつかったと思うので、もっとここに行きつきやすいような配慮をすべきだったなと反省しています。



第一段階は個人的には綺麗な問題だと思っているのですが、既出だったらすいません(笑)

email.txtは実際にサマーウォーズで出たものに近付けたかったので2056文字に合わせた結果、pow関数の計算に数分かかってしまうくらいの値になってしまいました…。ただ、実際のもののnをfactorDBに入れると3で割れてしまい、ちゃんとしているわけではなさそうでした。メルセンヌ素数を使ったのも、「nだけで素因数分解できるためには」と考えたときにこのくらいしか思いつきませんでした。


少しばかり意地悪になってしまいました…



Qualified class 50pt

小学生の頃見てたドラマ「探偵学園Q」が面白くて、漫画まで買いました。ドラマ版ではなかったのですが、ピッグペンに似た暗号があったので、ほとんどそのまま流用しました。

順番変えたのではなく、記憶違いで変わってしまいました…。



I'm lovin' it 50pt

オリンピックで国の名前をアルファベット3文字で表すのをよく見たのですが、これって問題になるんじゃね？となりました。暗号問題というよりは謎解きに近いですね(笑)

ただ似たようなコードがあったのはサーベイ不足です…



Too hints 150pt

picoCTF 2021 で出た問題で、dp = d mod p-1 を求められたら素因数分解できるというのに気付いた時が本当に嬉しかったのでいつか出そうとあっためてました。

ただ、簡単にdp, dqが分かるとつまらないなと思いもう一つ数学的要素を増やしました。それなりに良い難易度になったのかなと思ってます。


今年のm1z0r3 CTF用に残すつもりだったので、そちらをどうしようかと思案しているところです…。



Mystery House 150pt

zh3r0 CTF b00tlegをモチーフにしました。最後まで行ってもflagは出ず、もう一ひねり必要としました。これも最後は暗号というよりは謎解きですね。

今回チーム戦なので、各階の暗号についてはチームであーだこーだ言ってもらって進んでいけばいい感じになるかなと想定していたのですが、まさかの担当別で解いていたみたいで思惑から外れてました(笑)

それにしても毎回Hastad's broadcast attack使っている気がする。



終わりに

年末にm1z0r3 CTFも開催するので、またその時に作問します。是非解いてください！

今回の問題の感想なども教えてくれると嬉しいです！！

m1z0r3 Crypro CTF 2021 問題＆ヒント

我がm1z0r3では暗号問題(Crypto)とプログラミング問題(Programming)担当を同じ班にしております。

今年は初の試みとなるm1z0r3 Crypro CTFを開催しました！！

問題とこの記事の後ろの方にヒントを載せています。是非感想などを言っていただけると大変励みになります！お願いします！！



Challenge


今回かなりエスパー要素強めです…

github : GitHub - ksbowler/m1z0r3CryproCTF_2021


Solve Me 100pt

Kenji has got a cipher message, and Kazuma encrypted it because Kenji likes cryptography. Kazuma said that something is longer than usual, and Kenji said that Kazuma's method is a little like email encryption, but even more vulnerable. But I don't understand what they said.
ファイル：chal.txt problem.py



Qualified class 50pt

I made a new cipher! I built it based on a really famous language.
The flag are made up of lowercase letters and underscore only.
ファイル：problem.pdf



I'm lovin' it 50pt

I love 26 very much!
The flag are made up of lowercase letters only.
Submit the flag after wrapping m1z0r3{}.
ファイル：challenge.txt



Too hints 150pt

Did I give you many hints?
ファイル：problem.py, chal.txt



Mystery House 150pt

Missing is Important! You should Escape!
nc xxx.xxx.xxx.xxx yyyyy
※この問題は本番ではサーバプログラムは公開しませんが、サーバ立てるの面倒なのでserver.py, my_secrets.pyを渡します。皆さんローカルでこのプログラムをそのまま「python3 server.py」で動かして別の端末で「nc 127.0.0.1 4500」とすれば接続されます。 しかし、このプログラムを見ると問題の難易度がめちゃくちゃ下がるのでできるだけ見ないようにお願いします



Hint


Solve Me

Hint 1

エスパー要素ふんだんの問題です。第一段階は、hintに何かを足せば素因数分解ができます。
そして、とある計算に数分かかります。






Hint2

第一段階で復号された文で終わりではありません。まだ続きます。
この復号文を知らない方はgoogle先生を使ってみてください。






Hint3

第一段階のものは変数hintを与える以外にも脆弱な点がありました。第二段階はその点を半分だけ使っています。






Qualified class

Hint 1

似ている暗号はありますが、全く同じではありません。ただ、多少は似ています。






Hint 2
m=159586143928003353212328091264988384551392290037117
long_to_bytes(m)






I'm lovin' it

Hint1

①：ホームページに今年のものが載っています

②：似ているものが二つあるので両方試してみてください






Hint2

Let's combine! And look up the length! It doesn't need mathematical knowledge!






Too hints

Hint1

まずはd1, d2を求めましょう。数学的な考察が多少が必要です。






Hint2

α = -d2, β = e+d1 が解となる二次方程式を立てれば、解けるはずです。






Hint3

d1,d2 を求められたらp, qが分かります。
がっつり数学的考察が必要です。






Mystery House

Hint1

2Fは引き算ではありません。片方の値はランダムになっており、それによりもう片方が決まっています。






Hint2

3F以降、小さい値と大きい値をいくつか送ってみることが重要です。






Hint3

4F以降、1を何回も選んでみましょう






Hint4

屋上まで来れたら、問題文などを振り返ってみましょう。足りないものが重要…？