Hatena::ブログ(Diary)

JULYの日記

2011-03-17 調べてみると、結構複雑

[]/etc/shadow のパスワードフィールド

question:1299688445 を切っ掛けに、/etc/shadow ファイルパスワードフィールドを調べてみたら、思いの外、複雑な処理をしているのが分かったので、実際にこの処理を追いかけてみました。

近頃の UNIXOS の /etc/shadow のパスワードフィールドは、実際にはいくつかのハッシュ関数を選べる事になっています

Crypt (Unix) - Wikipedia

UNIXOS には、crypt という C 言語用の関数が用意されていて、伝統的には DES を使った処理でパスワードフィールド用の文字列を生成していたのですが、この関数自体を拡張することで、MD5 や SHA-256、512 といったハッシュ関数を使う処理も出来るようになっています。どの方式を使っているかは、パスワードフィールド文字列の先頭にある「$1$」といった部分で判断します。

先頭文字列使用されるハッシュ関数
$1$MD5
$2$(または $2a$)Blowfish*1
$5$SHA-256
$6$SHA-512

「$」で区切られたフィールドの 2 つ目がソルトの値で、3 つ目のフィールドが、変換処理後のパスワード情報、という事になります

ただ、先の OpenLDAP 上の userPassword に SSHA(Salted SHA)形式で保存したときと違って、「パスワード文字列ソルトを足してハッシュ値を求める」というものではなく、もっと複雑な処理をしています*2

じゃぁ、その複雑な処理を、先の SSHA の時のように、ステップ・バイ・ステップで追ってみます。使うのは glibcソースコードMD5 を使った場合の実装がある、crypt/md5_crypt.c を元にします。

はじめの一歩

まず、最初に「パスワード文字列 + ソルト文字列 + パスワード文字列」というデータに対して、MD5 の値を求めます

パスワード文字列を「password」、ソルト文字列を「bOdL64wj」とすると、

$ echo -n 'passwordbOdL64wjpassword' | md5sum
66f2d102571eece1f5082f5d7cc5fab6  -

となります

話はそれますが、このパスワードソルト文字列組合せで、実際に /etc/shadow のパスワードフィールドに書かれた文字列は「vBdPmrEBHvsjyUhT2EK.O/」でした。これがゴールになります*3

ストレッチングの準備

準備体操の前に準備体操、みたいですが、別に、これから激しい運動をするわけじゃありません。

ハッシュ値をさらに入力としてハッシュ値を求める、といった具合に、何度もハッシュ値計算を何度も繰り返す手法をストレッチングと呼びますハッシュ値を求める処理自体は、いろんなところで使われるので、計算時間が短いほうが良いのですが、パスワード情報を保存する上では、ブルートフォース攻撃(総当り攻撃)に対して好ましくはありません。

glibc の処理でも、このストレッチングをしているのですが、単に何回も繰り返しているのではなく、かなり複雑です。実際、1,000 回のストレッチング処理があるのですが、その前に、もうひとひねり、処理が入っています

まず、「パスワード文字列 + "$1$" + ソルト文字列」というデータを用意します。そのデータの後ろに、先に求めたハッシュ値を加えます

ただし、パスワードの長さによって、「加える量」が違ってきます

16 文字以下であれば、先のハッシュ値の先頭からパスワード長と同じバイト数を加えます。今回の例では「password」なので、先のハッシュ値の先頭 8 バイト分の「66f2d102571eece1」を加えます

16 文字以上であれば、ハッシュ値が何度も繰り返されているデータイメージして、文字列長と同じ分、となります。もし 35 文字であれば、「66f2d102571eece1f5082f5d7cc5fab666f2d102571eece1f5082f5d7cc5fab666f2d1」が加えられることになります

次に、「パスワード長さの数値を使って 0 になるまで右へビットシフトを行い、その時の値が奇数なら値 0 の 1 バイト、偶数の時はパスワードの先頭文字を追加していく」という処理があります。これだと分かりづらいので、具体的に見てみます

今は、パスワード長は 8 文字でしたから、8 からスタートします。8 は偶数なので、パスワードの先頭文字を追加します。次に 8 という値を右へビットシフトします。8 を右へビットシフトすると 4 になり、偶数なので、パスワードの先頭文字を追加します。

これを繰り返すとこんな感じになります

数値2 進数表記付け加える値(バイナリの 16 進数表記)
8100070*4
410070
21070
1100
00-

数値が 0 になった時は、値を付け加える事はしません。結果的に 8 文字のパスワードの時は「70707000」(16 進数表記)というバイナリ値が付加される事になります

ここまでで、用意される入力データは次のようになります

「password$1$bOdL64wj」(文字列)+「66f2d102571eece1」(バイナリ値)+「70707000」(バイナリ値)

で、このデータハッシュ値を求めます

$ printf 'password$1$bOdL64wj\x66\xf2\xd1\x02\x57\x1e\xec\xe1\x70\x70\x70\x00' | md5sum
5217ba3fe42c400a718563a73c65f323  -

1,000 回のストレッチング

いよいよ、1,000 回のストレッチングに入るのですが、これも単純ではありません。「今、何回目か」というのを 0 始まりの数字で考えて(つまり、一番最初が 0 回目)、下記のようになります

  1. 奇数の時はパスワード文字列、偶数の時は前回のハッシュ値入力データとして用意する。
  2. 3 の倍数ではないときソルト文字列入力データに追加する。
  3. 7 の倍数ではないときパスワード文字列入力データに追加する。
  4. 奇数の時は前回のハッシュ値、偶数の時はパスワード文字列入力データに追加する。
  5. ハッシュ値計算する。

一番最初ときの「前回のハッシュ値」は、先の「ストレッチングの準備」で求めたハッシュ値になります

さすがにこれを手でやるのは無理なので、シェルスクリプトします。

#/bin/sh

last_hash='5217ba3fe42c400a718563a73c65f323' # ストレッチングの準備の値
salt_str='bOdL64wj' # ソルト文字列
pass_str='password' # パスワード文字列

hash_hex=`echo -n $last_hash | sed 's/\(.\{2\}\)/\\\\x\1/g'`
counter=0

while [ $counter -lt 1000 ]
do
    input_data=""

    remainder=`expr $counter % 2`
    if [ $remainder -ne 0 ]; then
        input_data=$pass_str
    else
        input_data=$hash_hex
    fi

    remainder=`expr $counter % 3`
    if [ $remainder -ne 0 ]; then
        input_data=${input_data}${salt_str}
    fi

    remainder=`expr $counter % 7`
    if [ $remainder -ne 0 ]; then
        input_data=${input_data}${pass_str}
    fi

    remainder=`expr $counter % 2`
    if [ $remainder -ne 0 ]; then
        input_data=${input_data}${hash_hex}
    else
        input_data=${input_data}${pass_str}
    fi

    last_hash=`printf $input_data | md5sum | cut -d ' ' -f1`
    hash_hex=`echo -n $last_hash | sed 's/\(.\{2\}\)/\\\\x\1/g'`

    counter=`expr $counter + 1`
done

echo $last_hash

これを実行すると、「6e35bf7e0104930d8ed8645a7bf2d33e」というハッシュ値が得られます

謎の Base64 もどき

後は、このハッシュ値パスワード情報として格納する文字列の形式に変換すれば良いのですが、この変換方法が摩訶不思議です。一見、Base64 っぽく見え、かつ、実際にソースコード上でも「b64_from_24bit」という名前マクロ定義して処理しているので、「で、Base64 で変換してお終いかな」と思うのですが、処理内容を見ると似て非なるものでした。

実際のコードは下記のようになっています

/* Table with characters for base64 transformation.  */
static const char b64t[64] =
"./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";

/* 中略 */

#define b64_from_24bit(B2, B1, B0, N)                         \
  do {                                        \
    unsigned int w = ((B2) << 16) | ((B1) << 8) | (B0);               \
    int n = (N);                                  \
    while (n-- > 0 && buflen > 0)                         \
      {                                       \
    *cp++ = b64t[w & 0x3f];                           \
    --buflen;                                 \
    w >>= 6;                                  \
      }                                       \
  } while (0)


  b64_from_24bit (alt_result[0], alt_result[6], alt_result[12], 4);
  b64_from_24bit (alt_result[1], alt_result[7], alt_result[13], 4);
  b64_from_24bit (alt_result[2], alt_result[8], alt_result[14], 4);
  b64_from_24bit (alt_result[3], alt_result[9], alt_result[15], 4);
  b64_from_24bit (alt_result[4], alt_result[10], alt_result[5], 4);
  b64_from_24bit (0, 0, alt_result[11], 2);

b64_from_24bit の処理内容は、3 つのバイトデータをつなげて、6 bit ずつ取り出し、b64t というテーブルで定義された文字を割り当てます

先に求めたハッシュ値を、実際に最初の b64_from_24bit に渡すと、

B2alt_result[0]6e
B1alt_result[6]93
B0alt_result[12]7b

ですから、まずこの 3 つのデータから「6e937b」という数値が作られます。この数値に対して下位 6 bit の値を取り出すと、111011(2進数表記)になり、10 進数だと 59 になります。で、b64t で列挙されている文字の 59 番*5に当たる文字「v」を採用します。その後、6 bit 右へシフトして、同様の処理を残り 3 回、実行します。

数値(2 進表記)下位 6 bit文字
1011011 101001 001101 111011111011(59)v
2011011 101001 001101001101(13)B
3011011 101001101001(41)d
4011011011011(27)P

これが、1 つ目の b64_from_24bit の処理内容になります

同様に 2 つ目の b64_from_24bit は「35 0d f2」、3 つ目は「bf 8e d3」、4 つ目は「7e d8 3e」、5 つ目は「01 64 04」、最後は「00 00 5a」*6入力となり、それらを順に処理してみると、下記のようになります

2つ目:35 0d f2
数値(2 進表記)下位 6 bit文字
1001101 010000 110111 110010110010(50)m
2001101 010000 110111110111(55)r
3001101 010000010000(16)E
4001101001101(13)B

3つ目:bf 8e d3
数値(2 進表記)下位 6 bit文字
1101111 111000 111011 010011010011(19)H
2101111 111000 111011111011(59)v
3101111 111000111000(56)s
4101111101111(47)j

4つ目:7e d8 3e
数値(2 進表記)下位 6 bit文字
1011111 101101 100000 111110111110(62)y
2011111 101101 100000100000(32)U
3011111 101101101101(45)h
4011111011111(31)T

5つ目:01 64 04
数値(2 進表記)下位 6 bit文字
1000000 010110 010000 000100000100(4)2
2000000 010110 010000010000(16)E
3000000 010110010110(22)K
4000000000000(0).

数値(2 進表記)下位 6 bit文字
最後:00 00 5a
1000000 000000 000001 011010011010(26)O
2000000 000001 011010000001(1)/

最初から順に文字を並べると、「vBdPmrEBHvsjyUhT2EK.O/」となり、実際の /etc/shadow に書きこまれたものと同じになりました。

「6 bit ずつ区切って文字を割りつける」というところは Base64 と同じなのですが、

という点が違います

まとめ

UNIXOS では古くからソルトが使われていて、Rainbow Table に対する耐性を持っていたのですが、対ブルートフォースも、ある程度考えられている事が分かりました。

それにしても、後発の Windows はなぜ、ソルトを付けなかったんだろう...。

*1:Blowfish 自体はハッシュ関数ではなく、暗号化処理ですが、パスワードを鍵として特定の文字列暗号化することで、ハッシュ関数と同様の使い方をしています。このやり方は、伝統的な DES を使った処理に似ています

*2:という事を、glibcソースを見るまで知らなかった...

*3:というか、「password」というパスワードを実際に付けてみたら、その時のソルト文字列が「bOdL64wj」だった、ということです。

*4:「p」の ASCII コード上の値を 16 進数表記すると 70。

*5:0 が最初の文字なので、60 番目の文字。

*6最後に文字に変換するのは下位 12 bit 分の2回だけ

*7Base64 は「0-9A-Za-z+/」の順。「+」の代わりに「.」があって、英数字以外の2文字が前にあるのが、Base64 との違い。

Connection: close