bcrypt

bcrypt は、 Niels Provosと David Mazièresによって設計されたパスワードハッシュ関数です。Blowfish暗号に基づいており、1999 年にUSENIXで発表されました。 ^{[ 1 ]}レインボーテーブル攻撃から保護するためのソルトを組み込むことに加えて、bcrypt は適応関数です。時間の経過とともに反復回数を増やして処理を遅くすることができるため、計算能力が向上しても総当たり検索攻撃に対する耐性を維持します。

bcrypt関数はOpenBSDのデフォルトのパスワードハッシュアルゴリズムであり^{[ 2 ]}、SUSE Linuxなどの一部のLinuxディストリビューションのデフォルトでもありました^{[ 3 ]}。

bcrypt の実装は、C、C++、C#、Embarcadero Delphi、Elixir、^{[ 4 ]} Go、^{[ 5 ]} Java、^{[ 6 ] [ 7 ]} JavaScript、^{[ 8 ]} Perl、PHP、Ruby、Python、Rust、^{[ 9 ]} V (Vlang)、^{[ 10 ]} Zig ^{[ 11 ]}およびその他の言語で存在します。

Blowfishは、ブロック暗号の中でも特に鍵設定フェーズのコストが高いことで知られています。まず、サブキーを標準状態に設定し、その状態を用いて鍵の一部でブロック暗号化を実行します。そして、その暗号化結果（ハッシュ化の精度が高い）を用いて一部のサブキーを置き換えます。次に、この変更された状態を用いて鍵の別の部分を暗号化し、その結果を用いてさらに多くのサブキーを置き換えます。このように、段階的に変更された状態を用いて鍵をハッシュ化し、状態の一部を置き換えていく処理を、すべてのサブキーが設定されるまで繰り返します。

プロヴォスとマジェールはこの点を活用し、さらに発展させた。彼らはBlowfish用の新しい鍵設定アルゴリズムを開発し、その結果生まれた暗号を「Eksblowfish」（「高価な鍵スケジュールBlowfish」）と名付けた。鍵設定は、標準のBlowfish鍵設定を修正した形式から始まり、すべてのサブキーを設定するためにソルトとパスワードの両方が使用される。その後、標準のBlowfish鍵生成アルゴリズムが複数回適用され、鍵としてソルトとパスワードが交互に使用され、各ラウンドは前のラウンドのサブキーの状態から始まる。理論的には、これは標準のBlowfish鍵スケジュールよりも強力ではないが、鍵生成ラウンドの数は設定可能である。そのため、このプロセスを任意に遅くすることができ、ハッシュやソルトに対する総当たり攻撃を防ぐのに役立つ。

bcrypt関数への入力は、パスワード文字列（最大72バイト）、数値コスト、および16バイト（128ビット）のソルト値です。ソルトは通常、ランダムな値です。bcrypt関数はこれらの入力を使用して24バイト（192ビット）のハッシュ値を計算します。bcrypt関数の最終出力は、次の形式の文字列です。

$2 < a/b/x/y > $[cost]$[22文字のソルト][31文字のハッシュ]

例えば、入力パスワードabc123xyz、コスト12、ランダムなソルトを使用した場合、bcrypt の出力は次の文字列になります。

$2a$12$R9h/cIPz0gi.URNNX3kh2OPST9/PgBkqquzi.Ss7KIUgO2t0jWMUW \__/\/ \____________________/\_____________________________/ アルゴリズムコストソルトハッシュ

どこ：

• $2a$ハッシュアルゴリズム識別子（bcrypt）
• 12入力コスト（2 ¹²、つまり4096ラウンド）
• R9h/cIPz0gi.URNNX3kh2O入力された塩のBase64エンコード
• PST9/PgBkqquzi.Ss7KIUgO2t0jWMUW計算された24バイトのハッシュの最初の23バイトをBase64エンコードしたもの

bcrypt の base-64 エンコーディングは、./ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789RFC 4648 Base64エンコーディングとは異なるテーブル^{[ 12 ]を使用します。} 

2ドル（1999年）

元のbcrypt仕様では、プレフィックスが定義されていました$2$。これは、OpenBSDのパスワードファイルにパスワードを保存する際に使用されるモジュラー暗号フォーマット^{[ 13 ]の形式に準拠しています。}

• $1$: MD5ベースの暗号化（'md5crypt'）
• $2$: Blowfishベースの暗号化ライブラリ（'bcrypt'）
• $sha1$: SHA-1ベースの暗号化アルゴリズム（'sha1crypt'）
• $5$: SHA-256ベースの暗号化（'sha256crypt'）
• $6$: SHA-512ベースの暗号化（'sha512crypt'）

$2a$

元の仕様では、非ASCII文字の処理方法やヌル終端文字の処理方法が定義されていませんでした。仕様は、文字列をハッシュ化する際に、以下の点を規定するように改訂されました。

• 文字列はUTF-8でエンコードされている必要があります。
• ヌル終端文字を含める必要があります

この変更により、バージョンは に変更されました$2a$。^{[ 14 ]}

2x年、2y年（2011年6月）

2011 年 6 月、bcrypt の PHP 実装であるcrypt_blowfishにバグが発見されました。8 ビット目がセットされた文字の処理が間違っていました。^{[ 15 ]}システム管理者は、既存のパスワード データベースを更新し、$2a$を に置き換えることで、これらのハッシュが不正であることを示す (古い壊れたアルゴリズムを使用する必要がある) ことを提案しました。また、修正されたアルゴリズムによって生成されたハッシュに対してcrypt_blowfish がを出力する$2x$というアイデアも提案しました。$2y$

CanonicalやOpenBSDを含め、2x/2yという考え方を採用した組織は他にありませんでした。このバージョンマーカーの変更はcrypt_blowfishに限られていました。

20億ドル（2014年2月時点）

OpenBSD の bcrypt 実装にバグが発見されました。パスワードの長さを保持するために、符号なし 8 ビット値を使用していました。^{[ 14 ] [ 16 ] [ 17 ]} 255 バイトより長いパスワードの場合、72 バイトで切り捨てられる代わりに、72 または長さを256で割った余りのうち小さい方で切り捨てられていました。たとえば、260 バイトのパスワードは、72 バイトで切り捨てられるのではなく、4 バイトで切り捨てられていました。OpenBSD がこの問題を修正したとき、バージョンを に変更しました$2b$。

以下の bcrypt 関数は、テキスト「OrpheanBeholderScryDoubt」をBlowfishを使用して 64 回暗号化します。bcrypt では、通常の Blowfish キー設定関数が、コストのかかるキー設定 (EksBlowfishSetup) 関数に置き換えられています。

関数bcrypt 入力: cost: 数値 (4..31)  log 2 (反復回数)。例: 12 ==> 2 12 = 4,096 回反復 salt: バイト配列 (16 バイト) ランダムなソルト password: バイト配列 (1..72 バイト)  UTF-8 エンコードされたパスワード出力: ハッシュ：バイト配列（24バイト） //高価なキー設定アルゴリズムを使用して Blowfish の状態を初期化します//P: 18 個のサブキーの配列 (UInt32[18]) //S: 4 つの置換ボックス (S ボックス)、S 0 ...S 3。各 S ボックスは 1,024 バイト (UInt32[256]) ですP、S ← EksBlowfishSetup( password、salt、cost ) //テキスト「OrpheanBeholderScryDoubt」を64回繰り返し暗号化するctext ← "OrpheanBeholderScryDoubt" //24バイト ==> 64ビットブロック3つrepeat (64) ctext ← EncryptECB( P , S , ctext ) //標準のBlowfishをECBモードで使用して暗号化する//24バイトのctextは結果として得られるパスワードハッシュです。return Concatenate ( cost , salt , ctext )

関数EksBlowfishSetup 入力: password:  UTF-8 エンコードされたパスワードのバイト配列 (1～72 バイト) salt: ランダムなソルトのバイト配列 (16 バイト) cost: 数値 (4～31)  log 2 (反復回数)。例: 12 ==> 2 12 = 4,096 反復出力: P: ラウンドごとに 18 個のサブキーの UInt32 配列 S 1 ..S 4 :  4 つの SBox の UInt32 配列。各 SBox は 256 UInt32 (つまり、各 SBox は 1 KiB)// P (サブキー) と S (置換ボックス) を円周率の 16 進数で初期化します。P , S ← InitialState() //パスワードとソルトに基づいてPとSを並べ替えるP , S ← ExpandKey( P , S , password , salt ) //これは「高価なキー設定」の「高価な」部分です。//それ以外はキー設定はBlowfishと同じです。repeat (2 cost ) P , S ← ExpandKey( P , S , password, 0) P , S ← ExpandKey( P , S , salt, 0) P、 Sを返す

関数ExpandKey 入力: P: UInt32 配列 18 個のサブキーの配列 S 1 ..S 4 : UInt32[1024]  4 つの 1 KB SBox パスワード: バイト配列 (1 ～ 72 バイト)  UTF-8 エンコードされたパスワード ソルト: バイト[16] ランダムなソルト出力: P: UInt32配列 18 個のラウンドごとのサブキー の配列 S 1 ..S 4 : UInt32[1024]  4 つの 1 KB SBox//パスワードをPサブキー配列に混ぜるfor n ← 1 to 18 do P n ← P n xor password [32(n-1)..32n-1] //パスワードを循環的として扱う// 128 ビットのソルトを 2 つの 64 ビットの半分 (Blowfish ブロック サイズ) として扱います。 saltHalf[0] ← salt [0..63] // ソルトの下位 64 ビット saltHalf[1] ← salt [64..127] // ソルトの上位 64 ビット// 8バイト（64ビット）のバッファをすべてゼロで初期化します。 ブロック ← 0 //内部状態をPボックスに混合します。n ← 1 から9まで繰り返します。 //64ビットブロックと64ビットソルトハーフブロックをXORします。 block ← block xor saltHalf [(n-1) mod 2] //各イテレーションでsaltHalf [0]とsaltHalf [1]を交互に繰り返します。//現在のキーを使用してブロックを暗号化する スケジュールブロック← Encrypt( P , S , block ) P 2n ←ブロック[0..31] //ブロックの下位 32 ビット P 2n+1 ←ブロック[32..63] //ブロックの上位 32 ビット//暗号化された状態を状態の内部Sボックスに混合します。i ← 1から4まで繰り返します。n ← 0から127まで繰り返します。 block ← Encrypt( state , block xor saltHalf [(n-1) mod 2]) //上記と同様 S i [2n] ← block [0..31] //下位 32 ビット S i [2n+1] ← block [32..63] //上位 32 ビットreturn state

bcryptの多くの実装では、OpenBSDの実装に倣って、パスワードを最初の72バイトに切り詰めます。

数学的アルゴリズム自体は、18 個の 32 ビットサブキー (72 オクテット/バイトに相当) による初期化を必要とします。bcrypt の元の仕様では、ユーザーランドからのテキストベースのパスワードをアルゴリズムの数値にマッピングするための特定のメソッドは規定されていません。本文中の短いコメントでは、文字文字列の ASCII エンコード値をそのまま使用する可能性について言及していますが、それを義務付けているわけではありません。「最後に、キー引数は秘密の暗号化キーであり、最大 56 バイト (キーが ASCII 文字列の場合は終端のゼロ バイトを含む) のユーザーが選択したパスワードにすることができます。」^{[ 1 ]}

上記の引用文では、アルゴリズム自体は72バイトの初期値を使用しているにもかかわらず、「最大56バイト」のパスワードについて言及していることに注意してください。ProvosとMazièresは、より短い制限の理由を述べていませんが、Bruce SchneierによるBlowfishの元の仕様書にある次の記述に影響を受けた可能性があります。「鍵サイズの448 [ビット]制限により、すべてのサブキーのすべてのビットが鍵のすべてのビットに依存することが保証されます。」^{[ 18 ]}

実装方法によって、パスワードを初期数値に変換するアプローチは様々であり、場合によっては非ASCII文字を含むパスワードの強度を低下させることもある。^{[ 19 ]}

bcryptは鍵導出関数（KDF）ではありません。例えば、bcryptを使ってパスワードから512ビットの鍵を導出することはできません。一方、pbkdf2、scrypt、argon2などのアルゴリズムはパスワードベースの鍵導出関数であり 、その出力は鍵導出だけでなく、パスワードハッシュ化の目的で使用されます。

パスワードハッシュ化は通常1000ミリ秒未満で完了する必要があります。このシナリオでは、bcryptはpbkdf2、scrypt、およびargon2よりも強力です。

• PBKDF2 : pbkdf2 は bcrypt より弱い。一般的に使用されている SHA2 ハッシュアルゴリズムはメモリハードではない。SHA2 は軽量デバイス (スマートカードなど) で実行できるように非常に軽量に設計されている。 ^{[ 20 ]}これは、毎秒数兆回のハッシュを実行できる市販の SHA-2 ハッシュハードウェアが容易に入手できるため、PBKDF2 はパスワードの保存には非常に弱いことを意味する。
• scrypt : scryptは、4MB未満のメモリ要件ではbcryptよりも弱い。 ^{[ 21 ]} scryptは、GPUベースの攻撃に対する同等の防御レベル（パスワードの保存用）を達成するには、bcryptの約1000倍のメモリを必要とする。
• argon2 : bcrypt は Argon2 よりも軽量です。これは、Argon2 を使用するとパフォーマンスを維持するためにセキュリティ パラメータを許容できないレベルまで下げる必要がある一部の Web アプリケーションでは問題になる可能性があります。具体的には、実行時間が 1 秒未満 (つまり、一般的なパスワード認証の場合) では、Argon2 は bcrypt よりもセキュリティが低くなります。Argon2 は、実行時間が約 1000 ms を超えるまで、bcrypt の強度に匹敵またはそれを超えることはありません。 これはパスワード ハッシュには適さない可能性がありますが、鍵導出には完全に許容されます。 ^{[ 22 ]} セキュリティ パラメータが十分に高い場合は、場合によっては、bcrypt よりも Argon2 が推奨されます。 ^{[ 23 ]}
• pufferfish2は、bcrypt の進化版で、bcrypt の固定 4 KB メモリ フットプリントではなく、調整可能なメモリ フットプリント(scrypt や argon2 と同様) を使用します。scrypt や argon2 と同様に、pufferfish2 はより多くのメモリを使用することで難易度を上げています。scrypt や argon2 とは異なり、pufferfish2 は CPU コアの L2 キャッシュでのみ動作します。scrypt や argon2 は大量の RAM にランダムにアクセスすることでメモリのハードネスを上げていますが、pufferfish2 は CPU コアで使用可能な専用 L2 キャッシュのみに制限されています。そのため、scrypt や argon2 よりもカスタム ハードウェアでの実装がさらに難しくなっています。pufferfish2 の理想的なメモリ フットプリントは、コアで使用可能なキャッシュのサイズです (たとえば、Intel Alder Lake ^{[ 24 ]}の場合は 1.25 MB )。これにより、pufferfish2 は GPU や ASIC に対してはるかに耐性があります。

• Argon2 - 2015年のパスワードハッシュコンテスト優勝者
• bcrypt - 2002年に開発された、Blowfishベースのクロスプラットフォームファイル暗号化ユーティリティ^{[ 27 ] [ 28 ] [ 29 ] [ 30 ]}
• crypt - Unix Cライブラリ関数
• crypt - Unixユーティリティ
• ccrypt - ユーティリティ
• キーストレッチング
• mcrypt - ユーティリティ
• PBKDF2 - 広く使用されている標準規格 パスワードベース鍵導出関数2
• scrypt - パスワードベースの鍵導出関数（およびユーティリティ）
• yescrypt

• Openwallが管理する実装であるcrypt_blowfish