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

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

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

Crypt (Unix) - Wikipedia

UNIX 系 OS には、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 進数表記）
8	1000	70*4
4	100	70
2	10	70
1	1	00
0	0	-

数値が 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 に渡すと、

B2	alt_result[0]	6e
B1	alt_result[6]	93
B0	alt_result[12]	7b

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

回	数値（2 進表記）	下位 6 bit	文字
1	011011 101001 001101 111011	111011(59)	v
2	011011 101001 001101	001101(13)	B
3	011011 101001	101001(41)	d
4	011011	011011(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	文字
1	001101 010000 110111 110010	110010(50)	m
2	001101 010000 110111	110111(55)	r
3	001101 010000	010000(16)	E
4	001101	001101(13)	B

3つ目：bf 8e d3

回	数値（2 進表記）	下位 6 bit	文字
1	101111 111000 111011 010011	010011(19)	H
2	101111 111000 111011	111011(59)	v
3	101111 111000	111000(56)	s
4	101111	101111(47)	j

4つ目：7e d8 3e

回	数値（2 進表記）	下位 6 bit	文字
1	011111 101101 100000 111110	111110(62)	y
2	011111 101101 100000	100000(32)	U
3	011111 101101	101101(45)	h
4	011111	011111(31)	T

5つ目：01 64 04

回	数値（2 進表記）	下位 6 bit	文字
1	000000 010110 010000 000100	000100(4)	2
2	000000 010110 010000	010000(16)	E
3	000000 010110	010110(22)	K
4	000000	000000(0)	.

最後：00 00 5a

回	数値（2 進表記）	下位 6 bit	文字
1	000000 000000 000001 011010	011010(26)	O
2	000000 000001 011010	000001(1)	/

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

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

• 割りつける文字のテーブルが違う*7。
• Base64 はバイトストリームの先頭から順に変換するのに対し、この場合は飛び飛びのデータをピックアップして変換している。

という点が違います。

まとめ

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

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

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

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

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

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

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

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

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