SHA256とかMD5とかのハッシュ値から逆算して平文を割り出すツールを作った話

現実的な時間&空間計算量でハッシュ値から平文を割り出せるレインボーテーブルというデータ構造を知ったので、その解説と実装と対処法の話。

 

※この記事における「平文」は意味の正確さより、ニュアンスを大事にしてください。

 

 

ハッシュ値から平文を逆算するツールを作った

細かい話は後にして、とりあえずこんなものを作りました。

rainbow.shumon.pro

数秒でsha256をぶち破れます。

送信ボタンを押してから表示されるまで10秒ぐらいかかるんですが、後ろでサーバがCPUバウンドな処理をしているので、連打されるとサーバが落ちます。気長に待ってください。

あと雑なフォームがあるので変なタグを埋め込んだりできますが、あんまり悪いことはしないでください。 ここはCTF会場ではありません。

 

ハッシュ関数って単方向じゃないんかい

もちろんハッシュ関数は単方向です。(ハッシュ関数の要件に単方向であることは本来含まれませんが、この記事では便宜上単に「ハッシュ関数」といった場合は暗号学的ハッシュ関数を指すこととします)

あるハッシュ関数\( H \)と平文\( x \)があったとき、ハッシュ値は\( H(x) \)となります。

ここで、\( H(x) \)を入力とし\( x \)を返す関数\( H^{-1} \)のような計算のことを原像計算と呼びますが\( H \)が暗号的ハッシュ関数であるならば原像計算は困難です。

MD5とかSHA256とか、よく見るやつは大体原像計算は困難です。

 

原像計算のナイーブな実装

暗号的ハッシュ関数の原像計算は困難は困難なんですけど、ゴリ押せば解けます。

任意の\( x \)について\( H(x) \)を事前に計算し、メモ化しておくと\( H^{-1} \)を実現することができます。

ただし、値域の広さに比例した記憶空間が必要になるため、かなり莫大なサイズになりそうなのが直感的に分かると思います。

たとえば62種類(a-zA-Z0-9)の文字からなるパスワードをMD5でハッシュ化したものを考えてみます。MD5ハッシュ値は128bitなので1通りあたり16+文字列長バイト使うとすると、完全に網羅しようとすると大体これくらいのサイズになります。

文字列長 組み合わせ サイズ
1文字以下 62通り 1.1KB
2文字以下 3,844通り 70.2KB
3文字以下 238,328通り 4.6MB
4文字以下 14,776,336通り 300.1MB
5文字以下 916,132,832通り 19.5GB
6文字以下 56,800,235,584通り 1.3TB
7文字以下 3,521,614,606,208通り 82.3TB
8文字以下 218,340,105,584,896通り 5.32PB

計算がめんどくさいのでこれ以上は書きませんが、これを使って平文を特定するのは明らかに現実的ではないことが分かると思います。

 

レインボーテーブルとは

レインボーテーブルも基本的は方針は先ほどのナイーブな実装と変わらず、考えられるハッシュを事前に計算・メモ化して、そのテーブルを照合して原像計算を行います。

ただし、還元関数というアイデアを元にテーブルの持ち方を工夫して、照合に分割統治を使うことで、時間と空間のトレードオフを実現した物です。

ちなみに、どうでもいいんですけど時間と空間のトレードオフ(space-time tradeoff)ってテクニカルタームになるんですね

時間と空間のトレードオフ - Wikipedia

 

還元関数とは

平文からハッシュ値を生成するのがハッシュ関数ですが、還元関数はその逆で、ハッシュ値から平文を生成する関数のことです。

ただし還元関数は原像計算をしているわけではないので、ある平文\( x\) とハッシュ関数\( H \),還元関数\( R \)があったとき、ほとんどの場合\( x \neq R(H(x)) \)であることに注意してください。

例えば平文に4文字の英数字、ハッシュ関数MD5を使った場合を考えてみると、4文字で"12Ab"という文字列をハッシュ化するとハッシュ値は"29c84bc59e51df367572cc979f5d2697"になります。ここで還元関数はハッシュ値を入力として4文字の英数字を返すような関数ならばなんでもよいです(ただし、同じハッシュ値からは必ず同じ平文を生成できなくてはなりません)

 

チェーン化によってテーブルサイズを削減する

ここから、テーブルサイズを削減していきます。

ナイーブな実装で使ったテーブルが巨大なのは、平文とハッシュ値を1対1で持っていたためでした。

還元関数を使うことでハッシュ値から別の平文に変換することができるようになったため、還元関数の出力を再びハッシュ関数の入力とすることで、1つの平文から大量のハッシュ値と平文を生成できることになります。

このハッシュ関数と還元関数を順番に通していく流れをチェーン化といい、チェーンを長くすることで、最初の1つの平文さえ覚えておけば、チェーン中に登場する平文とハッシュ値は逆算していくことができるので記憶する必要がなくなります。

これで覚えておく必要のある情報は、

  • どのチェーンに目的の平文が含まれているかを判定するのに使う最後尾の平文
  • 目的の平文が含まれているチェーンを完全に復元するために使う先頭の平文

だけになるため、チェーン長を長くするとメモリが抑えられる分、復元に時間がかかり、チェーンを短くするとメモリを食う分、復元は高速になります。

 

実装した

というわけでGolangで実装しました。

github.com

使い方とかはexampleとREADMEを読んでいい感じにしてください。

example/serverにレインボーテーブルで遊べるwebアプリも置いていて、この記事の冒頭で貼った

rainbow.shumon.pro

これはexample/serverそのものです。かなり重いので、できれば自分でローカルに立ててください。

 

破られるならハッシュ化する意味ないやんけ

常識的なwebサービスであれば、ユーザのパスワードはハッシュ化して保存すると思うのですが、ハッシュ値から平文が割れるなら、平文で保存するのと本質的に大差ありません。

そこで、レインボーテーブルに対抗するために、ソルトとストレッチングという手法があります(実際にはレインボーテーブル対策というより、FPGAとかASICとかで作られたハッシュ計算特化ハードウェア対策ですが)

 

ソルトとストレッチング

ソルトとは、平文単体でハッシュ関数に通すのではなく、平文の後ろに何か文字列を追加してそれをハッシュ関数に通すことで、実質パスワードを長くしたのと同等の効果を得るための文字列のことです。

ソルトはなんでもいいのですが、ユーザごとに違うものを使うことが推奨されており、これはユーザごとにソルトが違うと、ユーザごとに別々のレインボーテーブルを持つ必要があり、原像計算が困難になるからです。

ストレッチングとは「ソルトをつけてハッシュ化」を何回も繰り返すことです。

ストレッチングもソルトも共通して、ハッシュを使う側の負担はハッシュ計算時に少しのコストを払うだけ(極端にストレッチングを増やさない限り無視できる程度)であり、ハッシュ値の照合には従来と全く同じ負荷である点が素晴らしくて、サービスのビジネス的側面に影響を与えることがありません。

それに対し、クラック側はソルトが加わることで、レインボーテーブルによってせっかくテーブルサイズを小さくしたのに、ユーザごとに別々のテーブルを作らされることで空間計算量が壊れ、ストレッチングが加わることで、チェーンの探索と復元を繰り返す必要があり時間計算量が壊れます。

 

まとめ

パスワードをハッシュ化して保存するときは、必ずソルト+ストレッチングをやりましょう。

ついでに言うと、ハッシュ化と暗号化は対立する概念ではないので、ソルト+ストレッチング+暗号化を併用してもいいと思います。

ソルトとストレッチング大事だよみたいな話はよく聞くけど、具体的になんでやらなあかんねんってずっと思ってたので、自分で実装してみると身を以て理解できていいですね。

f:id:cameremon84:20190428155746p:plain