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

hamayanhamayan's blog

CTFのCryptoにおけるハッシュまとめ

Security

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

Hash

  • 一方向ハッシュ関数, メッセージダイジェスト関数、メッセージ要約関数、暗号的ハッシュ関数
  • 暗号学的ハッシュ関数（RFC4270に記載がある）
    • 第１原像攻撃困難性: ハッシュ値Hに対して、H=HASH(M)となるような入力Mを計算することが困難。つまり、狙ったハッシュ値を出力させる入力を作ることが困難
    • 第２原像攻撃困難性: 入力値M1に対して HASH(M1)=HASH(M2)となるようなM1と異なるM2を計算することが困難
    • 衝突困難性（強衝突耐性）: ハッシュ値が同じになる(M1,M2)の組を計算することが困難。原像攻撃とは異なり、どんなハッシュ値でも成り立つとき
  • 使われる所
    • ソフトウェアの改ざん検知
    • PBE: Password Based Encryption, 暗号化ではないがパスワードとソルトを使った辞書攻撃を防ぐアレ
      • これには計算空間量、また、探索空間量をストレッチングする効果がある
    • MAC: メッセージ認証コード
    • デジタル署名
    • 疑似乱数生成器
    • ワンタイムパスワード
  • HMAC: Keyed-Hashing for Message Authentication Code
  • 文字列からハッシュ取るときはecho -n "[plain]" | md5sumみたいにすること
    • -nを入れると最後に改行を入れずにハッシュが取れる。有無でハッシュが変わる
  • リプレイ攻撃には弱い（シーケンス番号、タイムスタンプ、ノンスとかを使いましょう）

アルゴリズム

関連ワード

  • Merkle-Damgard: MD5, SHA-1, SHA-2が持つ構造。どれも似たようなアルゴリズム
  • ソルト: ハッシュを作成する前に適当な文字列をくっつける
  • ストレッチング: ハッシュ値の総当たりを大変にするために何重もハッシュを計算すること
    • 例えばbcryptoのようにハッシュブルートフォースに時間がかかるようにしてあるものがある
  • HMAC: 鍵とハッシュ関数を用いてメッセージに改ざん防止用の符号を付与するアルゴリズム
    • Poly1305: ブロック暗号（AES）を使ってMACを作成
    • HMAC-SHA1
    • HMAC-MD5
    • HMAC-SHA256
    • HKDF: HMACベースのKDF（鍵導出関数）
      • KDF: 鍵導出関数、鍵を構成する初期値を受け取って、1つないしは複数の暗号学的に強い鍵を生成することができる仕組み
      • 手順
        1. 入力となる鍵の初期値(IKM:Input Keying Material)を受け取り、固定長となるPRK(PesedoRandom Key)を取得する
        2. 生成したPRKを複数のPRKへと拡張する
  • ハッシュ衝突攻撃
    • RFC4270で定義されている衝突攻撃の要件はハッシュのビット長Lに対して、2の2分のL乗回未満の攻撃で突破できること
    • MITM, Meet-in-the-Middle Attack: ハッシュの衝突が起きれば大丈夫という状況で2つの平文A,Bに対してハッシュ値をたくさん取っていくことで、一致するハッシュと平文の組を探そうとする方針
    • 誕生日のパラドックス Birthday Attack
      • 全探索したときに衝突する組が見つかる確率は集合全体がNであればsqrt(N)回の試行で50%の確率で見つけられる
      • 確率論における生日パラドックスに根ざしています。n個の異なる値を持つハッシュ関数において、約√n回の試行で50%の確率で衝突が発生する現象 WikipediaMahalozを利用します。 Wikipedia +2実際の攻撃実装では、メモリ効率を考慮したFloydsサイクル検出アルゴリズムやPollardのrho法が使用されます。
    • 差分解析
    • 線形解析
    • z3で衝突を解析

Length Extension Attack

  • 特定のハッシュ関数（Merkle-Damgard）に対して[unknown][known]という平文に対してハッシュ化されたものが判明しているときに、[unknown][known][many zerobytes][any]のような形に対してのハッシュ値を得られる
    • 対応: crc32, md5,. sha1, sha256, sha512
    • unknownは長さは分かっている必要がある
      • MACとしてハッシュを使っていればここに秘密鍵が置かれていることがある
        • [秘密鍵][平文]のハッシュ値を署名に使ってるいるとか
    • knownに制約があるかは分からない。末尾にある必要はある（最後のブロックを構成するための長さくらいは必要そうだけれど）
    • many zerobytesはアルゴリズム上勝手につく
    • anyは自由に決められる。最後にしかくっつけることができないので注意
  • CTF/Toolkit/HashPump - 電気通信大学MMA
    • HashPumpを使えば達成できる
      • git clone https://github.com/bwall/HashPump && cd HashPump && makeで用意
    • $ ./hashpump -s (既知ハッシュ) -d (既知初期文字列) -k (UNKNOWNの長さ) -a (追加文字列)
    • ./hashpump -s 846624fb43da2ad7adcf1e4a6a760e54ed1830050cbd44a0baafbf6260b861e5e6723d2f6a0c5c265267dfe1c984fb3a29d07e347d1c273899615e96c52bb015 -d 8,8 -k 21 -a ,10とすると、以下のようになる。1行目が新しいハッシュで、2行目が追加後の文字列となる。unknown + (2行目の\xを%に変換したもの) 6b25918b4b2b303c44d3cdd67f337d3acbdf722e2f006b19226e8b0c6f77ea2b0dbfcf6d9f4c2a5bbe98d252c6c1f5ae8af70dceee7df0c22e690c92bf35fd0e 8,8\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\xc0,10
  • iagox86/hash_extender
    • ./hash_extender --data "" --secret [unknownの長さ] --append [追加文字列] --signature [既知ハッシュ] --format [md5]
  • stephenbradshaw/hlextend: Pure Python hash length extension module
    • SHA1, SHA256, SHA512で使える

Bcrypt Truncation

  • bcryptは72bytesを超えると72bytesに丸められる制約がある
  • これを使って不明文字列を平文の末尾において先頭から1文字ずつ特定していく方法がある https://blog.hamayanhamayan.com/entry/2024/06/10/003618#Web-Rusty-Road-%E8%A7%A3%E3%81%91%E3%81%AA%E3%81%8B%E3%81%A3%E3%81%9F
  • 言語によらずbcyrpt側の仕様っぽい？
    • phpだとpassword_hashとpassword_verify
      • password_hashでアルゴリズムをPASSWORD_BCRYPTとして使うと、 password が最大 72 バイトまでに切り詰められる。ハッシュの元の先頭72バイトが一致するように作れば署名を共有することができる。偽装できる。
    • rust
      • use bcrypt::{hash, verify, DEFAULT_COST};でhash(password, DEFAULT_COST).unwrap()みたいになっていると使われている

自作ハッシュ衝突問題

ハッシュ関数署名

  • SPHINCS+

CTFのCryptoにおける共通鍵暗号と公開鍵暗号まとめ [PQC]

Security

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

共通鍵暗号と公開鍵暗号

  • 共通鍵暗号: 暗号化時と復号時に同じ鍵を使う暗号
    • ブロック暗号: 一定長のブロックに分けて暗号化
    • ストリーム暗号: 一定数のビットをまとめて1つの単位として暗号化
  • 公開鍵暗号: 暗号化時と復号化時に異なる鍵を使う暗号
  • ハイブリッド暗号: 公開鍵暗号を用いて鍵共有を行い、共有した鍵により高速な共通鍵暗号を用いて秘匿通信を行う
    • 鍵共有として、長期鍵を利用した公開鍵暗号(RSAなど)を使った場合、前方秘匿性（つまり、一度鍵が漏洩すると、過去にさかのぼって全て復号可能）を持たないため、非推奨でTLSv1.3には入ってない
    • 鍵共有ができればよいので、TLSv1.3ではECDHによる鍵共有を採用している
  • 認証付き暗号: AEAD: Authenticated Encryption with Associated Data
    • 暗号化と認証（改ざん検知）の両方が備わった暗号のこと
      • 暗号 + MACの単純な組み合わせでも概ね実現できるが、不適切な組み合わせなどにより想定した安全性を達成できない場合があるっぽい
    • AES-GCMとかChaCha20-Poly1305
  • 鍵配送問題
    • 事前共有: 安全な方法で鍵を前もって渡しておく
    • 個別に鍵を作ると大量になっちゃうので鍵配布センター（KDC）を用意する
    • Deffie-Hallman鍵交換 -> 共通鍵を共有可能
    • 公開鍵で解決
      • 公開鍵の認証、公開鍵の真生性が証明できない問題が残る

ブロック暗号

https://tex2e.github.io/blog/crypto/symmetric-key-ciphers

Feistel構造

攻撃手法

  • 選択平文攻撃: 暗号解読者が任意の平文を暗号化できることを前提がある攻撃
    • 差分解読法
      • 平文の一部を変更すると暗号文がどう変化するかを調べる暗号解読法
      • 暗号文の変化の手がかりを調べて解読の手がかりを得ていく
    • 線形解読法
      • 平文と暗号文のビットをいくつかXORして0になる確率を調べる
      • 暗号文が十分にランダムであれば、平文と暗号文のビットをいくつかXORした結果が0になる結果は1/2のはずだが、そこからのずれが大きいビットの箇所を調べて、鍵に関する情報を得る
  • 弱い鍵
    • 暗号強度を下げるような特性を持つ特定の鍵のこと
    • DES: 弱い鍵を使うと、暗号化モードと復号化モードが同じように動作する
      • 例：0000000000000000ffffffffffffffff
      • 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF でもいいみたい
  • 単純な平文を使って、定数が求められるかも
  • 暗号化手順が全部線形であれば、逆計算できるかも

Wikipediaに書いてある攻撃

  • ショートカット法: ブロック暗号アルゴリズムの弱点を用いて鍵の全数探索以下の計算量で鍵（の一部）を求める手法の総称
    • 差分解読法（差分暗号解読） en:Differential cryptanalysis (Biham, 1989): XX以上の確率を有するような差分特性を探す
      • 不能差分解読法 en:Impossible differential cryptanalysis
      • 切詰差分解読法 Truncated Differential Cryptanalysis
      • 高階差分解読法 Higher Order Differential Cryptanalysis
      • ブーメラン攻撃 en:Boomerang attack
      • 補間攻撃 en:Interpolation attack (Jakobsen, Knudsen, 1997)
        • 線形和攻撃 Linear Sum Attack (Aoki, 1999)
    • 線形解読法（線形暗号解読） en:Linear cryptanalysis (Matsui, 1993): XX以上の確率を有するような線形特性を探す
      • 差分線形攻撃 en:Differential-linear attack
      • 切詰線形攻撃 Truncated Linear Attack
    • スライド攻撃 en:Slide attack (David Wagner, Alex Biryukov, 1999)
    • カイ2乗攻撃
    • mod n攻撃 en:Mod n cryptanalysis
    • XSL攻撃 en:XSL attack
  • サイドチャネル攻撃
    • 単純電力解析 Simple Power Analysis
    • 電力差分攻撃 en:Differential power analysis
    • タイミング攻撃 en:Timing attack
  • 書いてなかった攻撃
    • 関連鍵攻撃
    • 丸め差分攻撃

ストリーム暗号

  • ストリーム暗号
  • ストリーム暗号の基本方針
  • ストリーム暗号は対称暗号化
  • ストリーム暗号に求められる代表的な安全性
    • キーストリームの乱数性：キーストリームを真性乱数と識別することが困難
      • 識別攻撃
    • キーストリームの予測困難性: とあるキーストリーム系列の集合から、以降のキーストリームの予測が困難
      • 予測攻撃
      • 内部状態復元攻撃
    • 秘密鍵回復困難性: キーストリームから秘密鍵を求めるのが困難
      • 鍵回復攻撃 (weak key)
  • 共通問題
    • とある2つの暗号化について、同じ鍵ストリームを使ってはならない
      • 2つの暗号化文をxorすることで、それぞれの平文のxor和が得られ、文字の頻度分析やそのほかの基本的な手法により、暗号化前の情報が得られるかもしれない
      • 対策として暗号鍵が同じ場合でもivを鍵に加えて異なる鍵ストリームを生成させることが大事
  • カオスベース・ストリーム暗号

ワンタイムパッド One-Time Pad / Vernam / バーナム暗号

  • 方式
    1. 平文と同じ長さの鍵を用意する
    2. 平文 xor 鍵によって暗号文を作成する
  • One-Timeとあるように鍵は1回きりで使用する必要がある
    • そうしないと、同一の鍵で作られた暗号文AとBをxorすると、それぞれの平文aとbのxorが得られてしまう
    • multi-time pad: ワンタイムパッドが使いまわされた結果、復号されてしまうのをやじったもの
  • ワンタイムパッドは平文と同じ長さの鍵が必要なため、実際には使われないが、ワンタイムパッドは全ての暗号文が同じ確率で現れるような安全性を持つ暗号であり、情報理論的安全である。ストリーム暗号では、情報理論的安全であるワンタイムパッドの枠組みを使いながら、共通鍵として共通の疑似乱数系列を使うことで暗号としての安全性を担保しようとしている
    • この時使われる疑似乱数系列をキーストリームと呼ぶ
  • 攻撃方法
    • https://labs.spookies.co.jp/entry/2019/11/12/174348
      • 同じ平文に対してランダムな鍵での暗号化結果が与えられるが、鍵は0x00を含むことはできない。
      • 0x00で暗号化されると平文がそのまま出てくるが、このパターンはあり得ないということは、何回か試して出てくるパターンを計測したときに、現れない文字が平文の文字であるということが言える
    • 頻度解析, Key Reuse: キーストリームが共通で暗号文が複数あるとき、頻度解析をすれば根性でキーストリームが復元できる

RC4

ChaCha20

  • ChaCha20ではkeyとnonce（=iv）からkeystreamを作成して、それを逐次平文にxorして暗号文を作成している
    • ということは、keyとnonceが同じであれば全く同じkeystreamが作成されるので、keyとnonceが同じで、かつ、平文と対応する暗号文の組が手に入っていれば平文 xor 暗号文でkeystreamが手に入り、それを平文にxor和すれば暗号文になるし、暗号文にxor和すれば平文に戻せる
  • キーストリームの作成方法 https://gitlab.mma.club.uec.ac.jp/mmabeginners/wanictf-2024/-/tree/main/Crypto/dance?ref_type=heads
    1. 以下のような情報を元に初期状態を作る 定数：16byte（4 words）->{0x61707865, 0x3320646e, 0x79622d32, 0x6b206574} 鍵：32byte (8 words) ブロックカウント：4byte（1 word） Nonce: 12byte（3 words）

    2. 20ラウンド分ラウンド操作を行う（column round -> diagonal roundを10セットやる） ```python def __quarter_round(self, a: F2_32, b: F2_32, c: F2_32, d: F2_32): a += b; d ^= a; d <<= 16 ## <<=は「巡回」左シフト c += d; b ^= c; b <<= 12 a += b; d ^= a; d <<= 8 c += d; b ^= c; b <<= 7 return a, b, c, d

      def Qround(self, idx1, idx2, idx3, idx4): self.state[idx1], self.state[idx2], self.state[idx3], self.state[idx4] = \ self.quarter_round(self.state[idx1], self.state[idx2], self.state[idx3], self.state[idx4])

      def update_state(self): for _ in range(10): # column round self.Qround(0, 4, 8, 12) self.Qround(1, 5, 9, 13) self.Qround(2, 6, 10, 14) self.Qround(3, 7, 11, 15) # diagonal round self.Qround(0, 5, 10, 15) self.Qround(1, 6, 11, 12) self.Qround(2, 7, 8, 13) self.__Qround(3, 4, 9, 14) ```

    3. 作成したキーストリームと平文をxorして暗号化
  • 弱点
    • 同一nonce, 同一キーで暗号化すると同じキーストリームを作る
    • ラウンド操作は逆計算が可能であるため、平文と暗号文の組が分かっていれば、そこからキーストリームを作っている状態が分かり、そこから逆計算をして初期状態を計算し、それにより鍵とivが判明する
    • ChaCha without Poly is vulnerable to a bit flip attack
  • 資料
  • ChaCha20-Poly1305 https://tex2e.github.io/blog/crypto/chacha20poly1305
    • Googleは共通鍵暗号としてChaCha20, MACとしてPoly1305を組み合わせたものを、RC4に変わるストリーム暗号として提唱している。TLS通信でも使われている。

RC4 / ARC4

  • RC4: 安全ではないとされていてもう使ってはいけない
  • RC4: 以下2つのアルゴリズムから成り立つ https://zenn.dev/mahiro33/articles/6f74d1dc8532b4
    • KSA: Key Scheduling Algorithm. 暗号鍵を用いてそれに応じた内部状況を生成する
    • PRGA: Pseudo-Random Generation Algorithm. KSAで生成した内部状態をもとに、かき混ぜと1byteの乱数出力を行い、これを使ってXORして暗号文を生成
  • 完全にRC4 = ARC4(Alleged-RC4)である。RC4が商標登録されているため名前が使えないのでARC4と表記されるようになったらしい
  • 「RC4の鍵テーブルにおける統計的な偏り[8]を利用することで、平文の一部が回復可能であるというものである[9][10]。この攻撃法により、13 × 220通の暗号文を用いれば128ビットのRC4が解読可能であることが示され、2013年のUSENIXセキュリティシンポジウムにおいて「実現可能である」と評された」 from Wikipedia
  • https://www2.nict.go.jp/csri/plan/H26-symposium/files/3-1.pdf も非常に良い資料
    • ストリーム暗号としての安全性は満たしていないが、見た感じCTFで使えそうなpracticalな攻撃方法は現状無い？

公開鍵暗号

  • 公開鍵暗号 PKE: Public Key Encryption: 暗号化時と復号化時に異なる鍵を使う暗号。一方向性関数を利用して構築する
  • 一方向性関数: 入力→出力は容易に計算可能だが、出力→入力は困難な関数。各公開鍵暗号方式の安全性の根拠となる。
  • 公開鍵暗号の3ステップ
    • KeyGen 鍵生成
    • Enc 暗号化
    • Dec 復号
  • 公開鍵暗号を用いたデジタル署名: 公開鍵暗号を使って署名を作成し、改ざん検知や否認防止、真正性担保を行う機構
    • 3つのアルゴリズムにて定義される
      • KeyGen 鍵生成
      • Sign 署名
      • Verify 検証
    • 方式
      • RSA署名: 素因数分解の難しさを数学的背景とした署名方式
      • ElGamal方式: mod N上での離散対数が難しいことを数学的背景とした署名方式
      • DSA: 同上
      • ECDSA: 楕円曲線暗号を使用した署名
      • Rabin方式: mod N上で平方根を求めることが難しいことを数学的背景とした署名方式
    • 他色々な署名
      • メッセージ復元型署名
      • 使い捨て鍵署名
      • 否認不可署名
      • 故障停止署名
      • ブラインド署名
      • グループ署名
      • リング署名
      • 検証者指定署名
      • 代理署名
      • フォワード安全署名
  • 公開鍵基盤 PKI, CA, CRL, X.509 電子証明書
  • 証明書の基盤となる分野

他、方式

  • Okamoto-Uchiyama cryptosystem
  • Paillier暗号
    • 素因数分解を難しさにもつ公開鍵暗号
    • 鍵生成（kはセキュリティパラメタ）
      1. 2つの素数p,qをランダムに選ぶ
      2. n=pq, λ=lcm(p-1, q-1)
      3. μ = 1/L(g^λ mod n2) mod nを計算。逆元が存在しない場合はgを新たにランダムに選ぶ。L(x)=(x-1)/n切り捨てとする
      4. (n,g)が公開鍵、(λ,μ)が秘密鍵
    • 暗号化
      1. 0<r<nとなる整数rをランダムに選ぶ
      2. c=gm rn mod n2を計算し、暗号文cとする
    • 復号
      1. m=L(c^λ mod n2) μ mod nを計算すると平文になる
    • 加法準同型性 Enc(m1, r1) × Enc(m2, r2) = Enc(m1+m2, ?)
    • 乗法準同型性（正確には準同型ではないらしい）
      • Enc(m1,r1)m2 = Enc(m1*m2, ?)
  • Goldwasser-Micali暗号
    • 通称GM
    • en:Shafi Goldwasserとen:Silvio Micaliによって1982年に提案された公開鍵暗号方式である。 この暗号方式は標準的な仮定の下安全性が示された初の確率的公開鍵暗号方式である。 しかし、効率は悪く、暗号文のサイズは平文のサイズの数百倍になる。暗号方式の安全性を示すために彼女らは、現在では広く使われることになった強秘匿性を定義した。
    • 問題例

PQC / 耐量子暗号 / ポスト量子暗号

多変数多項式暗号 MPKC

CTFのCryptoにおけるAESまとめ

Security

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

AES

  • AES = ブロック暗号コンペで選定されたRijandaelという対称暗号
    • AESの欠点「ちょうど16bytesしか暗号化できない」
    • 表記方法: AES-128-CBC
      • AES: 暗号プリミティブ名
      • 128: 鍵長（bit）
      • CBC: 暗号利用モード
  • ブロック暗号
    • 一定長のブロックに分けて暗号化
    • 構成要素
      • パディング方式: ブロック毎に分けたときに端数をどのようにブロックに丸めるかを決めたもの
      • ブロック暗号利用モード: 分けたブロックに対してどのようにブロック暗号を適用していくかを決めたもの
      • 暗号化方式: ブロック暗号のコア部分。ブロックをどのように暗号化するかを決めたもの

Rijandael暗号

パディング方式

  • ゼロパディング: paddingとしてゼロ0x00埋めする方式
  • PKCS#7 pkcs7 Padding
    • PKCS(: Public-Key Cryptography Standards)の7番目として決められた、暗号メッセージ構文に関する仕様の中で言及されているパディング方式
    • 1ブロックは255バイトまで
    • パディングとして0x00ではなくて、パディング長を入れこむ
      • 仮に8bytesでアラインメントするなら…
      • AAAAなら4つ入れる必要があるのでAAAA\x04\x04\x04\x04みたいな感じ
      • ピッタリなら新しくブロックを作ってパディング長を入れる。BBBBBBBBならBBBBBBBB\x08\x08\x08\x08\x08\x08\x08\x08

ブロック暗号モード

必ずしも+AESではないみたい。

ECBモード

  • ECB:Electronic CodeBlock ブロックごとに単純に暗号化する
    • 平文のブロックで同じものがあれば同じような暗号文が生成されてしまう
    • 暗号化 encrypt([平文block])
    • 復号化 decrypt([暗号block])
    • 鍵はあるけどivがないならECBかも
  • 攻撃テク
    • ECBでは16バイトのブロックごとに暗号化されるので、暗号化文字列を切り貼りして16バイト単位で差し替えが可能
      • ブロック長を意識して暗号文を作成して、切り貼りしていくことで任意の復号文を作る
      • 例えばjson形式を暗号化していたりすればスペースは無視されるので、スペースとかを利用して任意の文字だけを含むブロックを作ったりしながら頑張る
      • https://qiita.com/kusano_k/items/8a63b97d1427ef2e3369#imaginary
    • ECBではブロックごとに平文と鍵が同じであれば、同じ暗号文が出力される
      • 同一の鍵で平文が操作できるときに、全通りのブロックを作って比較して特定みたいなことができる
        • SECCON Beginner CTF 2025 01-Translator
    • 同じ平文で同じ暗号文になるので頻度分析に脆弱

CBCモード

  • CBC:Cipher Block Chaining 暗号化する前に平文を1つ前のブロックとXORして暗号化する
    • 最初のブロックは1つ前というのが無いのでIV（初期化ベクトル）というのを初期状態として用意する
      • IVは復号時にも必要になるが、鍵という扱いはされないみたい
      • 人に依って意見は分かれそうな雰囲気があるが、個人的には鍵がいくつもあるメリットもないので秘密ではないと考えておくスタンスでよさそう
    • 暗号化 encrypt([平文block] xor [IVか1つ前暗号block])
    • 復号化 decrypt([暗号block]) xor [IVか1つ前暗号block]
  • ivを外部注入できる場合
    • 最終的な復号文の先頭16bytesを自由に変更することができる
    • 復号時に先頭16bytesにAESの復号化処理がかかった後、xor ivされる。ここでAという風に復号化され、Bに復号化したい場合は、ivをiv xor A xor Bとしてやればxorでうまく相殺されて、Bに書きかえることが可能になる
  • Bit-flipping attack
    • CBCモードでは復号時に、decrypt関数に通した後1つ前の暗号のblockとxorをするので、とある暗号ブロックを1bitフリップさせることで、その次の暗号ブロックの対応bitもフリップさせられる
      • 例えば復号したら"test1"になるようにしておいて、その前の暗号ブロックの対応ビット部分を"test1" xor "admin"にしておけば復元したらadminになっている。
      • 副作用で色々壊れるかもしれないが、それでも問題なければ攻撃につなげることが可能
    • picoCTF2021 [Web Exploitation] writeup - 好奇心の足跡
    • https://tryhackme.com/r/room/flip 練習に便利
  • Padding Oracle Attack
    • Bit-flipping attackの発展形
    • CBCモードにおいて復号するときに、PKCS#7パディングが不正であるエラーが発生する場合に有効なテクニック
      • 名前にもあるように復元後のパディングチェックが成功したか失敗したかをオラクルとして攻撃を進めていく
    • 復元への動作原理
      • 暗号文の最終ブロックを特定することをまず考える
        • 最後から2番目のブロックを特定したい場合は最終ブロックを削除して同じことを行えばできるので、最後ブロックの復元だけ考えればいい
      • 最終ブロックc[N]を特定するために、最終ブロックc[N-1]部分を改変してpayloadを送る
        • c[1],c[2]...,改変c[N-1],c[N]
        • c[N-1]前まではどうでもいいが、c[N]はそのままにしておくこと
      • c[N]は元のままなので、復号用関数に通した結果は解析したいものと同じになるdec(c[N])
        • 攻撃で求めるのはdec(c[N])の内容になる。この内容が分かれば平文p[N]がdec(c[N]) xor c[N-1]で求まる
      • c[N-1]を00...0000から00...00ffまで全探索してc[1],c[2]...,改変c[N-1],c[N]のようにして送る
        • この改変後のc[N-1]をc'[N-1]としておこう
        • 送った後のN番目のブロックの復号文はdec(c[N]) xor c'[N-1]となっている
        • そして重要なのが『paddingを検証をしているとこのうち少なくとも1つはpadding検証は成功で返ってくるはずである』
          • ここの理解が難しい！
          • xorしているので、N番目のブロックの復元後は??????00～???????ffが均等に現れてくるはずである
          • この復元後に対してpaddingチェックが確実にOKとなるのは???????01の時だけである
            • N番目の元々の原文が何であるかというのは全く関係ない。paddingチェックという観点だけで見ると末尾が0x01になっていればチェックは通る
            • （もしかしたらたまたま末尾が0x0202みたいになってて成功する場合もあるかも）
          • つまり、255通りのうち成功で返ってきているならば、その入力において復号したdec(c[N]) xor c'[N-1]の末尾1byteが0x01である可能性が非常に高いと言える
          • もっと言えば、255通りのうち1つだけ成功で返ってきているならば確実にその入力において復号したdec(c[N]) xor c'[N-1]の末尾1byteは0x01である
        • これで dec(c[N]) xor c'[N-1] = ???????01となるc'[N-1]が特定できたので、dec(c[N])の末尾1byteは0x01 xor c'[N-1][:-1]であると特定できた
        • ここまで理解できていればだいぶ完全理解まで近い
      • これでdec(c[N])の末尾1byteは分かったのでは次は末尾2byte目を特定しよう
        • c[N-1]を00...0000XXから00...00ffXXまで全探索してc[1],c[2]...,改変c[N-1],c[N]のようにして送る
          • XXはなんだと思うかもしれないが、padding検証のことを加味して考えてみる
          • 末尾1byte特定の場合は最終的に0x01で終わることを考えたが、次は末尾が0x0202で終わることを考えよう
          • この場合のXX部分は、既にdec(c[N])の末尾1byteが特定されているので、0x02にするためには XX = dec(c[N])[:-1] xor 0x02を置けばいい
          • これでXXの1つ上のbyteを00からffまで全探索すれば末尾が0x0202となる1つだけがpadding検証は成功した状態で返ってくることになる
        • padding検証が成功でかえってきた入力を見れば、末尾1byte目の特定と同じ要領で末尾2byte目まで特定できたことになる
      • このような感じでブロックサイズ16byteのdec(c[N])を特定していく
        • dec(c[N])が特定できればもともとのc[N-1]を使って、平文p[N]を求めることができた
      • ivが用意されていればそれもうまく弄って全文復元可能
    • 改ざんへの実行原理
      • まずは復元時と同様にして、改ざんしたいブロックのdec(c[x])を求める
      • そしたら、改ざんしたい値に合わせてc[x-1]を(改ざん後としたい文字列) xor dec(c[x])にすれば改ざん完了
        • こうするとx-1番目の内容も変わってしまうが、変わった後のdec(c[x])も求めることができるので、それを使ってさらに前の文章も修正できる
      • ivが用意されていればそれもうまく弄って全文改ざん可能
      • https://writeups.thebusfactoris1.online/posts/2025-09-05-decryption-execution-service-writeup
    • Padding Oracle Attack 分かりやすく解説したい - Attack All Around
    • 実装
  • ivが隠匿されていて、暗号化を任意の値で行えて結果が取得できる場合にivを特定可能
    1. b'A'*16+b'\x00'*16+b'A'*16というのを復号する
    2. 復号はdecrypt([暗号block]) xor [IVか1つ前暗号block]のように行われるので...
      • 1ブロック目の復号結果はdecrypt(b'A'*16) xor IV
      • 3ブロック目の復号結果はdecrypt(b'A'*16) xor b'\x00'*16よりdecrypt(b'A'*16)
    3. つまり、1と3ブロック目の復号結果をxorするとIVが得られる
      • decrypt(b'A'*16) xor IV xor decrypt(b'A'*16) = IV
    4. https://github.com/rerrorctf/writeups/blob/main/2025_02_07_BITSCTF25/crypto/alice_n_bob_in_wonderland/writeup.md
  • 同じ鍵が使われていて、何度も復号化できる場合は、復号先を任意の値に変更可能
  • Key reuse https://github.com/jvdsn/crypto-attacks/tree/master/attacks/cbc_and_cbc_mac
    • EAM, ETM, MTEの鍵が再利用されていると脆弱瀬

CFB: Cipher FeedBack Mode / OFB: Output-FeedBack mode

  • CFB: Cipher FeedBack Mode
    • 暗号復号化
      • 暗号化 encrypt([IVか1つ前暗号block]) xor [平文block]
      • 復号化 encrypt([IVか1つ前暗号block]) xor [暗号block]
      • 暗号化と復号化が全く同じ
    • レプレイ攻撃可能
  • OFB: Output-FeedBack mode

CTR / GCM

  • CTR: CounTeR カウンタを使ってブロック暗号をストリーム暗号として使う
    • カウンタ/疑似乱数 = [nonce（毎回作り直すランダムな値）] + [ブロックごとにインクリメントするブロック番号]
    • 疑問点: ストリーム暗号になってる？
    • 例えばnonceが123456789であれば、ブロックごとに1234567890001, 1234567890002, 1234567890003,...を使うイメージ
    • 暗号化 encrypt([疑似乱数]) xor [平文block]
    • 復号化 encrypt([疑似乱数]) xor [暗号block]
    • 攻撃
      • 同一KEY かつ 同一NONCEが使われている場合は Enc(x) xor Enc(y)はencrypt([疑似乱数])部分が相殺されて、x xor yとなる。
        • 平文が分かっていれば、Enc(x) ^ x ^ yにすればyの暗号化に変換可能
      • 暗号化と復号化は同一の処理であるため、カウンタが同じであれば暗号化処理を復号化処理として利用可能
      • カウンタが何等かの問題でループする場合
        • 同じKEY, NONCEを使っている場合、カウンタをいい感じにループさせて暗号化時に使った初期カウンタと同じものが用意できれば復号可能
    • CTRはストリーム暗号として使えるので、平文はブロックサイズにpaddingされてなくてもよく、また、暗号文もpaddingされずに同じサイズ長で出てくる
      • （全部でそうなのか分からないが、少なくとも、pycryptodomeだとそうなった。Counterでブロック長が指定されていても出力サイズはpaddingされない）
    • 他攻撃 https://github.com/jvdsn/crypto-attacks/tree/master/attacks/ctr
  • GCM: Galois/Counter Mode, ガロア認証（GHASH関数）+カウンターモードで暗号化。暗号化/復号化と同時にデータが正しい人に作成されて改ざんされてないことも確認可能

XCBモードへの攻撃

XTS: XEX encryption mode with tweak and ciphertext stealing

他

  • AES-CFB8: Advanced Encryption Standard –Cipher Feed Back 8 bit
    • ZeroLogon CVE-2020-1472 で悪用された。昔のADではこれに加えてivが0で固定だったため、平文が全部0のものを与えると暗号文をとある1文字から成るものに強制できた
  • PCBCモード + Padding Oracle Attack

他、攻撃メモ

CTFのCryptoにおける楕円曲線まとめ [EC, isogeny]

Security

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

体系的に理解できておらず、殴り書きです。何も分からん。

楕円曲線

  • 楕円曲線: 体Kに対して y2+a_1xy+a_3y = x3 + a_2x2+a_4x + a_6 を満たす解の集合を楕円曲線と呼ぶ
    • 数学的には、楕円曲線とは種数1の非特異代数曲線のことを指す。その中でもワイエルシュトラスの標準形が一般的な表現形式の1つ
      • 点の計算方法は楕円曲線（weierstress, edwards, mongomery,...）によって違うが、代数的構造は同じになる
        • 離散対数問題の困難性は同等で、同じレベルのセキュリティを担保できる
        • 実用上用いる楕円曲線によって計算効率が異なったり、mongomery形式はサイドチャネル攻撃に脆弱と言った実装上の差もある
      • 「種数1の非特異代数曲線」とは
        • 代数曲線 -> 多項式方程式 f(x,y) = 0 で定義される曲線
        • 非特異（smooth） -> 特異点がない。つまり、曲線上で偏微分が同時に0になる点（∂f/∂x = 0 かつ ∂f/∂y = 0）がない。尖ってるとダメ。だからsmooth
          • 楕円曲線の計算に接線を用いるものがあるが、その際に接線が一意に定まらない
          • また、「特異楕円曲線では離散対数問題が多項式時間で解ける」
            • Smart攻撃: 特定の特異曲線で効率的に離散対数を計算
            • 以上楕円曲線攻撃: 特異点を利用した鍵回復
        • 種数(genus) -> 種数1：トーラス（ドーナツ型、穴が1個）- 楕円曲線
          • 種数1の曲線のみが自然な群構造を持つ
    • Weierstrass 方程式: y2+a_1xy+a_3y = x3 + a_2x2+a_4x + a_6
    • ワイエルシュトラスの標準形 y^2 = x^3 + ax + b
      • a,bは有限体、x,yはa,bの「代数的閉包」
      • 4 a^3 + 27 b^2 != 0を満たす必要がある
        • これは特異点が存在しないための条件
      • 体Kの標数が2,3でないとき、x,yの線形変換によって2次項を消すことができ、a,b ∈ Kを用いてワイエルシュトラスの標準形に変換可能
      • mod pで素数pは5以上である必要がある
    • 表現方法: アフィン座標(x,y) -> 投影座標[X:Y:Z]
      • 投影座標：楕円曲線上の点を[x:y:1]で、無限遠点Oは[0:1:0]と表現する
        • sagemathもこの形式
        • この形式で計算することで加算公式が無限遠点があっても統一的に書けるし、計算も早いらしい
      • 他にもJacobian座標やProjective座標が使われ、こっちは除算が避けられ、計算効率が良いらしい
      • 多分座標の取り方は単純に実装上の問題だけであり、数学的なアレコレの問題ではない
  • 体Kいろいろ
  • 楕円曲線E上の点に対して特殊な演算を定義して、無限遠点を足すと群になる
    • この楕円曲線上の二点A,Bに対してA+Bの足し算を定義する（無限遠点を0として定義すると、交換法則・結合法則が成り立つ。可換群）
    • A(x,y)に対する逆数は-A(x,-y)とx座標で反転させた点になる
    • A(x1,y1) + B(x2,y2) = C(x3,y3)
      • x3 = φ2 - x1 - x2
      • y3 = -φ x3 - ψ
        • φ = (y2 - y1) / (x2 - x1)
        • ψ = (y1 x2 - y2 x1) / (x2 - x1)
    • 可換群であるため、掛け算が定義可能になる
      • 3R = R + R + R
    • 同様の定義で楕円曲線の有理点のなす群と考えたものをMordell-Weil群という（？）
      • 楕円曲面の Mordell-Weil 群には格子の構造が入るらしい（？？？）
  • スカラー倍について
    • 楕円曲線上の点に定数xの逆数x^−1をかけるときは楕円曲線の位数の逆数をとる。つまり、位数が分かっていればスカラー倍で割れる
  • 楕円曲線の位数 #E(Fp): mod p上の楕円曲線上にある点の総数のこと
  • 楕円曲線上の「点Pの位数」とは，rP=Oとなる最小の正整数rである．位数は常に存在し，楕円曲線の位数 #E(Fq)を割り切る
  • Hasse の定理
    • 体の標数が2,3ではない有限体Fq上の楕円曲線E/Fqの位数#E(Fq)について、|#E(Fp) - (q+1)| ≦ 2 sqrt(q) が成り立つ
    • Hasse の定理 |E(Fq)|=q−t+1 の方が正しい？
      • tはフロベニウス写像Φのtraceであり、Φ2-tΦ+p=0を満たす数tである
  • 群構造
    • 楕円曲線はアーベル群
    • 楕円曲線がなす群については、以下のいずれかになる EC.abelian_group()で確認可能
      • 1点集合の群（自明な群） Trivial group embedded in Abelian...
      • 巡回群。Eが全体で巡回群であることはまあまあ多い。実用されている暗号システムでは基本的に素数位数の巡回群になるようにパラメタが選ばれる
      • 巡回群2個の直和
        • BLS12-381の大元となる群は巡回群ではないが、その一部だけを使って巡回群になるようにしている
  • 安全曲線 https://www.fujitsu.com/downloads/JP/archive/imgjp/jmag/vol50-4/paper06.pdf
    1. 曲線の位数が素数、またはほぼ素数であること
    2. 特殊な曲線にならない（特にtraceは0～2にならない）
  • sagemathでx座標から点を求めるときは、 A = E.lift_x([x座標])とする
  • SageMathが曲線を初期化できない -> 曲線が壊れている -> 楕円曲線に置いて壊れているというのは「特異である」ということ
  • 曲線によって、色々な性質が出てきたり、計算が高速化できたりする
  • 色々な楕円曲線
  • 有限体上の楕円曲線は通常曲線と超特異曲線に分類できる
    • 標数p上の超特異曲線は…
      • 約p/12個存在する。つまり、ランダムに曲線を生成したとき超特異である確率はおおよそ1/p
      • 全てFp2上で定義される（これ大事では？）
        • j-不変量を鍵として共有するときサイズは2logpくらい
    • Tateの定理：超特異曲線と同種な曲線は超特異
    • 超特異曲線Eは位数で特徴づけられる
      • #E(Fp) = p+1
      • #E(Fp^2) = (p+1)^2 または (p-1)^2
  • 判別式D、j-不変量が固定であれば、位数と素数の間に固定的な関係があるかも
    • ハッセの定理
    • フロベニウス跡、トレース t を使って、#E(Fp) = p+1-t
  • 色んな情報から、もともとの楕円曲線を導く
  • sagemathでP(x,y)から定数倍をしたときのQの多項式表現が得られる
    • E.multiplication_by_m(2)とすると((x^4 + 2*x^2 - 24*x + 1)/(4*x^3 - 4*x + 12),(8*x^6*y - 40*x^4*y + 480*x^3*y - 40*x^2*y + 96*x*y - 568*y)/(64*x^6 - 128*x^4 + 384*x^3 + 64*x^2 - 384*x + 576))が得られる。x座標はxの多項式になり、次数はk2になる
    • E.multiplication_by_m(2, x_only=True)とすればx座標のみ得られる
    • https://github.com/ImaginaryCTF/ImaginaryCTF-2025-Challenges/blob/main/Crypto/scalar-division/solve2.sage
      • poly = E.multiplication_by_m(k,1)でk倍した表現を得て、定数倍した後のx座標Qxが分かっているので、poly = poly.numerator()-Qx*poly.denominator()という多項式が得られて、R.<x> = PolynomialRing(GF(p))のように多項式環を作ってpoly = R(poly)と変換し、mod pなのでpoly2 = pow(x,p,poly)-xも同様に成り立ち、これでfinal = poly.gcd(poly2)のように多項式のGCDをして簡約してroots = final.roots()のように根を取れば元々のxが分かる
  • j-不変量
    • F = GF(p)でE = EllipticCurve(F, [1, 2])のとき- F(1728) * F(4*1) ** 3 / F(E.discriminant())で計算
    • 楕円曲線の同型類を考えるためのもの
  • 性質の良い楕円曲線を探す https://github.com/Sarkoxed/ctf-writeups/blob/master/trx-2025/magic_curves/solve.py
    • 以下の条件を満たす(p,a,b)を探す例
      • Fp上の2つの楕円曲線、y2=x3+ax+bとy2=x3+bx+aが同型である
      • 同型であるということは位数が等しいということだが、その位数がsmoothである
    • 写像x→λxを使って色々変形すると、b/λ2=aかつa/λ3=bを満たせばよく、これはλ5=1を満たすλを選べば、この条件が満たされる。λ5=1を満たすλを見つけるためにはFpの位数が5の倍数である必要があるため、p-1が5の倍数であるpを最初に選択している。それで1の5乗根を取ってλとして、Fp乗の適当な元をaとして、そこからλを使ってb=a/λ3で計算し、あとは生成した楕円曲線の位数がsmoothであることを確認する。

楕円曲線暗号: ECC: Elliptic Curve Cryptography と楕円曲線上の離散対数問題 ECDLP: Elliptic Curve Discrete Logarithm Problem

  • ECC: Elliptic Curve Cryptography
  • CurveBall CVE-2020-0601: Q=dPでQとPが固定のときdを解くのは難しいが、Qが与えられてdとPを自由に決められるなら、等式を満たすdとPをQから決めるのは簡単。d=2とかにしてP=Q/dすればいい。

ECDLP 楕円曲線における離散対数問題

MOV / FR Reduction

  • MOV / FR Reduction: Fp上の楕円曲線Eについて#E=p±1である、つまり、Supersingular な曲線であれば適用可能で、埋め込み次数kを用いてFpk+上の DLP に帰着できる。ECDLPをFFDLPに変換可能
    • 唯一日本語で細かく解説されている https://zenn.dev/anko/articles/ctf-crypto-ellipticcurve
    • https://risencrypto.github.io/WeilMOV/
      • MOV Attackができると、E(GF(p))をGF(p^k)×に、もっと言うとGF(p)×上での離散対数問題に帰着させることができる
      • この時、112ビットセキュリティを担保するには、RSA,DHだと2048bitsの鍵長が必要になるが、ECDHであれば224bitsの鍵長で済む
        • よって、同じGF(p)上での離散対数問題であってもECDHをDHに変換できるだけで、必要な計算量を各段に減らすことができている
      • 線形写像 linear map「f:V→W」において、「f(v1+v2)=f(v1)+f(v2)」かつ、「f(av)=af(v)」である
      • 双線形写像 Bilinear map「f:U×V→W」において、「f(u1+u2,v)=f(u1,v)+f(u2,v)」かつ「f(u,v1+v2)=f(u,v1)+f(u,v2)」かつ「f(au,v)=af(u,v)=f(u,av)」である
      • Fpの元は全部p-1乗すると1になる。その拡大体のFptでは全部p^t-1乗すると1になる（最小ではなくp^t-1を割り切るらしいが、今後の理論には関係しなさそう）
        • この式が埋め込み次数kと関係する
      • 埋め込み次数k: 素体Fq上の楕円曲線Eについて、Pを位数mの点、mが素数でありqと互いに素である場合に、q^k=1 mod mが成り立つ最小のkを埋め込み次数と呼ぶ
      • 位数mの点、つまりmP=Oを満たすPをm-ねじれ点といい、全てのm-ねじれ点の集合（m-ねじれ群）の部分集合をm-ねじれ部分集合という
        • m-ねじれ部分集合（m-ねじれ集合？） E(Fq)[m] = {P∈E: mP=O}
      • ここで、埋め込み次数kを使った、素体Fqの拡大体Fqkを考える
        • 拡大体Fqkはベースの体Fqよりも大きいため、m-ねじれ群もまた大きくなる
        • よって、この拡大体では、より多くのmねじれ点を追加しないFqkよりもより大きい拡大体になる（？）
        • よって、E(Fqk)[m]はfull m-ねじれ群と呼ばれる
      • Full Torsion Group、全ねじれ群は複数の部分群をもち、そのうちの2つをWeil Pairingでは使う
        • G1: E(Fq)上にある点の部分集合
        • G2: E(Fq)上にはないがE(Fqk)にはある点の部分集合。複数考えられるが、どれを選んでも問題ない
      • Weil Pairing
        • 埋め込み次数の定義からq^k-1=0 mod mということはq^k-1=mxということになる
        • また、Fq^k上での乗法群を考えると0以外の全ての要素はq^k-1乗すると1になる。1つ上の定義からq^k-1はmで割り切れるため、巡回群の基本的な定理より、位数がmである一意の部分群GTが存在することになる
        • m∤(q−1)、つまり、mが(q-1)を割り切らないとき、G1×G2→GTとなるWeil pairingを構築可能（なぜ？）
          • em: G1×G2 → GT
        • このWeil Paringでは、EC側（左辺）は加算群であるが、GT側は乗法群となる。この写像は以下のような性質を持つ
          • 双線形写像
            • em(A1+A2,B)=em(A1,B)*em(A2,B)
            • em(A,B1+B2)=em(A,B1)*em(A,B2)
            • em(aG1,bG2)=em(bG1,aG2)=em(abG1,G2)=em(G1,abG2)=em(G1,aG2)b=em(G1,G2)ab
          • Identity: em(A,A)=1 for all A ∈ E[m]
          • Alternation: em(A,B)=em(B,A)-1
          • 非退化 Non-Degeneracy: em(A,O)=1 for all A∈E[m] であり、逆にem(A,B)=1でB∈E[m]であればA=O
      • MOV Attack:
        • Fq上の楕円曲線Eで、素数位数mを持つ2点P,Qがあり、Q=rPという関係にあるとする。P,Q∈G1である
        • n = #E(Fqk)を計算する。m|nになるはず
        • E(Fqk)上にある位数がmの点Sを取得する
          • ランダムにT∈E(Fqk)を取る。T∉E(Fq)である必要がある
          • S=(n/m)Tを計算する。S=OならTを取り直す。こうするとmS=nTになる
          • Tの位数をtとすると、ラグランジュの定理より、tは#E(Fqk)を割り切る。つまり、t|n。よってdをつかってn=dtと書ける。こうすると、mS=dtTとなる
          • tはTの位数なのでdtT=dO=Oとなる。つまり、mS=Oとなり、Sの位数はmになる
          • https://furutsuki.hatenablog.com/entry/2022/12/13/131802 にあるテク
        • これでP,rP∈G1, S∈G2が手に入ったのでWeil Pairingをする
          • u=em(P,S)
          • v=em(rP,S)=em(P,S)r
          • u,v∈Fqk、かつ、v=urを満たすu,vが手に入り、これでECDLPからDLPへの変換が成功した
        • qkが大きすぎなければ、u=vrはIndex Calculusで解け、rが求まる。このrはECDLP上でのrの値と一致している
      • kは20以下でないことを確認するように推奨している。CTFでは2か、大きくても6くらい？
  • 勉強してみたお気持ち: そのままWeil PairingをQ=rPに使おうとすると線形性があるのでem(P,rP)=em(P,P)r=1となってしまって進まないので拡大体に一回映してねじれ群を増やして線形独立な点を探してきて使うことでem(P,B)!=1にしてうまくWeil Pairingによって乗法巡回群に落とし込んでいる？
  • 実用的には...
    1. 埋め込み次数kの計算 p^k-1 = 0 mod #E(Fp)を満たす最小のkを計算
    2. k≦6ならMOV攻撃可能！
    3. https://zenn.dev/hk_ilohas/articles/3c7ff88cb319fc からmov_attackを借りて使う 他実装 https://www.hackthebox.com/blog/movs-like-jagger-ca-ctf-2022-crypto-writeup
  • 埋め込み次数 k
    • k=1のとき、つまり、位数がp+1のとき、楕円曲線はSupersingularであると言う
      • E.is_supersingular()でsupersingularか判定できる
  • MOV attack 有限体の上の離散対数問題になる -> Weil-paringを使う
    • E(GF(p)) ≅ E(GF(p**k)) ≅ GF(p**k)×
  • Frey-Rück Reduction (同上, Tate-pairingを用いる)
  • https://zenn.dev/anko/articles/ctf-crypto-ellipticcurve#supersingular-%E3%81%AA%E6%9B%B2%E7%B7%9A%E3%82%92%E7%94%A8%E3%81%84%E3%81%A6%E3%81%AF%E3%81%AA%E3%82%89%E3%81%AA%E3%81%84-(mov-%2F-fr-reduction)
  • 楕円曲線上のペアリングを利用して、楕円曲線のDLPを有限体の乗法群上のDLPへ帰着。特にEが超特異曲線のときに有効

Singular Curve Point Decompression Attack

Invalid Curve Attack / Small-Subgroup Attack

他、資料

ECDH鍵共有: ECDH, 楕円ElGamal暗号

  • ECDH鍵共有: ECDH
    1. 最初に、楕円曲線E/FpとベースポイントP ∈ E/Fpを作成し、共有する
    2. [Alice] 乱数aを用意して、aGを計算して、送る
    3. [Bob] 乱数bを用意して、bGを計算して、送る
    4. [Alice] 貰ったbGから、abGを計算する
    5. [Bob] 貰ったaGから、abGを計算する
    6. S=abGという共通鍵が生成できた
      • Sのx座標をハッシュ化して共通鍵とすることもある？
  • 楕円ElGamal暗号
    1. [両者] ECDH鍵共有で共通鍵 abGを生成する
    2. [Alice] 送りたいメッセージ M を用意して、M+abGを計算して送る
    3. [Bob] 貰ったM+abGから-abGをしてMを復元する
    4. 楕円曲線のFp 有理点E(Fp)は巡回群 or 二つの巡回群の直積らしい https://mitsu1119.github.io/blog/p/%E7%BE%A4%E3%81%A7%E7%90%86%E8%A7%A3%E3%81%99%E3%82%8B-elgamal/

ECDSA署名

攻撃手法

https://furutsuki.hatenablog.com/entry/2020/05/05/112207 https://eprint.iacr.org/2023/305.pdf

他メモ

楕円ペアリング

モンゴメリー曲線 Montgomery

  • y^2=x^3+Ax^2+x
    • Aはモンゴメリ係数
    • sagemathだと EllipticCurve(F, [0, A, 0, 1, 0])
  • wikipediaではBy^2=x^3+Ax^2+xとして、パラメタをA,B（B(A^2-4)≠0を満たす）だった
  • 単一座標系を持つ。つまり、座標はx座標のみで表現される。yは無視される
    • これにより効率的なスカラー倍演算が可能になる
  • モンゴメリー座標 P = (X:Z)
    • アフィン空間での座標(x,y)に対してx=X/ZとなるようにX,Zを取り、モンゴメリー座標 P=(X:Z) で表すことができる
      • 変換方法は色々ありそうだが、P(x,y) → P(x:1)
    • モンゴメリー座標に変換して計算することでy座標が無くても高速に計算が可能になる
  • モンゴメリ曲線とツイステッドエドワーズ曲線とは双有理同値

超楕円曲線暗号

同種写像 isogeny

https://mitsu1119.github.io/blog/p/%E3%82%BB%E3%82%AD%E3%83%A5%E3%83%AA%E3%83%86%E3%82%A3%E3%82%AD%E3%83%A3%E3%83%B3%E3%83%97%E5%BF%9C%E5%8B%9F%E8%AA%B2%E9%A1%8C%E6%99%92%E3%81%97-2023-l1-%E6%9A%97%E5%8F%B7%E5%8C%96%E9%80%9A%E4%BF%A1%E3%82%BC%E3%83%9F/ https://project-euphoria.dev/blog/35-yoshicamp-2022-winter-sidh/ https://giapppp.notion.site/Isogeny-based-cryptography-aec3e90af4d14ca1a3db8be7ffd0794a

SIDH

CSIDH

CTF

巻末資料

CTFのCryptoにおけるDLPまとめ [DLP, ElGamal, 離散対数]

Security

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

DLP: 離散対数問題

離散対数問題の効率的な解法

Pohlig–Hellman法

  • 位数の約数がsmoothであるときに離散対数問題が効率的に解けるという問題
  • 離散対数問題 y=g^x mod p に対して、x部分の上限がより小さくなった問題に分割して計算する方法
  • 計算方法
    1. (p-1)を因数分解する。q1 * q2 * ... qk になったとする
      • q1,q2,...,qkは互いに素である必要がある。よって、素因数分解した上で各素因数の累乗についてqiとしてまとめていくことになる
    2. 各qiについて、yi = y ^ (p-1/qi), gi = g^(p-1/qi)と定義して yi = gi^ai mod pで0≦ai＜qiとして離散対数問題を解きaiを求める
      • p-1の因数分解の結果がsmoothな（最大値が小さい）ときにこの小問題が解けてPohling-Hellman法が適用可能になる
      • なぜこうなるかについては、x = ai + bi * qiと定義した後にy ^ (p-1/qi)を色々計算して、逐次定義を付けるとyi = gi^aiが得られる
    3. この時得られたaiの値はx = ai mod qiを満たすので、CRTを適用することでxが得られる
  • ちなみにsageのdiscrete_logはpohlig-hellman + BSGS
    • sageのdiscrete_logは素因数分解できた全部でbsgsやろうとするから、最後の一素因数についてはやらなくていいみたいな場合は手動でやる

DLPの困難性を利用した暗号

Deffie-Hellman 鍵共有

  • Deffie-Hellman 鍵共有: 2者間で秘密a,bを交換することで秘密鍵gabを秘密裏に共有できるアルゴリズム
  • 手順
    1. 整数 g,p を事前に両者で決める（公開して良い）
    2. Aさんが秘密aを、Bさんが秘密bを持っているとする
    3. それぞれ、KA = ga mod p, KB = gb mod p を計算して相手に渡す （つまり、g, p, KA, KBは公開情報で、aはAさんのみ、bはBさんのみ知っている状態）
    4. Aさんは KBa, BさんはKAbをすることで、互いにgabを取得することができる。これは公開情報のみで作るのは困難である
  • g, pの条件
    1. pは1024ビット以上の素数で、p-1の約数の中にpに近いサイズの素数qがある
      • ベストは(p-1)/2が素数
    2. gはi=1, ..., q-1に対してgi != 1 mod pとなる値（このようなgを生成元と言う）
      • 2や5が使われることが多い
  • 改ざん、中間者攻撃には弱い
    • 第三者がKC = gc mod pをAさんに送った場合は秘密鍵がgacとなってしまい、これは盗聴したKAと自身の秘密cから簡単に計算可能

ElGamal暗号

  • ElGamal暗号
  • （法nの）既約剰余類群でのアルゴリズム
    • 鍵生成
      1. p = 2q+1を満たす素数p,qを用意する
        • pを安全素数, qをソフィー・ジェルマン素数と呼ぶ
      2. 法pの既約剰余類群を生成するための生成元gを選ぶ（何言っているのか分からん）
      3. 秘密鍵xを1＜x＜q-1の範囲からランダムに選んで h = gx mod pを計算する
      4. 公開鍵(p,q,g,h), 秘密鍵(x)となる
        • 「離散対数問題の難しさからg,h,pからxを求めるのは難しい」となる
    • 暗号化
      1. 0からq-1の範囲からランダムな値rを選ぶ
      2. c1 = gr mod p, c2 = m * hr mod p を計算。(c1, c2)が暗号文となる
        • ランダム要素が入るのでRSAとは違い、暗号文が2つで、かつ、非決定的な暗号文となる。
        • このrも離散対数問題的に逆算できないようになっていて、かつ、共有しなくても復号可能（使ったら捨てる）
    • 復号 m = c2 * (c1 ^ x) ^ (-1) mod p
  • 乗法準同型性を持つ
    • mxの暗号文(cx1, cx2, rx)とmyの暗号文(cy1, cy2, ry)の場合、暗号文(cx1cy1, cx2cy2)はmx*myをrx+ryを使って暗号化したことになる
  • 脆弱なElGamal暗号
    • 乱数rの流用
      • 流用されている2つの暗号文が手に入ってしまうと、片方が復号化された場合にもう片方も復号できてしまうようになる
    • 危険な法pの使用
      • 安全素数じゃないと危ない
      • Pohlig-Hellmanと効率的な離散対数問題へのアルゴリズム Baby-step Giant-step法で解ける確率が上がる
        • SageMathのdiscrete_log関数を使って離散対数問題を解いてくれる（内部でPohlig-Hellman使われてる）
    • 第三者は復号はできないが、メッセージの値は改変できる可能性がある。暗号文を整数倍すれば、復号文も整数倍される？
  • 平方剰余のルジャンドル記号を使うことで偶奇性は判定が可能

ElGamal署名

  • 実際はElGamal署名から派生したDSAが良く使われる
  • 派生したDSAというデジタル署名方式がある
  • 鍵生成
    • 大きな素数pを選択
    • pを法とする原始根gを選択
    • 秘密鍵xを(1,p-1)の範囲でランダムに選択
    • y=gx mod pを計算し、公開鍵(p,g,y)を作る
  • 署名生成
    • (1,p-1)かつgcd(k,p-1)=1となる乱数kを選択
    • r=gk mod pを計算
    • s=(H(m)-xr)/k mod (p-1)を計算
    • (r,s)が署名
  • 署名検証
    • rが(0,p)、sが(0,p-1)の範囲にあることを確認
    • gH(m) = yr * rs mod pであることを確認
  • 注意点
    • kは予測不可能でないといけない
    • kの再利用により秘密鍵が漏洩する
      • kが共通であり、既知のメッセージm1とm2、またそれらの署名(r,s1), (r,s2)が分かっているとき
      • s1 = (H(m1)-xr) / k
      • s2 = (H(m2)-xr) / k
      • 引くと、s2 - s1 = (H(m2) - H(m1)) / kとなり、k以外は既知なのでkが求まる
      • kが求まれば、s1 = (H(m1)-xr) / kからxが導けて秘密鍵が漏えいする。

Schnorr（シュノア）署名

  • DLP(:離散対数問題)を数学的根拠とする署名方式
    • DSAやECDSAの基礎となっている
  • アルゴリズム
    • 用意：巨大な素数q, qと互いに素な整数g, 署名対象m, 秘密鍵である整数s
    • 以下、署名対象をmとする
    • 署名作成
      1. 適当な乱数 r を作成する
      2. ハッシュ関数Hを用いて、e := H(m;gr)を計算する
      3. 前のステップで求めたeを用いて y = r-se を計算する
      4. (y, e)が電子署名
    • 署名検証
      • 公開鍵としてp=gsが公開される
      • e' := H(m;gype)を計算し、e=e'になることを確認する
    • 検証時の式を見ると変数eが式の両辺に現れている自己言及型の式となっている。ハッシュ関数も使われており、そのようなeを見つけるのは難しそうであるが、実際はp=gsによりyを調整することで（署名作成の手順3）eを簡単に求められる
      • このようにある情報を知っていれば簡単に答えが計算できてしまう処理のことをトラップドア関数と言う
  • セキュリティ
    • 巨大素数qや整数gを適切に選ばないと署名が偽装できるかも
      • 離散対数問題が簡単になって、p=gsが計算できsが漏れる
      • 安全な選び方は原論文に書いてあるとのこと
    • 乱数r
      • 使いまわすと秘密鍵sが漏れる
        • y1=r-se1, y2=r-se2となり、r,sが未知の二次方程式になるので解けばsが得られてしまう
      • 安全でない乱数生成も推測によりrが分かればsが漏洩してしまう

DSA: Digital Signature Algorithm

  • 現状は利用には推奨されない
  • 歴史
    • 1991年にNISTによって、DSS: Digital signature Standardでの目的として提唱
    • 1993年 FIPS 196として標準化され、2013年までに何度か改訂されている
      • なお、FIPS 186-5により、新たにデジタル署名を行うことは推奨されなくなった
  • DSA: ElGamal署名の改良版の1つであり、同様に離散対数問題の困難性に基づく電子署名方式
  • 問題

CTFのCryptoにおけるRSAまとめ [RSA, Coppersmith]

Security

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

RSA

  • RSA: 素因数分解が困難であることを安全性の根拠とした公開鍵暗号
    • 鍵生成 素数p,qを作り、phi=(p-1)(q-1)を計算し、phiと互いに素なeを選択し、d=e-1 mod phiでdを計算する。(N,e)が公開鍵で、dが秘密鍵
    • 暗号化 c = m^e (mod n)で暗号化。Pythonだとc = pow(m, e, n)
    • 復号化 m = c^d (mod n)で復号化。Pythonだとm = pow(c, d, n)
  • 前提となってる数学的なことや性質
    • オイラーの定理
      • aとnが互いに素であり、φ(n)をオイラーのφ関数とするとき、a^φ(n) ≡ 1 mod nが成り立つ
    • phi: オイラーのφ(n), nに対してnと互いに素である1～nの自然数の個数
      • φ(n)=φ(pq)=(p-1)(q-1)である
      • 他にもφ(pqr)=(p-1)(q-1)(r-1)、φ(ppqq)=p(p-1)q(q-1)、φ(p^n)=p^(n-1)(p-1)、φ(ppp)=pp(p-1)、φ(pp)=p(p-1)、φ(p^rq)=(p-1)*p**(r-1)*(q-1)みたいな感じ
    • 乗法準同型性: RSAの暗号化処理をfとした場合に平文a,bに対してf(ab)=f(a)f(b)が成立
      • つまり、任意の平文から暗号文が作れるときに、暗号化したまま既存の平文に乗算できるということ
      • これを使って、適応的選択暗号文攻撃が可能
    • ちなみに、累乗計算は繰り返し二乗法（バイナリ法）で高速計算している
  • 簡単なRSA問題はRsaCtfToolで解けたりする setodaNote CTF Writeup (Crypto) - Tahoo!!
  • nが素数のとき（ポーリック・ヘルマン暗号）
    • gcd(n-1,e)=1のとき
      • d = inverse(e,n-1) dをこんな感じで計算する。
        • つまり ed = 1 mod (n-1) なので ed = k(n-1) + 1
      • m = pow(c,d,n) 復号化は普通
        • (me)d = med = m^{k(n-1) + 1} = m
          • 最後の部分はm^(n-1) = 1 mod nなのでm^{k(n-1)} = 1となるため
    • gcd((n-1)/2,e/2)=1のとき
      • d = inverse(e//2,(n-1)//2) そのままじゃ逆数計算できないので、2で割って無理矢理やる
        • つまり ed/2 = 1 mod {(n-1)/2}なのでed/2 = k{(n-1)/2} + 1でed = k(n-1) + 2
      • mm = pow(c,d,n)とする
        • mm = (me)d = med = m^{k(n-1) + 2} = m2
      • Cipollaのアルゴリズムを使って m2 = x (mod n) でx,nが既知の状態からmを求める
  • eとphiは互いに素である必要がある
  • Nが分からないとき
    • (-1)eが計算できると、N-1(mod N)が得られるので、+1すればNが得られる
    • eが既知で平文と暗号文の組がいくつか得られるときは、gcd(平文1^e-暗号文1, 平文2^e-暗号文2, 平文3^e-暗号文3, ...)をすればNが得られる
  • ed = 1 mod phiであるので、ed = 1 + k * phiということになるが、このときのkはそれほど大きくないので全探索可能だったりする（理屈はよくわかっていないが、min(e,d)くらいの大きさ？）
  • RSA-CRT m = c^d mod Nの計算をCRTを使って高速化する手法
    • Nを素因数分解してN=p1*p2*...*pnであるとする
    • di = d mod (pi-1)をしてdiを求め、mi = c^di mod piでmiをそれぞれ求める
    • こうすると、mi = m mod piになっているので、CRTでp1～pnをまとめるとm mod Nが求まる
    • Fault Attack https://hackmd.io/@Xornet/ryoP8VxUw

攻撃手法

nの素因数分解が出来てしまう

Low Public-Exponent Attack

Håstad's Broadcast Attack（同報通信、同一平文の問題, Hastad Broadcast Attack）

  • m,eが同じでNが異なるメッセージがいくつかある場合、Hastad's broadcast attackという攻撃が可能
  • c1 = m^e (mod N1) c2 = m^e (mod N2) ...というのが与えられているので、中国剰余定理を使うことでmod N1N2...におけるmeが得られて、後はe乗根を取れば平文に戻せる
  • m<Nであるはずなので、N1,N2とかのbit数を見れば何個のサンプルを使ってcrtしてやればいいか分かる
    • 例えば、eが3とかであれば、サンプルを3つ集めればmodがN1*N2*N3のようになるので、N-1を3乗してもちゃんと収まって解ける。ゴミデータが混ざっていてもサンプル3つを全探索で集めてやればよいという問題であった。
  • Wikipediaにある一般化
    • https://en.wikipedia.org/wiki/Coppersmith%27s_attack#H%C3%A5stad's_broadcast_attack
    • 互いに素な合成数を法とする一変数方程式系 g_i(M)=0 mod Ni が十分な数与えられると解ける
    • CakeCTF 2021 Party Ticket https://blog.y011d4.com/20210829-cakectf-writeup#party-ticket
      • c=m(m+b) mod nでn,b,cが異なるものが2組与えられるので、共通するmを求める
      • 最終的にはCoppersmithで解くが、そのためには個々の方程式だとmが十分小さくならないので、方程式を合成してmを十分小さくすることでCoppersmithする（ということだと思う。多分）
      • gi(m)=m(m+b)-c mod niとして構成したg1(m)=0 mod n1とg2(m)=0 mod n2から合成した、G(m)=0 mod n1n2 を作る
        • そのために、G(m)=(n1の倍数でなく、n2の倍数)*g1(m) + (n2の倍数でなくn1の倍数)*g2(m)mod n1n2を構成することを考える
          • これならmod n1、mod n2にすると元の方程式になる
        • この倍数を特定するのにCRTを使う(n2の倍数)=CRT([1, 0], [n1, n2])とすると、n2の倍数だが、n1の倍数ではない数が得られる
          • y011d4さんのブログにあるように、つまりは、クロネッカーのデルタδijを使って、Ti=δij mod nj for all jとなるTiをmod n1n2で求めて使うことになる
      • あとはCoppersmith
  • plain RSAに対する攻撃手法を実装してみる - ももいろテクノロジーが単純で読みやすい実装
  • 問題

Common Modulus Attack

  • Nと平文mが一緒で異なるeで暗号化した暗号文cの組がある場合、拡張ユークリッド互除法を用いて平文mを復号可能
  • mp+qが分かっている場合、mp-1(q-1)=1であることを使うと、mp+q=mN+1になり、meと合わせるとCommon Modulus Attackができる。gcd(N+1,e)=1
  • gcd(e1, e2) > 10の場合は攻撃が難しいらしい

Wiener's Attack

  • 1989年にWienerが提唱した、dが小さいことを利用した攻撃
  • 求め方
    • de=k(p-1)(q-1)+1 を近似していくと de≈knなので、e/n ≈ k/dと変形できる
    • e/nを連分数近似していくと、何処かの近似値がk/dと一致するようになり、k,dが求められる
      • とあるk,dが正しいかどうかはde=k(p-1)(q-1)+1から(p-1)(q-1)を求め、n=pqからp,qを求めてp,qが素数であるかを検証すればいい
  • だが、Coppersmith法を使ったBoneh-Durfee Attackというのがあり、d < n^0.292を満たすときに使える上位互換
    • 詳しくはCoppersmithの中で説明
  • 一般的な形
    • 無知：平文m1, m2
    • 既知：e, N, 暗号文c1, c2, 関数f(x)
      • このときm2 = f(m1)であることが分かっている
    • この時に、m1を高速に計算可能
  • 理屈
    • 関数f(x)=2x+1であるとする。以下は全部mod Nを省略する
    • m1e = c1 であるから g1(x) = xe - c1 とすると g1(m1) = 0
    • (2m2+1)e = c2であるから g2(x) = (2x+1)e - c2 とすると g2(m1) = 0
    • g1もg2も同じx=m1を根として持つので、
      • g1(x) = (x - m1) h1(x)
      • g2(x) = (x - m1) h2(x)
      • のように共通の多項式を持つ
    • よって、g1とg2の公約式を求めることでx - m1の式を得ることができ、m1の値が得られる
  • どうやって公約式を求めるか
  • https://project-euphoria.dev/blog/27-rsa-attacks/#franklin-reiter-related-message-attack
    • 関数f(x)は線形変換である必要はないし、eも共有している必要はない（e1, e2でそれぞれ違っていても良い）
  • より一般的には、無知である要素が平文部分のみである方程式が2つ手に入れば良い
    • SECCON 2020 CTF - urara https://jsur.in/posts/2020-10-12-seccon-2020-ctf#urara
      • EC上の点P(m, 乱数)に対して2P(Qx,Qy)が分かっている状態であれば、(3m^2+a)^2+4(m^3+am+b)(Qm+2m) = 0であることが分かる
      • もう一つ(m+t)^e-c = 0というのが分かっているので、mをxにしてf(x),g(x)を用意してgcdすれば(x-m)という項が出てくるはず
  • e,Nが共有で、2つの平文m, m+dがあったとする。つまり、2つの平文の差が判明している場合
  • https://www.yumpu.com/en/document/read/54527505/ctf-crypto-matome
    • ここによると、「e,nが同じ、かつ、enc(m)とenc(am+b)であれば攻撃可能らしい」
  • m1=m+d1, m2=m+d2でc1=(m+d1)eとc2=(m+d2)e mod Nとなっていて、c1,c2,e,N,d1,d2が既知である状態でも、m'=m+d1とすれば元の形にできるので解ける

Fermat's Method

  • 2つの素数に対して N=pq=(a+b)(a-b) と表現できる
    • p,qの間が小さい場合、aはNのおおよその平方数となり、bは小さくなる
    • よって、Nの平方数周りをaとして採用して、bを全探索すれば素因数分解可能
  • フェルマー法 https://tex2e.github.io/blog/crypto/fermat-factorization-method の実装が一番良い
    • p,qはnの平方根付近になるので、そのあたりで探索
    • nが4092bitsで、pとqの差が512bitsくらいなら直ぐ出てきた
  • (a+b)(a-b)と表現できて、aが比較的簡単に計算できて、bが全探索可能な大きさであれば何でも適用可能
    • 2つの合成数に対しても適用可能 https://project-euphoria.dev/blog/19-ccc-2021/#no-stone-left-unturned
      • 11q = 7p + 11xということが分かっていて、11xが520bitsくらいで小さいため11q ≈ 7pであることが分かる
      • また、11qと7pはどちらも奇数であるため、(a+b)(a-b)と表現可能
      • そして、pとqの積であるNは既知であるため、11*7*Nに対してフェルマー法が適用でき、11q, 7pが得られたら、それぞれ割り算すればp,qが求まる
  • (a+b+1)(a-b)の場合で作問できそうでは？
  • 3乗での応用例 SECCON CTF 2022 - CCC
    • 式をこねくり回すと、aN = s^3 - b^3という式が出てくる。条件は以下
      • a, Nは既知で、s = ap+b
      • 大きさはaが23なので5bits, pが1024bits, bが691bits、よってsは1029bits, Nは2058bitsということで
        • 3082bits = 1029bits^3 - 691bits^3という感じなので、b3は半分ほどの大きさしかないため、無視できるほど小さいと見る
    • 以上の情報から aN ≈ s^3であると言えるため、sの値はaNの3乗根にとても近い所にあると推測される
    • よって、aNの3乗根を取り、+0,+1,+2,...+10000をsの値として、s^3-aNが立方数になるものを探していく
      • 立方数となれば、a3-aNの3乗根がbとなり、sも既知であるため、pを求めることができる（よって、qも求まり、RSAが解ける）
  • 問題

Multi-prime RSA: 3つ以上の素因数からなるRSA

  • n=pqrであれば、φ(n)=(p-1)(q-1)(r-1)が分かれば良い
    • ちなみに、(p-1)(q-1)(r-1) = n+(pq+qr+rp)+(p+q+r)-1なので、そっちが分かるのでも良い
  • Fireshell CTF 2019 Biggars writeup - ふるつき
  • sagemathで素因数分解したら3つ以上の素因数へ分解でき、かつ、個数が多い場合はCRTを使って復元していく

復号化時間を正確に取得できる場合はタイミング攻撃が成立するかも

LSB Decryption Oracle Attack / LSB Oracle Attack

Coppersmith's Method/Attack

Coppersmithは「整数方程式」の絶対値の小さな整数解を多項式時間で求める手法。RSA問題の部分問題としてこのような問題がでてくるので、CoppersmithがRSA問題を解くのに使える。RSA問題以外でも良く出てくる。

Coppersmithの歴史

  • 1996年 Coppersmithが提案した手法
    1. 2変数「整数方程式」の絶対値の小さな整数解を多項式時間で求める手法 - Finding a Small Root of a Bivariate Integer Equation; Factoring with High Bits Known
      • RSAの秘密鍵導出攻撃ができる。N=pqのpとqの上位半分のビットp',q'が分かっているときに、(p'+x)(q'+y)-N=0がx,yがN1/4程度なので解ける
      • 非常に難解なため、Coronによって再定式化された以下の論文での理解がオススメ
        • 2004 Finding Small Roots of Bivariate Integer Polynomial Equations Revisited
          • Coppersmithの手法より少し劣っていた
        • 2007 Finding Small Roots of Bivariate Integer Polynomial Equations: A Direct Approach
          • Coppersmithの手法と同等に
      • https://www.jstage.jst.go.jp/article/bjsiam/18/3/18_KJ00005033174/_pdf 他にも研究が続けられていることが分かる
    2. 1変数整数係数合同方程式の絶対値の小さな整数解を多項式時間で求める手法 - Finding a Small Root of a Univariate Modular Equation
      • RSAの平文回復攻撃ができる。平文mの |m-m'|<N1/e上位ビットm'
      • 非常に難解のため、Howgrave-Grahamによって再定式化されたより簡潔な手法による説明が一般的らしい
        • 1997 Finding Small Roots of Univariate Modular Equations Revisited
  • 有名問題とCoppersmith: 有名問題をCoppersmithで解くという観点で攻撃に名前がついていたりする

最強のCoppersmith's Method Solver - cuso

https://yu212.hatenablog.com/entry/2025/07/27/163347

1変数の場合

  • 1変数の合同方程式に関する最も汎用的な形
    • Nを既知の整数, モニックな1変数δ次多項式f(x)の答えを知りたい
      • モニックとは最高次係数が1であるような多項式
    • 0＜β≦1を決める
      • β=1とすると mod Nでのみ考えることになる
      • β<1とすると N^β≦b かつ b|N である mod bでも答えを導くことができる
        • これが非常に重要でRSAだとmod Nの合同式が得られることが多いと思うが、βを調整することでmod pでの根が得られたりする
    • このとき、f(x') = 0 (mod b) かつ |x'|≦Nβ2/δ を満たすx'を求めることができる
      • 計算量はlogN,δの多項式時間
        • 計算時間はβの値には依存しない
    • 以上のことを考えると、Nは別に大きくてもよさそうだが、式変形などを頑張ってδをなるべく小さくする（多項式の次数を下げる）ことで、計算可能なx'の範囲も広がるし、計算時間も短くなるので嬉しい
    • この手法がSagemathのsmall_roots関数やPari/GPのzncoppersmith関数で採用されている
  • sagemathのsmall_roots関数
    • 使い方 python PR.<x> = PolynomialRing(Zmod(n)) f = e * (s + 2**470 * x) - 1 - k * (-1) * (rq - 1) # 多項式を用意 f = f.monic() # モニック多項式である必要があるので変換 roots = f.small_roots() # 解く ans = int(roots[0]) # intでキャストしないとバグるので注意
    • small_roots(self, X=None, beta=1.0, epsilon=None) https://github.com/sagemath/sage/blob/e7477f887968f0f133e15618ad5444473aa8fb4b/src/sage/rings/polynomial/polynomial_modn_dense_ntl.pyx#L471
      • X: 根の上界。つまり、|x'| < Xを満たすXのこと
        • 省略されるとX = ceil(1/2 N^{\beta^2/\delta - \epsilon})で計算される
        • 省略せずに2^Kbitsみたいにギリギリでちゃんと指定したほうが良さそう
        • X < N^(1/degree)
      • beta: 上で説明しているβ。mod Nで計算したい場合はβ=1とする（つまり省略）。Nの約数modにしたい場合は、ギリギリまで調整する
      • epsilon: 「根の近似度」や「誤差」の量を制御するためのパラメータ
        • 多変数の多項式の解の近似を求める際に重要です。特に、RSAのような大きな整数問題を扱う場合、ϵ の選び方によって、解がどれだけ正確に求まるか、または計算が成功するかに影響を与えます
        • 小さい根を求める場合（小さな公開鍵の因数分解など）：ϵ は比較的小さく設定される傾向があります。これは、多項式の小さな根を近似的に求める場合に高い精度が必要であるためです。
        • より大きな問題に対する攻撃の場合：ϵ は問題のスケールに応じて調整されることがあります。例えば、整数のサイズが大きくなるほど、適切な近似のために大きめのϵ が必要になることがありますが、攻撃の成功率を維持するためには、依然として小さめに設定することが多いです。
        • 一般的には、ϵ は logN （NはRSA modulus）の一部に比例する形で選ばれることが多いです。
        • デフォルトはepsilon = beta/8。epsilon = beta^2/7としているものもある
      • パラメタ色々
      • sageのsmall_rootsはbetaを適当な値にしたら法nの代わりにnの約数を法とした式をそのまま法nで突っ込んでも正しい答えが得られることがあるっぽい
        • nとpののbit数がかなり離れている必要がある？
    • パラメタガチャ py for i in trange(1, 101): cur_sol = f.small_roots(X=2**(8*flag_len), beta=i/100)
  • テク
    • 未知変数は全体に対して小さくないといけないし、次数はある程度小さくないと計算できない。終結式とかグレブナー基底で簡単にするとうまくいくかも？
    • 法は約数modとして考えて答えを出すこともできる
    • 約数modで計算できることを利用して、元々の法の値が分からなくても、因数が共通なら計算できちゃう
      • Full Weak Engineer CTF 2025 Multi ﾊﾟﾜｰ RSA
        • A+d=0 mod p^(r-1)(p-1)(q-1)を計算したいのだが法は分かってない状態で、A+d=0 mod NでCoppersmithして計算するとdが求められる。これは、A+d=0 mod p^(r-1)(p-1)(q-1)であるならばA+d=0 mod p^(r-1)であると言えて、またN=pr qであるならば、mod Nでcoppersmithするとmod pr-1での答えが求められるためである。d < p^(r-1)なら正確な値が出せる。
        • 元問題をPrime-Power RSA(Takagi RSA)と呼ぶみたい？
    • 2乗や3乗のものは扱えないのだが、2乗や3乗してもまだ小さければそれを1つの変数として扱ってしまえる
    • Coppersmithの高速化テクがある？ Codegate 2024 FactorGame https://blog.y011d4.com/20240602-codegate-writeup#factorgame
  • Coppersmithに祈りの要素はあまりなさそう

多変数の場合

  • 一般に変数の数が増えれば増えるほど解くための条件が厳しくなるため、なるべく変数の数を減らす方向で考察する必要がある
  • 多変数の方程式を解くときはdefundのライブラリを使うのが良い
  • （あまり理解してない。ガチャ）

初めて勉強する人が読むべき資料

  • shihoさんの https://elliptic-shiho.github.io/slide/katagaitai_winter_2018.pdf
    • 必ず最初に読むべき。ちゃんと飛ばさずに読むこと
    • 特に「方程式を増やすパート」についてはこれ以上分かりやすい説明は多分なく、実際に計算できる問題も付いている
  • 2つ目の資料として本「暗号の理論と技術」が良い
    • 多変数の場合の話が書いてあるのと、LLLにどんな格子を投げるかについて色々書いてある
  • （偉そうに書いているけど、全然理解できてません。cusoでブラックボックス的に解けてしまうので、背景の理論を定期的に忘れる）
  • （あと、ちゃんと原論文を読めないとダメなんだと思います）

Coppersmithで解ける問題などなど

RSA署名：RSAで公開鍵署名をするとき（秘密鍵で暗号化して、公開鍵で復号化して検証するとき）

https://www.jnsa.org/active/topics/rsa_doc.pdf

  • 公開鍵(N,e)で秘密鍵dであったとする
    • mを署名するとき、md mod Nを計算して渡す
    • もらったmdに対して(md)e mod Nを計算することで復号化して検証する
  • パディングについて
    • RSAは復号ができても、それが正しく元のメッセージになっているとは限らない
    • つまり、メッセージの真正性を検証する必要があり、その用途のためにパディングが用いられる
    • パディングをつけて暗号化し、復号化した後にパディングが正しいかを検証することになる
  • 署名enc関数のブラックボックス実行環境が与えられているとき、公開鍵Nを特定する方法
    • gcd(enc(2)^2 - enc(4), enc(3)^2 - enc(9))が公開鍵N
    • これはenc(2)^2 - enc(4)がmodNだと0にはなるが、2部分はmodNがかかからないので、ちょうどNの倍数になっている
    • よって、こういう例をいくつか用意してgcdを取るとNが特定できる
  • RSA署名には乗法性がある。f(m)=md mod Nとすると、f(a)f(b)=ad*bd=(ab)d=f(ab) mod N
    • 小素数法 f(m) のmが素因数分解可能な場合に、その素因数pを署名したf(p)が得られればその情報でf(m)が得られる
  • RSA-FDH署名: RSA署名にハッシュ関数を組み合わせた方式
    • 安全性は向上しているが、効率はあまりよくないらしい

RSA-OAEP

PKCS #1 v1.5

CTFにおけるCrypto入門とまとめ

Security

はじめに

CTFのCrypto問題を2024年の末からコツコツ解いてきたのだが、明らかにAIの方が強く、この進捗だと抜かせそうにない雰囲気なので、ここらでcrypto関連の集めた知見をまとめておいておくことにする。
そこそこ勉強したと思うのだが、未だに解説が読めないときがあるので、数学をもっと勉強しないとですね...（こういう記事を書いている場合ではない）
ちなみに、ここでは"Crypto"を暗号通貨を指しては使わない。CTFではどちらかというと"Web3"とか"Blockchain"とかのカテゴリに入れられることが多いように思う（私見です）。

CTF入門

CTFとは何なのか

CTFとはセキュリティ的な問題を解く競技のことであり、色々なジャンルに分かれている。
全体的な話は他の記事に譲るとして、Crypto問題に絞って話すことにしよう。
大体のCTFは一問一答の形をとっており、とある暗号システムが与えられて、そのシステムの脆弱性を突くことで暗号を復元したり、内部で生成される乱数を推測することで「お宝」を出力させるのが目的である。
このお宝をFlagと呼んでおり、一般的にはハッカーが暗号システムを攻撃して手に入れたい情報という風に解釈されている。
分かりやすい問題の例を挙げておくと、秘密鍵が分からないにも関わらず脆弱性があるために、暗号文が復号できてしまうといった感じである。

初学者に向けて

中級者になったとは思ってはいないが、初学者は脱したかなと思うので、これからCTFのCryptoをやってみたい初学者が取るとよさそうな道筋を考えて残しておくことにする。

  • 現状、まっさらな状態でCryptoに取り組もうとする場合は、CryptoHackのコースやチャレンジに取り組むのが良いのではと思う。英語ではあるが、特にコースでは1歩1歩教えてくれるので非常に参考になる。
  • 書籍で勉強するのが好きな人向け
    • 本を1冊オススメするとしたら結城先生の「暗号技術入門 秘密の国のアリス」を挙げておく。日本語で非常に分かりやすく書かれており、内容の濃さもさすが結城先生といった1冊になっている。
    • 他にも分厚いので1冊目としてはオススメしにくいがIPUSIRON先生の「暗号技術のすべて」も日本語で暗号について広く書かれている良書であり、「暗号の理論と技術 量子時代のセキュリティ理解のために」も難しいテーマやあまり日本語では解説が分厚くない分野を易しく説明していてとても参考になった。
  • インターネットでアクセスできるもの
  • 各トピックで色々参考になる

…と色々書いたが、トライアンドエラーで試行錯誤していく他無いのが現状ではないだろうか。
CTFは毎週何かしらやっている。
CTFtimeというサイトでActiveなCTFが見られるので、そこで毎週出てみよう。
大会開催後は有志による解説、CTF用語で言う所のWriteupが公開されるので、解けなかった問題を復習していく。
Writeupが公式から提供される確証は無いので、なるべく参加人数が多いCTFに出ると復習できる可能性が上がるだろう。
YouTubeで動画形式で上げてくれている人もいるので、理論だけでなく実践的なやり方をこれで学ぶこともできる。

なお、Cryptoで最初に勉強する分野に迷ったら"RSA"から始めることを推奨する。

Crypto問への取り組み方

ここからは入門者が知識として得づらい部分や話しておくべきこと、暗黙知的や経験則をつらつら書いていくことにする。

  • 問題にhoge.ctf.example 1337のように接続情報が書かれている場合は問題サーバが与えられていることを指している
    • 単純なテストであればnc hoge.ctf.example 1337としてインタラクティブに操作してみると良い
    • 大体はサーバから得られた値を使って計算することになるので、Pythonであればptrlibやpwntoolsを使って通信も含めたソルバーを書いて解く
  • Pythonっぽいけど何か違うというソルバーを見かけたら、SageMathで書かれているので注意
    • CryptoではSageMathという数学ソフトウェアを使ってソルバーを書くことが多々ある。SageMathには計算を簡潔に書くための便利なアレコレが揃っているので、より本質的な解法に集中しやすい。Pythonで動かしてみたが、なんか構文エラーになるぞというとき、SageMathであることを疑うと良い（慣れれば、見ればすぐSageMath向けのソルバーであることが分かってくるようになる）
    • またfrom Crypto.Util.number import *みたいにPythonで使われているのは、PyCryptodome。PyCryptoは古いので使わないこと
  • 古典暗号というのがあるが、真に面白い（個人差有り）のは近代暗号
    • 暗号というとシーザー暗号などが最初に持ち出されがちではあり、歴史的には正しい順番ではあるのだが、古典暗号と近代暗号は暗号システムとしての考え方や取り組み方がまったくもって異なることに注意すること。
    • 個人的には近代暗号に面白さが詰まっているので、古典暗号を頑張ってCryptoはこういうものだと理解するのはとてももったいない。古典暗号にもある種の面白さはあるのかもしれないが、個人的には近代暗号をやってほしい
    • だが、実際にはCTFに出てくるときがあるので、本まとめでは最後に古典暗号を取り扱っておく。エニグマまでが古典暗号っぽい。
  • 数学知識は必要か
    • 最初から必要とは思わないが、合同式の理解が前提とされていたり、数論の記法を使って説明されることもよくあるため、数学知識が無いと解説が読めないという事態が発生する
    • だが、あると有利なのは確実で、特に数論・代数論の背景があると良い。情報学部ではやらない（多分）ので、数学科や物理学科の方が向いてそうではある（多分）
    • それ以外にも競技プログラミングでも良く出る解析まわりも使われるので、競技プログラミングをやっていると幾分有利な気もする
      • 正確には「数オリ上がりの競プロer」にはとても得意そうである
  • たまにうまく検索するとばっちり使える論文があるので解けますみたいな問題があったりする
    • Webにおけるワンデイ問題みたいな雰囲気なのかも
    • 論文を検索するのにも論文を読むのにも英語と数学知識が必要
  • （AIが無茶苦茶賢いので分からなかったら聞くといいです。Writeupでもソルバーだけポンと置かれて数学的背景が全く分からんという状況でもそれっぽく答えてくれます（ですが、ソルバー読んで分からない場合は前提知識が付いていない場合も多く、その場合AIから色々言われても正しいのか分からんという問題もありますが...））

まとめ

これからはまとめ記事をいつものように書いていく。手取り足取りという解説記事ではなく、キーワード集であり、勉強の足掛かりや全体像の把握に活用してほしい。

より強くなるために

解説も読めないときが多々あるので強くなったら書き足します。