暗号学的ハッシュ関数

三つの特徴

よく見る暗号学的ハッシュ関数も奥が深いのです。

デジタル署名を語る上で欠かせないこの暗号学的ハッシュ関数は以下の三つの特徴をもっています。

https://scrapbox.io/files/6197edbbc2c9c0001f65bc3b.png

衝突耐性

暗号学的ハッシュ関数だけがわかっているときに同じハッシュが出力されるようなふたつの異なる入力を見つけるのが難しい

ハッシュ関数とハッシュだけがわかっているときに、ハッシュの原像を見つけるのが難しい

ハッシュ関数と1個の原像が分かっているときに、同じハッシュを出力する別の原像を見つけるのが難しい

ハッシュ値からメッセージを特定する攻撃を考えましょう。

典型的なデスクトップコンピュータの場合、6千万回/秒のハッシュ計算が可能とすると総当たり攻撃によって解を見つけるのに必要な試行回数は2^255回なので解を見つけるのにかかる時間は

$ 2^{255}÷(60×10^6)≈3×10^{6}1年

この計算量的安全性がハッシュ関数そしてデジタル署名の安全性の根拠になります。

この様なハッシュ関数を一方向性ハッシュ関数と呼びますが、実は完全な一方向性を持ったハッシュ関数は見つかっておらず、「たぶん大丈夫」という感じなので研究者がこぞって攻撃手法を考えたり安全な関数を選定しています。

そのなかでもNIST(アメリカ国立標準技術研究所)が全世界から公募し、選定されたSHA(Secure Hash Algorithm)と呼ばれるシリーズがデファクトスタンダードになっており今までにSHA1,SHA2,SHA3が選定されました(厳密にはSHA0も存在する)

https://scrapbox.io/files/6197edcba07827002341bdab.png

SHA1はハッシュ値の衝突が見つかっており、現在では使用されていません。

Bitcoin Coreの実装が2009年の話なので、このときSHA2が採用されました。

一方で、Ethereumは2015年なので、SHA3を採用しています。

SHA2

SHA2のなかでも広く使用されているSHA256は以下のような仕組みでメッセージをハッシュしています。

https://scrapbox.io/files/6197edd4224559001dab1124.png

①〜②はメッセージのビット数を合わせる為の作業です。

ハッシュ化するためには撹拌部と呼ばれる③が大事になってくるので詳しく見てみると...

https://scrapbox.io/files/6197eddd4297a5001eda61a9.png

何やってるかわからないレベルでごちゃ混ぜにされている模様

SHA3

SHA2と違い、入力サイズに制限がなく、出力も任意長に設定できるのがSHA3の良いところ

SHA3では二つのフェーズに分かれてハッシュ化されています。それが吸収フェーズと搾出フェーズです

前述の通り、この様に、入力されたメッセージのビットを撹拌し、必要なビット数を取り出す様子からスポンジ構造と呼ばれています。

出力を任意長に設定できるのは、搾出フェーズで必要なビット数だけ抜き出しているためです。

https://scrapbox.io/files/6197ede4614f59001d097a3d.png

下の図における関数fはSHA2の図における,③の部分にあたるので詳しく観てみよう

https://scrapbox.io/files/6197edee8af610001f1e8cb9.png

関数fで何が起きているかというと、各ビットを三次元ベクトルに置き換え、ルービックキューブのようにごちゃ混ぜしている。

以下のパターンはその動かし方の一部

https://scrapbox.io/files/6197edf78af610001f1e8cd2.png

https://scrapbox.io/files/6197edfe750d94001f22e22e.png

https://scrapbox.io/files/6197ee0587a3570021ede354.png