Dovecot が保存する CRAM-MD5 認証用パスワード

チャレンジ・レスポンス型の認証 (CRAM-MD5, APOP など) では、 その認証方式の性質上、サーバに保存するパスワードは平文のままで なければならないと思っていた。 しかし、Dovecot が CRAM-MD5 認証用に保存するパスワードは平文ではない。

$ dovecotpw -s HMAC-MD5
Enter new password: secret
Retype new password: secret
{HMAC-MD5}cd3ba7deaad6e5ca23448ba42e379747a9e0f7f1fbc00c8a81bbaac395731b56

この HMAC-MD5 という物はハッシュ値のようだが、 この文字列は HMAC-MD5 値では無く、HMAC-MD5 算出途中の値らしい。

この値は以下の様に求められている。

HMAC-MD5 とは MD5 の HMAC なので、まず MD5 について言うと、 MD5 の多くの実装は MD5Init, MD5Update, MD5Final の 3 つの処理からなる。 MD5Init と MD5Final は最初と最後に 1 度だけ実行され、 MD5Update は MD5 値を求めようとするデータの 64 バイト毎に繰り返し実行される。 MD5 のアルゴリズムを以下とすると、

MD5(X, Y)

データが 64 バイト以下の場合、その処理は以下の様になる。

1: MD5Init()
2: MD5Update(X)
3: MD5Update(Y)
4: MD5Final()

一方 HMAC のアルゴリズムは以下で、

H(K XOR opad, H(K XOR ipad, text))

HMAC-MD5 の場合、上記の H が MD5 になる。 そして CRAM-MD5 では上記の K がパスワード、text がチャレンジ文字列なので 結果以下となる。

MD5(password XOR opad, MD5(password XOR ipad, challenge))

するとこちらの処理は以下となる。

1: MD5Init()
2: MD5Update(password XOR ipad)
3: MD5Update(challenge)
4: MD5Final()              <--- この結果が MD5(X, Y) の Y
5: MD5Init()
6: MD5Update(password XOR opad)
7: MD5Update(Y)
8: MD5Final()              <--- これで HMAC-MD5 値が完成

この手順を考えてみると、challenge は認証が開始されるまで不明だが password はサーバ側に保存する物なので、 2 と 6 は予め計算しておくことが可能だと解る。 そしてこの 2 と 6 の結果を連結したものが Dovecot が CRAM-MD5 認証用に 保存しているパスワードだ。

MD5 のアルゴリズムについて詳しく無いので、 この MD5Final する前の状態でも一方向ハッシュとしての性質を 備えているのかどうか判らないが、もしそうなら、この値から元のパスワードを 知る事はできない。 ただし、パスワードファイルの内容とチャレンジ文字列から HMAC の計算を続行し、CRAM-MD5 における authenticate コマンドの レスポンスを返す事が出来そうなので、わざわざ計算途中の値を保存しても 意味無いと思うのだけど。

ちなみに APOP は MD5(challenge, password) なので同じ事はできない。

参考:
HMAC: メッセージ認証のための鍵付ハッシング
MD5 メッセージダイジェストアルゴリズム
IMAP4 and CRAM-MD5 Authentication