|
Bcrypt
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のべき乗の数となっていて、暗号アルゴリズムの入力値となっている。
バージョン履歴$2$ (1999年) オリジナルの仕様では接頭辞が
$2a$ オリジナルの仕様ではASCII以外の文字やnull終端をどのように扱うべきかの定義がなかった。このバージョンの仕様では文字列のハッシュ化について定義され改訂された:
これらの変更により、バージョンが $2x$, $2y$ (2011年6月) 2011年6月に、BCryptのPHP実装であるcrypt_blowfishの中でバグが発見された。8ビット文字列の扱いを間違っていたのが原因であった[15]。システムの管理者は既存のパスワードデータベースを開き、 標準的な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 EksBlowfishSetup(cost, salt, password) //"OrpheanBeholderScryDoubt"という文字列を64回繰り返し暗号化 ctext "OrpheanBeholderScryDoubt" //24バイト ==> 3つの64ビットブロック repeat (64) ctext EncryptECB(state, ctext) //通常のBlowfishのECBモードを使って暗号化 //24-byteのctextが結果のパスワードのハッシュ return Concatenate(cost, salt, ctext) Expensive key setupアルゴリズムは、次のロジックを持つ鍵セットアップアルゴリズムの"Eksblowfish"に強く依存している: Function EksBlowfishSetup 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: state: opaque BlowFish state structure state InitialState() state ExpandKey(state, salt, password) repeat (2cost) state ExpandKey(state, 0, password) state ExpandKey(state, 0, salt) return state InitialStateはオリジナルのBlowfishアルゴリズムと同じように動作する。P配列とS-boxに の16進数の少数点数部分を設定したものである。 Expand keyExpandKey関数は次のような処理を行う: Function ExpandKey(state, salt, password) Input: state: Opaque BlowFish state structure P配列 と S-box のエントリーを含む salt: array of Bytes (16 bytes) ランダムソルト password: array of Bytes (1..72 bytes) UTF-8エンコードされたパスワード Output: state: opaque BlowFish state structure //パスワードを状態の内部にあるP-arrayに混ぜていく for n 1 to 18 do Pn Pn xor password[32(n-1)..32n-1] //パスワードが循環しているように扱う //ソルトの下位8バイトを使いstateの暗号化を行い、8バイトの結果を P1|P2 に格納する block Encrypt(state, salt[0..63]) P1 block[0..31] //下位32ビット P2 block[32..63] //上位32ビット //ソルトを用いて繰り返し状態の暗号化を行い、Pの配列の残りの部分に格納していく for n 2 to 9 do block Encrypt(state, block xor salt[64(n-1)..64n-1]) //現在のkey scheduleと循環するソルトを用いて暗号化 P2n-1 block[0..31] //下位32ビット P2n block[32..63] //上位32ビット //暗号化された状態を、状態内部のS-boxに混ぜていく for i 1 to 4 do for n 0 to 127 do block Encrypt(state, block xor salt[64(n-1)..64n-1]) //同上 Si[2n] block[0..31] //下位32ビット Si[2n+1] block[32..63] //上位32ビット return state
ユーザー入力多くのbcrypt実装はパスワードを最初の72バイトだけ切り出して利用する実装になっている。 算術アルゴリズムが18個の32ビットサブキー（72オクテット/バイトと同じ）に初期化することを要求しているからである。bcryptのオリジナル仕様[1] はユーザーランドのテキストベースのパスワードをこのアルゴルズムの数値とどのようにマッピングするべきかを強制するものはなかった。テキストで書かれた短いコメントで文字列のASCIIエンコードされた文字をシンプルに利用する可能性があると書かれているが、強制するものではない: 「最後に、key引数は秘密暗号鍵であり、ユーザーが選んだ56バイトまでのパスワードである可能性がある（文字列がASCII文字列の場合はゼロのバイトの終端も含む）」 アルゴリズムは初期値として72バイトの入力を扱うが、上記に引用文が「56バイトまで」のパスワードに言及している点は注目に値する。ProvosもMazièresも制約を短くした理由については表明していないが、ブルース・シュナイアーによるBlowfishのオリジナルの仕様[17]を見て決定した可能性がある: 「鍵サイズの448ビット制限によりすべてのサブキーのすべてのビットは、鍵のすべてのビットに依存していることが保証される」 パスワードを初期の数値の値に変換する方法は実装によって異なる可能性があるため、非ASCII文字を含んだパスワードの強度が低下する可能性がある[18]。 関連項目
参考文献
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||
