Hatena::ブログ(Diary)

JULYの日記

2011-02-18 塩加減は重要?

[]ソルト効用

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

id:JULY:20100515

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

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

ソルトとは

塩です。

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

こうしておくと、

という状態になります

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

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

OpenLDAP での SSHA の例

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

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

userPassword:: e1NTSEF9Qmc3UEwwN2RQSjB0bzBrYm5rUWNJeFQ4MU1ibTl0VUo=

「userPassword」の後ろにコロンが2つ続いているのは、続く文字列Base64エンコードされた結果である事を表すので、デコードしてみます。以下は、CentOS 5.5 上で実行した様子ですが、他のディストリビューションでも同様だと思います。使っているコマンドGNU 版の echobase64od、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 のデータなので、232 = 4,294,967,296 通りのソルトが考えられます

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

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

ハッシュ値パスワード
51abb9636078defbf888d8457a7c76f85c8f114ctesttest

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

ハッシュ値 + ソルトパスワード
55bc8442d5d0614101515ab345ee0a12b5989d4000000000testtest
3955ef9cf1ba8a6341e40511d5347ba472d42a4600000001testtest
c8c951ffb7c35a83eb36fad72105a8d66dcb8d3d00000002testtest
........
455f99a067b95a9477cd47f478224f188f91a411fffffffftesttest

といった具合になり、1つのパスワードで 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 を使うアプローチ実質的に使えなくなる事が分かりました。しかし、愚直にブルートフォースを行う場合、それに対抗するための効果はソルトにはありません。

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

まとめ

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

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

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

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

*1id:JULY:20110216

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

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

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

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