IDコラム

トップページ > コラム >  【エバンジェリスト・ボイス】暗...

IDコラムとは

カテゴリー

【エバンジェリスト・ボイス】暗号学的ハッシュ関数とブロックチェーン技術 2018/05/16 (水)

サイバー・セキュリティ・ソリューション(CSS)部
エバンジェリスト フェロー 関原 弘樹


こんにちは!
CSS部エバンジェリスト フェローの関原です。

ちょっと遅れましたが、新年度になりました。少し早い初夏の風がとても心地よいですね。

突然ですが、今年度から肩書が少し変わり、フェローを拝命しました。
当社にはグループ全体で約2,500名の社員がおり、2,000名以上の技術者を擁しています。以前の当社のキャリアパスでは、エンジニアとしてステップアップした先はラインの管理職になるのが常でした。
しかし、今後の社会変化に対応するため2015年に新しいキャリアパスとして「エバンジェリスト」を新設し、これからの技術革新に対応出来るようなハイスキルエンジニアへの新しい道を示しました。「フェロー」はその最上位として位置づけられている職位で、ありがたいことに私もそのうちの一人として認定されました。
フェローのミッションには社外へのプレゼンス向上や社内の後進の育成等の活動も含まれていますので、これからも本コラムをはじめとしてこれまで以上に活動の幅を拡げていきたいと思っております。


前置きが長くなりましたが、今回は少し前にニュースで話題となった仮想通貨/ブロックチェーン技術でも使われている暗号学的ハッシュ関数(以下ハッシュ関数)について簡単におさらいしてみましょう。

ハッシュ関数はITセキュリティの分野でよく扱われますが、暗号鍵を使用して機密性を確保するための暗号アルゴリズム(例えば共通鍵暗号方式であるAESや公開鍵暗号方式であるRSAですね)とは用途がちょっと異なります。
皆様もMD5、SHA-1、SHA-2という単語を耳にしたことがあるかと思いますが、これらがハッシュ関数で様々なアルゴリズムと実装が存在します。では、どのような場合に使用されていたかは覚えていますでしょうか。

すぐに思い出すのはインターネット上のWebサイトからダウンロードしたファイルが壊れていないかを確認するときや、照合すべき認証情報をシステム内に保存するときでしょうか。
データベース関連でいえばKVSのキー値として使用されているかもしれませんし、ネットワークに詳しい方はTLSで使用するデジタル証明書のフィンガープリントやTLSのMAC(メッセージ認証符号)としての方がなじみがあるかもしれません。
いずれもデータの機密性を確保したい場面ではなく、データが正しいか、変更されていないかを確認したい場面で使用されていますね。

ハッシュ関数が持つ特徴を簡単にまとめてみました。

 ① 入力が同じであれば常に出力も同じです。
   ⇒ 簡単にファイルの同一性が確かめられます

 ② 1ビットでも入力が異なれば出力は全く異なるものとなります。
   ⇒ どんな小さな変更も一目で確認できます

 ③ 出力長は入力長に依存せずアルゴリズムごとに一定です。
   ⇒ ファイルの大きさによらず確認の手間は常に同一です

 ④ 暗号鍵は使用しません。

 ⑤ 出力から入力を再現することは不可能です。
   ⇒ つまり復号が必要なデータの暗号化には使えません。
     この性質を利用しユーザのパスワードをシステム内に
     保存するときに使用します。

ということで、これらの特徴を持つハッシュ関数を用いると"ハッシュ値"(フィンガープリント/指紋にも例えられますね)の比較により完全性の担保が可能となることがご理解いただけましたでしょうか。

参考として、上記の例として取り上げた主なハッシュ関数の名称と出力するハッシュ値は以下のようになります。

 MD5(エムディーファイブ)
  ⇒ Message Digest Algorithm 5の略。2進数128桁(16バイト)のハッシュ値を出力。

 SHA-1(シャーワン)
  ⇒ Secure Hash Algorithm 1の略。2進数160桁(20バイト)のハッシュ値を出力。

 SHA-2(シャーツー)
  ⇒ Secure Hash Algorithm 2の略。出力するハッシュ値の長さによりいくつかの
    バリアントがあり、SHA-256(シャーニゴロ)の場合は、2進数256桁
   (32バイト)のハッシュ値を出力。

Windows上では"certutil"コマンドから以下のようにファイルのハッシュ値を簡単に算出できます。

--
C:\Users\*********>certutil -hashfile C:\Windows\notepad.exe SHA1
SHA1 ハッシュ (ファイル C:\Windows\notepad.exe):
fc 64 b1 ef 19 e7 f3 56 42 b2 a2 ea 5f 5d 9f 42 46 86 62 43
CertUtil: -hashfile コマンドは正常に完了しました。
--


このように便利なハッシュ関数ですが、いくつかの落とし穴もあります。
例えば"衝突"により特徴の②が不成立になる(つまり破られる)場合ですね。
③の特徴により、ハッシュ値の範囲は有限の範囲に収まりますので、例えばSHA-256ですと2^256(2の256乗)+1個のファイル※1を集めると最低でも1組、異なる2ファイルが同じハッシュ値を持ちます。
とはいったものの2^256+1個という値は10進数では78桁ほどになるようで(68桁である現行の"無量大数"※2の十億倍)実用上ハッシュ値の衝突はまず発生しませんが、故意に発生させようと試みた場合に「今後いつか」は可能となることは間違いないということを知っておいてください。

※1 最悪のケースですので実際はそれ以下で発生します。ここでは参考に「誕生日攻撃」というキーワードでリンクを置いておきます。

 外部リンク:誕生日攻撃


※2 桁数に関しては様々な解釈があるようですね。

 外部リンク:無量大数


なお、破られた/破られそうなハッシュ関数は危殆化している(もう危ないよ)とされ、強制力はないものの以下のように使用を控えるように周知されます。

 外部リンク:電子政府における調達のために参照すべき暗号のリスト (CRYPTREC暗号リスト)


ちなみに、現時点では前述のMD5、SHA-1、SHA-2のうち、MD5とSHA-1は既に危殆化しています。
一例として以下のサイトに現実に同じSHA-1のハッシュ値を持つファイルがアップロードされていますので、ご興味がある方は確認いただければと思います。
(MD5のハッシュ値が異なるのでPDF1とPDF2は異なるファイルだというのはすぐわかりますね。)

 外部リンク:SHATTERED
 外部リンク:PDF1
 外部リンク:PDF2


--
C:\Users\*********>certutil -hashfile C:\Users\*********\Desktop\shattered-1.pdf SHA1
SHA1 ハッシュ (ファイル C:\Users\*********\Desktop\shattered-1.pdf):
38 76 2c f7 f5 59 34 b3 4d 17 9a e6 a4 c8 0c ad cc bb 7f 0a
CertUtil: -hashfile コマンドは正常に完了しました。

C:\Users\*********>certutil -hashfile C:\Users\*********\Desktop\shattered-2.pdf SHA1
SHA1 ハッシュ (ファイル C:\Users\*********\Desktop\shattered-2.pdf):
38 76 2c f7 f5 59 34 b3 4d 17 9a e6 a4 c8 0c ad cc bb 7f 0a
CertUtil: -hashfile コマンドは正常に完了しました。

C:\Users\*********>certutil -hashfile C:\Users\*********\Desktop\shattered-1.pdf MD5

MD5 ハッシュ (ファイル C:\Users\*********\Desktop\shattered-1.pdf):
ee 4a a5 2b 13 9d 92 5f 8d 88 84 40 2b 0a 75 0c
CertUtil: -hashfile コマンドは正常に完了しました。

C:\Users\*********>certutil -hashfile C:\Users\*********\Desktop\shattered-2.pdf MD5

MD5 ハッシュ (ファイル C:\Users\*********\Desktop\shattered-2.pdf):
5b d9 d8 ca bc 46 04 15 79 a3 11 23 05 39 b8 d1
CertUtil: -hashfile コマンドは正常に完了しました。
--


また、④⑤に関してですが、パスワードのハッシュ値を保存する仕様のシステムに対してはハッシュ値をゲットし、力技でパスワードを推測する攻撃が存在します。
具体例として、さまざまなパスワード文字列に対して事前にハッシュ値を計算し一覧化(レインボーテーブルといいます)しておき、盗み出したハッシュ値とテーブル内の値を照合するという手法があります。

しかしながら実装により有効な対策はすでにありますのでご安心ください。
例えばLinuxのログインパスワードの場合、ハッシュ値計算の前にユーザごとに毎回ランダムなsalt(ソルトすなわち塩ですね)をパスワードの先頭に付加しておきます。
完全に防げるわけではありませんが、こうしておけば事前計算が必要な値は膨大なものとなり、事実上パスワードの推測が不可能になります。
Linuxの場合、/etc/shadow のパスワードフィールドが$1$で始まる場合はMD5、$5$で始まる場合はSHA-256、$6$で始まる場合はSHA-512となり、いずれもフィールドの2番目の$から3番目の$までがsaltです。
(具体的には"$6$4zjnWwJZ…………$wR……"という形式)

この「saltがあるため①の性質持つハッシュ値であっても事前計算を使用した攻撃に耐性ができる」ということをここで初めて知ったという方は、この機会にぜひ覚えていただければと思います。


ここで再度Wikipediaを参照し、ハッシュ関数が持つべきセキュリティ上の耐性(破られてはいけないもの)を挙げておきます。

 ・同一のハッシュ値であるのに、そっくりだが実は異なるというような
  メッセージの作成が不可能であること

 ・ハッシュ値から、そのようなハッシュ値となるメッセージを得ることが
  (事実上)不可能であること(原像計算困難性、弱衝突耐性)

 ・同じハッシュ値となる、異なる2つのメッセージのペアを求めることが
  (事実上)不可能であること(強衝突耐性)


耐性の観点からいうと、前述のハッシュ関数のうち残ったSHA-256は他の2つとは異なり現時点では危殆化していません。
当面、そうですね…あと10年は危殆化しないと考えられています。
それが理由であると私が断言することはできませんが、10年ほど前に実装されたBitcoinでもSHA-256は実装上コアとなるテクノロジーとして採用されています。

Bitcoinではブロックチェーンの正につながった/つなぎたいチェーンを計算するために、SHA-256をsalt付きで使用しています。
ただしハッシュ関数では順方向、つまり「元の値⇒ハッシュ値」を簡単に求めることができるので、ハッシュ関数をそのまま使用したのでは誰でも簡単に不正なチェーンをつなげることができてしまいます。
そこでブロックチェーンではチェーンを構成させたい、その前のブロックのハッシュ値に任意の乱数(nonce)をsaltとして結合します。
その値に対して2回(俗にいうストレッチング)SHA-256の値を計算し、その結果が一定の値以下(先頭に一定数以上の0が並ぶ)ことを要求しています。
(これを満たすnonceを求めるための計算を俗に「マイニング」とよんでいます。)
このメカニズムによりBitcoinの「過去の取引の正当性の検証と分散化された台帳」と「正当な取引の承認とチェーンへの追加」が実現されているわけですね。


ちょっと長くなりすぎた感もありますので、今回のコラムでは以下の3点の質問を提示し筆を置かせていただきます。

 ・SHA-256は全てのBitcoinの払い出しが完了する2140年以前に
  危殆化します。どのように対応すべきでしょうか?

 ・主要なハッシュ関数はシステムのパフォーマンスを上げるため、
  ハードウェアでの対応を含め計算が最適化されてきました。
  効率化のため、いかなる場合も最適化されたハッシュ関数を
  使用するべきでしょうか?

 ・力の裏付けのない通貨は通貨として存在し得るのでしょうか?


ではまた、次回のエントリーでお会いしましょう。

Hiroki Sekihara CISSP, CEH, PMP, CCIE #14607

お問い合わせ