bcrypt
bcrypt
一般的な
デザイナーニールス・プロヴォス、デヴィッド・マジエール
初版1999
由来フグ（暗号）
詳細
ダイジェストサイズ184ビット
ラウンドコストパラメータによる変数

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は、まず標準状態のサブ鍵から開始し、この状態を用いて鍵の一部を用いたブロック暗号化を実行します。そして、その暗号化結果（ハッシュ精度が高い）を用いてサブ鍵の一部を置き換えます。そして、この変更された状態を用いて鍵の別の部分を暗号化し、その結果を用いてさらに多くのサブ鍵を置き換えます。このように、段階的に変更された状態を用いて鍵をハッシュし、状態の一部を置き換えていく処理を、すべてのサブ鍵が設定されるまで繰り返します。

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

説明

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

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

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

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

どこ：

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

bcryptのBase64エンコーディングではテーブル[ 12 ]./ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789が使用され、これはRFC 4648のBase64エンコーディングとは異なります。  

バージョン履歴

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月、PHPによるbcrypt実装である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 関数は、 Blowfishを用いてテキスト「OrpheanBeholderScryDoubt」を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バイト ==> 3つの64ビットブロックrepeat (64) ctext ← EncryptECB( P , S , ctext ) //標準のBlowfishをECBモードで使用して暗号化する//24バイトのctextは結果のパスワードハッシュです 。Concatenate( cost , salt , ctext ) を返します。

高価なキー設定

bcrypt アルゴリズムは、次のように実行される「Eksblowfish」キー設定アルゴリズムに大きく依存しています。 

関数EksBlowfishSetup 入力: パスワード: バイト配列 (1..72 バイト)  UTF-8 でエンコードされたパスワード ソルト: バイト配列 (16 バイト) ランダム ソルト コスト: 数値 (4..31)  log 2 (反復回数)。例: 12 ==> 2 12 = 4,096 反復出力: P: UInt32 配列 18 個のラウンドごとのサブキーの配列 S 1 ..S 4 : UInt32 配列 4 つの SBox の配列。各 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を返す

InitialState は、元の Blowfish アルゴリズムと同じように動作し、P 配列と S ボックスのエントリに 16 進数の小数部分を入力します。 π{\displaystyle \pi }

展開キー

ExpandKey 関数は次のことを行います。 

関数ExpandKey 入力: P: UInt32 配列 18個のサブキーの配列 S 1 ..S 4 : UInt32[1024]  4個の1 KB SBoxes パスワード: バイト配列 (1..72 バイト)  UTF-8でエンコードされたパスワード ソルト: Byte[16] ランダムソルト出力: P: UInt32 配列 18個のラウンドごとのサブキーの配列 S 1 ..S 4 : UInt32[1024]  4個の1 KB SBoxes//パスワードを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 ボックスにミックスします。for n ← 1から9 do // 64 ビットブロックと 64 ビット ソルト ハーフを xor します。 block ← block xor saltHalf [(n-1) mod 2] // 各反復でsaltHalf [0] とsaltHalf [1]を交互に繰り返します。//現在のキースケジュールを使用してブロックを暗号化します。block ← Encrypt( P , S , block ) P 2n ←ブロック[0..31] //ブロックの下位32ビット P 2n+1 ←ブロック[32..63] //ブロックの上位32ビット//暗号化された状態をstateの内部 S-box に混ぜるfor i ← 1 to 4 do for n ← 0 to 127 do 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

したがって、すべてゼロのソルト値を持つすべての XOR は無効であるため、通常の Blowfish キー スケジュールと同じです。 は同様ですが、ソルトを 128 ビット キーとして使用します。 ExpandKey(state, key, 0)ExpandKey(state, salt, 0)

ユーザー入力

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

数学的アルゴリズム自体は、18個の32ビットサブキー（72オクテット/バイトに相当）による初期化を必要とします。bcryptのオリジナル仕様では、ユーザーランドのテキストベースのパスワードをアルゴリズムの数値にマッピングするための特定の方法は規定されていません。仕様書には、文字列のASCIIエンコード値をそのまま使用できる可能性について簡潔なコメントが1つ記載されていますが、必須ではありません。「最後に、key引数は秘密の暗号化キーであり、これはユーザーが選択した最大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 ]つまり、PBKDF2はパスワード保存に非常に弱い。毎秒数兆回のハッシュを実行できる市販のSHA-2ハッシュハードウェアは容易に入手できるためである。
  • scrypt：メモリ要件が4MB未満の場合は、scryptはbcryptよりも弱いです。 [ 21 ] scryptは、GPUベースの攻撃（パスワード保存用）に対して同等の防御レベルを実現するために、bcryptの約1000倍のメモリを必要とします。
  • argon2 : bcryptはArgon2よりも軽量です。これは、一部のWebアプリケーションでは、Argon2を使用するとパフォーマンスを維持するためにセキュリティパラメータを許容できないレベルまで下げる必要があるため、問題となる可能性があります。具体的には、Argon2は実行時間が1秒未満（一般的なパスワード認証など）の場合、bcryptよりも安全性が低くなります。Argon2は実行時間が約1000ミリ秒を超えるまで、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 に対してはるかに耐性があります。

批判

パスワードの最大長

bcryptのパスワードの最大長は72バイトです。この最大値は、ExpandKey関数の最初の演算で、 18個の4バイトのサブキー（P）とパスワードの XOR演算を行うことによって決まります。

P 1 ..P 18 ← P 1 ..P 18のパスワードバイトの排他的論理和

パスワード（UTF-8でエンコード）は、72バイトになるまで繰り返されます。例えば、次のようなパスワードは、

correct horse battery staple␀（29バイト）

18 P のラウンドごとのサブキーの 72 バイトと一致するまで繰り返されます。

correct horse battery staple␀correct horse battery staple␀correct horse （72バイト）

最悪の場合、パスワードは18文字に制限され、各文字はUTF-8で4バイトのエンコードが必要になります。例えば：

𐑜𐑝𐑟𐑥𐑷𐑻𐑽𐑾𐑿𐑿𐑰𐑩𐑛𐑙𐑘𐑙𐑒𐑔（18文字、72バイト）

2024年にOkta社のシングルサインオンサービスは、ユーザー名の後にパスワードが連結され、そのペアがbcryptでハッシュ化されるため、ユーザー名が長すぎるログインではパスワードが無視されてしまうという脆弱性を発表しました。[ 25 ]

パスワードハッシュの切り捨て

bcrypt アルゴリズムでは、24 バイトのテキストを繰り返し暗号化します。

OrpheanBeholderScryDoubt（24バイト）

これにより、24 バイトの暗号文が生成されます。例:

85 20 af 9f 03 3d b3 8c 08 5f d2 5e 2d aa 5e 84 a2 b9 61 d2 f1 29 c9 a4（24バイト）

標準的なOpenBSD実装では、これを23バイトに切り捨てます。[ 26 ]

85 20 af 9f 03 3d b3 8c 08 5f d2 5e 2d aa 5e 84 a2 b9 61 d2 f1 29 c9（23バイト）

標準的な実装では、結果として得られるパスワード ハッシュから 8 ビットが削除される理由は不明です。

これらの 23 バイトは、Base64 でエンコードすると 31 文字になります。

fQAtluK7q2uGV7HcJYncfII3WbJvIai（31文字）

base64エンコードアルファベット

標準的なOpenBSD実装で使用されるエンコーディングはcryptと同じBase64アルファベットを使用します。[ 12 ]つまり、このエンコーディングはより一般的なRFC 4648とは互換性がありません。 ./ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789

参照

参考文献

  1. ^ a b Provos N , Maziéres D (1999年6月10日).将来適応型パスワードスキーム(PDF) . 1999 USENIX 年次技術会議. 第5巻. FREENIXトラック議事録. カリフォルニア州モントレー: USENIX協会.
  2. ^ "CVS log for src/lib/libc/crypt/bcrypt.c" . CVSリポジトリ. OpenBSD . 2014年3月23日. リビジョン1.32（ログにbcryptが初めて記載）. 2023年5月25日閲覧。静的グローバル変数を必要としないため、bcryptの実装に最小限の変更が加えられました。
  3. ^ 「SUSEセキュリティアナウンスメント：（SUSE-SA:2011:035）」。セキュリティアドバイザリ。SUSE 。2011年8月23日。 2016年3月4日時点のオリジナルからのアーカイブ。 2015年8月20日閲覧。SUSEのcrypt()実装は、blowfishパスワードハッシュ関数（ID $2a）をサポートしており、システムログインもデフォルトでこの方法を使用します。
  4. ^ Whitlock, David (2021年9月21日). 「Bcrypt Elixir: Elixir用bcryptパスワードハッシュアルゴリズム」 . GitHub . riverrun.
  5. ^ 「パッケージ bcrypt」 . godoc.org .
  6. ^ 「jBCrypt - Java用の強力なパスワードハッシュ」 www.mindrot.org . 2017年3月11日閲覧。
  7. ^ 「bcrypt - bcryptパスワードハッシュ関数のJavaスタンドアロン実装」 . github.com . 2018年7月19日閲覧。
  8. ^ "bcryptjs" . npm . riverrun. 2017年2月7日.
  9. ^ "rust-bcrypt" . GitHub . Vincent Prouillet. 2024年11月8日.
  10. ^ "V Bcrypt" . vlang .
  11. ^ "zigstd" . GitHub . jedisct1. 2020年10月26日.
  12. ^ a b Provos, Niels (1997年2月13日). 「bcrypt.c ソースコード、57-58行目」 . 2022年1月29日閲覧。
  13. ^ 「モジュラー暗号フォーマット — Passlib v1.7.1 ドキュメント」 . passlib.readthedocs.io .
  14. ^ a b「bcrypt パスワードハッシュのバグ修正、バージョン変更および結果」。undeadly.org 。
  15. ^ Designer、Solar。 「oss-sec: CVEリクエスト: crypt_blowfishの8ビット文字の誤った処理」。seclists.org 。
  16. ^ "「bcrypt バージョンの変更」 - MARC" . marc.info .
  17. ^ “bcrypt.c code fix for 2014 bug” . 2014年2月17日. 2022年2月18日時点のオリジナルよりアーカイブ。 2022年2月17日閲覧。
  18. ^ Schneier, Bruce (1993年12月). 「高速ソフトウェア暗号化：新しい可変長鍵、64ビットブロック暗号（Blowfish）の説明」 . Cambridge Security Workshop Proceedings . Springer-Verlag: 191–204 .
  19. ^ 「jBCrypt セキュリティアドバイザリ」 2010年2月1日。そして、「PHP 5.3.7 での CRYPT_BLOWFISH の変更点」。php.net 。
  20. ^セキュアハッシュ標準nist.gov
  21. ^ 「Scrypt を推奨しない理由」 2014 年 3 月 12 日。
  22. ^ 「Argon2 vs bcrypt vs. scrypt：どのハッシュアルゴリズムが適していますか？」 2023年3月。
  23. ^ 「OWASP パスワード保存チートシート」。
  24. ^ 「製品仕様」。
  25. ^ Jones, Conner (2024年11月4日). 「なぜ長い名前なのか？ Oktaが52文字のユーザー名に影響する認証バイパスのバグを公表」 The Register . 2024年11月5日閲覧。
  26. ^ "src/lib/libc/crypt/bcrypt.c at master · openbsd/src" . GitHub . 2016年8月30日. 2024年12月3日閲覧。
  27. ^ bcryptファイル暗号化プログラムのホームページ
  28. ^ 「Android用bcrypt APK - Droid Informerで無料でダウンロード」。droidinformer.org 。
  29. ^ 「T2 パッケージ - trunk - bcrypt - ファイルを暗号化するユーティリティ」。t2sde.org 。
  30. ^ “Oracle GoldenGateのライセンス” . docs.oracle.com。
「 https://en.wikipedia.org/w/index.php?title=Bcrypt&oldid=1330993803」から取得