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

hamayanhamayan's blog

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