アルゴン2

アルゴン2
一般的な
デザイナー	アレックス・ビリュコフ; ダニエル・ディヌ; ドミトリー・ホヴラトヴィッチ;
初版	2015年; 9年前
暗号の詳細
ダイジェストサイズ	変数
ブロックサイズ	変数
ラウンド	変数

Argon2は、2015年のパスワードハッシュコンペティションで優勝した鍵導出関数です。^[1]^{[2]これは、}ルクセンブルク大学のAlex Biryukov、Daniel Dinu、Dmitry Khovratovichによって設計されました。^[3] Argon2のリファレンス実装は、クリエイティブ・コモンズCC0ライセンス（パブリックドメイン）またはApacheライセンス2.0の下でリリースされており、3つの関連バージョンが提供されています。

Argon2d は GPUクラッキング攻撃に対する耐性を最大限に高めます。パスワードに依存する順序でメモリ配列にアクセスするため、時間とメモリのトレードオフ(TMTO) 攻撃の可能性は減りますが、サイドチャネル攻撃の可能性は高まります。
Argon2i はサイドチャネル攻撃に対抗するように最適化されています。パスワードに依存しない順序でメモリ配列にアクセスします。
Argon2id はハイブリッドバージョンです。メモリの最初の半分のパスでは Argon2i アプローチに従い、その後のパスでは Argon2d アプローチに従います。RFC 9106では、タイプの違いがわからない場合や、サイドチャネル攻撃が脅威になる可能性があると考えられる場合は、Argon2id を使用することを推奨しています。^[4]

3 つのモードはすべて、次のものを制御する 3 つのパラメータによる指定が可能です。

実行時間
必要なメモリ
並列度

暗号解読

Argon2dに適用可能な公開暗号解読法はないが、Argon2i関数に対する2つの攻撃が公開されている。最初の攻撃はArgon2iの古いバージョンにのみ適用可能で、2番目の攻撃は最新バージョン（1.3）にまで拡張されている。^[5]

最初の攻撃は、時間のペナルティなしで必要なスペースの4分の1から5分の1を使用してシングルパスArgon2i関数を計算し、時間のペナルティなしで $N$ / $e$ （≈N $/2.72$ ）スペースのみを使用してマルチパスArgon2iを計算することが可能であることを示しています。^[6] Argon2の作者によると、この攻撃ベクトルはバージョン1.3で修正されました。^[7]

2番目の攻撃は、Argon2iが、 $n$ = $σ$ ∗ τとなるパラメータ $σ$ （スペースコスト）、 $τ （時間コスト）、およびスレッド数のあらゆる選択に対して、複雑度O($ $n$ ^7/4 log( $n$ ))のアルゴリズムで計算できることを示しています。^{[8] Argon2の作者は} $、$ Argon2iが3回以上のパスで使用される場合、この攻撃は効率的ではないと主張しています。[ ^7]しかし、Joël AlwenとJeremiah Blockiは攻撃を改良し、攻撃が失敗するにはArgon2i v1.3でメモリを10回以上パスする必要があることを示しました。^[5]

これらの懸念に対処するために、RFC9106では、このような攻撃を大幅に軽減するためにArgon2idを使用することを推奨しています。^[9]

アルゴリズム

出典: ^[4]

関数Argon2
   入力: 
      password ( P ): バイト (0..2³² -1)    ハッシュするパスワード (またはメッセージ) 
      salt ( S ): バイト (8..2³² -1)    ソルト (パスワードハッシュには 16 バイトを推奨) 
      parallelism ( p ): 数値 (1..2²⁴ -1)   並列度 (つまりスレッド数) 
      tagLength ( T ): 数値 (4..2³² -1)   返されるバイト数の希望値
      memorySizeKB ( m ): 数値 (8p..2³² -1)  使用するメモリ量 (キビバイト単位) 
      iterations ( t ): 数値 (1..2³² -1)   
      version ( v ): 数値 (0x13)現在のバージョンは 0x13 (10 進数で 19) です
      key ( K ): バイト (0..2³² -1)    オプションのキー (Errata: PDF には次のように記載されています0..32バイト、RFCでは0..2 ³²バイトとされている)
      関連データ( X ): バイト(0..2³² -1)    オプションの任意の追加データ
      ハッシュタイプ( y ): 数値(0=Argon2d、1=Argon2i、2=Argon2id)
   出力:
      タグ: バイト(タグ長)結果として生成されるバイト、タグ長バイト長      

   最初の64バイトブロックH0を生成し_ます。
    すべての入力パラメータは連結され、追加のエントロピーのソースとして入力されます。
    訂正: RFC では H ₀は 64 ビットと記載されていますが、PDF では H ₀は 64 バイトと記載されています。
    訂正: RFC ではハッシュは H^ と書かれていますが、PDF では ℋ と書かれています (ただし、ℋ が何であるかは文書化されていません)。実際は Blake2b です。
    可変長項目には、その長さが 32 ビットのリトルエンディアン整数として先頭に付加されます。
   バッファ ← 並列性 ‖ タグ長 ‖ メモリサイズ KB ‖ 反復回数 ‖ バージョン ‖ ハッシュタイプ
         ‖ 長さ(パスワード) ‖ パスワード
         ‖ 長さ(塩) ‖ 塩
         ‖ 長さ(キー) ‖ キー
         長さ(関連データ) 関連データ
   H ₀ ← Blake2b(buffer, 64) //Blake2bのデフォルトのハッシュサイズは64バイトです

   メモリサイズKBを4*並列キビバイトの最も近い倍数に切り捨てて1KBブロックの数を計算します。
   ブロック数 ← Floor(メモリサイズKB、4*並列度)

   1 KiB ブロックの 2 次元配列 (parallelism 行 x columnCount 列) を割り当てます。columnCount 
   ← blockCount / parallelism;    //RFC では、columnCount はqと呼ばれます。

   
   _{各レーン（つまり行）の}最初と2番目のブロック（つまり列0と1）を計算します。i ← 0から並列度-1まで、各行に対して実行します 。B 
      i [0] ← Hash(H _{0 ‖}₀ ‖ i, 1024) //1024バイトのダイジェストを生成します。B 
      i [1] ← Hash(H ₀ ‖ 1 ‖ i, 1024) //1024バイトのダイジェストを生成します。

   各レーンの残りの列を計算します
   。i ← 0からparallelism-1まで実行します。//各行に対して実行します。j ← 2からcolumnCount-1まで実行します。//各後続の列に対して実行します。//i' および j' インデックスは、Argon2i、Argon2d、または Argon2id のいずれであるかによって異なります (セクション 3.4 を参照)。i 
         ′、j′ ← GetBlockIndexes(i、j)   //GetBlockIndexes 関数は定義されていません_{。B i} 
         [ j] = G(B _i [j-1]、B _i′ [j′]) //G ハッシュ関数は定義されていません。 
       
         

   さらに、反復回数 > 1 の場合は、
    nIteration ← 2からiterationsまで実行し、
       i ← 0からparallelism-1まで実行し、各行に対して実行し、 j ← 0からcolumnCount-1まで実行し、//後続の各列に対して実行します//i' と j' のインデックスは、Argon2i、Argon2d、または Argon2id のいずれであるかによって異なります (セクション 3.4 を参照) 
         
           
           i′, j′ ← ブロックインデックスを取得(i, j)
           j == 0の場合、  
             B _i [0] = B _i [0] xor G(B _i [columnCount-1], B _i′ [j′])、
           それ以外の場合は
             B _i [j] = B _i [j] xor G(B _i [j-1], B _i′ [j′])

   最終ブロックCを各行の最後の列のXORとして計算します
   。C ← B ₀ [columnCount-1]
    for i ← 1 to parallelism-1 do 
      C ← C xor B _i [columnCount-1]

   出力タグを計算し、
    Hash(C, tagLength)
を返します。

可変長ハッシュ関数

^{Argon2 は、最大 2 32}バイトの長さのダイジェストを生成できるハッシュ関数を使用します。このハッシュ関数は、内部的にBlake2上に構築されています。

関数Hash(message, digestSize)
   入力: 
      message: バイト (0..2³² -1)     ハッシュされるメッセージ
      digestSize: 整数 (1..2³² )     返される希望のバイト数
   出力: 
      digest: バイト (digestSize)結果として生成されるバイト、digestSize バイト長 

   ハッシュはBlake2bを使用して構築された可変長ハッシュ関数であり、生成することができます。
   最大 2 ³²バイトをダイジェストします。

   要求されたダイジェストサイズが64バイト以下の場合は、Blake2bを直接使用します。if 
   ( digestSize <= 64) then 
      return Blake2b(digestSize ‖ message, digestSize) //32ビットのリトルエンディアンのダイジェストサイズをメッセージバイトと連結します。

   64バイトを超えるハッシュ（例：Argon2ブロックの場合は1024バイト）の場合、
   Blake2bを使用して、必要な64バイトブロックの2倍の数を生成します。
   そして各ブロックから32バイトだけを使用する

   ブロック全体の数を計算する（各ブロックから32バイトのみを使用することを前提とする）
   r ← Ceil(ダイジェストサイズ/32)-2;

   r 個のブロック全体を生成します。
   最初のブロックはメッセージから生成されます
   V ₁ ← Blake2b(digestSize ‖ message, 64);
   後続のブロックは前のブロックから生成されます
   for i ← 2 to r do 
      V _i ← Blake2b(V _i-1 , 64)
   最後の（部分的な）ブロックを生成します
   partialBytesNeeded ← ダイジェストサイズ – 32*r;
   V _r+1 ← Blake2b(V _r , 部分バイトが必要)

   _{各ブロック V i}の最初の 32 バイトを連結します
   (最後のブロックは部分的である可能性があり、全体を取得します)。A 
   _{i がブロック V}_iの下位 32 バイトを表すとし
   ます。A ₁ ‖ A ₂ ‖ ... ‖ A _r ‖ V _r+1を返します。

推奨される最小パラメータ

2023年5月現在、OWASPのパスワードストレージチートシートでは、「19MiBのメモリ、反復回数2、並列度1の最小構成でArgon2idを使用する」ことを推奨しています。^[10]

OWASPは、GPUベースの攻撃とサイドチャネル攻撃の両方に対してバランスの取れた耐性を提供するため、Argon2dやArgon2iよりもArgon2idを優先することを推奨しています。^[10]

OWASPはさらに、以下のArgon2idオプションは同等の暗号強度を提供し、計算負荷に対するメモリ使用量を単純にトレードオフすると述べています。^[10]

メモリ: 46 MiB、反復: 1、並列処理: 1
メモリ: 19 MiB、反復: 2、並列処理: 1
メモリ: 12 MiB、反復: 3、並列処理: 1
メモリ: 9 MiB、反復: 4、並列処理: 1
メモリ: 7 MiB、反復: 5、並列処理: 1

参考文献

^ 「パスワードハッシュコンテスト」
^ Jos Wetzels (2016-02-08). 「Open Sesame: パスワードハッシュコンペティションと Argon2」. arXiv : 1602.03097 [cs.CR].
^ Argon2: パスワードハッシュやその他のアプリケーションのためのメモリハード関数、Alex Biryukov 他、2015 年 10 月 1 日
^ ab Biryukov, Alex; Dinu, Daniel; Khovratovich, Dmitry; Josefsson, Simon (2021 年 9 月). 「パスワードハッシュおよびプルーフオブワークアプリケーション向けの Argon2 メモリハード関数」。2021年9 月 9 日閲覧。
^ ab Joël Alwen; Jeremiah Blocki (2016-08-05). Argon2i と Balloon Hashing に対する実践的な攻撃に向けて(PDF) (レポート).
^ Henry、Corrigan-Gibbs、Dan Boneh、Stuart Schechter (2016-01-14)。バルーンハッシュ：データに依存しないアクセスパターンを備えた、証明可能なスペースハードハッシュ関数(PDF) (レポート)。
^ ab "[Cfrg] Argon2 v.1.3". www.ietf.org . 2016年10月30日閲覧。
^ Joël Alwen、Jeremiah Blocki (2016-02-19)。データに依存しないメモリ困難な関数の効率的な計算(PDF) (レポート)。
^ 「推奨事項」。 パスワードハッシュおよびプルーフオブワークアプリケーション向けの Argon2 メモリハード関数。IETF。2021年9 月。sec. 7.4。doi : 10.17487/RFC9106。RFC 9106。2023年7月 12 日に取得。
^ abc 「パスワード保存チートシート」。OWASPチートシートシリーズ。OWASP 。 2023年5月17日閲覧。

外部リンク

Github 上の Argon2 ソースコードリポジトリ
アルゴン2仕様
パスワードハッシュコンテスト
Uni.Lu Argon2 ページ
バルーンハッシュ: 連続攻撃に対する証明可能な保護を提供するメモリ困難な関数
RFC 9106 パスワードハッシュとプルーフオブワークアプリケーションのための Argon2 メモリハード関数

[1] 「パスワードハッシュコンテスト」

[2] Jos Wetzels (2016-02-08). 「Open Sesame: パスワードハッシュコンペティションと Argon2」. arXiv : 1602.03097 [cs.CR].

[3] Argon2: パスワードハッシュやその他のアプリケーションのためのメモリハード関数、Alex Biryukov 他、2015 年 10 月 1 日

[:1-4] Biryukov, Alex; Dinu, Daniel; Khovratovich, Dmitry; Josefsson, Simon (2021 年 9 月). 「パスワードハッシュおよびプルーフオブワークアプリケーション向けの Argon2 メモリハード関数」。2021年9 月 9 日閲覧。

[blocki-5] Joël Alwen; Jeremiah Blocki (2016-08-05). Argon2i と Balloon Hashing に対する実践的な攻撃に向けて(PDF) (レポート).

[6] Henry、Corrigan-Gibbs、Dan Boneh、Stuart Schechter (2016-01-14)。バルーンハッシュ：データに依存しないアクセスパターンを備えた、証明可能なスペースハードハッシュ関数(PDF) (レポート)。

[:0-7] "[Cfrg] Argon2 v.1.3". www.ietf.org . 2016年10月30日閲覧。

[8] Joël Alwen、Jeremiah Blocki (2016-02-19)。データに依存しないメモリ困難な関数の効率的な計算(PDF) (レポート)。

[9] ^ 「推奨事項」。 パスワードハッシュおよびプルーフオブワークアプリケーション向けの Argon2 メモリハード関数。IETF。2021年9 月。sec. 7.4。doi : 10.17487/RFC9106。RFC 9106。2023年7月 12 日に取得。

[owasp-10] 「パスワード保存チートシート」。OWASPチートシートシリーズ。OWASP 。 2023年5月17日閲覧。