ハッシュ関数の基礎

 ちょっとずつ勉強を進めているブロックチェーンに関連して、ハッシュ関数について調べた時のメモ。『暗号技術のすべて』(翔泳社)などを参考にした。

ブロックチェーンの4つの構成要素
1.ピア・ツー・ピア(P2P)ネットワーク
2.コンセンサス・アルゴリズム(PoW、PoS、PDFTなど)
3.電子署名・ハッシュ関数
4.スマートコントラクト

情報セキュリティの6要素

 公開鍵暗号や電子署名、ハッシュ関数などが情報セキュリティの構成要素だというのは分かったとして、そもそも情報セキュリティとはなにか?

--> OECDの情報セキュリティガイドラインが挙げる3要素「機密性」「完全性」「可用性」に、ISO/IEC TRI13335が追加する「責任追跡性」「真正性」「信頼性」加えた6要素が、情報セキュリティの6要素になる。

暗号や電子署名などの各技術は、この6要素の少なくとも1つを実現するための技術なので、それぞれが担当する範囲を意識すると関係性が分かりやすい。

1.機密性(Confidentiality)

  • 意図した相手以外に情報が漏れないこと。
  • 脅威の例:盗聴(データの盗み見や抜き取り),内部からの情報漏洩
  • 対策の例:暗号,誤り対策符号

2.完全性(Integrity)

  • 情報が正確であること
  • 脅威の例:改ざん,ノイズなどによるビット反転・欠落
  • 対策の例:ハッシュ関数,メッセージ認証コード,デジタル署名

3.可用性(Availability)

  • 許可された人が必要な時点で情報を使用できること
  • 脅威の例:過負荷,災害,意図しないロック状態
  • 対策の例:クラウド化,負荷分散,ログの記録

4.責任追跡性(Accountability)

  • ユーザの行動や責任を説明できること
  • 脅威の例:ログの改ざん,否認
  • 対策の例:デジタル署名(否認防止)

5.真正性(Authenticity)

  • ユーザやシステムによる振舞いが正確であること
  • 脅威の例:なりすまし
  • 対策の例:デジタル署名(なりすまし防止),認証

6.信頼性(Reliability)

  • システムやプロセスが矛盾なく動作したり、一貫して動作したりすること
  • 対策の例:システムの多重化,負荷の監視

ハッシュ関数

ハッシュ関数とは、任意長のビット列から規則性のない固定長のビット列を生成する関数、手順のことをいう。 一般に、ハッシュ関数への入力データは「メッセージ」、ハッシュ関数からの出力データは「ハッシュ値」「メッセージダイジェスト」「フィンガープリント」などと呼ばれる。

@IT

ハッシュ関数の性質と理想形

性質

  1. 任意長のメッセージを入力すると、メッセージを代表する固定長のハッシュ値が得られる
  2. 同じハッシュ関数に同じメッセージを入力すると、同じハッシュ値が得られる
  3. 入力値が大きくても高速でハッシュ値を計算できる

理想とされるハッシュ関数の振舞い

※nビットのハッシュ値を出力するものとする。

  • メッセージをハッシュ関数に入力したのち、それがリストに記録されていなければ、コインをn回投げる。仮におもて面が出れば0、裏面が出れば1として、n回振った結果のビット値を連結して出力する。
  • 入力値がリストに記録されている場合は、該当レコードから以前出力した値を調べてそれを出力する

ハッシュ関数の標準的な安全性

1.一方向性(原像計算困難性)
2.第2原像計算困難性
3.衝突困難性

一方向性(One-wayness: OW)

  • ハッシュ値が与えられたとき、元のメッセージを求めることが困難であること
  • 原像計算困難性(Preimage Resistance : PR)ともいう
  • 一方向性を破ろうとする攻撃を原像攻撃という

第2原像計算困難性(Second Preimage Resistance : 2PR)

あるメッセージ(第1原像)とそのハッシュ値が与えられたときに、同一のハッシュ値になる別のメッセージ(第2原像)の計算が困難であること

衝突困難性(Collision Resistance:CR)

同じハッシュ値になるような2つの異なるメッセージを求めることが困難であること


ハッシュ値の衝突
メッセージ空間からメッセージを選択してハッシュ関数に入力するとハッシュ値が得られるが、ハッシュ値空間はメッセージ空間より小さいため、かならず、メッセージは異なるがハッシュ値が同じになる、メッセージのペアが存在する。このペアを衝突ペアと呼ぶ。

n = 10 羽の鳩が m = 9 つの巣の中にいる。したがって少なくとも1つの巣には2羽以上の鳩がいる。 (Wikipedia)

鳩の巣原理(はとのすげんり、英: Pigeonhole principle)またはディリクレの箱入れ原理(ディリクレのはこいれげんり、英: Dirichlet’s box principle, Dirichlet’s drawer principle)、あるいは部屋割り論法とは、n 個の物を m 個の箱に入れるとき、n > m である。

wikipedia