Bcrypt
'[Blowfish(cipher)| Blowfish]]暗号に基づいて、Niels ProvosとDavidMazièresによって設計された[[bcrypt]' 'は[[暗号化ハッシュ関数#パスワード検証|パスワードハッシング関数] 1999年にUSENIXで発表されました。bcryptは、[rainbow table]攻撃から保護するために[[salt(暗号化)| salt]を組み込むことに加えて、時間の経過と共に反復回数を増やすことができますそれを遅くするので、計算能力が増してもブルートフォース検索攻撃に耐えられます。
bcrypt関数はOpenBSDやSUSE LinuxなどのLinuxディストリビューションを含む他のシステムのデフォルトのパスワードハッシュアルゴリズムです。 シャドウパスワードファイルのハッシュ文字列の接頭辞 "$ 2a $"または "$ 2y $"は、ハッシュ文字列がモジュラー暗号形式のbcryptハッシュであることを示します。 残りのハッシュ文字列には、コストパラメータである128ビットのsalt([Base64 | Radix-64と互換性のない[Base64 | Radix-64アプリケーション]]が22文字としてエンコードされています)、結果のハッシュ値の184ビット Radix-64アプリケーションはBase64 | Radix-64と互換性がありませんは31文字でエンコードされています)。 Radix-64エンコーディングはunix / cryptアルファベットを使用し、 '標準' Base-64ではありません。 costパラメータは、暗号化アルゴリズムへの入力である2の累乗としてのキー展開反復カウントを指定します。
例えば、シャドーパスワードレコード< code> $ 2a $ 10 $ N9qo8uLOickgx2ZMRZoMyeIjZAgcfl7p92ldGxad68LJZdL17lhWy< / code> 2の10乗を示す10のコストパラメータを指定する。キー拡張ラウンド。塩は、 N9qo8uLOickgx2ZMRZoMye </ code>である。結果のハッシュは<code> IjZAgcfl7p92ldGxad68LJZdL17lhWy </ code>です。標準的な慣行では、ユーザーのパスワード自体は保存されません。
C、C#、Go、Java、JavaScript、Perl、PHP、Python、Rubyなどの言語用のbcryptの実装があります。
背景[編集]
ブローフィッシュは、その高価なキーセットアップフェーズでブロック暗号の中で注目されています。標準状態のサブキーで始まり、この状態を使用してキーの一部を使用してブロック暗号化を実行し、その暗号化の結果(より正確にはハッシュ)を使用してサブキーの一部を置き換えます。次に、この変更された状態を使用してキーの別の部分を暗号化し、結果を使用してより多くのサブキーを置き換えます。これは、すべてのサブキーが設定されるまで、徐々に変更された状態を使用してキーをハッシュし、状態のビットを置き換えるこのような方法で進行する。
プロボスとマジエールはこれを利用してさらにそれを取った。 Blowfishの新しい鍵設定アルゴリズムを開発し、結果として生成された暗号「Eksblowfish」(「高価な鍵スケジュールBlowfish」)をダビングしました。キーのセットアップは、塩とパスワードの両方を使用してすべてのサブキーを設定する標準Blowfishキー設定の変更された形式から始まります。次に、標準のBlowfishキーイングアルゴリズムが適用され、saltとpasswordをキーとして使用し、各ラウンドは前のラウンドのサブキー状態から開始します。理論的には、これは標準のBlowfishキースケジュールよりも強力ではありませんが、鍵の再生成の回数は設定可能です。したがって、このプロセスは任意に遅くすることができ、ハッシュまたはソルトに対するブルートフォース攻撃を抑止するのに役立ちます。
バージョニング履歴[編集]
'$ 2 $(1999)'
元のBcrypt仕様では、< code> $ 2 $< / code>のプレフィックスが定義されていました。これは、OpenBSDパスワードファイルにパスワードを保存する際に使用される Modular Crypt Format 形式に従います:
- < code> $ 1 $< / code>:MD5
- < code> $ 2 $< / code> ;: Bcrypt
- < code> $ sha1 $< / code> ;: SHA-1
- < code> $ 5 $< / code> ;: SHA-256
- < code> $ 6 $< / code> ;: SHA-512
'$ 2a $'
元の仕様では、非ASCII文字の処理方法やヌルターミネータの処理方法は定義されていませんでした。文字列をハッシュするときに指定するように仕様が改訂されました:
- 文字列はUTF-8でエンコードされている必要があります
- ヌルターミネータを含める必要があります
この変更により、バージョンは< code> $ 2a $< / code>に変更されました。
'$ 2x $、$ 2y $(2011年6月)'
2011年6月に、BCryptのPHP実装である 'crypt_blowfish' にバグが発見されました。 8番目のビットがセットされたキャラクターが誤って処理されていました。彼らは、システム管理者が既存のパスワードデータベースを更新し、< code> $ 2a $< / code> < code> $ 2x $< / code>を使用して、これらのハッシュが不良であることを示します(古い破損アルゴリズムを使用する必要があります)。彼らはまた、「crypt_blowfish」が「< code> $ 2y $< / code>固定アルゴリズムによって生成されたハッシュに対して
標準的なOpenBSDを含む他の誰も、2x / 2yの考え方を採用していません。このバージョンのマーカーの変更は 'crypt_blowfish' に限定されていました。
'$ 2b $(2014年2月)'
bcryptのOpenBSD実装で発見されたバグです。彼らは文字列の長さをunsigned char '(' 8ビット<code> Byte </ code>)に格納していました。
BCryptはOpenBSD用に作成されました。ライブラリにバグがあったとき、彼らはバージョン番号にバンプすることにしました。
アルゴリズム[編集]
bcryptアルゴリズムは、 Blowfishを使用して、テキスト "'" OrpheanBeholderScryDoubt "' 'を64回暗号化した結果です。 bcryptでは、通常のBlowfishキー設定機能は、「高価な」キー設定(EksBlowfishSetup)機能に置き換えられました:
< span style = "color:#004DBB;"> '機能' < / span> bcrypt
< span style = "color:#004DBB;"> '入力:' < / span>
コスト:Number(4..31)< span style = "color:green;"> log< sub2>(反復)。例えば12 ==> 2 12 12 / = 4,096回の繰り返し< / span>
salt:Bytes(16バイト)の配列< span style = "color:green;">ランダムな塩< / span>
パスワード:バイトの配列(1..72バイト) UTF-8でエンコードされたパスワード< / span>
< span style = "color:#004DBB;"> '出力:' < / span>
ハッシュ:バイトの配列(24バイト)
< span style = "color:green;"> //高価なキー設定アルゴリズムでブローフィッシュの状態を初期化する< / span>
'状態' '<数学> \は< /数学> EksBlowfishSetup( コスト 、 塩 、 パスワード )
< span style = "color:green;"> //テキスト "OrpheanBeholderScryDoubt"を64回< / span>
ctext < math> \は< / math>を取得します。 < span style = "color:maroon"> "'" OrpheanBeholderScryDoubt "' '< / span> < span style = "color:green;"> // 24 bytes ==> 3つの64ビットブロック< / span>
< span style = "color:#004DBB;"> 'repeat' "'< / span> (64)
ctext < math> \は< / math>を取得します。 < span style = "color:green;"> // ECBモードで標準Blowfishを使用して暗号化する< / span>
< span style = "color:green;"> // 24-byte ctext は結果のパスワードハッシュです。< / span>
< span style = "color:#004DBB;"> 'return' < / span>連結( コスト 、 塩 、 ctext )
高価なキー設定[編集]
bcryptアルゴリズムは、次のように実行される "Eksblowfish"キー設定アルゴリズムに大きく依存します。
< span style = "color:#004DBB;"> '機能' < / span> EksBlowfishSetup
< span style = "color:#004DBB;"> '入力:' < / span>
コスト:Number(4..31)< span style = "color:green;"> log< sub2>(反復)。例えば12 ==> 2 12 12 / = 4,096回の繰り返し< / span>
salt:Bytes(16バイト)の配列< span style = "color:green;">ランダムな塩< / span>
パスワード:バイトの配列(1..72バイト) UTF-8でエンコードされたパスワード< / span>
< span style = "color:#004DBB;"> '出力:' < / span>
状態:不透明ブローフィッシュ状態構造
'状態' '<数学> \は< /数学>初期状態()
'状態' '<数学> \は< /数学> ExpandKey( 状態 、 塩 、 パスワード )
< span style = "color:#004DBB;"> 'repeat' "'< / span> (2"コスト"< / sup>)
'状態' '<数学> \は< /数学> ExpandKey(状態、0、パスワード)
'状態' '<数学> \は< /数学> ExpandKey(状態、0、塩)
< span style = "color:#004DBB;"> 'return' < / span> 状態
InitialStateは元のBlowfishアルゴリズムの場合と同様に動作し、P配列およびSボックスの項目には、<pi> / pi </ math> 16進数で表します。
拡大キー[編集]
ExpandKey関数は、次の処理を行います。
< span style = "color:#004DBB;"> '機能' < / span> ExpandKey( 状態 、 塩 、 パスワード )
< span style = "color:#004DBB;"> '入力:' < / span>
ステート:不透明ブローフィッシュステート構造<span style = "color:green;">内部的にP配列とSボックスのエントリを含む< / span>
salt:Bytes(16バイト)の配列< span style = "color:green;">ランダムな塩< / span>
パスワード:バイトの配列(1..72バイト) UTF-8でエンコードされたパスワード< / span>
< span style = "color:#004DBB;"> '出力:' < / span>
状態:不透明ブローフィッシュ状態構造
< span style = "color:green;"> // '状態' '< / span>の内部P配列にパスワードをミックスします。
< / span>< span style = "color:#004DBB;"> n < math> \< / math> 1< span style = "color:#004DBB;"> '〜' < / span> 18< span style = "color:#004DBB;"> 'do' "< / span>
P <n> </ sub>は、 <数学> \は< /数学> P <n> </ sub>は、 < span style = "color:#004DBB;"> xor< / span> < span style = "color:green;"> //パスワードをサイレント< / span>として扱います。
< span style = "color:green;"> // saltの下位8バイトを使用して状態を暗号化し、8バイトの結果をP 1 | P ;< / span>
'ブロック' '<数学> \は< /数学>暗号化( 状態 、 塩 [0..63])
P 1である。 <数学> \は< /数学> <span style = "color:green;"> // lower 32-bit< / span>
P <2> </ sub> <数学> \は< /数学> < / span>< / span>< / span>
< span style = "color:green;"> //状態をsaltで暗号化し、結果を残りのP配列< / span>に格納します。
< / span>< span style = "color:#004DBB;"> n < math> \< / math> 2< span style = "color:#004DBB;"> '〜' < / span> 9< span style = "color:#004DBB;"> 'do' "< / span>
'ブロック' '<数学> \は< /数学> """""""""< / span> salt [64(n-1) ); 64n-1])<span style = "color:green;"> //現在のキースケジュールを使用して暗号化し、その塩を循環的< / span>
P <2n-1 </ sub>は、 <数学> \は< /数学> <span style = "color:green;"> // lower 32-bit< / span>
P <2n </ sub>は、 <数学> \は< /数学> < / span>< / span>< / span>
< span style = "color:green;"> //暗号化された状態を 'state' '< / span>の内部Sボックスにミックスします。
< / span>< span style = "color:#004DBB;"> '< / math> \< / math> 1< span style = "color:#004DBB;"> '〜' < / span> 4< span style = "color:#004DBB;"> 'do' "'< / span>
< / span>< span style = "color:#004DBB;"> n < math> \< / math> 0< span style = "color:#004DBB;"> '〜' < / span> 127< span style = "color:#004DBB;"> 'do' "< / span>
'ブロック' '<数学> \は< /数学> < / span> salt [64(n-1) ).. 64n-1])< span style = "color:green;"> //上記のように< / span>
S ij [2n] <math> \ gets< / math> <span style = "color:green;"> // lower 32-bit< / span>
S i [sub] [2n + 1] <math> \ gets< / math> < / span>< / span>< / span>
< span style = "color:#004DBB;"> 'return' < / span> 状態
したがって、< code> ExpandKey( 状態 、0、 キー )< / code>すべてのゼロの塩の値を持つすべてのXORが無効であるため、通常のBlowfishキースケジュールと同じです。 < code> ExpandKey( state 、0、 salt )< / code>似ていますが、128ビットのキーとして塩を使用します。
ユーザー入力[編集]
bcryptの多くの実装では、パスワードを最初の72バイトに切り捨てます。
数学的アルゴリズム自体には、18の32ビットサブキー(72オクテット/バイトに相当)での初期化が必要です。元の仕様 "キーサイズの448 [ビット]制限は、すべてのサブキーのすべてのビットがキーの各ビットに依存することを保証します。"
実装では、非ASCII文字を含むパスワードの強度を低下させるなど、パスワードを最初の数値に変換するアプローチが異なります。
関連項目[編集]
- Crypt(C)#Blowfishベースのスキーム暗号化パスワード保存と検証スキームBlowfish
- キーストレッチ
- PBKDF2(パスワードベースのキー導出関数2)
- scrypt