Carpe Diem

備忘録。https://github.com/jun06t

署名と暗号強度について

概要

署名ロジックを選ぶ際に、どのアルゴリズムにするか、どれくらいの鍵長が適切なのかが分からなかったので調べてまとめました。

対象

共通鍵暗号(対称暗号)

  • 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 (2016)

ざっくりとした特徴としては、

  • AESは鍵長がそのまま暗号強度になる
  • RSAは鍵長が倍になるたびに32bit増える
  • ECCは鍵長の半分程度が強度になる

という感じです。

ハッシュ関数の強度

セキュリティービット 署名 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 (2016)

特徴としては以下です。

  • HMACはほぼそのままが強度になる
  • 署名の場合は半分の値が強度になる

なぜ署名のケースとHMACのケースで異なるのか

ハッシュ関数の持つ、原像計算困難性(弱衝突耐性)強衝突耐性の違いによるためです。
HMACの方は原像攻撃に対する耐性で算出され、署名の方は誕生日攻撃に対する耐性で算出されています。

原像計算困難性(弱衝突耐性)

ハッシュ値からメッセージを発見することが困難となる性質です。
一方向ハッシュ関数と呼ばれるくらいなので、原像(元のメッセージ)を計算することができない事が必要ですね。

強衝突耐性

ハッシュ値が一致する二つのメッセージを見つける際の耐性です。
これは誕生日のパラドクスと呼ばれる理論から、ビット数の半分の試行回数で済みます。

最近だとGoogleSHA-1の強衝突耐性について、実際に同じハッシュになるPDFを公開してます。

Google Online Security Blog: Announcing the first SHA1 collision

まとめ

最低でも128bitのセキュリティービットの強度をもつ暗号や署名を使いましょう。
一方で鍵長が長くなればパフォーマンスが低下するので、そのバランスも考慮しましょう。

ソース