概要

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

対象

共通鍵暗号（対称暗号）

公開鍵暗号

鍵長とセキュリティ強度

各アルゴリズムの鍵長と、セキュリティ強度の表を示します。

セキュリティ強度	対称暗号（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)

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

AESは鍵長がそのままセキュリティ強度になる
RSAは鍵長が倍になるたびに32bit増える
ECCは鍵長の半分程度が強度になる

という感じです。

楕円曲線の種類

楕円曲線はさらにいくつかの種類があり、それぞれ特徴（曲線、性能など）が異なります。
主に使われる曲線は以下です。

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を使うなどバランスも考慮しましょう。

Carpe Diem

備忘録

署名と暗号強度について

概要

対象