パスワードハッシュアルゴリズム bcrypt と Modular Crypt Format(MCF)

これはmixiグループ Advent Calendar 2018 12日目の記事です。

TL;DR

• パスワードのハッシュ化だけでなく、ソルトの付与やストレッチングもしようね
• bcryptはソルトの付与とストレッチングをしてくれるので、パスワードハッシュアルゴリズムとしておすすめ
• bcryptのバージョンはできるだけ2bを使おう
• bcryptが生成する文字列はModular Crypt Format(MCF)に沿う
• MCFは/etc/shadowなどに使われるパスワードハッシュ文字列のフォーマット

パスワードのハッシュ化してますか？

さて、みなさんは認証機構を実装する際のパスワードの保存方法はどのようにしていますか？
もうこの時代にパスワードを平文で保存するなんてことしてないですよね？

もう常識と言っても過言ではないですがパスワードを保存する際には、ハッシュアルゴリズムを使って計算した結果を保存するか、秘密鍵を使った暗号化を行いその結果を保存するか、どちらかを行います。
（またはその両方を行っている場合もあったりするのでしょうか?）

しかし、秘密鍵を使った暗号化を施したパスワードでも解読されてしまったAdobeのパスワード流出事件（徳丸さんの解説記事）もありましたし、最近ではBigQueryで高速にレインボーテーブルを作成するという記事（BigQueryでレインボーテーブル攻撃をしてみた）を書いてらっしゃる方もいます。
これらのことから分かる通り、今の時代、ただ単にパスワードのハッシュ化や暗号化をしただけでは実際のパスワードの流出は防げません。そのため、次に挙げるソルト（salt）とストレッチング、2つの方法でより強い（解読されにくい）ハッシュを生成するのが常識となりつつあります。

ソルト（salt）

ただ単にハッシュを生成するだけでは、すべての文字列の組み合わせをハッシュ化したリストを用意するというレインボーテーブル攻撃に弱いため、「ソルト（salt）」と呼ばれる適当な文字列を生パスワードと結合し、それをハッシュ化するのが一般的です。

ストレッチング

生成したハッシュ値を再度ハッシュするというのを何度も繰り返す「ストレッチング」という手法を用い、ハッシュ計算時間を長くすることで大量のコンピュータ資源を使ったブルートフォース攻撃から解読の時間を稼げます。
ただし、ストレッチング回数が増えるごとに正規の手段でハッシングを行うサーバにも負荷がかかるため、そのサーバへの負荷に見合う回数にする必要があります。

ハッシュアルゴリズム

そして、実際にハッシュを行うハッシュアルゴリズムとして有名なのは、MD5やSHA-1, SHA-256, SHA-512が挙げられます。
ただ、MD5やSHA-1はすでにハッシュの衝突が発見されており、使用は推奨されません。

上に挙げたハッシュアルゴリズムの他にbcryptというパスワードハッシュアルゴリズムがあります。
やっと本題ですが、この記事ではそのbcryptについて解説したいと思います。

bcrypt

bcryptはBlowfish暗号を利用したパスワードハッシュアルゴリズムです。
ただ単にハッシュ化するだけでなく、ソルトの付与とストレッチングを行うことで、より強固なハッシュ値を求められるようになっています。
1999年に発表され、OpenBSDのデフォルトのパスワードハッシュアルゴリズムとして採用されています。また、その他のLinuxディストリビューションにもライブラリが含まれています。

bcryptが返す文字列の構造

大抵のbcryptを実装しているライブラリは、以下のような文字列を返します。

$2a$10$I.2aGOSpXNLLMhf1Zls8eewlsuRdUdHVWo67uhq/2ack.UAqoLi0q

この文字列には、bcryptのバージョンや、ストレッチング回数、ソルト、実際のハッシュ文字列が含まれており、それを頼りに同じ条件でハッシュを取ることで、例えばハッシュ済みのパスワードと入力されたパスワードが一致するかどうかを確認できます。

$がセパレータとなっており、以下のような構造となっています、

2a : 2文字目〜

ハッシュアルゴリズムのバージョンを示します。bcryptは2, 2a, 2b, 2x, 2yなどのバージョンがあります。バージョンの詳細については別の項で説明します。

10 : 4文字目〜

ストレッチング回数を示します。この数は2^nのnの部分に相当し、10を指定すれば、2^10である1,024回ストレッチングされます。たいていのbcrypt実装では、4〜31の数値を渡せるようです。

I.2aGOSpXNLLMhf1Zls8ee : ストレッチング回数の$の後から22文字

ソルトを示します。必ず22文字の[./0-9A-Za-z]にマッチする文字列でなければなりません。この文字種制限は後述するModular Crypt Formatの仕様のためです。

wlsuRdUdHVWo67uhq/2ack.UAqoLi0q : 残りの31文字

いままでに挙げたハッシュアルゴリズムのバージョンで、指定のソルト文字列を付与し、指定回数ストレッチングを行った実際のハッシュ文字列です。

bcryptのバージョン

これはほぼ https://en.wikipedia.org/wiki/Bcrypt#Versioning_history の和訳になってしまいますが…

2 (1999年)

1999年当時に発表されたbcryptでは、後述するModular Crypt Formatのバージョン(またはID)として、2を利用することが定義されました。
この1999年に発表されたbcryptを、今後は「オリジナル」と呼びます。

2a

オリジナルのbcryptでは、ASCII以外の文字列と、NULL終端文字のハンドリングについて定義されていませんでした。
そのため、ハッシュする文字列について以下のように決め、バージョンを2aとして改定しました。

• UTF-8エンコードされた文字列であること
• NULL終端文字を必ず含むこと

2x, 2y (2011年6月)

2011年にPHPのbcrypt実装にバグが見つかりました。そのバグは修正され一部の挙動が変更されましたが、バージョンの改定が行われませんでした。そのためバージョン2aには、バグ修正前のものと、バグ修正後のものが混在するようになってしまいました。
バグ修正前にハッシュされた文字列と修正後にハッシュされた文字列を見分けるために、修正前のものを2aから2xに置換し、修正後のものを2yとバージョニングすることが推奨されました。

2b (2014年2月)

さらに2014年にはOpenBSDのbcrypt実装にバグが見つかり、その修正を行ったバージョンを2bとしました。

bcryptを利用する上での注意点

bcryptの多くの実装では、パスワード文字列を受け取るのは72byteまでで、それ以降はサイレントに切り捨ててハッシュ化するものが多いようなので、ユーザの入力が72byteよりも長い場合はエラーとするなど工夫が必要です。

バージョンは最新の2bを利用するのがおすすめですが、2bに対応していないライブラリもあるようなので利用には注意が必要です。

Modular Crypt Format (MCF)

さて、ここまでがbcryptの説明でした。
このような、Base64のようなエンコードを施した文字列と$が混ざった文字列を、例えばLinuxのユーザのパスワードを管理する/etc/shadowなどで見たことがあるかも知れません。
これは、bcrypt独自のフォーマットではなく、Modular Crypt Format(MCF)というフォーマットで、bcryptの構造を説明したように、ハッシュ方式やストレッチング回数、ソルト、実際のハッシュ後の文字列などをまとめて保持するためのフォーマットです。

MCF登場の歴史

多くのUNIXシステムはDES暗号をサポートしていました。しかし、同時期にハッシュのバリエーションがいくつも開発され、どの方式でハッシュをした文字列なのか判別がつかない状態でした。
そのため、1つのDB(またはパスワードファイル)に複数のハッシュ方式を共存させたり、新しいハッシュ方式に順次移行させるようなことができませんでした。

これは、md5_cryptが開発されたときに導入されたMCFの出現で解決されました。MCFでは、すべてのハッシュ文字列に$identifier$というフォーマットのprefixをつけ、どの方式でハッシュ化したのかを示します。
これによって、1つのDBに複数のハッシュ方式を共存させることができるようになりました。

MCFの制約

7bitのASCII文字列を使うこと

$<identifier>$ で始まること

必ずprefixとして${identifier}$をつけます。<identifier>は、ハッシュ方式を短い一意な文字列で表します。小文字と数字、ハイフンのみが利用できます。
よく知られているidentifierは別の項で紹介します。

当初、identifierは1字の数字を想定していました。そのため古いシステムの中には、ハッシュ方式を判定するのに最初の文字だけを見るものがあります。しかし、それ以上の文字数を使用する新しいハッシュ方式が開発されました。そのようなハッシュ方式が開発されてしまったので、identifierの衝突を避けるために、新しいハッシュ方式は6-8文字のidentifierを使用する必要があります。

基本的に小文字のa-z、大文字のA-Z、数字の0-9、.と/のみを利用すること

セパレータとして$も使用可能です。

新しいハッシュ方式では、.の代わりに+を利用し、なるべく標準なBase64のエンコードに近づけるものもあります。

もっとも大事なのは、:;!*や印字が出来ないASCII以外の文字列、8bitの文字列を利用しないことです。これらの文字列は/etc/shadowなどのパスワードファイルのparseの妨げとなります。

ハッシュ文字列の最後に"digest"（実際のハッシュ結果）を置くこと

さらにdigestは$で区切るのが推奨されています。$で区切ることによってハッシュ方式やsaltなどの設定を示す文字列と"digest"の切り分けが簡単になるためです。

MCFの構造

基本的に、以下のような構造になっています。ただし、厳密にこれに沿わないハッシュ方式もあります。

$<identifier>[$<param>=<value>(,<param>=<value>)*][$<salt>[$<digest>]]

identifier

前述の通り、ハッシュ方式を示す文字列です。

param / value

ストレッチングの回数などハッシュ処理に必要な情報をパラメータとして記述することができます。

salt

ソルト文字列を示します。

digest

指定のハッシュ方式で、ストレッチングやソルト文字列の付与をした上で計算した実際のハッシュ値です。
これも後述しますが、実際のハッシュ結果はバイナリデータなのでそれに Base64 like なエンコードを施した文字列です。

よく利用されるidentifier

identifierとハッシュ方式の対応は以下の通りです。
（…Qiitaのテーブルの背景色とインラインコードの背景色が同じだから同化してしまう…）

identifier	ハッシュ方式
	DES
_	BSDi
1	MD5
2, 2a, 2b, 2x, 2y	bcrypt
3	NTHASH
5	SHA-256
6	SHA-512
md5	Solaris MD5
sha1	PBKDF1 with SHA1

Base64 like なエンコード

ハッシュしたデータは基本的にバイナリデータとなります。
そのため、使用が許可されているASCII文字列を利用してエンコードする必要があります。バイナリデータを印字可能なASCII文字列に変換するといえば、Base64ですね。
実際、標準なBase64から変換テーブルが若干変更されたものが利用されます。
例えばbcryptであれば、
./ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789
といった変換テーブルが利用されます。

ちなみに、通常のBase64変換テーブルは
ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/
なので、記号(+/, ./)とその位置が違うのでもしエンコード部分を実装する場合は注意が必要です。
また、Base64での=埋めもありません。

変換テーブルが若干違うのは、MCFの制約として「小文字のa-z、大文字のA-Z、数字の0-9、.と/のみを利用すること」というものがあるためです。

最後に

bcryptとMCFについて詳細に解説している日本語記事が少なかったので、英語版のWikipediaや実際の実装を読みつつ書いてみました。
とくに、PythonのpasslibのドキュメントがbcryptやMCFを含め、各種ハッシュアルゴリズムやその周辺の知識についてかなり詳しく説明されているので、興味がある方は読んでみると楽しいかもしれません。