ハッシュ関数について復習
前編では、Wu-Tang Name GeneratorというWebサイトを使って上司の名前のヒップホップアーティストっぽいハッシュ値を得ることで、上司にバレないように愚痴を言う作戦を紹介した。
しかし、単純に上司の名前のハッシュ値を得るだけでは、上司がWu-Tang Name Generatorの存在を知っていた場合、簡単に「このあだ名は自分のことだな」と気付かれてしまう。
ここでハッシュ関数について復習しておこう。
ハッシュ関数とは「メッセージから短い文字列（ハッシュ値）を生成する機能を持つプログラム」のことだ。
ハッシュ関数は一方向関数と呼ばれる関数の一種で、メッセージからハッシュ値を求めることはできるが、逆にハッシュ値をメッセージに戻すことは事実上不可能であるとされている。
上の図で言うと、左から右に行くことはできるが、右から左へは行けないという意味で一方向なのだ。
この特性から、WebサイトやSNSを運営する企業では、ユーザのデータを保存する際、パスワードなどの情報はユーザが入力したものをそのまま保存するのではなく、パスワードのハッシュ値を保存していることが多い。
そうすることで、万が一データベース内のデータが外部に漏れてしまった場合でも、パスワードなどの情報を秘匿できる。
ハッシュ関数は一方向関数なので、漏洩したハッシュ値からもともとのパスワードを得ることはできないというわけだ。
ハッシュ関数を破る必殺技、《レインボー攻撃》
だが、そんな一方向であるはずのハッシュ関数の穴をつき、漏洩したハッシュ値からもともとのパスワードを得る方法がある。
その名も、《レインボー攻撃》という。
「レインボー攻撃」。
名前だけ聞くとプリキュアの必殺技としか思えないが、ハッシュ関数を破るためのハッキング技術だ。
英語圏では「Rainbow Table Attack」と呼ばれ、私が知る中で2番目に名前がカッコいいハッキング技術である。ちなみに1番カッコいいのは、「1234」「Password1!」などの簡単なパスワードを設定しているアカウントを総当たり式に探し出す《逆ブルートフォース攻撃》（Reverse Brute Force Attack）だ。「ブルートフォース攻撃」だけでカッコいいのに、「逆」なのがさらにカッコいい。
レインボー攻撃の仕組みはこうだ。
攻撃者はまず、入力されるメッセージの候補と、そこから得られるハッシュ値をまとめたレインボーテーブルという表を用意する。
次に、データベースから手に入れたハッシュ値を、1件ずつレインボーテーブルに登録された値と比較していく。
そうして一致する値があれば、ハッシュ値からそのアカウントのもともとのパスワードがわかるというのがレインボー攻撃の仕組みだ。
以下の図は、0〜9までの数字を使った6桁のパスワードと、そこからCRC32というハッシュ関数で得たハッシュ値をまとめたレインボーテーブルのイメージだ。
0〜9までの数字で6桁のパスワードを作る場合、その組み合わせは10の6乗で1,000,000通りあるので、このレインボーテーブルには1,000,000件のデータが含まれる。
データベースから手に入れたハッシュ値を1,000,000件のデータと比較するとなると大仕事であるように思えるが、十分に処理能力の高いコンピュータを用いれば1秒もかからずにこの作業を完了させることができる。
そうして比較を進めていき、以下の図のようにレインボーテーブルの中にデータベースから漏洩したハッシュ値と同じものがあれば、それに対応するメッセージがもともとのパスワードであるとわかってしまう。
レインボー攻撃でパスワードを割り出すために必要な条件は、以下の3つだ。
1. ハッシュ値がわかっていること
2. 使用されているハッシュ関数の種類がわかっていること
3. レインボーテーブルが手元にあること
ただし、ハッシュ値を手に入れてしまえば、その桁数や使われている文字の特徴から、使われているハッシュ関数は想像できてしまう。つまり、1の条件を満たせばほとんど苦労せずに2の条件も達成できる。
そして、3のレインボーテーブルについても、主なハッシュ関数のレインボーテーブルはインターネットで簡単に見つけられるうえに、ハッシュ関数自体はなんら特別な処理ではないので一般的なコンピュータで簡単に実行できる。
つまり、ハッキング技術についての少しの知識があり、ハッシュ値さえ手に入れることができれば、レインボー攻撃は簡単に実行できる。
化学の専門家ならホームセンターで手に入るものだけで爆弾を製造できるのと同じように、ハッキングの専門家はインターネットで簡単に手に入るものだけで攻撃を行えるのだ。
あなたの上司が自分のあだ名と思われるWu-Tang Nameに対してレインボー攻撃を仕掛ける場合は、メッセージの候補が少ないぶん、話はもっと単純だ。
上司は今、あなたが口にしたあだ名を聞いてハッシュ値を手に入れた（レインボー攻撃の条件1を達成）。
そのあだ名が形容詞と名詞の組み合わせであることから、Wu-Tang Name Generatorで得られたあだ名であることがわかる（条件2を達成）。
次にやるべきことは、Wu-Tang Nameのレインボーテーブルを作成することだ。あなたが不満を持っていそうな人のリストを作成し、それぞれのWu-Tang Nameを得ることで、Wu-Tang Nameのレインボーテーブルが完成する（条件3を達成）。
そしてレインボーテーブルにまとめられたハッシュ値に、あなたが口にしていたあだ名と同じものがあれば、あなたが誰の愚痴を言っていたかがわかる。
レインボー攻撃への対策その1: ストレッチング
あなたは、単純に上司の名前のWu-Tang Nameを得るだけでなく、レインボー攻撃をかいくぐることのできる、暗号として強力なあだ名を用意する必要がある。
レインボー攻撃への対策として暗号を強化するためのテクニックの1つが、《ストレッチング》だ。名前のカッコよさではレインボー攻撃に遠く及ばないが、あなたが上司のあだ名を作る際にも簡単に用いることができる。
ストレッチングの仕組みは単純で、ハッシュ関数の実行結果に対して、さらにハッシュ関数を実行する。そしてそのことを繰り返す。つまり、ハッシュ値のハッシュ値のハッシュ値の……を得るのだ。
今回のケースで言うと、上司のWu-Tang Nameを得た後、そのWu-Tang Nameを入力欄にコピーし、もう一度Wu-Tang Nameを得て、さらにそのWu-Tang Nameを……と繰り返す。
レインボー攻撃を行う立場からすれば、ハッシュ値のストレッチングが行われている場合、レインボーテーブルのデータ件数をその回数のぶんだけ倍増させなければいけない。
先ほど、ハッシュ関数を1回実行した場合のレインボーテーブルを図にして説明したが、これを2回実行した場合、3回実行した場合……とデータの件数を増やしていく必要があるのだ。
ストレッチングを何回行えば暗号が安全と言えるかについては様々な意見があるが、アメリカ国立標準技術研究所（NIST）は、少なくとも1,000回以上はストレッチングを行うことを推奨している。
先ほど、十分に処理能力の高いコンピュータを用いれば1,000,000件のデータの比較を1秒もかからずに完了させることができると書いたが、ストレッチングを1,000回行えばその時間を1,000秒に、10,000回行えば10,000秒に増やすことができる。
さて、上司のあだ名の話に戻ろう。
通常のハッシュ関数はインターネットに接続せずに実行できるので、1,000回行うのにもそれほど時間はかからないが、Wu-Tang Name GeneratorはWebサイトからしか実行できない。
Wu-Tang Nameの取得を少なくとも1,000回繰り返していたら大変なので、今回は5〜10回ほど繰り返して良しとしておこう。
これで、上司がレインボー攻撃を仕掛ける手間も、5〜10倍に膨れ上がることになった。
レインボー攻撃への対策その2: ソルト
しかし、あなたの上司が想像以上の執念でレインボー攻撃を仕掛けてきた場合、ストレッチングでその手間を5〜10倍にしても十分ではない。
そこでもう1つ、レインボー攻撃に対するレインボー防御（そんな言葉はないが）を紹介しよう。
これもまた名前のカッコよさには欠けるが、《ソルト》というテクニックだ。
ソルトとは、メッセージの末尾に加える十分な長さの文字列のことだ。たとえば、Wu-Tang Name Generatorに「上司」という名前を入力する場合、末尾に「1234567890」という10桁の文字列を加えて「上司1234567890」と入力する。
レインボー攻撃を行う立場からすれば、メッセージにソルトが加えられている場合、レインボーテーブルのデータ1つ1つに対してソルトが加えられているパターンを考慮しないといけなくなり、入力候補の数は爆発的に増大する。
もし、ソルトに使用される文字の種類が大文字アルファベット（A〜Z）、小文字アルファベット（a〜z）、数字（0〜9）の62種類である場合、ソルトが1桁であると仮定してもレインボーテーブルのデータ件数は62倍に増やさなければならない。
ソルトが2桁なら3,844倍（62の2乗）、3桁なら238,328倍（62の3乗）……と必要なデータ件数は62の累乗で膨れ上がっていき、10桁のソルトに対応するレインボーテーブルを作ろうと思えば、当初の839,299,365,868,340,200倍のデータ件数が必要になる。仮に当初のデータ件数を1秒で比較できたとしても、10桁のソルトに対応するには270億年かかる計算だ。
270億年が経った頃には、あなたが誰の愚痴を言っていたのかを気にする人はいないだろう。
というわけで、上司の名前にソルトを付けてWu-Tang Nameを得ることが、上司のレインボー攻撃に対する有効な対策となる。
どのようなソルトを付けるかはあなたの自由だが、今回のケースではとにかく長いソルトがお勧めだ。先ほど例に挙げた「1234567890」のように、単純でも良いのでとにかく長いソルトを付けよう。
こうしてあなたはようやく、暗号として使用するのに十分な強度のあだ名を手に入れることができた。
ソルトを追加して得たあだ名にストレッチングをかけて、より強度の高いあだ名を作っても良いだろう。
おまけ: ソルトとパスワードで一番大切なのは、長さ
ソルトのパターンは桁数が増えると累乗で増えていくため、上司の名前に付けるソルトはとにかく長くさえあれば良いと言ったが、この知識はあなたがECサイトやSNSのアカウントのパスワードを考える際にも役立つ。
パスワードの強度という観点から言うと、大文字、小文字のアルファベットと数字と記号を組み合わせた複雑なパスワードを作るという考え方より、とにかく長ければ良いという考え方のほうが正しいのだ。
「ストレッチングは少なくとも1,000回行おうね」と言っていたアメリカ国立標準技術研究所（NIST）が2017年に発行したNIST Special Publication 800-63B（https://pages.nist.gov/800-63-3/sp800-63b.html）というレポートでは、パスワードの強度を決める一番の要素は、パスワードの複雑さではなく長さであるという結論が述べられている。
他人のECサイトなどのアカウントに不正にログインするためにパスワードの候補を総当たり式に試していく《ブルートフォース攻撃》というハッキング技術を用いる場合、大文字、小文字のアルファベットと数字と記号を組み合わせた「f40D71!」という一見強力そうに見えるパスワードと、「1234567」という単純なパスワードは、強度という面ではほとんど変わらない。
どちらも7桁のパスワードという点で同じだからだ。
Newsweekの記事によると、ハッキングツールを使えば7文字のWindowsパスワードはどれほど複雑なものでも0.029秒で破られる危険性があるのに対し、12文字のパスワードを破るのには200年、24文字のパスワードになると1800万年がかかるそうだ。
ただし、ハッキング技術の中には辞書に登録されている単語を片端から試していく《辞書攻撃》という手法もあるため、長いパスワードであっても意味のある英単語などは避けたほうが良い。
他にも、「パスワードは定期的に変更するべきではなく、できるだけ強いものを使い続けるほうが良い」「サイト設計者はパスワード欄へのペースト入力を禁止すべきでない」など、有益な情報が掲載されているので、興味のある方は一読しておくと次に何かのサイトのパスワードを考える時の参考になるだろう。
情報処理推進機構が翻訳監修した日本語版
https://www.ipa.go.jp/files/000025342.pdf