bcrypt
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2024/12/16 13:39 UTC 版)
この項目は内容が専門的であり、一般の閲覧者にはわかりにくくなっているおそれがあります。 |
一般 | |
---|---|
設計者 | Niels Provos, David Mazières |
初版発行日 | 1999 |
派生元 | Blowfish |
詳細 | |
ダイジェスト長 | 184 bit |
ラウンド数 | コストパラメータで変更可能 |
bcrypt(ビー・クリプト)はNiels ProvosとDavid Mazièresによって設計された1999年にUSENIXにて公開された、Blowfish暗号を基盤としたパスワードハッシュ化関数である[1]。レインボーテーブル攻撃に対抗するためにソルトを組み込んでいる以外に、bcryptは適応的な特性を備えている。計算能力が増えたとしてもブルートフォース攻撃に耐えられるように、繰り返し回数を増やして速度を落とせるようになっている。
bcryptはOpenBSD[2]のデフォルトのパスワードハッシュアルゴリズムとして利用されているほか、SUSE Linux[3]などのLinuxディストリビューションを含む他のシステムでも利用されている。
bcryptはC、C++、C#、Go[4]、Java[5][6]、JavaScript[7]、Elixir[8]、Perl、PHP、Python[9]、Ruby、その他の言語による実装がある。
背景
Blowfishはブロック暗号の中では鍵のセットアップフェーズのコストが高いことで知られている。Blowfishは標準状態はいくつかのサブキーで開始される。その後、鍵の一部を使ってブロック暗号化を行い、この暗号化(正確にはハッシュ)の結果を使ってサブキーのいくつかを置換する。その後は変更された状態を使って鍵の残りの部分の暗号化を行い、その結果を使ってより多くのサブキーを置換する。この方法を繰り返し、段階的に状態を変更しつつ鍵のハッシュ化とビットの状態の置き換えを行い、最終的にすべてのサブキーを設定していく。
ProvosとMazièresはこの方法を取り入れ、さらに発展させた。彼らはBlowfishのための新しい鍵セットアップアルゴリズムを開発し、その成果物の暗号に"Eksblowfish" ("expensive key schedule Blowfish")という名前をつけた。このアルゴリズムでは標準のBlowfishの鍵セットアップから変更され、すべてのサブキーの設定において、ソルトとパスワードの両方を利用する。その後は、ソルトとパスワードを交互に鍵として使い、標準のBlowfishの鍵作成アルゴリズムを複数ラウンド数適用していく。ラウンドのたびに、以前の適用結果をサブキーの状態として計算を行う。理論的にはBlowfishの鍵スケジュールほど強くはないが、鍵作成のラウンド数が変更可能であるため、任意でこのプロセスの計算量を増やして遅くすることが可能であり、ハッシュやソルトに対するブルートフォース攻撃に対抗できる。
説明
bcryptによってハッシュ化された文字列は"$2a$"や"$2b$" (あるいは "$2y$")という接頭辞を持つ。この接頭辞はハッシュ化する際に用いたアルゴリズムによって異なり、前述の接頭辞の場合はshadowパスワードファイルがModular Crypt Formatと呼ばれる形式で記述されており、bcryptハッシュであることを示す[10]。ハッシュ文字列の残りの部分にはコストパラメータ、128ビットのソルト(Radix-64エンコードされて22文字になっている)、184ビットの結果のハッシュ値 (Radix-64エンコードされて31文字になっている)が含まれる[11][要出典]. 。Radix-64はunix/cryptアルファベットを利用するもので、標準のBase-64とは異なる[12][13]。コストパラメータはキー拡張の反復回数を設定するもので、2のべき乗の数となっていて、暗号アルゴリズムの入力値となっている。
$2a$10$N9qo8uLOickgx2ZMRZoMyeIjZAgcfl7p92ldGxad68LJZdL17lhWy
というshodowパスワードのレコードを例にとると、コストパラメータは10で、キー拡張のラウンド数は210になる。ソルトはN9qo8uLOickgx2ZMRZoMye
であり、結果のハッシュは IjZAgcfl7p92ldGxad68LJZdL17lhWy
となっている。一般的なパスワード管理のプラクティス通り、ユーザーのパスワードそのものが格納されることはない。
バージョン履歴
$2$ (1999年)
オリジナルの仕様では接頭辞が $2$
であると定義されていた。これはOpenBSDのpasswordファイルにパスワードを格納するために使われるModular Crypt Format[10]フォーマットにしたがっている:
$1$
: MD5ベースの暗号('md5crypt')$2$
: Blowfishベースの暗号 ('bcrypt')$sha1$
: SHA-1ベースの暗号 ('sha1crypt')$5$
: SHA-256ベースの暗号 ('sha256crypt')$6$
: SHA-512ベースの暗号 ('sha512crypt')
$2a$
オリジナルの仕様ではASCII以外の文字やnull終端をどのように扱うべきかの定義がなかった。このバージョンの仕様では文字列のハッシュ化について定義され改訂された:
- 文字列はUTF-8エンコードされる
- null終端がふくまれなければならない
これらの変更により、バージョンが$2a$
[14]に変更された。
$2x$, $2y$ (2011年6月)
2011年6月に、BCryptのPHP実装であるcrypt_blowfishの中でバグが発見された。8ビット文字列の扱いを間違っていたのが原因であった[15]。システムの管理者は既存のパスワードデータベースを開き、$2a$
を$2x$
に更新することで、既存の間違ったハッシュアルゴリズムを明示的に使い続けていることを示すことを提案した。それ以外にも、修正されたアルゴリズムで生成されたハッシュ値で示すために、crypt_blowfishが接頭辞として$2y$
を出力するアイディアを提案した。
標準的なOpenBSDを含むどのディストリビューションも2x/2yのアイディアを採用しなかった。このバージョンマーカーの変更はcrypt_blowfish.に限定された。
$2b$ (2014年2月)
バグがOpenBSDのbcrypt実装で発見された。これは8ビットのバイトであるunsigned charに長さを格納をしていたのが原因である[14]。パスワード長として255文字を越えると、オーバーフローして長さが255に丸められてしまった[16]。
BCryptはOpenBSDのために作られた。OpenBSDのライブラリでバグが発見された時はバージョン番号が更新されることが決定される。
アルゴリズム
bcryptのアルゴリズムは"OrpheanBeholderScryDoubt" というアルゴリズムをBlowfishを用いて64回暗号化した文字列を作成する。bcryptでは通常のBlowfishの鍵セットアップ関数をコストが高価な(expensive key setup)EksBlowfishSetup関数に置き換えている:
Function bcrypt Input: cost: Number (4..31) log2(Iterations)。例えば 12 ==> 212 = 4,096回繰り返す salt: array of Bytes (16 bytes) ランダムソルト password: array of Bytes (1..72 bytes) UTF-8エンコードされたパスワード Output: hash: array of Bytes (24 bytes) //key setup algorithmを使って、Blowfishの状態を初期化 stateカテゴリ:ハッシュ関数・メッセージ認証コード・認証付き暗号
カテゴリ
- bcryptのページへのリンク