　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の方曰く、想定解の目処があるそうなので気になる方は調べてみてください．そしてあわよくば教えて...ください．

ちなみにwriteup書く気力がわかないのでZKPayの話を軽く書くと、
proofの形式はG1が7つとG2が1つ、これは調べるとBCTV14というSNARKで使われるフォーマット
さらにBCTV14をキーに調べるとzcashは今はこの方式を使ってなくてGroth16になってること、脆弱性が2019に公開されたことが出てくる
— narypto (@narypto) October 20, 2019

[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$ を代入すれば求めることができ、 $M$ は $c$ が分かればただの表現行列なので、単位ベクトルを与えると求めることができます．ここで、 $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)$ は正則であるので、計算が可能です．流れとしては、

入力文字に対する $CRC _ s (x)$ の $M, c$ を求める．
$(M^{n} + E)(M + E)^{-1}$ を計算する．
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が流れたので、僕も書く気分になりました．これは賢いですね．