Bcrypt

**bcrypt**（ビー・クリプト）はNiels ProvosとDavid Mazièresによって設計された1999年にUSENIXにて公開された、Blowfish暗号を基盤としたパスワードハッシュ化関数である。レインボーテーブル攻撃に対抗するためにソルトを組み込んでいる以外に、bcryptは適応的な特性を備えている。計算能力が増えたとしてもブルートフォース攻撃に耐えられるように、繰り返し回数を増やして速度を落とせるようになっている。

bcryptはOpenBSDのデフォルトのパスワードハッシュアルゴリズムとして利用されているほか、SUSE LinuxなどのLinuxディストリビューションを含む他のシステムでも利用されている。

bcryptはC、C++、C#、Go、Java、JavaScript、Elixir、Perl、PHP、Python、Ruby、その他の言語による実装がある。

## 背景
Blowfishはブロック暗号の中では鍵のセットアップフェーズのコストが高いことで知られている。Blowfishは標準状態はいくつかのサブキーで開始される。その後、鍵の一部を使ってブロック暗号化を行い、この暗号化（正確にはハッシュ）の結果を使ってサブキーのいくつかを置換する。その後は変更された状態を使って鍵の残りの部分の暗号化を行い、その結果を使ってより多くのサブキーを置換する。この方法を繰り返し、段階的に状態を変更しつつ鍵のハッシュ化とビットの状態の置き換えを行い、最終的にすべてのサブキーを設定していく。

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

## 説明
bcryptによってハッシュ化された文字列は"$2a$"や"$2b$" (あるいは "$2y$")という接頭辞を持つ。この接頭辞はハッシュ化する際に用いたアルゴリズムによって異なり、前述の接頭辞の場合はshadowパスワードファイルがModular Crypt Formatと呼ばれる形式で記述されており、bcryptハッシュであることを示す。ハッシュ文字列の残りの部分にはコストパラメータ、128ビットのソルト（Radix-64エンコードされて22文字になっている）、184ビットの結果のハッシュ値 （Radix-64エンコードされて31文字になっている）が含まれる.
。Radix-64はunix/cryptアルファベットを利用するもので、標準のBase-64とは異なる。コストパラメータはキー拡張の反復回数を設定するもので、2のべき乗の数となっていて、暗号アルゴリズムの入力値となっている。

`$2a$10$N9qo8uLOickgx2ZMRZoMyeIjZAgcfl7p92ldGxad68LJZdL17lhWy` というshodowパスワードのレコードを例にとると、コストパラメータは10で、キー拡張のラウンド数は210になる。ソルトは`N9qo8uLOickgx2ZMRZoMye`であり、結果のハッシュは `IjZAgcfl7p92ldGxad68LJZdL17lhWy`となっている。一般的なパスワード管理のプラクティス通り、ユーザーのパスワードそのものが格納されることはない。

## バージョン履歴

**$2$ (1999年) **

オリジナルの仕様では接頭辞が `$2$`であると定義されていた。これはOpenBSDのpasswordファイルにパスワードを格納するために使われる**Modular Crypt Format**フォーマットにしたがっている:

* `$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$`に変更された。

**$2x$, $2y$ (2011年6月) **

2011年6月に、BCryptのPHP実装である**crypt_blowfish**の中でバグが発見された。8ビット文字列の扱いを間違っていたのが原因であった。システムの管理者は既存のパスワードデータベースを開き、`$2a$`を`$2x$`に更新することで、既存の間違ったハッシュアルゴリズムを明示的に使い続けていることを示すことを提案した。それ以外にも、修正されたアルゴリズムで生成されたハッシュ値で示すために、**crypt_blowfish**が接頭辞として`$2y$` を出力するアイディアを提案した。

標準的なOpenBSDを含むどのディストリビューションも2x/2yのアイディアを採用しなかった。このバージョンマーカーの変更は**crypt_blowfish**.に限定された。

**$2b$ (2014年2月) **

バグがOpenBSDのbcrypt実装で発見された。これは8ビットのバイトである**unsigned char**に長さを格納をしていたのが原因である。パスワード長として255文字を越えると、オーバーフローして長さが255に丸められてしまった。

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* \gets EksBlowfishSetup(*cost*, *salt*, *password*)   
 
    //"OrpheanBeholderScryDoubt"という文字列を64回繰り返し暗号化
    *ctext* \gets *"OrpheanBeholderScryDoubt"*  //24バイト > 3つの64ビットブロック
    **repeat** (64)
       *ctext* \gets 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* \gets InitialState()
    *state* \gets ExpandKey(*state*, *salt*, *password*)
    **repeat** (2*cost*)
       *state* \gets ExpandKey(state, 0, password)
       *state* \gets ExpandKey(state, 0, salt)
 
     **return** *state*

InitialStateはオリジナルのBlowfishアルゴリズムと同じように動作する。P配列とS-boxに \piの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* \gets 1 **to** 18 **do**
       Pn \gets Pn xor *password*[32(n-1)..32n-1] //パスワードが循環しているように扱う
 
    //ソルトの下位8バイトを使いstateの暗号化を行い、8バイトの結果を P1|P2 に格納する
    *block* \gets Encrypt(*state*, *salt*[0..63])
    P1 \gets *block*[0..31]  //下位32ビット
    P2 \gets *block*[32..63] //上位32ビット
 
    //ソルトを用いて繰り返し状態の暗号化を行い、Pの配列の残りの部分に格納していく
    **for** *n* \gets 2 **to** 9 **do**
       *block* \gets Encrypt(*state*, *block* **xor** *salt*[64(n-1)..64n-1]) //現在のkey scheduleと循環するソルトを用いて暗号化
       P2n-1 \gets *block*[0..31] //下位32ビット
       P2n \gets *block*[32..63]  //上位32ビット
 
    //暗号化された状態を、状態内部のS-boxに混ぜていく
    **for** *i* \gets 1 **to** 4 **do**
       **for** *n* \gets 0 **to** 127 **do**
          *block* \gets Encrypt(*state*, *block* **xor** *salt*[64(n-1)..64n-1]) //同上
          Si[2n]   \gets *block*[0..31]  //下位32ビット
          Si[2n+1] \gets *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も制約を短くした理由については表明していないが、ブルース・シュナイアーによるBlowfishのオリジナルの仕様を見て決定した可能性がある: 「鍵サイズの448ビット制限によりすべてのサブキーのすべてのビットは、鍵のすべてのビットに依存していることが保証される」

パスワードを初期の数値の値に変換する方法は実装によって異なる可能性があるため、非ASCII文字を含んだパスワードの強度が低下する可能性がある。

## 関連項目
* bcrypt is also the name of a cross-platform file encryption utility implementing Blowfish developed in 2002.
* Argon2 (The algorithm selected by the Password Hashing Competition in 2015)
* Crypt (C)#Blowfish-based scheme crypt password storage and verification scheme Blowfish
* Key stretching
* PBKDF2 (Password-Based Key Derivation Function 2)
* scrypt

## 参考文献