概要
署名ロジックを選ぶ際に、どのアルゴリズムにするか、どれくらいの鍵長が適切なのかが分からなかったので調べてまとめました。
対象
共通鍵暗号（対称暗号）
- AES
公開鍵暗号
鍵長とセキュリティ強度
各アルゴリズムの鍵長と、セキュリティ強度の表を示します。
| セキュリティ強度 | 対称暗号（AES） | 素因数分解暗号（RSA） | 楕円曲線暗号（ECC） |
|---|---|---|---|
| 80bit | - | 1024 | 160 |
| 112bit | - | 2048 | 224 |
| 128bit | 128 | 3072 | 256 |
| 192bit | 192 | 7680 | 384 |
| 256bit | 256 | 15360 | 512 |
ref: Keylength - NIST Report on Cryptographic Key Length and Cryptoperiod (2020)
ざっくりとした特徴としては、
という感じです。
楕円曲線の種類
楕円曲線はさらにいくつかの種類があり、それぞれ特徴（曲線、性能など）が異なります。
主に使われる曲線は以下です。
- NIST
- Brainpool
- Curve25519
鍵長とセキュリティ強度の比較は以下です。
| セキュリティ強度 | NIST | Brainpool | Curve25519 |
|---|---|---|---|
| 128bit | 256 | 256 | 256 |
| 192bit | 384 | 384 | - |
| 256bit | 521 | 512 | - |
ハッシュ関数とセキュリティ強度
| セキュリティ強度 | 署名に使用 | HMACに使用 |
|---|---|---|
| 80bit | SHA-1 | - |
| 112bit | SHA-224 | - |
| 128bit | SHA-256 | SHA-1 |
| 192bit | SHA-384 | SHA-224 |
| 256bit | SHA-512 | SHA-256 |
ref: Keylength - NIST Report on Cryptographic Key Length and Cryptoperiod (2020)
特徴としては以下です。
- HMACに使用した場合はほぼそのままが強度になる
- 署名に使用した場合は半分の値が強度になる
なぜ署名のケースとHMACのケースで異なるのか
ハッシュ関数の持つ、原像計算困難性と強衝突耐性の違いによるためです。
HMACの方は原像攻撃に対する耐性で算出され、署名の方は誕生日攻撃に対する耐性で算出されています。
原像計算困難性
ハッシュ値からメッセージを発見することが困難となる性質です。
一方向ハッシュ関数と呼ばれるくらいなので、原像（元のメッセージ）を計算することができない事が必要ですね。
強衝突耐性
ハッシュ値が一致する二つのメッセージを見つける際の耐性です。
これは誕生日のパラドクスと呼ばれる理論から、ビット数の半分の試行回数で済みます。
最近だとGoogleがSHA-1の強衝突耐性について、実際に同じハッシュになるPDFを公開してます。
Google Online Security Blog: Announcing the first SHA1 collision
第2原像計算困難性（弱衝突耐性）
ちなみに弱衝突耐性と呼ばれる第2原像計算困難性もあります。
これはあるメッセージAがハッシュ値Zになるという前提条件の元で、同じハッシュ値ZになるメッセージBが見つけられるかどうかの耐性です。
これができるとハッシュ値で正当性を担保していたファイルのすり替えなどが可能になってしまいます。
弱とありますが強衝突耐性よりも計算は困難です
まとめ
最低でも128bitのセキュリティ強度をもつ暗号や署名を使いましょう。
一方で鍵長が長くなればパフォーマンスが低下するので、鍵長の短いECCを使うなどバランスも考慮しましょう。
