【セキュリティ基礎】ハッシュ関数での一方向性と衝突困難性

暗号系を構成する三種の神器の一つがハッシュ関数、ちなみにハッシュとは「切り刻んで混ぜる」という意味があり、もともとIBM発祥の隠語でしたが、後に専門用語として定着したそうです。

POINT暗号化的に重要な理由は、データの改竄を検出できること!!

ハッシュ関数では、原文を一文字でも変えるとハッシュ値全体が大幅に変わり、またハッシュ値から原文を辿ることが極めて困難(一方向性)であるため、原文の改竄検出に役立ちます。

またハッシュ関数で大切な要素の一つに衝突困難性で、これは異なるデータ同士で同一ハッシュ値が出力されない性質のことですが、プロの暗号学者が設計したハッシュ関数でも、同業者が注意深く調べると結構穴があったりするらしい。

マークル・ダンガード構成法

一方向性(原像計算困難性)と衝突困難性を満たすハッシュ関数は、どのように構成すれば良いのか!?

POINT最もわかりやすいと知られているのが、マークル・ダンガード構成法!!

圧縮関数f(入力全体を半分の長さにする)を用意し、原文を幾つかのブロック(一定の長さ)に分割。

◼️ マークル・ダンガード構成法のハッシュ化.

1. 初期ベクタとメッセージブロック1を圧縮関数fで処理して出力Aを得る.

2. 出力Aとメッセージブロック2を圧縮関数fで処理して出力Bを得る.

3. 同様の処理を最後のメッセージブロックnまで繰り返し行い、ハッシュ値を出力.

圧縮関数を繰り返し利用するので、繰り返し型ハッシュ関数、反復型ハッシュ関数とも呼ばれます。

POINTMD5はマークル・ダンガード構成された代表的なハッシュアルゴリズムの一つ.

マークル・ダンガード構成では直前のメッセージブロックを圧縮関数を通して次のブロックに混ぜるため、最後のハッシュ値が全てのデータブロックの影響を受け、原文を一文字しか変えると大幅にハッシュ値が変わり、メッセージの改竄検出が可能となります。

バースデーパラドックス

衝突困難性を満たすハッシュ関数の設計に役立つ概念がバーステーパラドックス。

部屋の23人の人がいる。
このとき、誕生日が同じペアが一組み以上いる確率はどれくらいか。
ただし、うるう年は考えないものとする。

本書ではこの例題からバーステーパラドックスの本質は「部屋にいる人数を増やすと、ペアの総数が2乗に比例して増える」と書かれているが、ペアの総数「n(n-1)/2」を展開すると分かりやすい。

展開するとn^2/2 – n/2なので、人数nが大きくなる程にn/2の影響を受けず、ほぼn^2/2に近い値を取り、ペア総数は人数nの2乗に比例して増加することが理解出来る。

POINTペア数の増加で誕生日の衝突増 = 誕生日の衝突検出を見つける人数は候補全体のルート.

ハッシュ値のサイズがmbitの場合、n = 2^mと表せる。

POINTバーステーパラドックスが働くためには、nのルート = 2^m/2となる.

例えばmを32bitの場合、n = 2^32となり、ルートn = 2^16=65536個程度のメッセージを集めれば衝突が起きるため、ルートnが大きくなるようにハッシュ値のサイズmを決めなければならない。

パスワード認証

Webサービスのパスワード認証でも利用されるハッシュ関数。

ネットワーク上でパスワードのやりとりをする場合、生のパスワードをやりとりするのは危険なので、パスワード流出を防ぐための仕組みが必要でその一つがAPOP。

POINTAPOPはサーバがチャレンジCを送り、ユーザは入力パスワードとCでハッシュ化し送信.

サーバ側でハッシュ値が一致するかチェックするので、盗聴されても復元は困難でしたが、攻撃者はチャレンジCを盗聴することで辞書攻撃ができ、APOPで採用されているハッシュ関数MD5が破られた影響で、現在では非推奨となっています。

POINT現在ではAPOPに代わり、POP3S(SSL/TLS上のPOP3)が推奨されています.

ただ2017年時点ではAPOPが使われている場合もあり、暗号的な穴が見つかっても、既に使われているシステムで安全なものに置き換えるには、かなりの時間を要するようです。