Pebble Coding

ソフトウェアエンジニアによるIT技術、数学の備忘録

ハッシュ関数の脆弱性

ハッシュ関数とは任意の数のビット列 \{ 0, 1 \}^{*}から固定長nのビット列 \{ 0, 1 \}^{n}を出力する関数です。
大きなサイズの入力を小さな出力にするわけですから、当然ながら衝突します。
衝突するのに出力のサイズに出来るだけ近い試行回数が必要になっていれば、十分な強度だと言えます。
ハッシュの手順は少ない方が実際に使うには都合が良いので、少ない手順で低い衝突率を実現させるのが、
優れたハッシュ関数だと言えます。

ハッシュの強度がどの程度なのかを一般的に測る手法は、聞いたことがないので、おそらく発明されていないっぽいです。
ハッシュの特徴を表す概念がいくつかありますので、見ていきます。

A) 現像計算困難性: 意図したハッシュ値を出力させる値を見つけるのが難しい。
B) 第二現象計算困難性(弱衝突耐性): 入力値とそのハッシュ値の情報から、同じハッシュ値を出力する別の入力値を見つけるのが難しい。
C) 衝突困難性(強衝突耐性): 異なる2つの入力値に対して、そのハッシュ値を等しくさせるのが難しい。

MD5(出力128bit)はC)衝突困難性の強度が十分でないことが、2004年に示されました。
SHA1(出力160bit)はC)衝突困難性の強度が十分でないことが、2017年に示されました。

要するに、出力サイズに比べて、ちょっと弱い強度しかないよということです。
普通のアプリケーションであれば、「ごめんごめん、じゃあ別のハッシュ関数使うから勘弁してくれや」で済みますが、
過去の履歴などが積み重なっているようなアプリの場合は入れ替えが大変そうです。

MD5,SHA1のB)は破られてはいないので、C)の条件が不要な場合は使用を続けても問題はありません。
gitではsha1が使われていますが、gitでは、入力値のサイズ自体も管理しており、サイズも衝突させるのは、
おそらく難しいので、実用上の問題はなさそうです。

GoogleのSHA-1のはなし

SipHash

ハッシュ関数のC)の特徴はまったく必要なく、B)の特徴だけが必要で速いハッシュ関数が必要な場合は、
遅いSHA系統のハッシュ関数ではなく、SipHashを使います。

SipHashの特徴 - Pebble Coding