はじめに
最近、ブロックチェーンについて調べたり勉強してたのだが、その中でハッシュが何度も使われているため、まとめてみました。
ハッシュ関数とは
あるデータが与えられた時に、そのデータを代表する値を導く操作、あるいはその数値を得るための関数。
hashは「切り刻んで混ぜる」の意味。ハッシュドビーフのハッシュ。
用途
ハッシュテーブル
検索キーのハッシュ値を取って、それを基準に値を格納する方法。
プログラミング言語で、連想配列をハッシュと呼ぶのは、連想配列の実装にハッシュテーブルが使われているため。
データ区分・検証用
gitのidとしてSHA-1が使われています。
ブロックチェーンのブロック、トランザクションの識別にはSHA-256が使われています。
変更・改ざん検出
データが正しくコピー、転送されたか確認するために、ハッシュ値と照らし合わせることがあります。（チェックサム計算やCRCの計算）
ビットコインのブロックチェーン技術にも、改ざん検出の為にハッシュ値が使われます。
電子署名
電子証明書のハッシュ値を計算し、そのハッシュ値を暗号化することで、証明書が改ざんされていないことを確認できるようになっています。
現在は、電子署名にSHA-2アルゴリズムが使われています。
ハッシュ関数に必要な性質
- データが少しでも変わったら、ハッシュ値も変化する
- データが異なるが、ハッシュ値が同じになる（衝突する）ことが少ない
- 低計算コスト
- ハッシュ値から元のデータが推測できない
代表的なハッシュ関数
チェックサム
単純加算のチェックサムも、簡易なハッシュ値算出方法の一つ。
データの改ざんに対する耐性はない。
CRC（巡回冗長検査）
誤り検出符号の一つ。
デジタル回路で実装が容易なことから、データ転送の誤り検出によく使われる。
多数のバリエーションがあり、ハッシュ値のビット数により CRC-○○と呼ばれる。
データの改ざんに対する耐性はない。
md5
与えられた入力に対して128ビットのハッシュ値を出力するハッシュ関数。
電子署名のために開発されたが、現在は、理論的な弱点が見つかり電子署名には使われていない。
SHA-1
Secure Hash Algorithmシリーズの１つ。gitのidに使われている。
SHA-1は、160ビット（20バイト）のハッシュ値を生成する。
gitのidが衝突する（違うコミットが同一idになる）確率は以下と言われている。
How hard is it to get a git hash collision?
非常に大きなプロジェクトで、1000人のアクティブな開発者が、日に10回のコミットをしたとする。この場合、4×10の17乗年間活動を続けると、50%の確率で衝突が発生する。
（4x10の17乗年は、40京年）
以前は、SSLサーバ証明書の電子署名に使われていたが、攻撃法の研究が進んだことにより、電子署名の用途はSHA-2に置き換えられている。
2017年、同じSHA-1ハッシュ値を持つ異なるデータがgoogleにより公開された。（後述）
SHA-2
SHA-2はSHA-224、SHA-256、SHA-384、SHA-512、SHA-512/224、SHA-512/256の6つのバリエーションを持ち、ハッシュ長は224、256、384、512ビットのいずれか。
今のところ、脆弱性は見つかっていない。
SHA-1衝突の検証
2017年2月にGoogleとオランダのCWI研究が、SHA-1衝突に成功したと発表し、衝突しているPDFを公開しました。
衝突しているPDFファイルは以下からダウンロードできます。
shattered
pythonでは、hashlibを使って各種アルゴリズムでのハッシュを計算できます。
>>> import hashlib
>>> hashlib.md5(b'hello hello').hexdigest()
'f52d885484f1215ea500a805a86ff443'
ダウンロードしたPDFのSHA-1を算出すると、同じになっていることが確認できますが、md5を計算すると異なる値になっています。実際に開いてみても異なるPDFです。
>>> import hashlib
>>> with open('shattered-1.pdf','rb') as f:
... hashlib.sha1(f.read()).hexdigest()
...
'38762cf7f55934b34d179ae6a4c80cadccbb7f0a'
>>> with open('shattered-2.pdf','rb') as f:
... hashlib.sha1(f.read()).hexdigest()
...
'38762cf7f55934b34d179ae6a4c80cadccbb7f0a'
>>> with open('shattered-1.pdf','rb') as f:
... hashlib.md5(f.read()).hexdigest()
...
'ee4aa52b139d925f8d8884402b0a750c'
>>> with open('shattered-2.pdf','rb') as f:
... hashlib.md5(f.read()).hexdigest()
...
'5bd9d8cabc46041579a311230539b8d1'