bcrypt

bcrypt
一般
設計者	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で、キー拡張のラウンド数は2¹⁰になる。ソルトは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)                      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  $\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)                      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  $\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
      P_n  $\gets$  P_n xor password[32(n-1)..32n-1] //パスワードが循環しているように扱う

   //ソルトの下位8バイトを使いstateの暗号化を行い、8バイトの結果を P₁|P₂ に格納する
   block  $\gets$  Encrypt(state, salt[0..63])
   P₁  $\gets$  block[0..31]  //下位32ビット
   P₂  $\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と循環するソルトを用いて暗号化
      P_2n-1  $\gets$  block[0..31] //下位32ビット
      P_2n  $\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]) //同上
         S_i[2n]    $\gets$  block[0..31]  //下位32ビット
         S_i[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のオリジナル仕様^[1] はユーザーランドのテキストベースのパスワードをこのアルゴルズムの数値とどのようにマッピングするべきかを強制するものはなかった。テキストで書かれた短いコメントで文字列のASCIIエンコードされた文字をシンプルに利用する可能性があると書かれているが、強制するものではない: 「最後に、key引数は秘密暗号鍵であり、ユーザーが選んだ56バイトまでのパスワードである可能性がある（文字列がASCII文字列の場合はゼロのバイトの終端も含む）」

アルゴリズムは初期値として72バイトの入力を扱うが、上記に引用文が「56バイトまで」のパスワードに言及している点は注目に値する。ProvosもMazièresも制約を短くした理由については表明していないが、Bruce SchneierによるBlowfishのオリジナルの仕様^[17]を見て決定した可能性がある: 「鍵サイズの448ビット制限によりすべてのサブキーのすべてのビットは、鍵のすべてのビットに依存していることが保証される」

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

参考文献[編集]

^ ^a ^b Provos, Niels; Mazières, David; Talan Jason Sutton 2012 (1999). “A Future-Adaptable Password Scheme”. Proceedings of 1999 USENIX Annual Technical Conference: 81–92.
^ “Commit of first work to repo” (1997年2月13日). 2021年1月29日閲覧。
^ “SUSE Security Announcement: (SUSE-SA:2011:035)” (2011年8月23日). 2016年3月4日時点のオリジナルよりアーカイブ。2015年8月20日閲覧。 “SUSE's crypt() implementation supports the blowfish password hashing function (id $2a) and system logins by default also use this method.”
^ “Package bcrypt”. godoc.org. 2020年1月29日閲覧。
^ “jBCrypt - strong password hashing for Java” (英語). www.mindrot.org. 2017年3月11日閲覧。
^ “bcrypt - A Java standalone implementation of the bcrypt password hash function” (英語). github.com. 2018年7月19日閲覧。
^ “bcrypt”. npm. 2021年1月29日閲覧。
^ “Bcrypt Elixir: Bcrypt password hashing algorithm for Elixir.”. GitHub. riverrun. 2021年1月29日閲覧。
^ Stufft, Donald. “bcrypt: Modern password hashing for your software and your servers”. 2021年1月29日閲覧。
^ ^a ^b “Modular Crypt Format — Passlib v1.7.1 Documentation”. passlib.readthedocs.io. Assurance Technologies, LLC.. 2021年1月29日閲覧。
^ passlib. "BCrypt"
^ “Python bcrypt - Modern password hashing for your software and your servers”. 2020年1月29日閲覧。
^ “Bouncy Castle Java Distribution - BCrypt implememntation”. 2021年1月29日閲覧。
^ ^a ^b “bcrypt password hash bugs fixed, version changes and consequences” (english). OpenBSD Journal. 2021年1月29日閲覧。
^ Designer, Solar. “oss-sec: CVE request: crypt_blowfish 8-bit character mishandling”. seclists.org. 2021年1月29日閲覧。
^ “'bcrypt version changes' - MARC”. marc.info. 2021年1月29日閲覧。
^ Schneier, Bruce (1994). “Fast Software Encryption, Description of a New Variable-Length Key, 64-Bit Block Cipher (Blowfish)”. Cambridge Security Workshop Proceedings (December 1993) (Springer-Verlag): 191–204.
^ “jBCrypt security advisory” (2010年2月1日). 2019年8月14日閲覧。 And “Changes in CRYPT_BLOWFISH in PHP 5.3.7”. php.net. 2019年8月14日閲覧。
^ http://bcrypt.sourceforge.net bcrypt file encryption program homepage
^ http://bcrypt463065.android.informer.com/
^ http://www.t2-project.org/packages/bcrypt.html
^ https://docs.oracle.com/cd/E51849_01/gg-winux/OGGLC/ogglc_licenses.htm

[provos-1] Provos, Niels; Mazières, David; Talan Jason Sutton 2012 (1999). “A Future-Adaptable Password Scheme”. Proceedings of 1999 USENIX Annual Technical Conference: 81–92.

[original-2] “Commit of first work to repo” (1997年2月13日). 2021年1月29日閲覧。

[3] “SUSE Security Announcement: (SUSE-SA:2011:035)” (2011年8月23日). 2016年3月4日時点のオリジナルよりアーカイブ。2015年8月20日閲覧。 “SUSE's crypt() implementation supports the blowfish password hashing function (id $2a) and system logins by default also use this method.”

[4] “Package bcrypt”. godoc.org. 2020年1月29日閲覧。

[5] “jBCrypt - strong password hashing for Java” (英語). www.mindrot.org. 2017年3月11日閲覧。

[6] “bcrypt - A Java standalone implementation of the bcrypt password hash function” (英語). github.com. 2018年7月19日閲覧。

[7] “bcrypt”. npm. 2021年1月29日閲覧。

[8] “Bcrypt Elixir: Bcrypt password hashing algorithm for Elixir.”. GitHub. riverrun. 2021年1月29日閲覧。

[9] Stufft, Donald. “bcrypt: Modern password hashing for your software and your servers”. 2021年1月29日閲覧。

[passlib_MCF-10] “Modular Crypt Format — Passlib v1.7.1 Documentation”. passlib.readthedocs.io. Assurance Technologies, LLC.. 2021年1月29日閲覧。

[11] sslib. "BCrypt"

[12] “Python bcrypt - Modern password hashing for your software and your servers”. 2020年1月29日閲覧。

[13] “Bouncy Castle Java Distribution - BCrypt implememntation”. 2021年1月29日閲覧。

[undeadly.org-14] “bcrypt password hash bugs fixed, version changes and consequences” (english). OpenBSD Journal. 2021年1月29日閲覧。

[15] Designer, Solar. “oss-sec: CVE request: crypt_blowfish 8-bit character mishandling”. seclists.org. 2021年1月29日閲覧。

[16] “'bcrypt version changes' - MARC”. marc.info. 2021年1月29日閲覧。

[17] Schneier, Bruce (1994). “Fast Software Encryption, Description of a New Variable-Length Key, 64-Bit Block Cipher (Blowfish)”. Cambridge Security Workshop Proceedings (December 1993) (Springer-Verlag): 191–204.

[18] “jBCrypt security advisory” (2010年2月1日). 2019年8月14日閲覧。 And “Changes in CRYPT_BLOWFISH in PHP 5.3.7”. php.net. 2019年8月14日閲覧。

[19] ttp://bcrypt.sourceforge.net bcrypt file encryption program homepage

[20] ttp://bcrypt463065.android.informer.com/

[21] ttp://www.t2-project.org/packages/bcrypt.html

[22] ttps://docs.oracle.com/cd/E51849_01/gg-winux/OGGLC/ogglc_licenses.htm

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]