2011-02-18

以前、Rainbow Table の説明で、ソルトに関して

id:JULY:20100515

Windows のパスワードの場合、「ソルト」と呼ばれる、パスワードに付加する乱数が無いので、同じパスワードから必ず同じハッシュ値が得られる、という側面もあります。UNIX 系 OS では「ソルト」が付加されるので、Rainbow Table が作りづらくなっています。

とサラッと流したのが、自分でも気になっていたのですが、エフセキュアブログの「ソルト付き SHA-1 は大丈夫か？」という話に言及*1したので、ソルトの効用に関して書いてみます。

ソルトとは

塩です。

というボケは置いといて、パスワードを保存する時に、何らかの「非可逆処理」を行った結果を保存しておく事は多いです。Windows での LM ハッシュや NTLM ハッシュ、UNIX 系であれば、古くは伝統的な「crypt」関数を使ったものだったり、今時だと MD5、SHA1 といったハッシュ関数を使ったりしています。

こうしておくと、

保存されているデータからは、元のパスワードを計算する事ができない。
しかし、入力された文字列に対して、同じ非可逆処理を行った結果と、保存されているデータを比較することで、パスワードの検証が可能である。

という状態になります。

この非可逆処理を行う際に、ランダムなデータをパスワードに付け加えてから処理を行うと、同じパスワードであっても、処理結果は違ったものになります。この付加されるデータを「ソルト」と言います。

パスワード情報を保存する時は、このソルトの値と処理結果の値を保存しておきます。検証する時には、入力されたパスワードと保存されているソルトの値を組み合わせて非可逆処理を行い、その結果と保存されている値を比較します。

OpenLDAP での SSHA の例

OpenLDAP でパスワード情報を保存する userPassword アトリビュートに、SSHA（ソルト付き SHA）のパスワード情報が保存されているケースを例に見てみます。

下記の例は、「testtest」というパスワードが保存されている様子です。

userPassword:: e1NTSEF9Qmc3UEwwN2RQSjB0bzBrYm5rUWNJeFQ4MU1ibTl0VUo=

「userPassword」の後ろにコロンが２つ続いているのは、続く文字列が Base64 でエンコードされた結果である事を表すので、デコードしてみます。以下は、CentOS 5.5 上で実行した様子ですが、他のディストリビューションでも同様だと思います。使っているコマンドは GNU 版の echo、base64、od、sha1sum です。

$ echo -n 'e1NTSEF9Qmc3UEwwN2RQSjB0bzBrYm5rUWNJeFQ4MU1ibTl0VUo=' | base64 -d; echo
{SSHA}Bg7PL07dPJ0to0kbnkQcIxT81Mbm9tUJ

先頭にある「{SSHA}」は、この userPassword が SSHA の形式である事を示していて、後ろがその値になります。つまり、保存されているパスワード情報は「Bg7PL07dPJ0to0kbnkQcIxT81Mbm9tUJ」です。

この文字列自体、Base64 でエンコードされた結果なのでデコードしてみます。但し、デコードした結果は文字データではないので、デコードした結果を 16 進ダンプしてみます。

$ echo -n 'Bg7PL07dPJ0to0kbnkQcIxT81Mbm9tUJ' | base64 -d | od -txC
0000000 06 0e cf 2f 4e dd 3c 9d 2d a3 49 1b 9e 44 1c 23
0000020 14 fc d4 c6 e6 f6 d5 09
0000030

SHA1 のハッシュ値は 160bit = 20 バイト固定です。実際のデータは 24 バイトあるので、後ろ 4 バイトがソルトの値になります*2。つまり「e6 f6 d5 09」がソルトの値です。

では、逆にパスワードから計算して見ましょう。先の例では 16 進でダンプしてますが、echo コマンドで 8 進表記をする都合があるので、8 進でダンプしてみます。

$ echo -n 'Bg7PL07dPJ0to0kbnkQcIxT81Mbm9tUJ' | base64 -d | od -toC
0000000 006 016 317 057 116 335 074 235 055 243 111 033 236 104 034 043
0000020 024 374 324 306 346 366 325 011
0000030

8 進表記だと、ソルトの値は「346 366 325 011」になります。パスワード文字列が「testtest」ですから、これを組み合わせると、下記のようになります。

$ echo -en 'testtest\0346\0366\0325\0011' | sha1sum
060ecf2f4edd3c9d2da3491b9e441c2314fcd4c6  -

この結果にソルトの値をつなげると、{SSHA} の後ろの文字列をデコードした結果に一致している事が分かると思います。

ソルトと Rainbow Table

ソルトを加えることで、同じパスワードでも得られる処理結果が違ってきます。OpenLDAP の SSHA の場合、ソルトは 4 バイト = 32bit のデータなので、2³² = 4,294,967,296 通りのソルトが考えられます。

という事は、１つのパスワード文字列に対して、4,294,967,296 通りのハッシュ値が考えられる、ということになります。

Rainbow Table は、「ハッシュ値がこうだったら、パスワードはこれ」というテーブルです。もしソルトが無ければ、

ハッシュ値	パスワード
51abb9636078defbf888d8457a7c76f85c8f114c	testtest

という表が作られます。ところがソルトがあると、同じパスワードでもソルトが違えばハッシュ値が違ってきます。もし、OpenLDAP の SSHA 用 Rainbow Table を作るとなると、

ハッシュ値 + ソルト	パスワード
55bc8442d5d0614101515ab345ee0a12b5989d4000000000	testtest
3955ef9cf1ba8a6341e40511d5347ba472d42a4600000001	testtest
c8c951ffb7c35a83eb36fad72105a8d66dcb8d3d00000002	testtest
....	....
455f99a067b95a9477cd47f478224f188f91a411ffffffff	testtest

といった具合になり、１つのパスワードで 4,294,967,296 行のデータが作られる事になります

Ophcrack で使える 7 文字までの LM ハッシュに対する Rainbow Table が 7.5 GB ですが、LM ハッシュでは大文字小文字を区別しないので、かなりコンパクトなサイズになっています。しかし、仮に LM ハッシュに 4 バイトのソルトを加えると、単純計算で 32,212,254 TB になります*3。実際の SSHA では大文字小文字を区別しますから、この数字のおよそ 100 倍になるはずです*4。既に非現実的な容量な上に、7 文字までです。

ソルトとブルートフォース

ソルトを付けることで、Rainbow Table を使うアプローチは実質的に使えなくなる事が分かりました。しかし、愚直にブルートフォースを行う場合、それに対抗するための効果はソルトにはありません。

前述のように、保存されているパスワード情報からソルトの値自体は分かります。試そうとするパスワード候補に対して、読み取ったソルトを加えてハッシュ値を求めれば、そのパスワード候補が当たっているかどうかの確認はできます。もちろん、１つのパスワードに対する検証処理で、若干、処理が多くなる（ソルト値を読み出す処理と、パスワード候補にその値を付け加える処理）のですが、全体の処理から見れば、ゴミみたいなものです。

まとめ

ソルトの効用は、あくまでも Rainbow Table のような、「予めハッシュ値を計算しておく」という手段に対抗するもので、ブルートフォースの様に「ひたすらハッシュ値を計算して、合致するものを探す」という手段には、ほとんど影響はありません。

ただ、Ophcrack で分かるように、Rainbow Table が使えると、ブルートフォースに比べて劇的に短い時間でパスワードが判明します。それを防げるのは大きなメリットでしょう。

エフセキュアのブログで「ソルト付き SHA-1 は大丈夫か」というのは、GPU を使うとハッシュ値が効率よく計算できるので、これまでだったら「ブルートフォースで見つかる時には、死んじゃってるよ」と言えたパスワードが、意外に早く見つかってしまう、という事です*5。

でも、パスワードを１文字増やすだけで、見つかる時間は約 100 倍になります。2 文字増やせば 10,000 倍です。今までより、２文字ぐらい、パスワードを長くした方が良さそうです。

*1:id:JULY:20110216

*2:OpenLDAP が userPassword に保存する際のソルトは 4 バイトですが、ソースを見ると、検証時にはソルトのサイズは決まってなく、得られたデータのうち、21 バイト目以降がソルト、という扱いになっているようです。なので、自前で 4 バイトより大きなソルトを使って計算した結果を保存しても、正しく検証されるはずです。

*3:もちろん、データベースの構造などを工夫して、圧縮できる可能性はあるかもしれませんが、10 分 1 にできても焼け石に水です。

*4:id:JULY:20100515 で、7 文字までのパスワードが大文字小文字を区別しないと 100 分の 1 になる、というところを参照

*5:その意味では、ソルト付きか否かは無関係だと思うのですが....