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

セキュリティー・CTF

The FIPS 140-3 Go Cryptographic Module - The Go Programming Language

  • The FIPS 140-3 Go Cryptographic Module
  • Go の暗号技術ライブラリーを FIPS 140-3 に対応させる話
  • 意見の食い違いに折り合いをつけた
    • "FIPS 140-3 has strict rules on how cryptographic randomness is generated, which essentially enforce the use of a userspace CSPRNG. Conversely, we believe the kernel is best suited to produce secure random bytes"
    • (FIPS 140-3 には乱数生成方法に関する厳格なルールがあり、ユーザースペースの暗号論的擬似乱数生成器を使うことを強制する。正反対に、我々はカーネルこそが安全な乱数バイトを作るのに最適な場所だと信じている。)
  • PQC も対応した。
    • "The post-quantum ML-KEM key exchange (FIPS 203), introduced in Go 1.24, is also validated, meaning crypto/tls can establish FIPS 140-3 compliant post-quantum secure connections with X25519MLKEM768."
    • Go の暗号技術チームは仕事が早いし正確だ。

Go Assembly Mutation Testing

  • Go Assembly Mutation Testing (Go のアッセンブリー改変テスト)
  • コードカバレッジの検査は基本的には if 文の両方の分岐を通ったことをテストするものだが、暗号技術のコードには if 文がない。
    • "The problem is that if you run code coverage, you’ll see all “branches” light up, even if all tests actually discard the result of one of them. We could have other untested paths like #20040 and not know about it."
    • if 文なしでどのように場合分け処理を実装するのか? 一定時間演算へようこそ。
      • 特定の関数内部ではアッセンブリーのレベルでも分岐命令 (x86-64 の jne など) がなくなることが期待されるしコード中にも単純な if 文がないので、常にその関数の全ての命令が実行される。
  • mutation testing (改変テスト) とは?
    • ソースコードを実際に書き換えてテスト結果が変わらなかったら、その書き換えた部分はテストされていないとみなす
    • 普通のコードなら分岐命令になるであろう場所 (c >= 0 なら 1 増やす) などが、両方の分岐を通っているかを試験する
      • そのような場所は arm64 だと SUBCS などの、フラグを読むが分岐はしないような命令で実現される
      • a = carryAdd(a, b, c) の代わりに a = a + b にしたらどうなるか、など

技術一般

Faster Go maps with Swiss Tables - The Go Programming Language

  • Go の map 内部のハッシュテーブルを Swiss Table に変えた話
  • Go の map は (K comparable という制約があるので) 平衡木だと思っていたが、実はずっとハッシュテーブルだった。


Notion Task Manager Guide: One Table for Goals, Projects & Tasks

  • Notion で全てのタスクを単一 DB に突っ込む話
  • Notion 上で一つの DB にプロジェクトも細かいタスクも全部積んで、relation で親子関係を表現する
    • 「双方向リレーション」は必要 (これをオンにしないと辺が無向辺になり、親子関係を適切に表現できない)


ディープコードリーディングのすすめ｜牛尾 剛

  • "もうだめならどうでもいいや。と思いながら思いついた戦略は次の通りアホみたいに単純である
    • 自分に特に関係ある主要開発者のすべてのPRを読む
    • １週間に、２回ほど時間を予約して、他の人のPRを読む時間を作る"
  • "私が参考にしている勉強法の YouTuber の人が、新しい事を学ぶときはインデックスつまり、概要をざっとつかんでから本とかでも読むと良いと言っていたので、同じストラテジをとった。"
  • "私はこのトランジションに３日使ったが、自分がかつて感じたことのない「コンフィデンス」を感じていた。どのPRを観ても全然簡単に理解できるし、時間もかからない。これが、技術イケメンの皆さんが観てた風景なのか。"
  • 個人的にも深く理解したとたん作業スピードが劇的に上がった経験があるので、詰まった時の一手として利用したい
  • できたら大きいけどできるかどうかわからない、でも今のまま待っていてもジリ貧、みたいなときに勇気を出したい

Be Careful Zero-Copying Strings with serde

  • serde (Rust で de facto standard な直列化ライブラリー) の面白機能の話
  • serde には文字列の参照で返す機能があるが、JSON などで escape された文字列だと発動せず Err(...) になる
    • 例えば JSON 文字列 {"a": "b\nc"} から脱直列化しようとすると、結果に含まれる文字列 (b, 改行文字, c をこの順に並べた文字列で、hex は 62 0a 63) がもとの JSON の部分バイト列になっておらず、serde が困って Err(...) にする
  • できる時だけ参照にしたいなら Cow<'a, str> に #[serde(borrow)] を付けよう

思想一般

Issue 715 – iOS Dev Weekly

  • "Programming communities can easily become tribal. It’s easy for people to slip into thinking that “their” programming language is the best, and nothing written with other languages can be good."
    • (プログラミングコミュニティーは容易に排外主義的になり得る。「自分たちの」プログラミング言語が最高で、他の言語で書かれたものが良いことなどありえない、という考えに陥るのはたやすい。)

『滅私』

  • https://www.amazon.co.jp/dp/B0D7VM318M
  • ミニマリストに関する物語と思いきや、実は矛盾を抱えた人間の物語かもしれない。登場人物はミニマリストの典型というよりは、自分の問題から逃げ回ってミニマリズムなどに傾倒する人間の典型に見えた。

『やり抜く力 GRIT(グリット)』

  • https://www.amazon.co.jp/dp/4478064806
    • "エキスパートたちは、すでに得意なところをさらに伸ばすのではなく、具体的な弱点の克服に努める。あえて自分がまだ達成していない困難な目標を選ぶのだ。"

山口周シリーズ

桜林 直子（サクちゃん）シリーズ

『フィードバック入門』

  • https://www.amazon.co.jp/dp/b06vvq8v36
    • "大人が何かを学ぶとき、行動を変容させるときには一定の「痛み」がともなうのです。しっかりと相手に向き合い、このセッションの目的を伝え、そのうえで、ともに改善していこうと誘うのがポイントです。"


叱られるととても傷つく人｜精神科医 益田裕介

"勉強だったら1日30分できるんだったら、30～35分を頑張ってみる。
楽すぎず、苦しすぎない、ちょうど中間ぐらい、適度なストレスがかかってる状態がラーニングゾーンと呼ばれるところなので、楽すぎるコンフォートゾーンにいすぎないで、かといって苦しすぎないゾーンにいればいいんです。
精神科の治療というのは二つポイントがあって、仕方がないということと、生まれてきてよかったと思える瞬間、この二つなんです。"

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.sage の approx_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.sage の approx_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 を名乗ってくれ