はまやんはまやんはまやん

hamayanhamayan's blog

SECCON 13 CTF FINAL (Domestic) Writeups

Security

Domesticですが、出題される問題はInternationalと同様です。

初めてSECCONの本選に出て、初めてKing of the Hill形式をやりました。全てがそうかは分かりませんが、今回のKing of the Hill形式では時間ごとに区切られて問題が出題されていたので、いつもと趣向を変えて時系列で問題の解説を書いていきます。

1日目: HECCON

前述の通り、SECCONではKing of the Hill形式の問題が出ていた。そのうちの1つがHECCON。テーマは準同型暗号で、暗号したままいくつかの計算ができるライブラリ HElayers 上で問題が作られている。HECCONでは4つのステージが用意されており、各ステージは3時間30分で切り替わり、初日に1と2、2日目に3と4のステージが順番に遊べるようになっている。

各ステージ、1つの問題が出る。どれも問題の形式は同じで、平文が分からない暗号文とその暗号文に対して実行してほしい計算が与えられるので、暗号文を計算して計算後の暗号文を返して、誤差（平均絶対誤差, MAE）が少なければ点数が高いというもの。この問題は全てのチームに同様に展開されていて、各チームは5分毎に1つの回答を送ることができ、それをもとに順位が付き、そして、順位に応じた点数（1位は20点、2位は16点、…）が与えられる。

他にも色々ありますが、主要なポイントを押さえると、以下。

  • 与えられた暗号文に対して与えられた計算して提出し、正解と誤差を小さくせよ
  • 良い順位をキープすることで高い点数をもらい続けることができる

さて、説明はこのくらいにして、問題を見ていこう。

1日目: HECCON Stage 1

11:00にSECCONスタートとともに、Stage 1スタート。

入力：[-3,3]の乱数を要素に持つ、サイズが213のベクトル
計算：各要素についてmax(x, 0.0)を計算する

実際、問題はプログラムコードで与えられる。先ほどの問題を HElayers で実装するとこうなる。

from pathlib import Path

import numpy as np
import pyhelayers


N = 2**13


class Challenge:
    @classmethod
    def generate(cls, pubkey: Path, dist_dir: Path):
        """Generate the challenge data.

        dist_dir is a distributed directory to contestants.

        Args:
            pubkey (Path): Path to the public key file.
            dist_dir (Path): Path to the directory where the challenge data is saved.
        """
        he_context = pyhelayers.SealCkksContext()
        he_context.load_from_file(str(pubkey))
        encoder = pyhelayers.Encoder(he_context)
        x = np.random.uniform(-3, 3, N)
        cx = encoder.encode_encrypt(x)
        cx.save_to_file(str(dist_dir / "enc"))
        (dist_dir / "challenge.py").write_text(Path(__file__).read_text())

    @classmethod
    def evaluate(
        cls, pubkey: Path, privkey: Path, enc: Path, submission: Path
    ) -> float:
        """Evaluate the submission.

        submission is a path to a submitted file and the server evaluate it.
        Contestants are supposed to get better MAE as much as possible.

        Args:
            pubkey (Path): Path to the public key file.
            privkey (Path): Path to the private key file.
            enc (Path): Path to the encrypted data file.
            submission (Path): Path to the submitted file.
        """
        he_context = pyhelayers.SealCkksContext()
        he_context.load_from_file(str(pubkey))
        he_context.load_secret_key_from_file(str(privkey))
        encoder = pyhelayers.Encoder(he_context)

        cx = encoder.encode_encrypt([])
        cx.load_from_file(str(enc))
        x = encoder.decrypt_decode_double(cx)
        cy_sub = encoder.encode_encrypt([])
        cy_sub.load_from_file(str(submission))
        y_sub = encoder.decrypt_decode_double(cy_sub)

        y_true = np.maximum(x, 0.0)
        mae = np.mean(np.abs(y_true - y_sub))  # less is better
        return float(mae)

普通にmax関数を使えばいいのでは？と思うかもしれないが、HElayersではそんなリッチな計算はできない。max関数無しでどうやってこれを実現しようかというのが、難しいポイント。

うーん、うーんと考えていると早々にポイントを取っているチームを発見する。最初は全員スコア無しで同じ順位なので同じ点数がもらえているのだが、しばらくすると点数を得て差をつけているチームが存在していた。

なぜだろうと思ってちょっと考えると、与えられた入力をそのまま提出している可能性に気が付く。どんな答えでもいいので出せばスコアが手に入るため、与えられている暗号文をそのまま提出すると、何も計算しない場合の点数がもらえる。入力された暗号文をそのまま提出して、最初の点数を獲得する。 ＜この時の点数をメモり忘れた＞ 1時間経過くらい経過してたかも。

とりあえず改善する ? → 0.5011

HElayers では和や積は計算できるが、max関数はない。どうやって計算するかをあれこれ考えていると、多項式近似が思い浮かぶ。正確なmax関数は作れないが、max関数と近い近似関数、特に和や積で計算可能な多項式近似を使えば、暗号計算でmax関数に近い計算ができそうだ。

AIに聞いて、多項式近似を答えてもらおう。全部の区間にフィットする必要はないので、[-3,3]に特化してもらおう。

これをなんとなく調整して、

\displaystyle max(x, 0.0) ≈ 0.25 x^2 + 0.5 x + 0.5

と近似して計算してみる。

def num(n, encoder):
    return encoder.encode_encrypt(np.array([n]*N))

def add(a, b, encoder):
    res = encoder.encode_encrypt(np.array([0]*N))
    res.add(a)
    res.add(b)
    return res

def mul_scalar(a, n, encoder):
    res = encoder.encode_encrypt(np.array([1]*N))
    res.multiply_tile(a)
    res.multiply_tile(num(n, encoder))
    return res

def pow(a, n, encoder):
    res = encoder.encode_encrypt(np.array([1]*N))
    for i in range(n):
        res.multiply_tile(a)
    return res

d1 = mul_scalar(pow(cx, 2, encoder), 0.25, encoder)
d2 = mul_scalar(pow(cx, 1, encoder), 0.5, encoder)
cx = add(add(d1, d2, encoder), num(0.5, encoder), encoder)

このようなコードで、0.5011 スコア獲得。（誤差なので小さいほど良い）2時間くらい経過した12:58提出。

パラメタ調整 0.5011 → 0.0902

他のチームでもっと段違いのスコアを出している所がある。何ができるか考えてみたが、特に思いつかず、パラメタ調整をしてみるとかなりスコアが変動した。

0.1 0.1 0.1 0.6001695523125761
0.1 0.1 0.5 0.6458592202784209
0.1 0.1 0.9 0.7623586064979018
0.1 0.5 0.1 0.3581625112388214
0.1 0.5 0.5 0.14937318336580932
0.1 0.5 0.9 0.4485987767065125
0.1 0.9 0.1 0.6037420462496992
0.1 0.9 0.5 0.6471614447482188
0.1 0.9 0.9 0.7584192815779367
0.5 0.1 0.1 0.9544925023066394
0.5 0.1 0.5 1.2474391035024894

0.15 0.5 0.4 0.10500946087176236

0.15 0.5 0.35 0.0896164483875018

色々ガチャってみると、

\displaystyle max(x, 0.0) ≈ 0.15 x^2 + 0.5 x + 0.35

でスコアが跳ねた。ソースコードは前回のやつのパラメタを変えただけ。結果は0.0902。13:53提出。この時点で3時間経過していた。これから30分くらいあれこれやっているとStage 1は終わってしまった。とりあえずは、多項式近似を使えば、割とどんな状況でもやっていけそうということが分かったのと、問題をなんとなく把握はできた。

1日目: HECCON Stage 2

14:30、Stage 1が終了し、次のStageへ。

入力：サイズN×2のランダムな行列をベクトルに変換したものが与えられる。N=212。また、各行はそれぞれランダムに作られた正規分布に従い、[-1,1]の乱数を平均、[0.5, 1.0]の乱数を標準偏差とする。
計算：各行 |a b| について|max(a,b) なんでもいい|を計算する

HElayers のプログラムコードで見る方が分かりやすいかも。

from pathlib import Path

import numpy as np
import pyhelayers


N = 2**12
M = 2**1


class Challenge:
    @classmethod
    def generate(cls, pubkey: Path, dist_dir: Path):
        """Generate the challenge data.

        dist_dir is a distributed directory to contestants.

        Args:
            pubkey (Path): Path to the public key file.
            dist_dir (Path): Path to the directory where the challenge data is saved.
        """
        he_context = pyhelayers.SealCkksContext()
        he_context.load_from_file(str(pubkey))
        encoder = pyhelayers.Encoder(he_context)
        mu = np.random.uniform(-1, 1, (N, 1))
        sigma = np.random.uniform(0.5, 1.0, (N, 1))
        x = np.random.normal(mu, sigma, (N, M))
        x = x.reshape(-1)
        cx = encoder.encode_encrypt(x)
        cx.save_to_file(str(dist_dir / "enc"))
        (dist_dir / "challenge.py").write_text(Path(__file__).read_text())

    @classmethod
    def evaluate(
        cls, pubkey: Path, privkey: Path, enc: Path, submission: Path
    ) -> float:
        """Evaluate the submission.

        submission is a path to a submitted file and the server evaluate it.
        Contestants are supposed to get better MAE as much as possible.

        Args:
            pubkey (Path): Path to the public key file.
            privkey (Path): Path to the private key file.
            enc (Path): Path to the encrypted data file.
            submission (Path): Path to the submitted file.
        """
        he_context = pyhelayers.SealCkksContext()
        he_context.load_from_file(str(pubkey))
        he_context.load_secret_key_from_file(str(privkey))
        encoder = pyhelayers.Encoder(he_context)

        cx = encoder.encode_encrypt([])
        cx.load_from_file(str(enc))
        x = encoder.decrypt_decode_double(cx)
        x = x.reshape(N, M)
        cy_sub = encoder.encode_encrypt([])
        cy_sub.load_from_file(str(submission))
        y_sub = encoder.decrypt_decode_double(cy_sub)
        y_sub = y_sub.reshape(N, M)[:, 0]

        y_true = x.max(axis=1)
        mae = np.mean(np.abs(y_true - y_sub))  # less is better
        return float(mae)

入力はサイズN×2のランダムな行列をベクトルに変換したもので、

\displaystyle \begin{vmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \\ \vdots & \vdots \\ a_{N1} & a_{N2} \end{vmatrix}

これを

\displaystyle \begin{vmatrix} a_{11} \\ a_{12} \\ a_{21} \\ a_{22} \\ \vdots \\ \vdots \\ a_{N1} \\ a_{N2} \end{vmatrix}

のように変換して与えられていることになる。よって、奇数番目と偶数番目のmaxを取って奇数番目に入れればよい。さて、前の教訓を生かして入力値をそのまま回答して点数をつけておこう。＜点数のメモは忘れた＞

多項式近似 ? → 0.1811

さっき手に入れたテク、多項式近似を使おう。max(x,y)を良い感じを計算で求める式がある。

\displaystyle \text{max}(x,y)=\frac{x+y}{2}+\frac{|x-y|}{2}

絶対値がまだ計算できない。これもアレコレ調べて多項式近似をしてみると、

\displaystyle \text{max}(x,y)≈\frac{x+y}{2}+\frac{(x-y)^2}{0.28}

これでいい感じの点数が取れた。計算の仕方は、ベクターのローテーションが使えたので、偶数番目を奇数番目に持ってきて計算した。

\displaystyle x = \begin{vmatrix} a_{11} \\ a_{12} \\ a_{21} \\ a_{22} \\ \vdots \\ \vdots \\ a_{N1} \\ a_{N2} \end{vmatrix}

これを1つローテーションして、

\displaystyle y = \begin{vmatrix} a_{12} \\ a_{21} \\ a_{22} \\ \vdots \\ \vdots \\ a_{N1} \\ a_{N2} \\ a_{11} \end{vmatrix}

とすれば、

\displaystyle x + y = \begin{vmatrix} a_{11} + a_{12} \\ a_{12} + a_{21} \\ a_{21} + a_{22} \\ \vdots \\ \vdots \\ a_{N1} + a_{N2} \\ a_{N2} + a_{11} \\ \end{vmatrix}

のようにできて、奇数番目に和が作れる。あとは、これを利用して残りも計算できるので、以下のように実装してやればよい。

def num(n, encoder):
    return encoder.encode_encrypt(np.array([n]*N))

def copy(a, encoder):
    res = encoder.encode_encrypt(np.array([0]*N*M))
    res.add(a)
    return res

def add(a, b, encoder):
    res = copy(a, encoder)
    res.add(b)
    return res
    
def sub(a, b, encoder):
    res = copy(a, encoder)
    res.sub(b)
    return res

def mul(a, b, encoder):
    res = copy(a, encoder)
    res.multiply_tile(a)
    res.bootstrap()
    return res

def mul_scalar(a, n, encoder):
    res = copy(a, encoder)
    res.multiply_scalar(n)
    return res

def rotate(a, c, encoder):
    res = encoder.encode_encrypt(np.array([0]*N*M))
    res.add(a)
    res.rotate(c)
    return res

def square(a, encoder):
    res = copy(a, encoder)
    res.square()
    return res

# ===============================

x = copy(cx, encoder)
y = rotate(cx, 1, encoder)

ad = add(x, y, encoder)
d1 = mul_scalar(ad, 0.5, encoder)
d2 = mul_scalar(square(sub(x, y, encoder), encoder), 0.27, encoder)
d2 = add(d2, num(0.16, encoder), encoder)
ans = add(d1, d2, encoder)

これで点数 0.1811。16:12提出。

絶対値の近似多項式の最適化 0.1811 → 0.1433

他のチームがかなり良い点数を付けていく中、全然点数が上がらない。近似しているのは絶対値部分だけなので最適化するためにパラメタガチャしていた。（パラメタガチャをしながら、より高次な多項式近似したりしようとしていたが全然うまくいかなかった）（上の実装を見れば分かるがmulがバグってa×bではなくa×aになっていた… Stage3で気づくのだが、多分これが原因）

色々ガチャガチャやって以下のようにした。

\displaystyle \text{max}(x,y)≈\frac{x+y}{2}+\frac{(x-y)^2}{0.27} + 0.16

これで点数 0.1433。17:00提出。実装が一生バグってて全くダメだった。このまま終了。SECCON会場でも一旦中締めとなった。だが、まだこの日は終わってはいなくて、日中はずっとHECCONをやっていた関係で、これからJeopardy問題を進めていくことになる。やばすぎる…

1日目夜: [crypto] RSA+

ソースコードは簡潔。

import os
import signal
from secrets import randbelow

from Crypto.Util.number import isPrime

flag = os.getenv("FLAG", "SECCON{this_is_not_a_flag}")


if __name__ == "__main__":
    signal.alarm(120)

    p = int(input("Your favorite prime p (hex) > "), 16)
    if not isPrime(p) and p.bit_length() >= 512:
        print("p must be a prime")
        exit()
    q = int(input("Your favorite prime q (hex) > "), 16)
    if not isPrime(q) and q.bit_length() >= 512:
        print("q must be a prime")
        exit()
    n = p * q

    g = n // 2
    h = n // 3
    x = randbelow(2**512)
    r = (pow(x, g, n) + pow(x, h, n)) % n
    print(f"{r = }")

    guess_x = int(input("Guess x > "))
    if x == guess_x:
        print(flag)
    else:
        print("Wrong...")

色々方針を考えてみると、足し算が非常に不便。

\displaystyle r = x^g + x^h \bmod n

足し算を何とかまとめたいな…ということを考えて g=h とできないか考える。普通にg=hとはできないので、オイラーの定理より

\displaystyle g = h \bmod \varphi(n)

が成り立つように調整していく。それにより

\displaystyle \begin{align} r &= x^g + x^h \bmod n \\ &= 2x^g \bmod n \\ \frac{r}{2} &= x^g \bmod n \end{align}

となり、mod n上でg乗根を取ればxが復元できる。これを計算しようと考えたがうまくいかず、mod nではなくmod pで考えることにした。mod nをmod pにしてもほとんど同じ計算で考えることができ、

\displaystyle g = h \bmod \varphi(p)

を満たすp,qを求めることができれば、先ほどの式を使ってxを求めることができる。g = h mod p-1を起点にして式変形していくと、pとqの間の条件を作ることができる。

\displaystyle \begin{align} g &= h \bmod p-1 \\ \frac{pq - 0or1}{2} &= \frac{pq - 0or1or2}{3} \bmod p-1 \\ 3pq + 0or3 &= 2pq + 0or2or4 \bmod p-1 \\ pq &= -4or-2or-1or0or1or3 \bmod p-1 \\ (p-1)q + q &= -4or-2or-1or0or1or3 \bmod p-1 \\ q &= -4or-2or-1or0or1or3 \bmod p-1 \\ q &= k(p-1) + -4or-2or-1or0or1or3 \end{align}

qは素数であり、k(p-1)はpが素数であることから偶数になるため、-4or-2or-1or0or1or3の候補のうち、奇数のみ可能性がある。

\displaystyle q = k(p-1) + -1or1or3

この式を使って素数pを適当に選び、そこからkと-1or1or3を雑に探索してqが素数になるもの、また、g = h mod (p-1)になるものを探す。探索スクリプトは以下。

from Crypto.Util.number import isPrime
from Crypto.Util.number import getPrime

for _ in range(1000):
    p = getPrime(512)
    for k in range(2, 100):
        for d in [1, 3, -1]:
            q = k * (p-1) + d
            if isPrime(q):
                g = p * q // 2
                h = p * q // 3
                if g % (p-1) == q % (p-1):
                    print("p =", hex(p)[2:])
                    print("q =", hex(q)[2:])
                    exit(0)

#p = daeb6fa97ec281f2b856946d6100457c2d777bb7de2c4999320d67e6c6f90cbaeadca2caecf59849ec14ce426c48797df572664acbe2fbbd370828e0a86a4baf
#q = 3e6d22d75525770e3690b05330a913d068f712476e5aa0fcaf45d2a0cebd04a14cf8ea6bdd92086d1451eed0f0e0aaa4eafd9f2b5423b9c8f4b153a810064f949d

これでp,qが分かればそれを使ってフラグを手に入れられる。以下が最終的なソルバ。

from ptrlib import *

sock = Process("python3 server.py", shell=True)

p = 0xdaeb6fa97ec281f2b856946d6100457c2d777bb7de2c4999320d67e6c6f90cbaeadca2caecf59849ec14ce426c48797df572664acbe2fbbd370828e0a86a4baf
q = 0x3e6d22d75525770e3690b05330a913d068f712476e5aa0fcaf45d2a0cebd04a14cf8ea6bdd92086d1451eed0f0e0aaa4eafd9f2b5423b9c8f4b153a810064f949d

sock.sendlineafter("Your favorite prime p (hex) > ", hex(p)[2:])
sock.sendlineafter("Your favorite prime q (hex) > ", hex(q)[2:])
r = int(sock.recvlineafter("r = "))

g = p * q // 2
h = p * q // 3

jou = g % (p-1)
# r = 2*x^jou mod p
# r/2 = x^jou mod p

r2 = r * pow(2, -1, p) % p

x = GF(p)(r2).nth_root(jou)

sock.sendlineafter("Guess x > ", str(x))
sock.interactive()

1日目夜: [web] purexss - 1st challenge

入力を出力するwebsiteが与えられる。

fastify()
  .get("/", async (req, reply) => {
    try {
      const html = sanitize(validate(req.query.html ?? defaultHtml));
      reply.type("text/html").send(html);
    } catch (err) {
      reply.type("text/plain").code(400).send(err);
    }
  })
  .listen({ port: 3000, host: "0.0.0.0" });

req.query.htmlでhtmlタグを入力させ、それをvalidateしてsanitizeしてそのまま出力している。まず、validateは

const validate = (html) => {
  if (typeof html !== "string") throw "Invalid type";
  if (html.length > 1024) throw "Too long";

  // Do not use ISO-2022-JP
  // ref. https://www.sonarsource.com/blog/encoding-differentials-why-charset-matters/
  if (html.includes("\x1b")) throw "Invalid character";

  return html;
};

のように、stringチェックをして、サイズをチェックして、その後、\x1bが存在していないかをチェックしている。これは、ソースコードにあるリンクを見てもらうのが良いが、ISO-2022-JPにおいてエスケープシーケンスによってエンコード方式が変わることを利用したテクを防止するための検証である。このテクはContent-Typeでcharsetが指定されていないなど、charsetの指定がどこにもなく、ブラウザ側でエンコードをsniffingしなくてはいけない状況が必要だが、呼び出し元のコードにreply.type("text/html").send(html);という感じでcharset指定がないことから対策がなされている。

次はsanitizeだが、

const sanitize = (html) => {
  const DOMPurify = createDOMPurify(new JSDOM("").window);
  DOMPurify.addHook("afterSanitizeAttributes", (node) => {
    for (const { value } of node.attributes) {
      if (/[^\w</>]/.test(value)) throw "Invalid attribute value";
    }
  });

  return DOMPurify.sanitize(html, { WHOLE_DOCUMENT: true });
};

のようにDOMPurifyに通して、出力している。このとき、addHookにてsanitize後にattributeの値が/[\w</>]/であることを検証している。つまり、attributeの値は、英数字か</>しか使うことができない。

Do not use ISO-2022-JPとあるがエンコーディングのsniffingが実行される状況ではあるので、ISO-2022-JPに変わる素敵なエンコーディング方式がもしかしたらあるのではないかと思い、エンコーディング方式をひたすら検索して実験していたが、使えそうな方式は見当たらない。

attributeの値は英数字か</>しか使えない所も微妙に怪しい、、、が、req.query.htmlが指定されていない場合に表示されるdefaultHTMLが以下のような形なので、ギリギリこのplaceholderのためな気がしないでもない。

const defaultHtml = `
<body>
  <h1>HTML Viewer</h1>
  <form action="/">
    <p>
      <textarea name="html" placeholder="<p>hello</p>"></textarea>
    </p>
    <input type="submit" value="Render">
  </form>
</body>
`.trim();

元々のISO-2022-JPテクでは"をうまく無効化することで属性の値を抜け出していた。仮に何等かの方法で"が無効化できた場合に、属性の値の制約、英数字か</>の条件下でpayloadを組めるか考えてみると… これは組める！

<img id=”<script>//">
alert(origin);
//<img id=”</script>”>

<img id=の後にある"を無効化できた場合に以下のようなscriptタグを埋め込める。

<script>//">
alert(origin);
//<img id=”</script>

不要な部分を//のコメントと改行でいい感じに消し込みながら任意のjavascriptを動かすことができるようになった。んー、やはり枠組みはISO-2022-JPテクと同じであるような問題設定に見えるが…

この時点で2am。あまりに眠くて一旦寝ることに…

2日目朝: [web] purexss - 2nd challenge

7amに起床して再開。Do not use ISO-2022-JPを改めて眺め、Do not useはDo useかと思い直し、if (html.includes("\x1b")) throw "Invalid character";を回避する方針を考える。ガチャガチャやっていると… 数値文字参照で&#x1b;(Jを使えば、\x1bを吐き出させることに成功！

かなり非自明な挙動で、これだ！と思いながらガチャガチャやっていたが結局差し切れず、会場に向かうことに…

2日目: HECCON Stage 3

10:00、SECCON 2日目と共にStage 3が開始。

入力：サイズN×Mのランダムな行列をベクトルに変換したものが与えられる。N=28でM=25。N個のガウス分布が与えられ、[-1,1]の乱数を平均、[0.5, 1.0]の乱数を標準偏差として、それを元にM個のサンプルを生成する
計算：各行の標準化を出力する。標準化とは: (x - 平均) / √(分散 + EPS) の計算。

ソースコードは以下。

from pathlib import Path

import numpy as np
import pyhelayers


N = 2**8
M = 2**5
EPS = 1e-5


class Challenge:
    @classmethod
    def generate(cls, pubkey: Path, dist_dir: Path):
        """Generate the challenge data.

        dist_dir is a distributed directory to contestants.

        Args:
            pubkey (Path): Path to the public key file.
            dist_dir (Path): Path to the directory where the challenge data is saved.
        """
        he_context = pyhelayers.SealCkksContext()
        he_context.load_from_file(str(pubkey))
        encoder = pyhelayers.Encoder(he_context)
        mu = np.random.uniform(-1, 1, (N, 1))
        sigma = np.random.uniform(0.5, 1.0, (N, 1))
        x = np.random.normal(mu, sigma, (N, M))
        x = x.reshape(-1)
        cx = encoder.encode_encrypt(x)
        cx.save_to_file(str(dist_dir / "enc"))
        (dist_dir / "challenge.py").write_text(Path(__file__).read_text())

    @classmethod
    def evaluate(
        cls, pubkey: Path, privkey: Path, enc: Path, submission: Path
    ) -> float:
        """Evaluate the submission.

        submission is a path to a submitted file and the server evaluate it.
        Contestants are supposed to get better MAE as much as possible.

        Args:
            pubkey (Path): Path to the public key file.
            privkey (Path): Path to the private key file.
            enc (Path): Path to the encrypted data file.
            submission (Path): Path to the submitted file.
        """
        he_context = pyhelayers.SealCkksContext()
        he_context.load_from_file(str(pubkey))
        he_context.load_secret_key_from_file(str(privkey))
        encoder = pyhelayers.Encoder(he_context)

        cx = encoder.encode_encrypt([])
        cx.load_from_file(str(enc))
        x = encoder.decrypt_decode_double(cx)
        x = x.reshape(N, M)
        cy_sub = encoder.encode_encrypt([])
        cy_sub.load_from_file(str(submission))
        y_sub = encoder.decrypt_decode_double(cy_sub)
        y_sub = y_sub.reshape(N, M)

        mu = x.mean(axis=1, keepdims=True)
        sigma2 = x.var(axis=1, keepdims=True)
        y_true = (x - mu) / np.sqrt(sigma2 + EPS)
        mae = np.mean(np.abs(y_true - y_sub))  # less is better
        return float(mae)

とりあえず、入力の暗号文をそのまま出してスコアを出しておく。0.549。

適当にスカラー倍する 0.549 → 0.5353

僅かにアドバンテージが得られればとりあえず良いので(x - 平均) / √(分散 + EPS)の計算を見て、なんかで割っておくと色々ガチャガチャやると0.6倍するとちょっとスコアが改善したのでシュッと出す。

def copy(a, encoder):
    res = encoder.encode_encrypt(np.array([0]*N*M))
    res.add(a)
    return res

def mul_scalar(a, n, encoder):
    res = copy(a, encoder)
    res.multiply_scalar(n)
    return res

ans = mul_scalar(cx, 0.6, encoder)

これで0.5353。10:22提出。

平均は計算できる 0.5353 → 0.4534

平均の計算ができるので平均を計算して引く部分を実装しよう。平均を求めるには、M個ずつ総和を取って、その総和をMで割って、それをそれぞれの要素に移して引いていく方針を取る。

総和については、Stage 2と同様にrotateして足すをM要素分繰り返せば良い。Mで割るのも1/Mをかければ良いので問題ない。Stage 2と同じ方法だと、最初の要素に総和が来て、連なるM-1個はゴミデータが残ってしまっている。つまり、

\displaystyle y = \begin{vmatrix} sum1 \\ ゴミ \\ ゴミ \\ \vdots \\ \vdots \\ ゴミ \\ sum2 \\ ゴミ \\ \vdots \\ \vdots \end{vmatrix}

となっている。これに[1]+[0]*(M-1)を繰り返した

\displaystyle y = \begin{vmatrix} 1 \\ 0 \\ 0 \\ \vdots \\ \vdots \\ 0 \\ 1 \\ 0 \\ \vdots \\ \vdots \end{vmatrix}

のようなベクタを要素ごとに掛け合わせることでゴミデータを0にした以下のようなベクタを作れる。

\displaystyle y = \begin{vmatrix} sum1 \\ 0 \\ 0 \\ \vdots \\ \vdots \\ 0 \\ sum2 \\ 0 \\ \vdots \\ \vdots \end{vmatrix}

これが用意できればあとは、総和の時と同様にrotateを使うことで各要素にsumを足し合わせることができる。割り算の部分は0.6で掛けることを継続した実装が以下。

def copy(a, encoder):
    res = encoder.encode_encrypt(np.array([0]*N*M))
    res.add(a)
    return res

def add(a, b, encoder):
    res = copy(a, encoder)
    res.add(b)
    return res
    
def sub(a, b, encoder):
    res = copy(a, encoder)
    res.sub(b)
    return res

def mul(a, b, encoder):
    res = copy(a, encoder)
    res.multiply_tile(b)
    return res

def mul_scalar(a, n, encoder):
    res = copy(a, encoder)
    res.multiply_scalar(n)
    return res

def rotate(a, c, encoder):
    res = encoder.encode_encrypt(np.array([0]*N*M))
    res.add(a)
    res.rotate(c)
    return res

# ======================

total = encoder.encode_encrypt(np.array([0]*N*M))
rotated = copy(cx, encoder)
for i in range(M):
    total = add(total, rotated, encoder)
    rotated = rotate(rotated, 1, encoder)
avg = mul_scalar(total, 1/M, encoder)

one = encoder.encode_encrypt(np.array(([1] + [0]*(M-1))*N))
diff = copy(cx, encoder)
for i in range(M):
    av = rotate(mul(avg, one, encoder), -i, encoder)
    diff = sub(diff, av, encoder)

ans = mul_scalar(diff, 0.6, encoder)

これで0.4534が得られる。実装がバグりまくって、11:52提出。うーん。

割り算のパラメタを調整 0.4534 → 0.1531

割り算部分を0.6で掛けていたが、このパラメタを調整して1.3で掛けるようにするとスコアが跳ねあがった。0.1531。12:03提出。

分散を計算し、平方根の逆数を近似関数を使って近似 0.1531 → 0.1057

計算したいのは(x - 平均) / √(分散 + EPS)なので、次は分散を計算しよう。分散s2は(x - 平均)^2の平均を取ることで分散は計算できる。(x - 平均)は既に計算済みなので2乗して1/Mで掛けることで分散は計算できる。それにEPSを足す。

問題が1 / √xをどう計算するかであるが、ここは殿下の宝刀、多項式近似を使う。AIが教えてくれた

\displaystyle \frac{1}{\sqrt{x}}≈-0.704x+1.628

を採用した。これらを総合的に実装すると以下のようになる。

def copy(a, encoder):
    res = encoder.encode_encrypt(np.array([0]*N*M))
    res.add(a)
    return res

def add(a, b, encoder):
    res = copy(a, encoder)
    res.add(b)
    return res
    
def sub(a, b, encoder):
    res = copy(a, encoder)
    res.sub(b)
    return res

def mul(a, b, encoder):
    res = copy(a, encoder)
    res.multiply_tile(b)
    return res

def mul_scalar(a, n, encoder):
    res = copy(a, encoder)
    res.multiply_scalar(n)
    return res

def pow2(a, encoder):
    res = copy(a, encoder)
    res.square()
    return res

def rotate(a, c, encoder):
    res = encoder.encode_encrypt(np.array([0]*N*M))
    res.add(a)
    res.rotate(c)
    return res

# ======================

total = encoder.encode_encrypt(np.array([0]*N*M))
rotated = copy(cx, encoder)
for i in range(M):
    total = add(total, rotated, encoder)
    rotated = rotate(rotated, 1, encoder)
avg = mul_scalar(total, 1/M, encoder)

one = encoder.encode_encrypt(np.array(([1] + [0]*(M-1))*N))
diff = copy(cx, encoder)
for i in range(M):
    av = rotate(mul(avg, one, encoder), -i, encoder)
    diff = sub(diff, av, encoder)

sigma2 = pow2(diff, encoder)
sigma2_total = encoder.encode_encrypt(np.array([0]*N*M))
rotated = copy(sigma2, encoder)
for i in range(M):
    sigma2_total = add(sigma2_total, rotated, encoder)
    rotated = rotate(rotated, 1, encoder)
sigma2 = mul_scalar(sigma2_total, 1/M, encoder)

# sigma2 + EPS
sigma2 = add(sigma2, encoder.encode_encrypt(np.array([EPS]*N*M)), encoder)

# 1.628 - 0.704*x
c = -0.704
d = 1.628
v1 = mul_scalar(sigma2, c, encoder)
v0 = encoder.encode_encrypt(np.array([d]*N*M))
sigma2_rev = add(v0, v1, encoder)

one = encoder.encode_encrypt(np.array(([1] + [0]*(M-1))*N))
sigma2_rev_ans = encoder.encode_encrypt(np.array([0]*N*M))
for i in range(M):
    av = rotate(mul(sigma2_rev, one, encoder), -i, encoder)
    sigma2_rev_ans = add(sigma2_rev_ans, av, encoder)

ans = mul(diff, sigma2_rev_ans, encoder)

これで0.1057獲得。12:46提出。

ちゃんと多項式近似する 0.1057 → 0.0040

これまでAIに多項式近似した結果を聞いていたが、そうではなく多項式近似をフィットさせたい多項式と範囲から計算させるスクリプトを吐かせて計算すると、群違いの精度の多項式が得られた。

\displaystyle \frac{1}{\sqrt{x}}≈-5.53x^5 + 22.72x^4 - 36.79x^3 + 30.15x^2 - 13.54x + 4.00

を使うとスコアが跳ねあがる。

def copy(a, encoder):
    res = encoder.encode_encrypt(np.array([0]*N*M))
    res.add(a)
    return res

def add(a, b, encoder):
    res = copy(a, encoder)
    res.add(b)
    return res
    
def sub(a, b, encoder):
    res = copy(a, encoder)
    res.sub(b)
    return res

def mul(a, b, encoder):
    res = copy(a, encoder)
    res.multiply_tile(b)
    return res

def mul_scalar(a, n, encoder):
    res = copy(a, encoder)
    res.multiply_scalar(n)
    return res

def pow2(a, encoder):
    res = copy(a, encoder)
    res.square()
    return res

def pow3(a, encoder):
    res = pow2(a, encoder)
    res.multiply_tile(a)
    return res

def pow4(a, encoder):
    res = copy(a, encoder)
    res.square()
    res.square()
    return res

def pow5(a, encoder):
    res = pow4(a, encoder)
    res.multiply_tile(a)
    return res

def rotate(a, c, encoder):
    res = encoder.encode_encrypt(np.array([0]*N*M))
    res.add(a)
    res.rotate(c)
    return res

# ======================

total = encoder.encode_encrypt(np.array([0]*N*M))
rotated = copy(cx, encoder)
for i in range(M):
    total = add(total, rotated, encoder)
    rotated = rotate(rotated, 1, encoder)
avg = mul_scalar(total, 1/M, encoder)

one = encoder.encode_encrypt(np.array(([1] + [0]*(M-1))*N))
diff = copy(cx, encoder)
for i in range(M):
    av = rotate(mul(avg, one, encoder), -i, encoder)
    diff = sub(diff, av, encoder)

sigma2 = pow2(diff, encoder)
sigma2_total = encoder.encode_encrypt(np.array([0]*N*M))
rotated = copy(sigma2, encoder)
for i in range(M):
    sigma2_total = add(sigma2_total, rotated, encoder)
    rotated = rotate(rotated, 1, encoder)
sigma2 = mul_scalar(sigma2_total, 1/M, encoder)

# sigma2 + EPS
sigma2 = add(sigma2, encoder.encode_encrypt(np.array([EPS]*N*M)), encoder)

# 多項式: -5.53*x^5 + 22.72*x^4 - 36.79*x^3 + 30.15*x^2 - 13.54*x + 4.00 
c5 = -5.53
c4 = 22.72
c3 = -36.79
c2 = 30.15
c1 = -13.54
c0 = 4
v0 = encoder.encode_encrypt(np.array([c0]*N*M))
v1 = mul_scalar(sigma2, c1, encoder)
v2 = mul_scalar(pow2(sigma2, encoder), c2, encoder)
v3 = mul_scalar(pow3(sigma2, encoder), c3, encoder)
v4 = mul_scalar(pow4(sigma2, encoder), c4, encoder)
v5 = mul_scalar(pow5(sigma2, encoder), c5, encoder)
sigma2_rev = add(add(v1, v2, encoder), add(add(v3, add(v4, v5, encoder), encoder), v0, encoder), encoder)

one = encoder.encode_encrypt(np.array(([1] + [0]*(M-1))*N))
sigma2_rev_ans = encoder.encode_encrypt(np.array([0]*N*M))
for i in range(M):
    av = rotate(mul(sigma2_rev, one, encoder), -i, encoder)
    sigma2_rev_ans = add(sigma2_rev_ans, av, encoder)

ans = mul(diff, sigma2_rev_ans, encoder)

これで0.0040獲得。13:18提出。ほとんどStageの切り替え時間だったが、やっと上位と戦えるスコアになってきた。

2日目: HECCON Stage 4

13:30、最終ラウンドのStage 4が始まる。

入力：サイズN×Mのランダムな行列をベクトルに変換したものが与えられる。N=29でM=24。N個のガウス分布が与えられ、[-1,1]の乱数を平均、[0.5, 1.0]の乱数を標準偏差として、それを元にM個のサンプルを生成する
計算：各行の最大値を出力

スクリプトは以下。

from pathlib import Path

import numpy as np
import pyhelayers


N = 2**9
M = 2**4


class Challenge:
    @classmethod
    def generate(cls, pubkey: Path, dist_dir: Path):
        """Generate the challenge data.

        dist_dir is a distributed directory to contestants.

        Args:
            pubkey (Path): Path to the public key file.
            dist_dir (Path): Path to the directory where the challenge data is saved.
        """
        he_context = pyhelayers.SealCkksContext()
        he_context.load_from_file(str(pubkey))
        encoder = pyhelayers.Encoder(he_context)
        mu = np.random.uniform(-1, 1, (N, 1))
        sigma = np.random.uniform(0.5, 1.0, (N, 1))
        x = np.random.normal(mu, sigma, (N, M))
        x = x.reshape(-1)
        cx = encoder.encode_encrypt(x)
        cx.save_to_file(str(dist_dir / "enc"))
        (dist_dir / "challenge.py").write_text(Path(__file__).read_text())

    @classmethod
    def evaluate(
        cls, pubkey: Path, privkey: Path, enc: Path, submission: Path
    ) -> float:
        """Evaluate the submission.

        submission is a path to a submitted file and the server evaluate it.
        Contestants are supposed to get better MAE as much as possible.

        Args:
            pubkey (Path): Path to the public key file.
            privkey (Path): Path to the private key file.
            enc (Path): Path to the encrypted data file.
            submission (Path): Path to the submitted file.
        """
        he_context = pyhelayers.SealCkksContext()
        he_context.load_from_file(str(pubkey))
        he_context.load_secret_key_from_file(str(privkey))
        encoder = pyhelayers.Encoder(he_context)

        cx = encoder.encode_encrypt([])
        cx.load_from_file(str(enc))
        x = encoder.decrypt_decode_double(cx)
        x = x.reshape(N, M)
        cy_sub = encoder.encode_encrypt([])
        cy_sub.load_from_file(str(submission))
        y_sub = encoder.decrypt_decode_double(cy_sub)
        y_sub = y_sub.reshape(N, M)[:, 0]

        y_true = x.max(axis=1)
        mae = np.mean(np.abs(y_true - y_sub))  # less is better
        return float(mae)

入力された暗号文をそのまま提出してスタート。1.3694。

Stage 1の計算を投げてみる 1.3694 → 0.9115

最初はちょっとでも改善できればいい。ちょっと考えると、max(x, 0)を適用すれば負の数が削除されてわずかにスコアが上がりそうである。実際にやってみると上がった。Stage 1の実装をそのまま適用した。

def copy(a, encoder):
    res = encoder.encode_encrypt(np.array([0]*N*M))
    res.add(a)
    return res

def add(a, b, encoder):
    res = copy(a, encoder)
    res.add(b)
    return res

def mul(a, b, encoder):
    res = copy(a, encoder)
    res.multiply_tile(b)
    return res

def mul_scalar(a, n, encoder):
    res = copy(a, encoder)
    res.multiply_scalar(n)
    return res

def pow2(a, encoder):
    res = copy(a, encoder)
    res.square()
    return res

# ======================

d1 = mul_scalar(pow2(cx, encoder), 0.15, encoder)
d2 = mul_scalar(cx, 0.5, encoder)
cx = add(add(d1, d2, encoder), encoder.encode_encrypt(np.array([0.325]*M*N)), encoder)
ans = cx

0.9115獲得。13:40提出。

Stage 2の方針を使って24個のうち23個のmaxを計算 0.9115 → 0.3108

maxの計算と言えばStage 2ととても良く似ている。違いは個数で24個のmaxを取る必要がある。例えば隣接する22=4個のmaxを考えてみると、トーナメント式で求められそうなことに気が付く。つまり、

a b c d
↓ 隣接する2つでmax計算 (=Stage 2)
max(a,b) any max(c,d) any
↓ 1つ飛びでmax計算 (=Stage 2とほぼ同じでrotateを1ではなく2でやる)
max(a,b,c,d) any any any

で解けることに気が付く。しかも、これだとmaxの計算回数は24個の対数を取った4回で済む。つまりは、ソーティングネットワークのように並列で計算ができる。これは良い方針に見える。

ということでmax関数の計算はStage 2のものを少し改良したものを利用してこの方針を実装してみるが、掛け算の計算限界を迎えてしまったのでとりあえず4回ループするのではなく3回ループさせて、先頭の23個のmaxを出力することにした。

def copy(a, encoder):
    res = encoder.encode_encrypt(np.array([0]*N*M))
    res.add(a)
    return res

def add(a, b, encoder):
    res = copy(a, encoder)
    res.add(b)
    return res

def mul(a, b, encoder):
    res = copy(a, encoder)
    res.multiply_tile(b)
    return res

def mul_scalar(a, n, encoder):
    res = copy(a, encoder)
    res.multiply_scalar(n)
    return res

def pow2(a, encoder):
    res = copy(a, encoder)
    res.square()
    return res

def rotate(a, c, encoder):
    res = encoder.encode_encrypt(np.array([0]*N*M))
    res.add(a)
    res.rotate(c)
    return res

# ======================

winner = copy(cx, encoder)
for p in range(3):
    x = copy(winner, encoder)
    y = rotate(winner, 1<<p, encoder)
    added = add(x, y, encoder)

    # 多項式: 0.23*x^2 + 0.75
    c2 = 0.23
    c0 = 0.75
    d2 = mul_scalar(pow2(sub(x, y, encoder), encoder), c2, encoder)
    absed = add(d2, encoder.encode_encrypt(np.array([c0]*N*M)), encoder)

    winner = add(added, absed, encoder)
    winner = mul_scalar(winner, 0.5, encoder)

ans = winner

0.3108。いいスコア。14:12提出。

掛け算を減らして4回ループするようにする 0.3108 → 0.2683

多項式近似で多く掛け算が行われているので多項式近似部分で少しでも掛け算を減らすため、xとyの和と差の絶対値を足してから1/2をかけるのではなく、xとyの平均を求め、差の絶対値/2の部分は多項式近似の係数を/2することで暗号文での掛け算を1回減らした。

これにより掛け算の上限に引っ掛からず4回ループさせることができた。加えて若干の近似多項式ガチャをした。

def copy(a, encoder):
    res = encoder.encode_encrypt(np.array([0]*N*M))
    res.add(a)
    return res

def add(a, b, encoder):
    res = copy(a, encoder)
    res.add(b)
    return res
    
def sub(a, b, encoder):
    res = copy(a, encoder)
    res.sub(b)
    return res

def mul(a, b, encoder):
    res = copy(a, encoder)
    res.multiply_tile(b)
    return res

def mul_scalar(a, n, encoder):
    res = copy(a, encoder)
    res.multiply_scalar(n)
    return res

def pow2(a, encoder):
    res = copy(a, encoder)
    res.square()
    return res

def rotate(a, c, encoder):
    res = encoder.encode_encrypt(np.array([0]*N*M))
    res.add(a)
    res.rotate(c)
    return res

# ======================

winner = copy(cx, encoder)
for p in range(4):
    x = copy(winner, encoder)
    y = rotate(winner, 1<<p, encoder)
    added = add(x, y, encoder)
    added = mul_scalar(added, 0.5, encoder)

    # 多項式: 0.31*x^2 + 0.56
    c2 = 0.31 * 0.5
    c0 = 0.56 * 0.5
    d2 = mul_scalar(pow2(sub(x, y, encoder), encoder), c2, encoder)
    absed = add(d2, encoder.encode_encrypt(np.array([c0]*N*M)), encoder)

    winner = add(added, absed, encoder)

ans = winner

これで0.2683。14:46提出。

[web] purexss 3rd challenge 解けた！

KotHの途中だったが、purexssが解けそうな雰囲気があり、改善アイデアもとりあえず出尽くしたので戻ってきた。これまでに"を消すことができれば、

<img id=”<script>//">
alert(origin);
//<img id=”</script>”>

でXSSできるということと、数値文字参照で&#x1b;(Jを使えば、\x1bを吐き出させることができるというのが分かっていた。

\x1bを吐き出すことができるということは&#x1b;$B[any string]&#x1b;(Bのようにしてやれば、[0x1B]$BでJIS X 0208 1983モードに変更させてそれ以降の文字を謎のマルチバイト文字に変換させることができ、[0x1B](BでASCIIモードに戻すことができるので、[any string]を消し込むことができるようになる。問題は何を消すかであり、色々思考を巡らせると… textareaタグ！

textareaタグの中にDOMPurifyでサニタイズした入力をそのまま入れるとXSSに繋げられるというテクがあり、以下のような形を作ることができればアラートが出るというものである。

<textarea><div id="</textarea><script>alert(origin);</script>"></div></textarea>

テクニックのミソは<div id="</textarea><script>alert(origin);</script>"></div>だけDOMPurifyに与えられても怪しい文字列はidの名前として解釈されないので残るというのと、textareaタグはhtmlの構造を見ず</textarea>の文字列があるかでタグを閉じるので良い感じにidの値を脱出してscriptタグが動くというもの。

今回は全体がDOMPurifyに送られているので上のpayloadを投げても正しくtextareaタグが処理されてscriptタグは消えてしまうのだが、ここでISO-2022-JPの消し込みテクが使える。

<textarea>&#x1b;$B</textarea>&#x1b;(B escaped?

こういうのを送ってみると

このようにtextareaの外にある文字列が中に吸い込まれているのが分かる。これはISO-2022-JPのエスケープシーケンスによって</textarea>が消し込まれているためである。よって、それに続く文字列がtextareaの中に取り込まれることになった。これにさっきのテクニックを組み合わせてみよう。

<textarea>&#x1b;$B</textarea>&#x1b;(B <div id="</textarea><s>XSS</s>"></div>

divタグのidに入っているはずのタグをうまく外に出すことに成功した！つまり、タグの"を消し込めたことになる！"が消し込めたときにXSSする方法は既に考えてあったので、以下のようにやるとアラートが出てくる。

<textarea>&#x1b;$B</textarea>&#x1b;(B <div id="</textarea><script>//"></div>
alert(origin)
//<textarea>&#x1b;$B</textarea>&#x1b;(B <div id="</script>"></div>

これで勝ったのでalert(origin)の部分を適当にcookieを外に送るコードにすればフラグ獲得。

自分も作問に関わったFlatt Security XSS Challengeの解説のhamayanhamayan問とkinugawamasatoさん問のおかげで解けた。

2日目: HECCON Stage 4に戻る

purexssが解けて満足したので、HECCONに戻ってきた。

絶対値の多項式近似のパラメタ調整 0.2683 → 0.2154

絶対値の多項式近似のパラメタを調整したらスコアがかなり上がった。

\displaystyle \text{abs}(x)≈0.35*x^2+0.4

として実装する。

def copy(a, encoder):
    res = encoder.encode_encrypt(np.array([0]*N*M))
    res.add(a)
    return res

def add(a, b, encoder):
    res = copy(a, encoder)
    res.add(b)
    return res
    
def sub(a, b, encoder):
    res = copy(a, encoder)
    res.sub(b)
    return res

def mul(a, b, encoder):
    res = copy(a, encoder)
    res.multiply_tile(b)
    return res

def mul_scalar(a, n, encoder):
    res = copy(a, encoder)
    res.multiply_scalar(n)
    return res

def pow2(a, encoder):
    res = copy(a, encoder)
    res.square()
    return res

def rotate(a, c, encoder):
    res = encoder.encode_encrypt(np.array([0]*N*M))
    res.add(a)
    res.rotate(c)
    return res

# ======================

winner = copy(cx, encoder)
for p in range(4):
    x = copy(winner, encoder)
    y = rotate(winner, 1<<p, encoder)
    added = add(x, y, encoder)
    added = mul_scalar(added, 0.5, encoder)

    # 多項式: 0.35*x^2 + 0.4
    c2 = 0.35 * 0.5
    c0 = 0.4 * 0.5
    d2 = mul_scalar(pow2(sub(x, y, encoder), encoder), c2, encoder)
    absed = add(d2, encoder.encode_encrypt(np.array([c0]*N*M)), encoder)

    winner = add(added, absed, encoder)

ans = winner

これで0.2154。15:59提出。

終了！

SECCON、とても楽しかったが、キツイ…