2025 年 4-6 月 koba の心を震わせたものまとめ

セキュリティー・CTF

https://www.tumblr.com/accidentallyquadratic/153545455987/rust-hash-iteration-reinsertion

  • Rust の HashMap で計算量が 2 乗になるパターンが過去あった話
  • 2016 年の話なのでもう修正されている: https://github.com/rust-lang/rust/pull/37470
  • このパターンがまずかった (根本原因は二つの HashSet で seed が同じであることと、one の要素を全列挙する際にバケット順に調べること)
let mut one = HashSet::new();
let mut two = HashSet::new();
/* one を埋めて 500000 要素にする */
for v in one { two.insert(v); }

Go Cryptography Security Audit - The Go Programming Language

  • Go の暗号理論のライブラリーを監査した話
  • (Go ということを考えれば当然だが) ほとんど問題が見つからなくてすごい
  • 公開鍵への適用を意図した関数でも constant-time にするのが几帳面
    • constant-time である必要がなさそうな関数でも constant-time にしたいときの言い訳として使える

技術一般

ChatGPTと1週間本気で語りあったら、いつか来てほしい未来が見えた - kondoyukoの踊る編集室

  • 生成 AI が得た「人格」は新しく会話を始める際に引き継げることがある。
  • これを読んだ時 (2025 年 4 月)、生成 AI と親密な関係になる人間が周りで増えている気がして恐ろしくなった。

When is a Rust function "unsafe"? // crescentro.se

  • Rust における unsafe の定義には諸説あり、公式の中でも諸説あるという話
  • memory bug 以外の脆弱性・危険性で議論になりやすい
    • 例: SQL injection が可能な関数は unsafe であるべきか?

So you want to serialize some DER? · Alex Gaynor

Faster shuffling in Go with batching – Daniel Lemire's blog

  • 乱数生成に変数除算を使わないことで高速化
    • 今回の記事の論点ではないが非自明。math/rand/v2 で採用されている
  • cutoff は十分小さいのでいい加減でもよい。粗い cutoff で引っ掛かったら厳密な cutoff を計算する
    • 厳密な cutoff は 2^64 % P(n, k) の形なので、計算しようとすると変数による除算が遅い。粗い cutoff はそれらより常に大きく、2^64 よりもそこそこ小さい値であれば何でも良く、たとえば 2^60 であれば 3/4 の確率で変数による除算を回避できる。
  • 乱数生成をバッチで実行することで高速化
    • 乱数生成が節約できる

思想一般

Make Time: How to Focus on What Matters Every Day

  • 時間泥棒に負けずにいかに時間を作り出すか、という話
  • 新しい日本語訳が最近 (2025 年 6 月) 出版された: とっぱらう――自分の時間を取り戻す「完璧な習慣」
  • 我々の生活には Busy Bandwagon (いくらでも湧いて出てくる仕事の山) と Infinity Pool (無限にスクロールをして情報を得たくなる、情報の源) が溢れている。それらとうまく付き合って時間を確保しようというのがこの本の主旨で、そのためのテクニックを紹介している。
    • "Being more productive didn’t mean I was doing the most important work; it only meant I was reacting to other people’s priorities faster." (生産性が上がったからといって、私は一番大事な仕事をしているというわけではなかった。他者の重要事により速く反応しているだけのことだった。)

宝くじ購入代行のドリームウェイ【公式サイト】

  • 宝くじ購入代行サービス。(一番利用者に有利なやり方だと) 60000 円分の宝くじ購入を 10% の手数料 (6000 円) でやってくれる。
  • このサービスがカネを取れるという発想がなく、シンプルに頭が良いと感じた。「西銀座チャンスセンター」で買うと当たりやすい、という思い込みを exploit してカネに変換する手腕が見事だと思った。

1対100でも勝つ!宮本武蔵の「極意」は合理的な戦法にあり

  • 「神仏は実在せぬと一面でおもい、一面でそれを叶わぬまでもすがろうとする半懐疑の心情をすてていない。その半懐疑は人間の弱さの投影であることを、兵法という合理性そのものにみちた思考法のなかにいるこの若者は十分に知っていた。」
    • 「半懐疑」を戒める評論。

Obvious and non-obvious ways to write great job ads - PostHog

  • 採用広告を出す時に気をつけること
    • 採用広告はまず hiring manager が書いて、書くことが得意な人が修正する
    • 応募量だけ追求しても仕方ない。採用したくない人を明確にして、job description を読んだらそもそも応募しないようにしてもらおう
  • 採用だけでなくあらゆる広告に応用できそう。

2025 年 1-3 月 koba の心を震わせたものまとめ

セキュリティー・CTF

https://github.com/cryptocoinjs/secp256k1-node/security/advisories/GHSA-584q-6j8j-r5pm

  • Invalid curve attack の亜種。2^35 回程度の前計算を行うことで、 11 回の通信 (ECDH) で秘密鍵を特定できるのが特筆すべき点。
    • 下手したら CTF で出題可能なくらいセットアップが楽。

​​https://www.latacora.com/blog/2024/07/29/crypto-right-answers-pq/

https://storj.dev/blog/two-mul-or-not-two-mul

  • Go 言語標準ライブラリーの Ed25519 実装において、19 倍する処理の高速化。高速化コミットはこれ
    • p = 2^{255} - 19 を位数とした有限体の上の演算が高速になる。よって Ed25519 関連の全ての演算速度が底上げされる。
    • Go 言語にもまだこのような高速化の余地が残っていたのがかなり意外だった。

数学

https://note.com/yu_kishi248/n/n1f99eb4435b5

  • SO(3, R) の有限部分群の分類。「巡回群、二面体群、正多面体の対称性の群 のいずれか」という結論になる。整数についての議論を駆使して証明する。
    • 結論が単純であり、議論もギリギリ高校生が追えそうな雰囲気がある。

https://www.youtube.com/watch?v=NkxsPu9Z-r8&ab_channel=KotoHa-Topic

SECCON CTF 13 Quals writeup

SECCON CTF 13 Quals にチーム ZK Lovers で参加した。日本時間で 2024-11-23 14:00 から 2024-11-24 14:00 まで。

結果は 35/653 位。日本のチーム内では 8/303 位だったため、決勝に進出した。

解法集

crypto

xiyi

解説は https://zenn.dev/sigma425/articles/826180135a39cb でやってもらったのでコードだけ。
コードは以下の通り。以下の点が記事とは違うことに注意。

  • 離散対数を取るところで、\log_{-2}(s^yg^r) を計算している。
  • s は s\equiv 1 \pmod{p^2}, s\equiv -2 \pmod{q} を満たす。これによって、 mod p^2 で出る結果が -r に、mod q で出る結果が y-r になる。

presolve.py (パラメーターの算出)

from Crypto.Util.number import isPrime


def order_prim(g: int, p: int, n: int) -> int:
    g = pow(g, (n - 1) // p, n)
    if g == 1:
        return 1
    return p


def order_log(g: int, n: int, prod_list: list[int]):
    ans = 1
    for p in prod_list:
        ans *= order_prim(g, p, n)
    return ans


def main() -> None:
    prod = 1
    prod_list = []

    for i in range(2, 374):
        if not isPrime(i):
            continue
        prod *= i
        prod_list.append(i)

    ps = []
    for i in range(1, 1000000):
        p = prod * i + 1
        if not isPrime(i):
            continue
        if p.bit_length() != 518:
            continue
        if isPrime(p):
            ps.append((p, i))
            if len(ps) == 2:
                break

    for index in range(2):
        p, i = ps[index]
        tmp = prod_list[:]
        tmp.append(i)
        print(f'p{index} = ' + ' * '.join(map(str, tmp)) + ' + 1')
        print(f'prod_list{index} =', tmp)
        print(f'assert p{index}.bit_length() == 518')
        print(f'assert isPrime(p{index})')
        o = order_log(p - 2, p, tmp)
        print(f'o{index} = {o}')

    print('gcd_o = math.gcd(o0, o1)')
    print('assert gcd_o.bit_length() >= 256')
    print('''
gcd_o_factors = []
for p in prod_list0:
    if gcd_o % p == 0:
        gcd_o_factors.append(p)
assert functools.reduce(lambda x, y: x * y, gcd_o_factors) == gcd_o''')

if __name__ == '__main__':
    main()

solve.py

import math
import time
import functools
import json
import sys
from Crypto.Util.number import isPrime
from pwn import remote, process
from params import L


p0 = 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 * 31 * 37 * 41 * 43 * 47 * 53 * 59 * 61 * 67 * 71 * 73 * 79 * 83 * 89 * 97 * 101 * 103 * 107 * 109 * 113 * 127 * 131 * 137 * 139 * 149 * 151 * 157 * 163 * 167 * 173 * 179 * 181 * 191 * 193 * 197 * 199 * 211 * 223 * 227 * 229 * 233 * 239 * 241 * 251 * 257 * 263 * 269 * 271 * 277 * 281 * 283 * 293 * 307 * 311 * 313 * 317 * 331 * 337 * 347 * 349 * 353 * 359 * 367 * 373 * 95111 + 1
prod_list0 = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 95111]
assert p0.bit_length() == 518
assert isPrime(p0)
o0 = 36661539024568114673630848676502229358837161250611654971980007790086057602635278619098631925083991929859953297191541221964453055358660192576524314518690
p1 = 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 * 31 * 37 * 41 * 43 * 47 * 53 * 59 * 61 * 67 * 71 * 73 * 79 * 83 * 89 * 97 * 101 * 103 * 107 * 109 * 113 * 127 * 131 * 137 * 139 * 149 * 151 * 157 * 163 * 167 * 173 * 179 * 181 * 191 * 193 * 197 * 199 * 211 * 223 * 227 * 229 * 233 * 239 * 241 * 251 * 257 * 263 * 269 * 271 * 277 * 281 * 283 * 293 * 307 * 311 * 313 * 317 * 331 * 337 * 347 * 349 * 353 * 359 * 367 * 373 * 95471 + 1
prod_list1 = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 95471]
assert p1.bit_length() == 518
assert isPrime(p1)
o1 = 433176388095566017443503977303018864439997415658581630574274185147818012525806889798787919014260344688923985302972314688075228224036485629700737413953932390
gcd_o = math.gcd(o0, o1)
assert gcd_o.bit_length() >= 256

gcd_o_factors = []
for p in prod_list0:
    if gcd_o % p == 0:
        gcd_o_factors.append(p)
assert functools.reduce(lambda x, y: x * y, gcd_o_factors) == gcd_o


def crt(a0: int, mo0: int, a1: int, mo1: int) -> int:
    return (a0 * mo1 * pow(mo1, -1, mo0) + a1 * mo0 * pow(mo0, -1, mo1)) % (mo0 * mo1)


def disc_log_prim(g: int, h: int, factor: int, order: int, n: int) -> int | None:
    g = pow(g, order // factor, n)
    h = pow(h, order // factor, n)
    cur = 1
    for i in range(factor):
        if cur == h:
            return i
        cur = cur * g % n
    return None

def disc_log(g: int, h: int, n: int, prod_list: list[int]) -> tuple[int, int]:
    order = functools.reduce(lambda x, y: x * y, prod_list)
    assert pow(g, order, n) == 1
    assert order == gcd_o
    a = 0
    mo = 1
    for factor in prod_list:
        res = disc_log_prim(g, h, factor, order, n)
        assert res is not None, f'{g = }, {h = }, {factor = }, {order = }, {n = }'
        a = crt(a, mo, res, factor)
        mo *= factor
    return (a, mo)


local = len(sys.argv) == 1
io = process(['python3', 'server.py']) if local else remote(sys.argv[1], int(sys.argv[2]))


def main() -> None:
    start = time.time()
    # initialize
    n = p0 * p0 * p1
    x = crt(1, p0 * p0, p1 - 2, p1)
    assert x % (p0 * p0) == 1
    assert x % p1 == p1 - 2
    enc_xs = [x] * L

    # 1: (client) --- n, enc_xs ---> (server)
    io.sendlineafter(b"> ", json.dumps({"n": n, "enc_xs": enc_xs}).encode())

    # 3: (server) --- enc_alphas, beta_sum_mod_n ---> (client)
    params = json.loads(io.recvline().strip().decode())
    enc_alphas = params["enc_alphas"]
    ys = []
    base_0 = -2
    exp_0 = 1
    base_1 = -2
    exp_1 = 1
    for p in prod_list0:
        if p in gcd_o_factors:
            continue
        assert (p0 - 1) % p == 0
        if pow(-2, (p0 - 1) // p, p0) != 1:
            base_0 = pow(base_0, p, p0)
            exp_0 *= p
    base_0 = pow(base_0, p0, p0 * p0)
    exp_0 *= p0
    for p in prod_list1:
        if p in gcd_o_factors:
            continue
        if pow(-2, (p1 - 1) // p, p1) != 1:
            base_1 = pow(base_1, p, p1)
            exp_1 *= p
    assert pow(base_0, gcd_o, p0) == 1
    assert pow(base_0, gcd_o, p0 * p0) == 1
    assert pow(base_1, gcd_o, p1) == 1
    for p in gcd_o_factors:
        assert pow(base_0, gcd_o // p, p0) != 1
        assert pow(base_0, gcd_o // p, p0 * p0) != 1
        assert pow(base_1, gcd_o // p, p1) != 1

    for i in range(L):
        disc_0 = disc_log(base_0, pow(enc_alphas[i], exp_0, p0 * p0), p0 * p0, gcd_o_factors)  # -r
        disc_1 = disc_log(base_1, pow(enc_alphas[i], exp_1, p1), p1, gcd_o_factors) # y - r
        print(f'# ({time.time() - start:.2f}s) {i = }, {disc_0 = }, {disc_1 = }')
        y = (disc_1[0] - disc_0[0]) % gcd_o
        ys.append(y)

    # If, by any chance, you can guess ys, send it for the flag!
    print(f'{ys = }')
    io.sendlineafter(b"> ", json.dumps({"ys": ys, "p": p0, "q": p1}).encode())
    print(io.recvline().strip().decode())  # Congratz! or Wrong...
    print(io.recvline().strip().decode())  # flag or ys


if __name__ == "__main__":
    main()

まとめ

xiyi を解いてギャンブルに大勝ち。

Approximate GCD の返り値の大きさについて、あるいは我々は何個のサンプルを取るべきか

最近の CTF では Approximate GCD を要求されることが多い。直近では 2024/10/26 の CTF (ISITDTU CTF QUALS 2024) で出題された。そのとき出題された Sign という問題において、解く側にはサンプルとなる署名を何個取るかの自由度があり、それによって Approximate GCD に渡す整数の個数が決まる。
Approximate GCD には以下のようなトレードオフがある。

  • 正しさ: 整数の個数が少なすぎると正しい答えが出ない確率が高い。
  • 速度: Approximate GCD は内部で LLL アルゴリズムを使っているので、一応多項式時間で動作はするものの整数の個数が多すぎると時間がかかる。

これにより、Approximate GCD に渡すべき整数の個数が分からなかったので調査した。

実験に使ったコードはコード置き場にある。またデータをまとめたスプレッドシートApproximate GCD の返り値 - Google スプレッドシート にある。

結論

nums を長さ n の s ビット程度の整数列とする。Approximate GCD (approx_gcd.sageapprox_gcd(d: list[int], approx_error: int) -> int) を approx_gcd(nums, 2**b) の形で呼び出す時、返ってくる間違った値は (s-b)/n + b ビット程度である。d ビット程度の値が欲しい場合は、(s-b)/n + b < d となるように十分大きい n を選ぶべきである。(n > (s - b) / (d - b))
Sign の場合、s = 2048 * 11 = 22528, b = 256, d = 2048 であったので、n > (22528 - 256) / (2048-256) ~= 12.43 である必要があった。(実装の都合上、n = (サンプル数) - 1 だったので、(サンプル数) >= 14 が必要。)

前提知識

Approximate GCD というのは、以下のような問題、およびそれを解くアルゴリズムのことを意味している。

n 個の整数 nums が与えられる。nums[i] が全て g の倍数に近いような、最大の g を求めよ。(どの程度の差であれば「近い」とみなすのかは問題によって決まる。)

参考資料はなかなか見つかりにくいが、例えば以下を参考にされたい。

実装は approx_gcd.sage を参考にされたい。

実験

予備実験

筆者はまず、「n 個の整数を approx_gcd に与えるのであれば、失敗確率は 1-1/\zeta(n) で成功確率は 1/\zeta(n) だろう」と考え、実験した。(ζ はゼータ関数であり、なぜゼータ関数が登場するのかは 任意に選んだn数が互いに素になる確率 | Mathlog などを参考にすること。失敗するのは欲しい gcd で割ったときの商がたまたま互いに素でなかったときである。)

結果は予想に反し、n <= 12 のとき (num_sigs <= 13 のとき) 確実に失敗し、n >= 13 のとき (num_sigs >= 14 のとき) 確実に成功した。
データについてはコード置き場の exp-0.sage, exp-0.log を見ること。

誤差の実験 (Sign)

num_sigs <= 13 のとき確実に失敗したので、gcd として得られた値が本来欲しい値と比べてどのくらい大きいかを実験した。
データについてはコード置き場の exp-1-error.sage, exp-1-error.log を見ること。
結果は以下のように、(反比例) + (定数) ビットという形になった。

exp-1-error.sage の結果 (表)
exp-1-error.sage の結果

誤差の実験 (10000 ビットのランダムな整数)

ランダムな整数については (反比例) + (定数) ビットという形になる可能性があると思い、10000 ビットのランダムな整数を num_nums 個与える実験をした。(2 <= num_nums <= 16)
データについてはコード置き場の exp-2.sage, exp-2.log を見ること。

結果はやはり (反比例) + (定数) ビットであった。

exp-2.sage の結果 (表)
exp-2.sage の結果 (グラフ)

結論

nums を長さ n の s ビット程度のランダムな整数列とする。Approximate GCD (approx_gcd.sageapprox_gcd(d: list[int], approx_error: int) -> int) を approx_gcd(nums, 2**b) の形で呼び出す時、返ってくる値は (s-b)/n + b ビット程度である。
この結論は以下の理屈で正当化できる。また実験とも整合している。

  • b が十分に大きい場合、全ての整数を 2^b で割れば nums は 2^(s-b) 程度のランダムな実数列と見なせる。これに対して LLL をやって得られる結果の大きさは s-b のみに依存し、s や b そのものには依存しないはず。そのため最終的なビット長は (s-b の式) + b ビットになるはず。
  • ビット長は n に関して単調減少であるはず。

ISITDTU CTF QUALS 2024 writeup

ISITDTU CTF QUALS 2024 にチーム ZK cha で参加した。日本時間で 2024-10-26 11:00 から 2024-10-27 19:00 まで。

結果は 95/315 位。
SpookyCTF 2024 で散々な目にあったから、SpookyCTF 2024 の競技中にもかかわらずこちらに移行した。

解法集

crypto

ShareMixer1

素数 p が決められる。flag を 1 つ含み他はランダムな係数を持つ、次数 32 の多項式 cs をジャッジが決めるので、長さ 256 以下の数列 xs を送れ。それの各値を代入した結果をシャッフルして返す。」という問題。

xs の中の頻度を調節する (たとえばある数は 1 個だけ入れ、ある数は 2 個入れ、…) と、特定の数を代入した結果が分かる。
これを利用して頻度を [(1, 3), (2, 3), (3, 2), (4, 2), (5, 2), (6, 2), (7, 2), (8, 2), (9, 2), (10, 2), (11, 2), (12, 2), (13, 1), (14, 1), (15, 1), (16, 1), (17, 1), (18, 1)] にすることで、組み合わせを 9216 通り試せば良くなる。
(この列は (頻度, その頻度をもつ数の個数) の列で、同じ頻度をもつ数は全ての順列を試す必要があるので、3! * 3! * 2^10 = 9216 通り)

なお、この問題では PoW を実行することを求められるが、配布されるソースコードにはそれが記載されておらず、リモートサーバーに接続した時に初めて分かる仕様になっていた。

pow.py は以下の通り。

#!/usr/bin/env python3
"""
Copied and modified from https://github.com/balsn/proof-of-work/blob/master/solver/python3.py
"""
import hashlib
import sys


difficulty = 24
zeros = '0' * difficulty


def is_valid(digest):
    if sys.version_info.major == 2:
        digest = [ord(i) for i in digest]
    bits = ''.join(bin(i)[2:].zfill(8) for i in digest)
    return bits[:difficulty] == zeros


def find(prefix: str) -> str:
    i = 0
    while True:
        i += 1
        s = prefix + str(i)
        if is_valid(hashlib.sha256(s.encode()).digest()):
            return str(i)

また solve.sage は以下の通り。

# https://stackoverflow.com/questions/65579133/every-time-i-run-my-script-it-returns-curses-error-must-call-setupterm-firs
import os
os.environ['TERM'] = 'linux'
os.environ['PWNLIB_NOTERM'] = '1'


import sys
import time
import itertools
import pow
from pwn import remote, process
from Crypto.Util.number import long_to_bytes, getPrime


local = len(sys.argv) == 1
io = process(["python3", "chall.py"]) if local else remote(sys.argv[1], int(sys.argv[2]))


l = 32
getPrime(256)


def decouple_multiset(multiset: list[int]) -> dict[int, list[int]]:
    """
    freq -> [val1, val2, ...]
    """
    decoupled_freqs = {}
    for val in multiset:
        if val not in decoupled_freqs:
            decoupled_freqs[val] = 0
        decoupled_freqs[val] += 1
    ret = {}
    for k in decoupled_freqs:
        v = decoupled_freqs[k]
        if v not in ret:
            ret[v] = []
        ret[v].append(k)
    return ret


def solve_lagrange(p: int, assoc: list[tuple[int, int]]) -> list[int]:
    K = GF(p)
    R = PolynomialRing(K, 'x')
    assert len(assoc) == l
    f = R.lagrange_polynomial(assoc)
    return f.list()


def dfs(keys: list[int], start: float, count: list[int], assoc: list[tuple[int, int]], p: int, xs: dict[int, list[int]], shares: dict[int, list[int]]) -> bytes | None:
    count[0] += 1
    if count[0] % 10000 == 0:
        print(f'# ({time.time() - start:.2f}s) count: {count[0]}')
    if len(keys) == 0:
        res = solve_lagrange(p, assoc)
        for v in res:
            bs = long_to_bytes(int(v))
            if bs.startswith(b"ISITDTU{"):
                return bs
        return
    xlist = xs[keys[0]]
    sharelist = shares[keys[0]]
    assert len(xlist) == len(sharelist)
    seq = range(0, len(xlist))
    for perm in itertools.permutations(seq):
        for i, index in enumerate(perm):
            assoc.append((xlist[i], sharelist[index]))
        ret = dfs(keys[1:], start, count, assoc, p, xs, shares)
        if ret is not None:
            return ret
        for _ in seq:
            assoc.pop()
    return None


def share_mixer_decipher(p: int, start: float, xs: dict[int, list[int]], shares: dict[int, list[int]]) -> bytes:
    keys = list(xs)
    count = [0]
    res = dfs(keys, start, count, [], p, xs, shares)
    if res is None:
        raise ValueError("Failed to find the flag")
    return res


def main() -> None:
    start = time.time()
    if not local:
        io.recvuntil(b'Send a suffix that:')
        io.recvline()
        problem = io.recvline().strip().decode()
        prefix = problem.split('"')[1]
        print(f'# ({time.time() - start:.2f}s) {prefix = }')
        suffix = pow.find(prefix)
        print(f'# ({time.time() - start:.2f}s) {suffix = }')
        io.recvuntil(b"Suffix: ")
        io.sendline(suffix.encode())
    io.recvuntil(b"p = ")
    p = int(io.recvline().strip().decode())
    io.recvuntil(b"Gib me the queries: ")
    xs = [1, 2, 3, 4, 4, 5, 5, 6, 6] + sum(([x] * max((x - 1) // 2, 1) for x in range(7, 33)), []) + [28, 29, 30, 30, 31, 31, 32, 32, 32]
    print(f'# {len(xs) = }')
    io.sendline(" ".join(map(str, xs)).encode())
    io.recvuntil(b"shares = ")
    shares = io.recvline().strip().decode()[1:-1].split(", ")
    shares = list(map(int, shares))
    xs = decouple_multiset(xs)
    shares = decouple_multiset(shares)
    print(f'# ({time.time() - start:.2f}s) shares obtained')
    print(f'# length_distrib: {[(v, len(xs[v])) for v in xs]}')
    print(f'# #combinations: {reduce(lambda x, y: x * y, (len(xs[v]) for v in xs))}')
    print(f'# {p = }')
    flag = share_mixer_decipher(p, start, xs, shares)
    print(flag.decode())


if __name__ == "__main__":
    main()
ShareMixer2

素数 p が決められる。flag を 1 つ含み他はランダムな係数を持つ、次数 32 の多項式 cs をジャッジが決めるので、長さ 32 以下の数列 xs を送れ。それの各値を代入した結果をシャッフルして返す。」という問題。
ShareMixer1 に比べて xs の長さ制限が短くなった代わりに、PoW を要求されなくなった。

p-1 が 32 の倍数であれば mod p で 1 の 32 乗根が存在するようになり、さらに xs としてそれらを与えると戻ってきた値の合計が 32 * cs[0] になる。
何回も接続して 1 の 32 乗根が存在するようになるまで (32 | p-1 が成立するまで) 待ち、さらに 1 の 32 乗根を xs として与えて cs[0] を取得して、flag が cs[0] に来るまでガチャを回す。試行回数の期待値は 32 * 32 = 1024 回。

# https://stackoverflow.com/questions/65579133/every-time-i-run-my-script-it-returns-curses-error-must-call-setupterm-firs
import os
os.environ['TERM'] = 'linux'
os.environ['PWNLIB_NOTERM'] = '1'


import sys
import time
from pwn import remote, process, context
from Crypto.Util.number import long_to_bytes


context.log_level = 'error'
local = len(sys.argv) == 1
def get_io():
    return process(["python3", "chall.py"]) if local else remote(sys.argv[1], int(sys.argv[2]))


l = 32


def try_one(start: float) -> None:
    io = get_io()
    while True:
        io.recvuntil(b"p = ")
        p = int(io.recvline().strip().decode())
        if (p - 1) % 32 == 0:
            break
        io.close()
        io = get_io()
    K = GF(p)
    g = K.multiplicative_generator()
    base_l = g ** ((p - 1) // l)
    io.recvuntil(b"Gib me the queries: ")
    xs = [int(base_l ** i) for i in range(l)]
    print(f'# {len(xs) = }')
    io.sendline(" ".join(map(str, xs)).encode())
    io.recvuntil(b"shares = ")
    shares = io.recvline().strip().decode()[1:-1].split(", ")
    shares = list(map(int, shares))
    print(f'# ({time.time() - start:.2f}s) shares obtained')
    io.close()
    cs0 = sum(shares) * pow(l, -1, p) % p
    flag = long_to_bytes(cs0)
    if flag.startswith(b'ISITDTU{'):
        print(flag.decode())
        return flag.decode()


def main() -> None:
    start = time.time()
    count = 0
    while True:
        print(f'# ({time.time() - start:.2f}s) trial {count}')
        res = try_one(start)
        if res is not None:
            print(res)
            return
        count += 1


if __name__ == "__main__":
    main()
Sign

競技終了後に解いた。
「n が未知な状態で PKCS#1 v1.5 形式でランダムなデータの署名を返すオラクルと、フラグに対して pow(flag, d, n) を返すオラクルが与えられる。flag を特定せよ。」という問題。

PKCS#1 v1.5 形式の署名は 0x1ff....ffXXXX (XXXX は対象のハッシュ値など) の形の整数を d 乗したものになることに注意すると、署名の e 乗の差分はほとんど n の倍数 (差は高々 257 ビット整数程度) であることに着目する。
Approximate GCD をやれば良い。

# https://stackoverflow.com/questions/65579133/every-time-i-run-my-script-it-returns-curses-error-must-call-setupterm-firs
import os
os.environ['TERM'] = 'linux'
os.environ['PWNLIB_NOTERM'] = '1'


import sys
import time
from pwn import remote, process
from Crypto.Util.number import long_to_bytes


local = len(sys.argv) == 1
io = process(["python3", "chall.py"]) if local else remote(sys.argv[1], int(sys.argv[2]))


def approx_gcd(d: list[int], approx_error: int) -> int:
    """
    Returns q where d[0] ~= qx and d[i]'s are close to multiples of x.
    The caller must find (d[0] + q // 2) // q if they want to find x.
    """
    l = len(d)
    M = Matrix(ZZ, l, l)
    M[0, 0] = approx_error
    for i in range(1, l):
        M[0, i] = d[i]
        M[i, i] = -d[0]
    L = M.LLL()
    for row in L:
        if row[0] != 0:
            quot = abs(row[0] // approx_error)
            return quot


def get_random_sig() -> int:
    io.recvuntil(b'> ')
    io.sendline(b'1')
    io.recvuntil(b'sig = ')
    return int(io.recvline().strip().decode(), 16)


def get_flag_sig() -> int:
    io.recvuntil(b'> ')
    io.sendline(b'2')
    io.recvuntil(b'sig = ')
    return int(io.recvline().strip().decode(), 16)


def main() -> None:
    start = time.time()
    e = 11
    count = 14
    sigs: list[int] = []
    for _ in range(count):
        sigs.append(get_random_sig())
    print(f'# ({time.time() - start:.2f}s) {sigs[0].bit_length() = }')
    diff = [abs(sigs[i]**e - sigs[i - 1]**e) for i in range(1, count)]
    q = approx_gcd(diff, 2**256)
    n = (diff[0] + q // 2) // q
    print(f'# ({time.time() - start:.2f}s) {n.bit_length() = }')
    print(f'# ({time.time() - start:.2f}s) {hex(pow(sigs[0], e, n)) = }')
    fs = get_flag_sig()
    flag = long_to_bytes(pow(fs, e, n))
    index = flag.find(b'ISITDTU')
    print(flag[index:].decode())


if __name__ == "__main__":
    main()

(2024-11-01 23:36 修正: n を求めるところで四捨五入の代わりに間違えて切り捨てをしてしまっていたので、修正した。)

まとめ

SpookyCTF 2024 よりはマシだったがこれもちょっと不親切なところがあった。

SpookyCTF 2024 writeup

SpookyCTF 2024 にチーム zk-aficionado で参加した。日本時間で 2024-10-26 08:00 から 2024-10-28 08:30 まで。

結果は 122/831 位。
crypto 問題だけ解いた感想としてはかなりワクワクコンテストだった。来年以降の犠牲者を減らすべく解けた問題について書く。
問題で与えられるソースコードや説明が self-contained ではなく、いろいろな推測をする必要があることに注意。

解法集

crypto

the-moth-flies-at-dawn

単語が並べられた wordList.txt と、それらのうちどれか一つのハッシュ値 (アルゴリズム不明) が書かれた hash.txt が与えられるので、どれのハッシュ値か当てる問題。
View Hints をすると「SHA256 を調べろ」(It would be a SHAme if all 256 of these meals went to waste.) と書いてあるので、それによってハッシュアルゴリズムに当たりをつける。

from hashlib import sha256


def main() -> None:
    with open('hash.txt', 'r') as f:
        hash_value = bytes.fromhex(f.read().strip())
    with open('wordList.txt', 'r') as f:
        words = f.read().splitlines()
    for word in words:
        if sha256(word.encode()).digest() == hash_value:
            print(f'NICC{{{word}}}')
            return


if __name__ == '__main__':
    main()
encryption-activated

ciphertext[i] = plaintext[i] - (letter + i) によって暗号化されたデータが与えられるので、letter を推測して復元せよという問題。
単に letter を総当たりしてそれっぽいものを探せば良いが、与えられる flag.output は最後に改行文字があり、それを無視して復元する必要があることに注意。

def mycipher(myinput: str, myletter: str) -> None:
    rawdecrypt = list(myinput)
    for iter in range(0,len(rawdecrypt)):
        rawdecrypt[iter] = chr(ord(rawdecrypt[iter]) + ord(myletter))
        myletter = chr(ord(myletter) + 1)
    if any(c < 0x20 or c > 0x7e for c in map(ord, rawdecrypt)):
        return
    encrypted = "".join(rawdecrypt)
    print("NICC{" + encrypted + "}", myletter)


def main() -> None:
    with open("flag.output", "rb") as f:
        cipher = f.read().strip()
    for c in range(32, 127):
        mycipher(cipher.decode(), chr(c))


if __name__ == "__main__":
    main()
tracking-the-beast

問題文のストーリー部分は完全に無視できて、重要なのは以下の部分だけ。

  • the curve y^2 = x^3 + 73x + 42 mod 251
  • Flag Format: NICC{(##,##)}
  • at (26,38)
    • おそらく基点 (ベースとなる点)
  • A large depiction of Green Lantern with 13 rings on his fingers

これらのことから、点が答えなら与えられた基点のスカラー倍くらいしか方法がないことが推測できるので、(26,38) * 49 = (72,17) が答えである。フラグは NICC{(72,17)} である。

計算には SageMath などを使えば良い。SageMath を使うと以下のように計算できる。

sage: E = EllipticCurve(GF(251), [73, 42])
sage: E
Elliptic Curve defined by y^2 = x^3 + 73*x + 42 over Finite Field of size 251
sage: E(26, 38) * 49
(72 : 17 : 1)

まとめ

crypto じゃなくて guessing を名乗ってくれ

AlpacaHack Round 5 (Crypto) writeup

AlpacaHack Round 5 (Crypto) に参加した。日本時間で 2024-10-12 12:00 から 2024-10-12 18:00 まで。

結果は 9/247 位

解法集

XorshiftStream

(key を hex string にしたもの) + (key と FLAG を xor したもの) を Xorshift で作ったストリームによって暗号化する (XOR)。

前半部分は平文のバイトが [0x30,0x39] または [0x61,0x66] の範囲に収まる。ここから、

  • 第 7 ビットが常に 0
  • 第 5 ビットが常に 1
  • 第 4 ビット xor 第 6 ビットが常に 1

あたりが言えるので、乱数ストリームの該当する位置のビットがわかる。
Xorshift はビットごとに見ると GF(2) の上の線型写像になっているので、1 << 0 から 1 << 63 までの 64 通りの seed によって得られる乱数ストリームのいくつかの xor になっているはず。それを線型代数で求める。

https://doc.sagemath.org/html/ja/tutorial/afterword.html#sagepython
にあるように、xor の記号が ^^ だと知った時かなり嫌な気持ちになった。(時間を無駄にした。)

実装は Sage でやった。

output = bytes.fromhex(open("output.txt").read().strip())
K = GF(2)


class XorshiftStream:
    def __init__(self, key: int):
        self.state = key % 2**64

    def _next(self):
        self.state = (self.state ^^ (self.state << 13)) % 2**64
        self.state = (self.state ^^ (self.state >> 7)) % 2**64
        self.state = (self.state ^^ (self.state << 17)) % 2**64
        return self.state

    def encrypt(self, data: bytes):
        ct = b""
        for i in range(0, len(data), 8):
            pt_block = data[i : i + 8]
            ct += (int.from_bytes(pt_block, "little") ^^ self._next()).to_bytes(
                8, "little"
            )[: len(pt_block)]
        return ct


def next(x: int) -> int:
    x = (x ^ (x << 13))
    x = (x ^ (x >> 7))
    x = (x ^ (x << 17))
    return x


def get_synd(dat: bytes, i: int) -> list[int]:
    u = []
    d = dat[i]
    # 0x3? or 0x6?
    u.append(d >> 7 & 1)
    c3a = d >> 5 & 1
    u.append(c3a ^^ 1)
    u.append((d >> 4 ^^ d >> 6 ^^ 1) & 1)
    return u


def main() -> None:
    keylen = len(output) // 3
    print(f'# {keylen=}')

    # Collect constraints
    units = []
    for h in range(64):
        tmp = XorshiftStream(1 << h)
        dat = tmp.encrypt(b'\x00' * (keylen * 2 + 7))
        u = []
        for i in range(keylen * 2):
            u += get_synd(dat, i)
        units.append(u)
    synd = []
    for i in range(keylen * 2):
        synd += get_synd(output, i)

    # Solve the equation
    A = matrix(K, units)
    b = matrix(K, [synd])
    print(f'# {A=}')
    print(f'# {b=}')
    x = A.solve_left(b)
    print(f'# {x=}')

    # Decrypt the flag
    seed = 0
    for i in range(64):
        seed |= int(x[0, i]) << i
    xss = XorshiftStream(seed)
    decrypted = xss.encrypt(output)
    key = bytes.fromhex(decrypted[:keylen*2].decode())
    flag = [decrypted[keylen*2+i] ^^ key[i] for i in range(keylen)]
    print(bytes(flag).decode())


if __name__ == "__main__":
    main()

NNNN

「n[0] = p * q, n[i] = (p + d[i]) * (q + d[i]) (1 <= i <= 3) が与えられる。ただし p, q は 768 ビットで d[i] は 192 ビット。このとき p, q, d[i] を求めよ。」という問題。

n[i] - n[0] = d[i] * (p + q) + d[i]^2 なので、Approximate GCD を使って p + q を求めれば良い。しかし単純にやると以下のような問題が発生する。

  • p + q が 770 ビットになる (期待される値より 2 倍くらい大きい)
  • Approximate GCD において、どの値を 0 番目として使うかによって p + q の値が異なる

これらの原因を調査したところ、Approximate GCD の値として得られる値が d[i] の 1/2 の値だった。
原因は、d[i] が常に偶数であることと、Approximate GCD が GCD としてなるべく大きい値を得ようとする (その結果戻り値が小さくなる) ことであった。

実装は Sage でやった。

from Crypto.Util.number import long_to_bytes


for line in open('output.txt').readlines():
    exec(line, globals())
ns = [n0, n1, n2, n3]
cs = [c0, c1, c2, c3]


def approx_gcd(d: list[int], approx_error: int) -> int:
    """
    Returns q where d[0] ~= qx and d[i]'s are close to multiples of x.
    The caller must find d[0] // q if they want to find x.
    """
    M = Matrix(ZZ, 3, 4)
    M[0, 0] = approx_error
    M[0, 1] = d[1]
    M[0, 2] = d[2]
    M[1, 1] = -d[0]
    M[2, 2] = -d[0]
    L = M.LLL()
    for row in L:
        if row[0] != 0:
            quot = abs(row[0] // approx_error)
            return quot


def main() -> None:
    # Find p and q
    d = [n1 - n0, n2 - n0, n3 - n0]
    k = 2 ** 400
    quot = approx_gcd(d, k) * 2
    rest = d[0] - quot * quot
    assert rest % quot == 0
    p_plus_q = rest // quot
    print(f'# {p_plus_q = }')
    d = p_plus_q^2 - 4 * n0
    sqrtd = d.sqrt()
    assert sqrtd^2 == d
    p = (p_plus_q + sqrtd) // 2
    q = (p_plus_q - sqrtd) // 2
    assert p * q == n0

    # Decrypt
    factors = []
    for val in ns:
        quot = (val - n0) // p_plus_q
        assert val == n0 + quot * quot + quot * p_plus_q
        factors.append((p + quot, q + quot))
    for i in range(4):
        (pp, qq) = factors[i]
        m = pow(cs[i], pow(65537, -1, (pp - 1) * (qq - 1)), ns[i])
        print(long_to_bytes(m).decode('ascii'), end='')
    print()


if __name__ == "__main__":
    main()

SchnorrLCG

「Schnorr 署名方式で署名と認証を行うサーバーがある。特定のメッセージの署名を偽造して受理せしめよ。」という問題。

x を秘密鍵とする。乱数 k が線形合同法 k[i+1] = a * k[i] + b (mod q) で生成される。このことを利用して、s[i] = k[i] + x * e[i] (mod q) であることから
s_{i+1} - as_i \equiv b + xe_{i+1} - xae_i \pmod q
という関係式ができる。これを LLL で解くことになる。(ECDSA に対する同じような攻撃を参考にする。)

詳細は実装に譲るが、注意点は以下。

  • 最終的に得られるベクトルの各要素が big = 2^1024 程度になるようにする
    • x, a は 384 ビットで xa は 768 ビットであるため、それが現れる位置の大きさが big 程度になるように係数で調整する

実装は Sage でやった。

# https://stackoverflow.com/questions/65579133/every-time-i-run-my-script-it-returns-curses-error-must-call-setupterm-firs
import os
os.environ['TERM'] = 'linux'
os.environ['PWNLIB_NOTERM'] = '1'


import sys
import time
import subprocess
from pwn import process, remote
from Crypto.Hash import SHA256
from Crypto.Util.number import long_to_bytes


local = len(sys.argv) == 1
io = process(["sh", "./run.sh"]) if local else remote(sys.argv[1], int(sys.argv[2]))


def get_hashcash(cmd: str) -> str:
    out = subprocess.check_output(cmd.split()).decode().strip()
    return out


def fetch_sign(msg: bytes) -> tuple[int, int]:
    io.recvuntil(b'option> ')
    io.sendline(b'1')
    io.recvuntil(b'message(in hex)> ')
    io.sendline(msg.hex().encode())
    io.recvuntil(b'e=')
    e = int(io.recvline().strip().decode())
    io.recvuntil(b's=')
    s = int(io.recvline().strip().decode())
    return e, s


def find_x(es: list[tuple[int, int]], q: int) -> int:
    count = len(es)
    big = 2 ** 1024
    M = Matrix(ZZ, count + 5, count + 5)
    for i in range(count - 1):
        (e, s) = es[i]
        (en, sn) = es[i + 1]
        M[count, i] = -sn * big
        M[count + 1, i] = s * big
        M[count + 2, i] = big
        M[count + 3, i] = en * big
        M[count + 4, i] = -e * big
    M[count, count] = big
    M[count + 1, count + 1] = big // (2 ** 384)
    M[count + 2, count + 2] = big // (2 ** 384)
    M[count + 3, count + 3] = big // (2 ** 384)
    M[count + 4, count + 4] = big // (2 ** 768)
    for i in range(count):
        M[i, i] = q * big
    L = M.LLL()
    for row in L:
        if abs(row[count]) != big:
            continue
        coef = row[count] // big
        x = row[count + 3] // M[count + 3, count + 3] // coef
        print(f'# {x = }')
        print(f'# {x.bit_length() = }')
        break
    else:
        raise ValueError('x not found')
    return x


def _hash(message: bytes, r: int, q: int):
    hash_res = SHA256.new(message + long_to_bytes(r))
    return int(hash_res.hexdigest(), 16) % q


def forge_sign(message: bytes, x: int, g: int, p: int) -> tuple[int, int]:
    k = 1
    q = (p - 1) // 2
    r = pow(g, k, p)  # r = g^k mod p
    e = _hash(message, r, q)  # e = H(m || r)
    s = (k + x * e) % q  # s = (k + x * e) mod q
    return (e, s)


def main() -> None:
    start = time.time()
    io.recvuntil(b'running the following command:')
    io.recvline()
    cmd = io.recvline().strip().decode()
    io.recvuntil(b'hashcash token: ')
    io.sendline(get_hashcash(cmd).encode())
    print(f'# ({time.time() - start:.2f}s) hashcash token sent')

    io.recvuntil(b'p=')
    p = int(io.recvline().strip().decode())
    io.recvuntil(b'g=')
    g = int(io.recvline().strip().decode())
    io.recvuntil(b'pub_key=')
    pub_key = int(io.recvline().strip().decode())
    q = (p - 1) // 2

    count = 5

    # collect
    es = []
    for _ in range(count):
        (e, s) = fetch_sign(b'koba')
        es.append((e, s))
    print(f'# ({time.time() - start:.2f}s) signatures collected')

    # solve
    x = find_x(es, q)
    print(f'# ({time.time() - start:.2f}s) x found')
    assert pow(g, x, p) == pub_key

    # forge + submit
    target_msg = b'give me flag'
    (e, s) = forge_sign(target_msg, x, g, p)
    io.recvuntil(b'option> ')
    io.sendline(b'2')
    io.recvuntil(b'message(in hex)> ')
    io.sendline(target_msg.hex().encode())
    io.recvuntil(b'e> ')
    io.sendline(str(e).encode())
    io.recvuntil(b's> ')
    io.sendline(str(s).encode())
    io.recvline()
    io.recvuntil(b'Here is your flag: ')
    print(io.recvline().decode().strip())


if __name__ == "__main__":
    main()

まとめ

反省点は
(i) 基本的な道具 (線型代数、Approximate GCD) に対する理解不十分
(ii) NTRU に対するリサーチ不足
(iii) 実装力の衰え
あたりだと思われる。

単純に典型知識を適用するだけでは解けず、中身の理解を要求するという点で、問題の質はかなり良かったと思われる。まさに実装力不足で全完できなかったのが悔やまれる。

あと Sage 祭り、LLL 祭りだった気がする