CTFのCryptoにおける細かな話題まとめ

CTFにおけるCrypto入門とまとめの1つです。

その他の解法方針

• 中間一致攻撃 Meet-in-the-middle attack
  • https://ja.wikipedia.org/wiki/%E4%B8%AD%E9%96%93%E4%B8%80%E8%87%B4%E6%94%BB%E6%92%83
  • 競プロで半分全列挙と言われる解法は、そうは呼ばれずMitMと呼ばれてる雰囲気がある
  • LINE CTF 2022 crypto challenges writeup - ふるつき
  • 1337UP LIVE CTF - kRSA https://ctftime.org/task/29474 / https://discord.com/channels/870275171938873395/1307444563002265620/1307641768396984321
    • c = k^e mod nでc,e,nが既知で、kが32bitsの乱数であり、リクエスト毎に生成されるときに、kを全探索して求める問題
    • 時間が厳しいので工夫が必要なのだが、kが乱数でリクエスト毎に生成されることを利用してkが合成数になるまでガチャって頑張る方法がある
    • kを17bitsで全探索して、c/(k^e)をメモしておき、kを17bitsで再度全探索して、k^eがメモの中に無いかを探して、あればそれと持ってきて答えることで半分全列挙する
      • つまり、k=a*bであり、かつ、a,bが16,17bitsである因数分解ができるkを乱数ガチャを繰り返して引き当て、その状態で半分全列挙をする
• 誕生日攻撃/鳩ノ巣原理
• 総当たり攻撃
  • 2**32くらいの簡単な計算ならC++とかの速い言語を使って総当たりしてもいい。競プロとは違い計算は数日のコンテスト中に終了すればいいので場合によってはぶん回せる
• 論文を見つける
  • 論文を見つけて実装するという方針が解説に書いてあったりする
  • 検索キーワード例
    • "rsa factoring crt exponents public exponent" -> https://eprint.iacr.org/2022/271.pdf (UniCTF2023 Mayday Mayday https://github.com/hackthebox/uni-ctf-2023/tree/main/uni-ctf-2023/crypto/%5BMedium%5D%20Mayday%20Mayday )
    • "y2=x3-12x-11 elliptic curve order" -> https://arxiv.org/pdf/2301.00711 (https://chocorusk.hatenablog.com/entry/2023/04/23/183504#dice-vs-kymn-crypto )
    • "elliptic curve torsion group Z/6Z" -> https://web.math.pmf.unizg.hr/~duje/pdf/Z6DPT.pdf (https://chocorusk.hatenablog.com/entry/2023/04/23/183504#dice-vs-kymn-crypto )
• サイドチャネル攻撃
  • AESの電力解析 https://zenn.dev/kurenaif/articles/ae83691511b966
  • 圧縮率の変化をオラクルとして、サイドチャネルで情報を抜き出す
    • CRIMEやBREACH攻撃
    • GlacierCTF 2025 - AES Zippy https://mcsch.dev/posts/aes_gcm_ctf/
    • https://furutsuki.hatenablog.com/entry/2021/03/16/095021#%E5%B9%B3%E6%96%87%E3%81%8C%E3%83%95%E3%83%A9%E3%82%B0%E3%81%A8%E9%80%A3%E7%B5%90%E5%9C%A7%E7%B8%AE%E3%81%95%E3%82%8C%E3%81%A6%E3%81%8B%E3%82%89%E6%9A%97%E5%8F%B7%E5%8C%96%E3%81%95%E3%82%8C%E3%82%8B%E5%9C%A7%E7%B8%AE%E3%82%B5%E3%82%A4%E3%83%89%E3%83%81%E3%83%A3%E3%83%8D%E3%83%AB%E6%94%BB%E6%92%83--compression-oracle
  • タイミング攻撃: 評価にかかる時間を計測することで隠匿された情報を抜き出す手法
    • https://book.jorianwoltjer.com/cryptography/timing-attacks
    • https://www.da.vidbuchanan.co.uk/blog/uoftctf-timed-aes.html
• 実装ミスが原因で解けるかも
  • pow(m, self.e, self.n)でm=-1すると、n-1が出てくる
  • pythonでマルチバイト文字を入れると、str的には1文字だけどbytesだと3文字みたいな状況起きない？
  • ^をxorではなくべき乗と勘違いしてませんか？
  • 負数入れられない？0は？
• 「ピピー！import secrets警察です！」https://www.youtube.com/watch?v=DPYlSEbIGsY
• 半分全列挙とかメモ化とかが使える
• 通常の実装と違う所は無いか？通常の実装は安全だから広がっているはず
  • ECDSA https://jia.je/ctf-writeups/2025-09-04-nullcon-berlin-hackim-2025-ctf/simple-ecdsa.html
  • DES https://jia.je/ctf-writeups/2025-09-04-nullcon-berlin-hackim-2025-ctf/narrow-des.html
• 二分探索/三分探索
  • https://blog.y011d4.com/20210606-zh3r0-ctf-writeup#in_jection
• 確率をうまく活用する
  • ランダムに得られる要素について何回も試行できる場合は上手くいく条件の乱数を引き当てるまでガチャる
    • ShareMixer2 https://koba-e964.hatenablog.com/entry/2024/11/01/103550
  • 試行回数を増やせば結果に何か偏りがあり、それが活用できるんじゃないか

ツール

• pycryptodome: 暗号計算に便利なアレコレが実装されている。pycryptoはもう古いので似ているが使わないこと
  • from Crypto.Util.number import *みたいに読み込まれているのはコレ
• sagemath: 数値計算に便利なアプリケーション
  • docker run -v ${PWD}:/mnt --rm -it sagemath/sagemath:10.3 /bin/bash
• ptrlib/pwntools: サーバとのリアクティブなやり取りに便利なライブラリ
• z3: SAT/SMTソルバー
  • Z3 Python CTF https://github.com/ViRb3/z3-python-ctf
  • ImaginaryCTF 2022 writeup - st98 の日記帳 - コピーのhash
    • sha42という自作関数を使ったハッシュ値が得られて平文を特定する問題
    • pythonで自作関数が用意されているならそのままz3に流用してサクッと解けるかも
  • z3を使って高次方程式を解く
    • Python PyMI.vn ニュース
    • https://furutsuki.hatenablog.com/entry/2020/12/27/160652#Crypto-QR
    • https://zenn.dev/hk_ilohas/articles/wani2024-writeup#speedy-%5Bhard%5D
• CyberChef: サクッとエンコードなどを試したいときに便利