Bcrypt

背景

Blowfishはブロック暗号の中では鍵のセットアップフェーズのコストが高いことで知られている。Blowfishは標準状態はいくつかのサブキーで開始される。その後、鍵の一部を使ってブロック暗号化を行い、この暗号化（正確にはハッシュ）の結果を使ってサブキーのいくつかを置換する。その後は変更された状態を使って鍵の残りの部分の暗号化を行い、その結果を使ってより多くのサブキーを置換する。この方法を繰り返し、段階的に状態を変更しつつ鍵のハッシュ化とビットの状態の置き換えを行い、最終的にすべてのサブキーを設定していく。
ProvosとMazièresはこの方法を取り入れ、さらに発展させた。彼らはBlowfishのための新しい鍵セットアップアルゴリズムを開発し、その成果物の暗号に"Eksblowfish" ("expensive key schedule Blowfish")という名前をつけた。このアルゴリズムでは標準のBlowfishの鍵セットアップから変更され、すべてのサブキーの設定において、ソルトとパスワードの両方を利用する。その後は、ソルトとパスワードを交互に鍵として使い、標準のBlowfishの鍵作成アルゴリズムを複数ラウンド数適用していく。ラウンドのたびに、以前の適用結果をサブキーの状態として計算を行う。理論的にはBlowfishの鍵スケジュールほど強くはないが、鍵作成のラウンド数が変更可能であるため、任意でこのプロセスの計算量を増やして遅くすることが可能であり、ハッシュやソルトに対するブルートフォース攻撃に対抗できる。

説明

ハッシュ文字列は"$2a$"や"$2b$" (あるいは "$2y$")という接頭辞を持つ。shadowパスワードは暗号フォーマットをモジュール化しているが、この接頭辞を見ることでハッシュ文字列がbcryptハッシュであることがわかる。ハッシュ文字列の残りの部分にはコストパラメータ、128ビットのソルト（Radix-64エンコードされて22文字になっている）、184ビットの結果のハッシュ値 （Radix-64エンコードされて31文字になっている）が含まれる 。Radix-64はunix/cryptアルファベットを利用するもので、標準のBase-64とは異なる。コストパラメータはキー拡張の反復回数を設定するもので、2のべき乗の数となっていて、暗号アルゴリズムの入力値となっている。
$2a$10$N9qo8uLOickgx2ZMRZoMyeIjZAgcfl7p92ldGxad68LJZdL17lhWy というshodowパスワードのレコードを例にとると、コストパラメータは10で、キー拡張のラウンド数は2¹⁰になる。ソルトはN9qo8uLOickgx2ZMRZoMyeであり、結果のハッシュは IjZAgcfl7p92ldGxad68LJZdL17lhWyとなっている。一般的なパスワード管理のプラクティス通り、ユーザーのパスワードそのものが格納されることはない。

アルゴリズム

bcryptのアルゴリズムは"OrpheanBeholderScryDoubt" というアルゴリズムをBlowfishを用いて64回暗号化した文字列を作成する。bcryptでは通常のBlowfishの鍵セットアップ関数をコストが高価な（expensive key setup）EksBlowfishSetup関数に置き換えている:
Function bcrypt
   Input:
      cost:     Number (4..31)                      log₂(Iterations)。例えば 12 ==> 2¹² = 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)                      log₂(Iterations)。例えば 12 ==> 2¹² = 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 (2ᶜᵒˢᵗ)
      state  ExpandKey(state, 0, password)
      state  ExpandKey(state, 0, salt)

    return state
InitialStateはオリジナルのBlowfishアルゴリズムと同じように動作する。P配列とS-boxに の16進数の少数点数部分を設定したものである。

Expand key

ExpandKey関数は次のような処理を行う:
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
      Pₙ  Pₙ xor password[32(n-1)..32n-1] //パスワードが循環しているように扱う

   //ソルトの下位8バイトを使いstateの暗号化を行い、8バイトの結果を P₁|P₂ に格納する
   block  Encrypt(state, salt[0..63])
   P₁  block[0..31]  //下位32ビット
   P₂  block[32..63] //上位32ビット

   //ソルトを用いて繰り返し状態の暗号化を行い、Pの配列の残りの部分に格納していく
   for n  2 to 9 do
      block  Encrypt(state, block xor salt[64(n-1)..64n-1]) //現在のkey scheduleと循環するソルトを用いて暗号化
      P₂ₙ₋₁  block[0..31] //下位32ビット
      P₂ₙ  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]) //同上
         Sᵢ[2n]    block[0..31]  //下位32ビット
         Sᵢ[2n+1]  block[32..63]  //上位32ビット
    return state
ExpandKey(state, 0, key) は通常のBlowfishのkey scheduleと同じため、すべてゼロのソルト値とのXORをとるのは意味がない。ExpandKey(state, 0, salt)も同様だが、ソルトを128ビットの鍵として扱っている。

ユーザー入力

多くのbcrypt実装はパスワードを最初の72バイトだけ切り出して利用する実装になっている。
算術アルゴリズムが18個の32ビットサブキー（72オクテット/バイトと同じ）に初期化することを要求しているからである。bcryptのオリジナル仕様 はユーザーランドのテキストベースのパスワードをこのアルゴルズムの数値とどのようにマッピングするべきかを強制するものはなかった。テキストで書かれた短いコメントで文字列のASCIIエンコードされた文字をシンプルに利用する可能性があると書かれているが、強制するものではない: 「最後に、key引数は秘密暗号鍵であり、ユーザーが選んだ56バイトまでのパスワードである可能性がある（文字列がASCII文字列の場合はゼロのバイトの終端も含む）」
アルゴリズムは初期値として72バイトの入力を扱うが、上記に引用文が「56バイトまで」のパスワードに言及している点は注目に値する。ProvosもMazièresも制約を短くした理由については表明していないが、Bruce SchneierによるBlowfishのオリジナルの仕様を見て決定した可能性がある: 「鍵サイズの448ビット制限によりすべてのサブキーのすべてのビットは、鍵のすべてのビットに依存していることが保証される」
パスワードを初期の数値の値に変換する方法は実装によって異なる可能性があるため、非ASCII文字を含んだパスワードの強度が低下する可能性がある。