Bcryptのソースを表示

{{for|bcryptファイル暗号化ユーティリティ|Blowfish}}
{{Technical|date=March 2017}}
{{lowercase|title=bcrypt}}
{{Infobox cryptographic hash function|name=bcrypt|image=|caption=<!-- General -->|designers=[[Niels Provos]], David Mazières|publish date=1999|series=|derived from=[[Blowfish]]|derived to=|related to=|certification=<!-- Detail -->|digest size=184 bit|block size=|structure=|rounds=コストパラメータで変更可能|cryptanalysis=}}
'''bcrypt'''（ビー・クリプト）は[[Niels Provos]]とDavid Mazièresによって設計された1999年に[[USENIX]]にて公開された、[[Blowfish]]暗号を基盤とした[[暗号学的ハッシュ関数#用途|パスワードハッシュ化関数]]である<ref name="provos">{{cite journal|last=Provos|first=Niels|year=1999|title=A Future-Adaptable Password Scheme|url=http://www.usenix.org/events/usenix99/provos/provos_html/node1.html|journal=Proceedings of 1999 USENIX Annual Technical Conference|pages=81–92|author2=Mazières, David|author3=Talan Jason Sutton 2012}}</ref>。[[レインボーテーブル]]攻撃に対抗するために[[ソルト (暗号)|ソルト]]を組み込んでいる以外に、bcryptは適応的な特性を備えている。計算能力が増えたとしても[[ブルートフォース攻撃]]に耐えられるように、繰り返し回数を増やして速度を落とせるようになっている。

bcryptは[[OpenBSD]]<ref name="original">{{cite web|url=//cvsweb.openbsd.org/cgi-bin/cvsweb/src/lib/libc/crypt/bcrypt.c|title=Commit of first work to repo|date=13 Feb 1997|accessdate=2021-01-29}}</ref>のデフォルトのパスワードハッシュアルゴリズムとして利用されているほか、[[SUSE Linux]]<ref>{{cite web|url=https://www.suse.com/support/security/advisories/2011_35_blowfish.html|title=SUSE Security Announcement: (SUSE-SA:2011:035)|date=23 August 2011|access-date=20 August 2015|quote=SUSE's crypt() implementation supports the blowfish password hashing function (id $2a) and system logins by default also use this method.|deadurl=yes|archiveurl=https://web.archive.org/web/20160304094921/https://www.suse.com/support/security/advisories/2011_35_blowfish.html|archivedate=4 March 2016|df=}}</ref>などの[[Linuxディストリビューション]]を含む他のシステムでも利用されている。

bcryptはC、C++、C#、Go<ref>{{cite web|url=https://godoc.org/golang.org/x/crypto/bcrypt|title=Package bcrypt|website=godoc.org|accessdate=2020-01-29}}</ref>、Java<ref>{{Cite web|url=http://www.mindrot.org/projects/jBCrypt/|title=jBCrypt - strong password hashing for Java|website=www.mindrot.org|language=en|access-date=2017-03-11}}</ref><ref>{{Cite web|url=https://github.com/patrickfav/bcrypt|title=bcrypt - A Java standalone implementation of the bcrypt password hash function|website=github.com|language=en|access-date=2018-07-19}}</ref>、JavaScript<ref>{{cite web|url=https://www.npmjs.com/package/bcrypt|title=bcrypt|website=npm|accessdate=2021-01-29}}</ref>、Elixir<ref>{{cite web|last1=Whitlock|first1=David|title=Bcrypt Elixir: Bcrypt password hashing algorithm for Elixir.|url=https://github.com/riverrun/bcrypt_elixir|website=GitHub|publisher=riverrun|accessdate=2021-01-29}}</ref>、Perl、PHP、Python<ref>{{cite web|url=https://github.com/pyca/bcrypt/|title=bcrypt: Modern password hashing for your software and your servers|first=Donald|last=Stufft|publisher=|via=PyPI|accessdate=2021-01-29}}</ref>、Ruby、その他の言語による実装がある。

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

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

== 説明 ==
bcryptによってハッシュ化された文字列は"$2a$"や"$2b$" (あるいは "$2y$")という接頭辞を持つ。この接頭辞はハッシュ化する際に用いたアルゴリズムによって異なり、前述の接頭辞の場合は[[Passwd|shadowパスワード]]ファイルがModular Crypt Formatと呼ばれる形式で記述されており、bcryptハッシュであることを示す<ref name="passlib_MCF" />。ハッシュ文字列の残りの部分にはコストパラメータ、128ビットのソルト（[[Base64#Radix-64 applications not compatible with Base64|Radix-64]]エンコードされて22文字になっている）、184ビットの結果のハッシュ値 （[[Base64#Radix-64 applications not compatible with Base64|Radix-64]]エンコードされて31文字になっている）が含まれる<ref>passlib.
[https://passlib.readthedocs.io/en/stable/lib/passlib.hash.bcrypt.html "BCrypt"]</ref>{{要出典|date=2021年1月|title=各要素のビット数及びRadix-64でエンコードされている点については出典に言及がない？文字数については言及あり}}.
。Radix-64はunix/cryptアルファベットを利用するもので、標準の[[Base64|Base-64]]とは異なる<ref>{{Cite web|url=https://github.com/pyca/bcrypt/blob/master/src/_csrc/bcrypt.c#L179|title=Python bcrypt - Modern password hashing for your software and your servers|last=|first=|date=|website=|archive-url=|archive-date=|dead-url=|access-date=2020-01-29}}</ref><ref>{{Cite web|url=https://github.com/bcgit/bc-java/blob/master/core/src/main/java/org/bouncycastle/crypto/generators/OpenBSDBCrypt.java#L19|title=Bouncy Castle Java Distribution - BCrypt implememntation|last=|first=|date=|website=|archive-url=|archive-date=|dead-url=|access-date=2021-01-29}}</ref>。コストパラメータはキー拡張の反復回数を設定するもので、2のべき乗の数となっていて、暗号アルゴリズムの入力値となっている。

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

== バージョン履歴 ==

'''$2$ (1999年) '''

オリジナルの仕様では接頭辞が <code>$2$</code>であると定義されていた。これはOpenBSDのpasswordファイルにパスワードを格納するために使われる'''Modular Crypt Format'''<ref name="passlib_MCF">{{cite web|url=https://passlib.readthedocs.io/en/stable/modular_crypt_format.html|title=Modular Crypt Format — Passlib v1.7.1 Documentation|website=passlib.readthedocs.io|accessdate=2021-01-29|publisher=Assurance Technologies, LLC.}}</ref>フォーマットにしたがっている:

* <code>$1$</code>: MD5ベースの暗号('md5crypt')
* <code>$2$</code>: Blowfishベースの暗号 ('bcrypt')
* <code>$sha1$</code>: SHA-1ベースの暗号 ('sha1crypt')
* <code>$5$</code>: SHA-256ベースの暗号 ('sha256crypt')
* <code>$6$</code>: SHA-512ベースの暗号 ('sha512crypt')

'''$2a$ '''

オリジナルの仕様ではASCII以外の文字やnull終端をどのように扱うべきかの定義がなかった。このバージョンの仕様では文字列のハッシュ化について定義され改訂された:

* 文字列はUTF-8エンコードされる
* null終端がふくまれなければならない

これらの変更により、バージョンが<code>$2a$</code><ref name="undeadly.org">{{Cite web|url=http://undeadly.org/cgi?action=article&sid=20140224132743|title=bcrypt password hash bugs fixed, version changes and consequences|accessdate=2021-01-29|publisher=|website=OpenBSD Journal|language=english}}</ref>に変更された。

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

2011年6月に、BCryptのPHP実装である'''crypt_blowfish'''の中でバグが発見された。8ビット文字列の扱いを間違っていたのが原因であった<ref>{{cite web|url=http://seclists.org/oss-sec/2011/q2/632|title=oss-sec: CVE request: crypt_blowfish 8-bit character mishandling|first=Solar|last=Designer|website=seclists.org|accessdate=2021-01-29}}</ref>。システムの管理者は既存のパスワードデータベースを開き、<code>$2a$</code>を<code>$2x$</code>に更新することで、既存の間違ったハッシュアルゴリズムを明示的に使い続けていることを示すことを提案した。それ以外にも、修正されたアルゴリズムで生成されたハッシュ値で示すために、'''crypt_blowfish'''が接頭辞として<code>$2y$</code> を出力するアイディアを提案した。

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

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

バグがOpenBSDのbcrypt実装で発見された。これは8ビットのバイトである'''unsigned char'''に長さを格納をしていたのが原因である<ref name="undeadly.org" />。パスワード長として255文字を越えると、オーバーフローして長さが255に丸められてしまった<ref>{{cite web|url=http://marc.info/?l=openbsd-misc&m=139320023202696|title='bcrypt version changes' - MARC|website=marc.info|accessdate=2021-01-29}}</ref>。

BCryptはOpenBSDのために作られた。OpenBSDのライブラリでバグが発見された時はバージョン番号が更新されることが決定される。

== アルゴリズム ==

bcryptのアルゴリズムは''"OrpheanBeholderScryDoubt"'' というアルゴリズムを[[Blowfish]]を用いて64回暗号化した文字列を作成する。bcryptでは通常のBlowfishの鍵セットアップ関数をコストが高価な（expensive key setup）EksBlowfishSetup関数に置き換えている:

 <span style="color: #004DBB;">'''Function'''</span> bcrypt
    <span style="color: #004DBB;">'''Input:'''</span>
       cost:     Number (4..31)                      <span style="color: green;">log<sub>2</sub>(Iterations)。例えば 12 <nowiki>==</nowiki>> 2<sup>12</sup> = 4,096回繰り返す</span>
       salt:     array of Bytes (16 bytes)           <span style="color: green;">ランダムソルト</span>
       password: array of Bytes (1..72 bytes)        <span style="color: green;">UTF-8エンコードされたパスワード</span>
    <span style="color: #004DBB;">'''Output:'''</span> 
       hash:     array of Bytes (24 bytes)
 
    <span style="color: green;">//key setup algorithmを使って、Blowfishの状態を初期化</span> 
    ''state'' <math>\gets</math> EksBlowfishSetup(''cost'', ''salt'', ''password'')   
 
    <span style="color: green;">//"OrpheanBeholderScryDoubt"という文字列を64回繰り返し暗号化</span>
    ''ctext'' <math>\gets</math> <span style="color: maroon">''"OrpheanBeholderScryDoubt"''</span>  <span style="color: green;">//24バイト <nowiki>==</nowiki>> 3つの64ビットブロック</span>
    <span style="color: #004DBB;">'''repeat'''</span> (64)
       ''ctext'' <math>\gets</math> EncryptECB(''state'', ''ctext'') <span style="color: green;">//通常のBlowfishのECBモードを使って暗号化</span>
 
    <span style="color: green;">//24-byteの''ctext''が結果のパスワードのハッシュ</span>
    <span style="color: #004DBB;">'''return'''</span> Concatenate(''cost'', ''salt'', ''ctext'')

=== Expensive key setup ===

アルゴリズムは、次のロジックを持つ鍵セットアップアルゴリズムの"Eksblowfish"に強く依存している:

 <span style="color: #004DBB;">'''Function'''</span> EksBlowfishSetup
    <span style="color: #004DBB;">'''Input:'''</span>
       cost:     Number (4..31)                      <span style="color: green;">log<sub>2</sub>(Iterations)。例えば 12 <nowiki>==</nowiki>> 2<sup>12</sup> = 4,096回繰り返す</span>
       salt:     array of Bytes (16 bytes)           <span style="color: green;">ランダムソルト</span>
       password: array of Bytes (1..72 bytes)        <span style="color: green;">UTF-8エンコードされたパスワード</span>
    <span style="color: #004DBB;">'''Output:'''</span> 
       state:    opaque BlowFish state structure
  
    ''state'' <math>\gets</math> InitialState()
    ''state'' <math>\gets</math> ExpandKey(''state'', ''salt'', ''password'')
    <span style="color: #004DBB;">'''repeat'''</span> (2<sup>''cost''</sup>)
       ''state'' <math>\gets</math> ExpandKey(state, 0, password)
       ''state'' <math>\gets</math> ExpandKey(state, 0, salt)
 
     <span style="color: #004DBB;">'''return'''</span> ''state''

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

=== Expand key ===
ExpandKey関数は次のような処理を行う:

 <span style="color: #004DBB;">'''Function'''</span> ExpandKey(''state'', ''salt'', ''password'')
    <span style="color: #004DBB;">'''Input:'''</span>
       state:    Opaque BlowFish state structure     <span style="color: green;">P配列 と S-box のエントリーを含む</span>
       salt:     array of Bytes (16 bytes)           <span style="color: green;">ランダムソルト</span>
       password: array of Bytes (1..72 bytes)        <span style="color: green;">UTF-8エンコードされたパスワード</span>
    <span style="color: #004DBB;">'''Output:'''</span> 
       state:    opaque BlowFish state structure
  
    <span style="color: green;">//パスワードを状態の内部にあるP-arrayに混ぜていく</span>
    <span style="color: #004DBB;">'''for'''</span> ''n'' <math>\gets</math> 1 <span style="color: #004DBB;">'''to'''</span> 18 <span style="color: #004DBB;">'''do'''</span>
       P<sub>n</sub> <math>\gets</math> P<sub>n</sub> <span style="color: #004DBB;">xor</span> ''password''[32(n-1)..32n-1] <span style="color: green;">//パスワードが循環しているように扱う</span>
 
    <span style="color: green;">//ソルトの下位8バイトを使いstateの暗号化を行い、8バイトの結果を P<sub>1</sub>|P<sub>2</sub> に格納する</span>
    ''block'' <math>\gets</math> Encrypt(''state'', ''salt''[0..63])
    P<sub>1</sub> <math>\gets</math> ''block''[0..31]  <span style="color: green;">//下位32ビット</span>
    P<sub>2</sub> <math>\gets</math> ''block''[32..63] <span style="color: green;">//上位32ビット</span>
 
    <span style="color: green;">//ソルトを用いて繰り返し状態の暗号化を行い、Pの配列の残りの部分に格納していく</span>
    <span style="color: #004DBB;">'''for'''</span> ''n'' <math>\gets</math> 2 <span style="color: #004DBB;">'''to'''</span> 9 <span style="color: #004DBB;">'''do'''</span>
       ''block'' <math>\gets</math> Encrypt(''state'', ''block'' <span style="color: #004DBB;">'''xor'''</span> ''salt''[64(n-1)..64n-1]) <span style="color: green;">//現在のkey scheduleと循環するソルトを用いて暗号化</span>
       P<sub>2n-1</sub> <math>\gets</math> ''block''[0..31] <span style="color: green;">//下位32ビット</span>
       P<sub>2n</sub> <math>\gets</math> ''block''[32..63]  <span style="color: green;">//上位32ビット</span>
 
    <span style="color: green;">//暗号化された状態を、状態内部のS-boxに混ぜていく</span>
    <span style="color: #004DBB;">'''for'''</span> ''i'' <math>\gets</math> 1 <span style="color: #004DBB;">'''to'''</span> 4 <span style="color: #004DBB;">'''do'''</span>
       <span style="color: #004DBB;">'''for'''</span> ''n'' <math>\gets</math> 0 <span style="color: #004DBB;">'''to'''</span> 127 <span style="color: #004DBB;">'''do'''</span>
          ''block'' <math>\gets</math> Encrypt(''state'', ''block'' <span style="color: #004DBB;">'''xor'''</span> ''salt''[64(n-1)..64n-1]) <span style="color: green;">//同上</span>
          S<sub>i</sub>[2n]   <math>\gets</math> ''block''[0..31]  <span style="color: green;">//下位32ビット</span>
          S<sub>i</sub>[2n+1] <math>\gets</math> ''block''[32..63]  <span style="color: green;">//上位32ビット</span>
     <span style="color: #004DBB;">'''return'''</span> ''state''

<code>ExpandKey(''state'', 0, ''key'')</code> は通常のBlowfishのkey scheduleと同じため、すべてゼロのソルト値とのXORをとるのは意味がない。<code>ExpandKey(''state'', 0, ''salt'')</code>も同様だが、ソルトを128ビットの鍵として扱っている。

== ユーザー入力 ==
多くのbcrypt実装はパスワードを最初の72バイトだけ切り出して利用する実装になっている。

算術アルゴリズムが18個の32ビットサブキー（72オクテット/バイトと同じ）に初期化することを要求しているからである。bcryptのオリジナル仕様<ref name="provos" /> は[[ユーザーランド]]のテキストベースのパスワードをこのアルゴルズムの数値とどのようにマッピングするべきかを強制するものはなかった。テキストで書かれた短いコメントで文字列のASCIIエンコードされた文字をシンプルに利用する可能性があると書かれているが、強制するものではない: 「最後に、key引数は秘密暗号鍵であり、ユーザーが選んだ56バイトまでのパスワードである可能性がある（文字列がASCII文字列の場合はゼロのバイトの終端も含む）」

アルゴリズムは初期値として72バイトの入力を扱うが、上記に引用文が「56バイトまで」のパスワードに言及している点は注目に値する。ProvosもMazièresも制約を短くした理由については表明していないが、[[ブルース・シュナイアー]]によるBlowfishのオリジナルの仕様<ref>{{cite journal|last=Schneier|first=Bruce|year=1994|title=Fast Software Encryption, Description of a New Variable-Length Key, 64-Bit Block Cipher (Blowfish)|url=https://www.schneier.com/paper-blowfish-fse.html|journal=Cambridge Security Workshop Proceedings (December 1993)|pages=191–204|publisher=Springer-Verlag}}</ref>を見て決定した可能性がある: 「鍵サイズの448ビット制限によりすべてのサブキーのすべてのビットは、鍵のすべてのビットに依存していることが保証される」

パスワードを初期の数値の値に変換する方法は実装によって異なる可能性があるため、非ASCII文字を含んだパスワードの強度が低下する可能性がある<ref>{{cite web|url=http://www.mindrot.org/files/jBCrypt/internat.adv|date=1 February 2010|title=jBCrypt security advisory|accessdate=2019-08-14}} And {{cite web|url=https://www.php.net/security/crypt_blowfish.php|title=Changes in CRYPT_BLOWFISH in PHP 5.3.7|work=php.net|accessdate=2019-08-14}}</ref>。

== 関連項目 ==
* bcrypt is also the name of a cross-platform file encryption utility implementing Blowfish developed in 2002.<ref>http://bcrypt.sourceforge.net bcrypt file encryption program homepage</ref><ref>http://bcrypt463065.android.informer.com/</ref><ref>http://www.t2-project.org/packages/bcrypt.html</ref><ref>https://docs.oracle.com/cd/E51849_01/gg-winux/OGGLC/ogglc_licenses.htm</ref>
* [[Argon2]] (The algorithm selected by the [[Password Hashing Competition]] in 2015)
* [[Crypt (C)#Blowfish-based scheme]] crypt{{snd}} password storage and verification scheme{{snd}} Blowfish
* [[Key stretching]]
* [[PBKDF2]] (Password-Based Key Derivation Function 2)
* [[scrypt]]

== 参考文献 ==
{{Reflist|30em}}

<!--==External links==-->
<!-- do not add "bcrypt implementation for language foo" links. See WP:EL if in doubt. -->

{{Cryptography navbox|hash}}

[[Category:暗号学的ハッシュ関数]]
[[Category:暗号ソフトウェア]]
[[Category:鍵導出関数]]