暗号技術はどう破られ、死んでいくのか？ ハッシュ関数を例に。

2004年8月、カリフォルニア大学サンタバーバラ校で、一人の中国人女性が極めて地味な発表を行った。それは「一定の条件を満たす数字の組を見つけた」というものだったが、聴衆はその意味を瞬時に理解し、スタンディングオベーションで彼女を見送った。彼女の発見は、世界中のウェブサイトの信頼基盤を揺るがすものだった。本エピソードでは、堀元見と水野太貴が、暗号技術の中でも特に重要な「暗号学的ハッシュ関数」を例に、技術がどのようにして「破られ、死んでいく」のかを、具体例と歴史的なエピソードを交えて解説する。軍艦の開発競争に例えられるように、一度破られたハッシュ関数は急速に陳腐化し、使われなくなる。そのプロセスを、身近な例から国家レベルの攻撃まで、幅広く掘り下げていく。

5:54ハッシュ関数とは何か

ハッシュ関数の「ハッシュ（hash）」は「切り刻む」という意味で、ハッシュドポテトのハッシュと同じ語源だと水野が指摘する。堀元は、ハッシュ関数の本質を二点に整理する。第一に、入力を切り刻んで全く違う形に変換するため、元に戻せないこと（一方向性）。第二に、同じ入力に対しては必ず同じ出力が得られることである。

この性質を料理に例えようとした水野は「野菜を炒めた後、元の野菜には戻せないが、同じ野菜を炒めたら同じような見た目になる」と試みるが、堀元は「それだと逆算できてしまう」と却下する。さらに「ラーメンのスープは隠し味が入っていて、何を突っ込んだか究極わからない」という提案も、「鶏ガラが入っていることぐらいはバレる」と否定される。結局、堀元は「例えるのが難しすぎるので、そのままのものとして理解してほしい」と結論づける。

ハッシュ関数の実用的な価値は、例えばパスワードの保存にある。Twitterのようなサービスがユーザーのパスワードを預かる際、ハッシュ化して保存しておけば、データが流出してもパスワードそのものは漏れない。ログイン時には、ユーザーが送信したパスワードを同じハッシュ関数で変換し、保存されている値と照合する。この仕組みにより、パスワード自体をサーバーに保存するリスクを回避できる。堀元は「ビットコインの技術的な核もこれだ」と付け加え、暗号資産の文脈でもハッシュ関数が中心的な役割を果たすことを示唆する。

10:30ハッシュ値を計算してみよう

堀元は、ハッシュ関数が「入力が1変わったら出力が1変わる」ような単純なものでは意味がないと指摘する。過去のビットコイン回で「一見ランダムに見える変化をする関数」の存在を説明したが、視聴者から「そんなもの本当にあるのか」という疑問が多く寄せられていた。そこで今回は、実際に手計算でハッシュ関数を動かしてみせる。

堀元が考案した「堀元法」という簡易ハッシュ関数は、以下の手順で動作する。まずアルファベットを数字に変換する（A=1, B=2, ..., Z=26）。初期値を1とし、一文字進むごとに「現在の値×7＋現在の文字の数字」を計算し、その下二桁を次の値とする。この「増幅して捨てる」という操作がハッシュ化の基本だと堀元は説明する。

実際に「CAT」をハッシュ化すると、C(3)→1×7+3=10、A(1)→10×7+1=71、T(20)→71×7+20=517、下二桁を取って17となる。次に、CをBに変えた「BAT」を計算すると、B(2)→1×7+2=9、A(1)→9×7+1=64、T(20)→64×7+20=468、下二桁は68となる。入力が1文字変わっただけで、出力は17から68へと大きく変化する。さらに「HAT」は62となり、BAT(68)とHAT(62)は入力文字が大きく異なるのに出力は近い値になるなど、一見ランダムな動きを示す。

堀元はこの仕組みを「増幅して捨てる」と総括する。前の計算結果を7倍することで小さな違いを増幅し、さらに下二桁以外を切り捨てることで、よりランダムに見える出力を得ている。水野は「ゆるコンピュータ科学ラジオも、面白い箇所だけ増幅して細かい部分は捨てているから、ハッシュ化しているのと同じだ」とジョークを飛ばすが、堀元は「公式には非推奨」と釘を刺す。

15:12ハッシュ関数をハックしよう

ハッシュ関数の重要な性質は、「狙って同じ出力を出せてはいけない」ことだと堀元は強調する。同じ出力を意図的に生成できることを「衝突（コリジョン）」と呼び、これがハッシュ関数の最大の脆弱性となる。水野にハッカーの気持ちになって「CATと同じハッシュ値17を持つ別の文字列を逆算する」課題を与える。

重要なのは、世の中のハッシュ関数は構造がすべて公開されているという点だ。堀元は「技術規格として構造をオープンにしているからこそ、検証できる」と説明する。水野は「X1、X2、X3」と変数を置いて数式を展開し、堀元法の構造を解析する。展開の結果、最終的な値は「343 + 49×X1 + 7×X2 + X3」となることがわかる。ここで、X1の係数は49、X3の係数は1と、重みが大きく異なることに気づく。

この構造を利用すれば、X1を2大きく（49×2=98増加）、X3を2大きく（2増加）することで、合計100増やせる。しかし、ハッシュ関数は下二桁しか取らないため、100増えても出力は変わらない。実際に、CATのCをEに、TをVに変えた「EAV」を計算すると、E(5)→1×7+5=12、A(1)→12×7+1=85、V(22)→85×7+22=617、下二桁は17となり、CATと同じハッシュ値が得られる。水野は「ハッカーとして堀元法を破ることに成功した」と宣言する。

堀元は、この「狙って同じハッシュ値を出せる」ことが脆弱性に直結すると警告する。例えば、電子署名の仕組みでは、文書全体をハッシュ化した値に署名を施すことで、文書の改ざんを検出している。しかし、もし悪意ある者が元の文書と異なる内容でありながら同じハッシュ値を持つ文書を生成できれば、署名を偽装できる。具体的には、PDFの白い文字でハッシュ値を調整する文字を埋め込み、「1億円をバリューブックスに振り込め」という指示書を「1億円を水野に振り込め」に書き換えても、同じハッシュ値になるよう細工できるというわけだ。

23:41業界を震撼させた無名の女性

ここで話は冒頭に戻る。2004年当時、世界で広く使われていたハッシュ関数「MD5」があった。このMD5の衝突を指摘したのが、無名の中国人女性「王小雲（ワン・シャオユン）」だった。彼女は国際学会CRYPTO 2004で、MD5の衝突を発見したと発表した。堀元は「水野がやった多項式展開の遥かに複雑なバージョンを、彼女は400ページぐらい手書きの数式でやったらしい」と説明する。

この発表の衝撃は計り知れない。もし悪意ある者が先にこの脆弱性を発見していれば、世界中の金融機関に成りすまし、全ての資金を奪うことも可能だった。しかし王小雲は、その危険性を理解した上で、学会で発表し、世界中のセキュリティ関係者に警告を発した。聴衆はスタンディングオベーションで彼女を見送ったという。

堀元は「この学会発表を聞いた悪意ある者が、その瞬間から悪いことができるようになるわけではない」と補足する。理論的な脆弱性が発見されてから、実際に攻撃に使えるツールができるまでには数年かかる。その間に業界全体で対策を進めるのがセキュリティの常識だ。ただし、脆弱性が発見された瞬間に攻撃に転用される「ゼロデイ攻撃」というケースも存在する。

実際にMD5の衝突を利用した強力なマルウェア「Flame」が存在する。これはアメリカとイスラエルが合同でイランを攻撃するために開発した国家レベルのマルウェアで、最も複雑なマルウェアの一つとされる。FlameはMD5の衝突を利用してMicrosoftの証明書を偽装し、Windowsアップデートを装って悪意あるコードを送り込む。正真正銘のMicrosoft公式アップデートと認証されてしまうため、ユーザーは気づかないまま感染する。

25:06Web全部を揺るがす脆弱性

王小雲の発表後、MD5は急速に非推奨となり、ブラウザなどでも警告を出すようになった。堀元は「ブラウザでウェブサイトを開いた時に『安全ではありません』と出た経験はないか」と問いかけ、その原因の一つが危険なハッシュ関数の使用にあると説明する。具体的には「SHA-1」という広く使われていたハッシュ関数の危険性が知られた後も、まだ使われているサイトが多数存在した。堀元は「某ビジネス書をいっぱい作っている中小の出版社などがそうなっていたのを見たことがある」と具体的な例を挙げる。

水野は「ただサイトを閲覧するだけなら、個人情報を打ち込んだりしないから問題ないのでは」と疑問を呈する。堀元は「それは12年ぐらい前の常識」と切り返し、現代のウェブサイトは高度に様々なサービスと連携しており、気づかないうちに個人情報を送信している可能性があると説明する。業界全体として、全ての通信を暗号化する「HTTPS」への移行が進められてきた背景には、こうしたリスクがある。

さらに堀元は、フィッシング詐欺対策の古い常識にも警鐘を鳴らす。「ドメイン名を確認しよう」という対策は12年前のもので、現在は非推奨だという。人間の認知は脆弱で、よく間違えるからだ。代わりに「ブックマークからのみ飛ぶようにしましょう」といった対策が推奨されている。水野が「また愛知県の差別か」と冗談を飛ばすと、堀元は「あなたのITリテラシーが12年前なだけで、愛知県は関係ない」と返す。

29:52日々進化し続ける暗号技術

堀元は「破られない暗号はない」と断言する。ハッシュ関数も常に破られ、改善される歴史を繰り返してきた。王小雲が破ったMD5も、実はその前身であるMD4の後継として開発されたものだった。MD4が危険だと判明したため改良されてMD5が生まれたが、それも王小雲の手によって破られた。

現在、広く使われているのは「SHA-2系」のハッシュ関数だが、堀元は「これも多分終わりが来る」と予測する。しかし、暗号学界の偉いところは、すでに次世代の標準「SHA-3」を開発済みだという点だ。SHA-3は単一の暗号ではなく、コンペティションで選ばれた優れた方式に与えられる称号で、複数の候補が存在する。堀元は「いつでも次に行けるようにしている。破られないと慢心するのではなく、どうせ破られるから次の乗り換え先を同時に研究している。この用意周到さに人類の英知を感じる」と語る。

水野は「好奇心だけで研究していた誰かの成果が、後になって社会で必要とされる瞬間が好きだ」と共感する。堀元も「数学の人が一方向の演算について考えていたことが、現代ではSHA-3の暗号のアイデアに繋がっている。数学が役に立っているなと感じる瞬間だ」と応じる。

最後に、ビットコインとハッシュ関数の関係が再び取り上げられる。ビットコインのマイニングは、ハッシュ値の先頭にゼロが連続して並ぶような「キリの良い数字」を総当たりで探索する作業であり、これは王小雲が行った「狙ったハッシュ値を出す」作業と本質的に同じだと堀元は指摘する。もしビットコインがMD5を採用していれば、王小雲は莫大な富を得られたかもしれないという冗談も飛び出す。

ブロックチェーンは、過去のブロックの情報をまとめたハッシュ値が次のブロックに記載される仕組みで成り立っている。過去のどこか1ブロックを改ざんすると、その先のハッシュ値が全て変わるため、改ざんが極めて困難になる。これがブロックチェーンの信頼性の基盤だ。堀元は「技術として美しい。論理的に改ざんが難しいものを計算だけで作り上げている」と評価する。

まとめ

本エピソードは、一見地味なハッシュ関数という技術が、いかにして現代のインターネットの信頼基盤を支え、そしてどのようにして「死んでいく」のかを、手計算による実演と歴史的なエピソードを交えて描き出した。特に、王小雲という一人の研究者の発見が、世界中のセキュリティを根本的に見直すきっかけとなった事実は、基礎研究の重要性と、技術の脆弱性が持つ破壊力を如実に示している。また、「破られない暗号はない」という前提で常に次世代を準備する暗号学界の姿勢は、技術の進歩に対する冷静で現実的な向き合い方の模範とも言える。ハッシュ関数が私たちの日常生活の裏側で数万回も動作しているという事実は、普段意識することのない技術の恩恵とリスクを再認識させるものだった。

要点

• ハッシュ関数は「一方向性」と「同じ入力には同じ出力」という二つの性質を持ち、パスワード保存や電子署名、ブロックチェーンなど、セキュリティの基盤として広く使われている。
• ハッシュ化の基本は「増幅して捨てる」ことで、小さな入力の違いを増幅し、一部を切り捨てることで一見ランダムな出力を得る。
• ハッシュ関数の最大の脆弱性は「衝突（コリジョン）」、すなわち異なる入力から同じ出力を意図的に生成できることである。
• 2004年、中国人研究者の王小雲がMD5の衝突を発見し、学会はスタンディングオベーションで彼女を見送った。この発見は世界中のウェブセキュリティの見直しを引き起こした。
• MD5の衝突は実際に国家レベルのマルウェア「Flame」に利用され、アメリカとイスラエルがイラン攻撃のためにMicrosoftの証明書を偽装する攻撃を行った。
• 暗号技術は「破られない」という前提ではなく「どうせ破られる」という前提で設計されており、SHA-3のように次世代の標準が事前に開発されている。
• ビットコインのマイニングは「狙ったハッシュ値を出す」作業であり、王小雲の研究と本質的に同じ原理に基づいている。
• ブロックチェーンは、過去のブロックのハッシュ値を次のブロックに記載することで改ざんを困難にしており、ハッシュ関数がその信頼性の基盤となっている。