Argon2

RFC 9106 Argon2 Memory-Hard Function for Password Hashing and Proof-of-Work Applications

パスワードハッシュとproof-of-work アプリケーションのためのArgon2メモリハード関数

パスワードハッシュおよびproof-of-work アプリケーション向けArgon2メモリハード関数

概要

本文書は、パスワードハッシュおよびproof-of-work アプリケーション向けArgon2メモリハード関数について解説します。実装者向けの説明とテストベクトルを提供します。本文書の目的は、インターネットプロトコルへのArgon2の導入を簡素化することです。本文書は、IRTFのCrypto Forum Research Group (CFRG) の成果物です。

1. はじめに

Argon2id は、本文書のいかなる実装においてもサポートされなければなりません（MUST）。一方、Argon2d と Argon2i はサポートされてもよい（MAY）。

本文書は、Crypto Forum Research Group (CFRG) の合意事項を反映しています。

1.1. 要件言語

2. 表記法と規則

table:表記と規則

x^y 整数 x をそれ自身で整数 y 回乗算した値

a*b 整数 a と整数 b の乗算

c-d 整数 d を整数 c から減算した値

E_f 添字インデックス f を持つ変数 E

g / h 整数 g を整数 h で割った値。結果は有理数。

I(j) 関数 I を j で評価した値

K || L 文字列 K と文字列 L の連結

a XOR b ビット列 a と b のビット単位の排他的論理和

a >>> n 64 ビット文字列 a を右に n ビット回転

trunc(a) 64 ビット値 (下位 32 ビットに切り捨て)

floor(a) a より大きくない最大の整数

ceil(a) a より小さくない最小の整数

extract(a, i) ビット列 a から i 番目の 32 ビットセット (0 番目から開始)

|A| 集合Aの要素数

LE32(a) 32ビット整数aをリトルエンディアンのバイト文字列に変換したもの（例えば、123456（10進数）は40 E2 01 00 です）

LE64(a) 64ビット整数aをリトルエンディアンのバイト文字列に変換したもの（例えば、123456（10進数）は40 E2 01 00 00 00 00 00 です）

int32(s) 32ビット文字列sをリトルエンディアンの非負整数に変換したもの

int64(s) 64ビット文字列sをリトルエンディアンの非負整数に変換したもの

length(P) 文字列Pのバイト長を32ビット整数で表したもの

ZERO(P) Pバイトのゼロ文字列

3. Argon2 アルゴリズム

3.1. Argon2 の入力と出力

Argon2 には以下の入力パラメータがあります。

並列度 p は、実行可能な独立した（ただし同期する）計算チェーン（レーン）の数を決定します。1 から 2^(24)-1 までの整数値である必要があります。

メモリサイズ m は 8p から 2^(32)-1 までの整数キビバイトでなければなりません。実際のブロック数は m' で、これは m を 4p の倍数に切り捨てた値です。

バージョン番号 v は 1 バイト 0x13 でなければなりません。

y 型は、Argon2d の場合は 0、Argon2i の場合は 1、Argon2id の場合は 2 でなければなりません。

Argon2 の出力、つまり「タグ」は、T バイトの長さの文字列です。

3.2. Argon2 の動作

Argon2 の動作は以下のとおりです。

1. H_0を以下の64バイト値として設定します。K、X、またはSの長さが0の場合、それらは単に存在しないだけで、長さフィールドは残ります。

code:図1 H_0 生成

H_0 = H^(64)(LE32(p) || LE32(T) || LE32(m) || LE32(t) ||

LE32(v) || LE32(y) || LE32(length(P)) || P ||

LE32(length(S)) || S || LE32(length(K)) || K ||

LE32(length(X)) || X)

2. メモリをm'個の1024バイトブロックとして割り当てます。ここで、m'は次のように求められます。

code:図2 メモリ割当

m' = 4 * p * floor (m / 4p)

code:図3 レーン開始ブロック

code:図4 次レーン ブロック

code:図5：さらなるブロック生成

code:図6 さらなるパス

7. tステップが反復された後、最終ブロックCは最後の列のXORとして計算されます。

code:図6 最終ブロック

8. 出力タグはH'^T(C)として計算されます。

3.3. 可変長ハッシュ関数 H'

V_i を64バイトのブロックとし、W_i をその最初の32バイトとします。関数 H' を以下のように定義します。

code:図8: タグと初期ブロックの計算のための関数H'

if T <= 64

H'^T(A) = H^T(LE32(T)||A)

else

r = ceil(T/32)-2

V_1 = H^(64)(LE32(T)||A)

V_2 = H^(64)(V_1)

...

V_r = H^(64)(V_{r-1})

V_{r+1} = H^(T-32*r)(V_{r})

H'^T(X) = W_1 || W_2 || ... || W_r || V_{r+1}

3.4. インデックス

並列ブロック計算を可能にするため、メモリマトリックスをさらにSL = 4の垂直スライスに分割します。スライスとレーンの交差はセグメントと呼ばれ、長さはq/SLです。同じスライス内のセグメントは並列計算が可能で、互いにブロックを参照しません。他のすべてのブロックは参照可能です。

code:図9 pレーンと4スライスを備えたシングルパスArgon2

slice 0 slice 1 slice 2 slice 3

___/\___ ___/\___ ___/\___ ___/\___

/ \ / \ / \ / \

+----------+----------+----------+----------+

| | | | | > lane 0

+----------+----------+----------+----------+

| | | | | > lane 1

+----------+----------+----------+----------+

| | | | | > lane 2

+----------+----------+----------+----------+

| ... ... ... | ...

+----------+----------+----------+----------+

| | | | | > lane p - 1

+----------+----------+----------+----------+

3.4.1. 32ビット値 J_1 と J_2 の計算

3.4.1.1. Argon2d

code:図10: Argon2dでJ1、J2を導出する

3.4.1.2. Argon2i

各セグメントについて、以下の処理を行います。まず、値Zを次のように計算します。

code:図11: Argon2iでJ1、J2を計算するための入力

Z= ( LE64(r) || LE64(l) || LE64(sl) || LE64(m') ||

LE64(t) || LE64(y) )

ここで

r: パス番号

l: レーン番号

sl: スライス番号

m': メモリブロックの総数

t: パスの総数

y: Argon2 のタイプ (Argon2d の場合は 0、Argon2i の場合は 1、Argon2id の場合は 2)

次に、以下の値を計算します。

q/(128*SL) 個の 1024 バイト値

G(ZERO(1024),G(ZERO(1024),

Z || LE64(1) || ZERO(968) )),

G(ZERO(1024),G(ZERO(1024),

Z || LE64(2) || ZERO(968) )),... ,

G(ZERO(1024),G(ZERO(1024),

Z || LE64(q/(128*SL)) || ZERO(968) )),

これらはq/(SL)個の8バイト値Xに分割され、X1||X2として扱われ、J_1=int32(X1)、J_2=int32(X2)に変換されます。

r、l、sl、m'、t、y、iの値は、リトルエンディアンで8バイトとして表現されます。

3.4.1.3. Argon2id

パス番号が0でスライス番号が0または1の場合、Argon2iと同様にJ_1とJ_2を計算します。それ以外の場合は、Argon2dと同様にJ_1とJ_2を計算します。

l = J_2 mod p の値は、ブロックが取得されるレーンのインデックスを示します。最初のパス (r=0) と最初のスライス (sl=0) では、ブロックは現在のレーンから取得されます。

集合 W には、以下の規則に従って参照されるインデックスが含まれます。

次に、次のマッピングを使用して、W から [0, |W|) に不均一に分布するブロックを 1 つ取得します。

code:図12: コンピューティング J1

J_1 -> |W|(1 - J_1^2 / 2^(64))

浮動小数点計算を回避するために、次の近似値が使用されます。

code:図13: コンピューティング J1、パート2

x = J_1^2 / 2^(32)

y = (|W| * x) / 2^(32)

zz = |W| - 1 - y

3.5. 圧縮関数G

圧縮関数 G は、BLAKE2b ベースの変換 P に基づいて構築されます。P は 128 バイトの入力に対して動作し、これは 8 つの 16 バイト レジスタとして見ることができます。

code:図14 ブレイクラウンド関数P

P(A_0, A_1, ... ,A_7) = (B_0, B_1, ... ,B_7)

圧縮関数 G(X, Y) は、2つの1024バイトブロック X と Y に対して作用します。まず、R = X XOR Y を計算します。次に、R は16バイトレジスタ R_0、R_1、…、R_63 からなる8x8行列とみなされます。次に、P を各行に適用し、次に各列に適用して Z を取得します。

code:図15: 圧縮関数Gのコア

( Q_0, Q_1, Q_2, ... , Q_7) <- P( R_0, R_1, R_2, ... , R_7)

( Q_8, Q_9, Q_10, ... , Q_15) <- P( R_8, R_9, R_10, ... , R_15)

...

(Q_56, Q_57, Q_58, ... , Q_63) <- P(R_56, R_57, R_58, ... , R_63)

( Z_0, Z_8, Z_16, ... , Z_56) <- P( Q_0, Q_8, Q_16, ... , Q_56)

( Z_1, Z_9, Z_17, ... , Z_57) <- P( Q_1, Q_9, Q_17, ... , Q_57)

...

( Z_7, Z_15, Z 23, ... , Z_63) <- P( Q_7, Q_15, Q_23, ... , Q_63)

最後に、G は Z XOR R を出力します。

code:図16: Argon2圧縮関数G

G: (X, Y) -> R -> Q -> Z -> Z XOR R

+---+ +---+

| X | | Y |

+---+ +---+

| |

---->XOR<----

--------|

| \ /

| +---+

| | R |

| +---+

| |

| \ /

| P rowwise

| |

| \ /

| +---+

| | Q |

| +---+

| |

| \ /

| P columnwise

| |

| \ /

| +---+

| | Z |

| +---+

| |

| \ /

------>XOR

|

\ /

3.6. 順列P

順列PはBLAKE2bのラウンド関数に基づいています。8つの16バイト入力S_0、S_1、…、S_7は、64ビットワードの4x4行列として扱われます。ここで、S_i = (v_{2*i+1} || v_{2*i}) です。

code:図17:行列要素のラベル付け

v_0 v_1 v_2 v_3

v_4 v_5 v_6 v_7

v_8 v_9 v_10 v_11

v_12 v_13 v_14 v_15

動作は次のようになります。

code:図18: 行列要素をGBに入力する

GB(v_0, v_4, v_8, v_12)

GB(v_1, v_5, v_9, v_13)

GB(v_2, v_6, v_10, v_14)

GB(v_3, v_7, v_11, v_15)

GB(v_0, v_5, v_10, v_15)

GB(v_1, v_6, v_11, v_12)

GB(v_2, v_7, v_8, v_13)

GB(v_3, v_4, v_9, v_14)

GB(a, b, c, d)は次のように定義されます。

code:図19: GBの詳細

a = (a + b + 2 * trunc(a) * trunc(b)) mod 2^(64)

d = (d XOR a) >>> 32

c = (c + d + 2 * trunc(c) * trunc(d)) mod 2^(64)

b = (b XOR c) >>> 24

a = (a + b + 2 * trunc(a) * trunc(b)) mod 2^(64)

d = (d XOR a) >>> 16

c = (c + d + 2 * trunc(c) * trunc(d)) mod 2^(64)

b = (b XOR c) >>> 63

GBにおけるモジュラー加算は、64ビット乗算と組み合わせられています。乗算は、オリジナルのBLAKE2b設計との唯一の違いです。この選択は、回路の深さを増やし、ASIC実装の実行時間を短縮する一方で、並列処理とパイプライン化によりCPUとほぼ同等の実行時間を実現するためです。

4. パラメータの選択

Argon2dは、攻撃者がシステムメモリやCPUに定期的にアクセスできない環境向けに最適化されています。つまり、タイミング情報に基づくサイドチャネル攻撃を実行できず、ガベージコレクションを用いてパスワードを高速に復元することもできません。これらの設定は、バックエンドサーバーや暗号通貨マイニングにおいてより一般的です。実践的な例として、以下の設定をお勧めします。

暗号通貨マイニング：2GHz CPU、1コアで0.1秒（Argon2d、2レーン、250MB RAM）

Argon2idは、攻撃者が同じマシンにアクセスしたり、CPUを利用したり、コールドブート攻撃を仕掛けたりする可能性のある、より現実的な環境向けに最適化されています。以下の設定をお勧めします。

バックエンドサーバーの認証：2GHz CPU、4コアで0.5秒（Argon2id、8レーン、4GiB RAM）

ハードドライブ暗号化のための鍵導出。2GHz CPU、2コア、4レーン、6GiB RAMのArgon2idで3秒かかります。

フロントエンドサーバーの認証。2GHz CPU、2コア、4レーン、1GiB RAMのArgon2idで0.5秒かかります。

Argon2を実際に使用する場合、タイプとパラメータを選択するには、以下の手順をお勧めします。

1. アプリケーションやハードウェアに合わせてカスタマイズされていない、均一に安全なオプションが許容される場合は、t=1 反復、p=4 レーン、m=2^(21) (RAM 2GiB)、128 ビットソルト、256 ビットタグサイズの Argon2id を選択します。これが第一推奨オプションです。

2. 使用可能なメモリがはるかに少ない場合、均一に安全なオプションは、t=3 反復、p=4 レーン、m=2^(16) (RAM 64MiB)、128 ビットソルト、256 ビットタグサイズの Argon2id です。これが第二推奨オプションです。

3. それ以外の場合は、まずタイプ y を選択します。タイプの違いがわからない場合、またはサイドチャネル攻撃が現実的な脅威であると考えられる場合は、Argon2id を選択します。

4. p=4 レーンを選択します。

5. 各呼び出しが許容できる最大メモリ量を計算し、それをパラメータ m に変換します。

6. 各呼び出しが許容できる最大時間（秒単位）を計算します。

7. ソルト長を選択します。128 ビット長はすべてのアプリケーションで十分ですが、メモリ容量の制約がある場合は 64 ビットに短縮できます。

8. タグ長を選択します。128 ビット長は、鍵導出を含むほとんどのアプリケーションで十分です。より長い鍵が必要な場合は、より長いタグを選択します。

9. サイドチャネル攻撃が現実的な脅威である場合、または不確かな場合は、ライブラリ呼び出しでメモリワイピングオプショ ンを有効にします。

10. タイプ y、メモリ m、プレーンのスキームを、異なるパス数 t を使用して実行します。実行時間が許容時間を超えないような最大 t を計算します。t = 1 の場合でも許容時間を超える場合は、m をそれに応じて減らします。

11. m、p、t の値を決定して Argon2 を使用します。

5. テストベクトル

このセクションでは、Argon2 のテストベクトルについて説明します。

5.1. Argon2d テストベクトル

完全な出力（タグ）を持つテストベクターを提供します。開発者の利便性を考慮し、中間変数（具体的には各パスの最初と最後のメモリブロック）もいくつか提供します。

code:Argon2d バージョン番号 19

=======================================

Argon2d バージョン番号 19

=======================================

Memory: 32 KiB

Passes: 3

Parallelism: 4 lanes

Tag length: 32 bytes

01 01 01 01 01 01 01 01

01 01 01 01 01 01 01 01

01 01 01 01 01 01 01 01

Pre-hashing digest: b8 81 97 91 a0 35 96 60

bb 77 09 c8 5f a4 8f 04

d5 d8 2c 05 c5 f2 15 cc

db 88 54 91 71 7c f7 57

08 2c 28 b9 51 be 38 14

10 b5 fc 2e b7 27 40 33

b9 fd c7 ae 67 2b ca ac

5d 17 90 97 a4 af 31 09

After pass 0:

...

After pass 1:

...

After pass 2:

...

Tag: 51 2b 39 1b 6f 11 62 97

53 71 d3 09 19 73 42 94

f8 68 e3 be 39 84 f3 c1

a1 3a 4d b9 fa be 4a cb

5.2. Argon2i テストベクトル

code:Argon2i バージョン番号 19

=======================================

Argon2i バージョン番号 19

=======================================

Memory: 32 KiB

Passes: 3

Parallelism: 4 lanes

Tag length: 32 bytes

01 01 01 01 01 01 01 01

01 01 01 01 01 01 01 01

01 01 01 01 01 01 01 01

Pre-hashing digest: c4 60 65 81 52 76 a0 b3

e7 31 73 1c 90 2f 1f d8

0c f7 76 90 7f bb 7b 6a

5c a7 2e 7b 56 01 1f ee

ca 44 6c 86 dd 75 b9 46

9a 5e 68 79 de c4 b7 2d

08 63 fb 93 9b 98 2e 5f

39 7c c7 d1 64 fd da a9

After pass 0:

...

After pass 1:

...

After pass 2:

...

Tag: c8 14 d9 d1 dc 7f 37 aa

13 f0 d7 7f 24 94 bd a1

c8 de 6b 01 6d d3 88 d2

99 52 a4 c4 67 2b 6c e8

5.3. Argon2idテストベクトル

code:Argon2id バージョン番号 19

=======================================

Argon2id version number 19

=======================================

Memory: 32 KiB, Passes: 3,

Parallelism: 4 lanes, Tag length: 32 bytes

01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01

Pre-hashing digest: 28 89 de 48 7e b4 2a e5 00 c0 00 7e d9 25 2f

10 69 ea de c4 0d 57 65 b4 85 de 6d c2 43 7a 67 b8 54 6a 2f 0a

cc 1a 08 82 db 8f cf 74 71 4b 47 2e 94 df 42 1a 5d a1 11 2f fa

11 43 43 70 a1 e9 97

After pass 0:

...

After pass 1:

...

After pass 2:

...

Tag: 0d 64 0d f5 8d 78 76 6c 08 c0 37 a3 4a 8b 53 c9 d0

1e f0 45 2d 75 b6 5e b5 25 20 e9 6b 01 e6 59

6. IANAに関する考慮事項

この文書はIANAの承認を受けていません。

7. セキュリティに関する考慮事項

7.1. ハッシュ関数およびKDFとしてのセキュリティ

Argon2の衝突耐性および原像耐性レベルは、基礎となるBLAKE2bハッシュ関数のそれと同等です。衝突を発生させるには2^(256)回の入力が必要です。原像を見つけるには2^(512)回の入力を試行する必要があります。

KDFのセキュリティは、鍵長とハッシュ関数H'の内部状態のサイズによって決まります。鍵付きArgon2の出力をランダムな値と区別するには、BLAKE2bを少なくとも(2^(128),2^length(K))回呼び出す必要があります。

7.2. 時間空間トレードオフ攻撃に対するセキュリティ

時間空間トレードオフは、メモリ容量の少ないメモリブロックを格納することで、内部圧縮関数の呼び出し回数を増やすメモリ難関数の計算を可能にします。トレードオフ攻撃の利点は、時間と面積の積に対する削減係数で測定されます。メモリと追加の圧縮関数コアが面積に寄与し、欠落したブロックの再計算に対応するために処理時間が長くなります。削減係数が高いと、原像探索が高速化される可能性があります。

tパスArgon2dに対する最善のトレードオフ攻撃はランキングトレードオフ攻撃であり、これは時間と面積の積を1.33分の1に削減する。

Argon2idに対する最善の攻撃は、1パスArgon2iに対する最善の攻撃とマルチパスArgon2dに対する最善の攻撃を補完することで得られる。したがって、1パスArgon2idに対する最良のトレードオフ攻撃は、メモリ前半に対するローストレージ攻撃と後半に対するランキング攻撃を組み合わせたものであり、これにより約2.1倍の係数が生成される。tパスArgon2idに対する最良のトレードオフ攻撃はランキングトレードオフ攻撃であり、時間面積積は1.33倍に減少する。

7.3. 時間制限のある防御者に対するセキュリティ

7.4. 推奨事項

t=1、メモリ容量2GiBのArgon2idバリアントは、第一推奨オプションであり、すべての環境のデフォルト設定として提案されています。この設定はサイドチャネル攻撃に対して安全であり、専用のブルートフォースハードウェアにおける攻撃コストを最大化します。t=3、メモリ容量64MiBのArgon2idバリアントは、第二推奨オプションであり、メモリ制約のある環境のデフォルト設定として提案されています。

8. 参考文献

8.1. 規範的な参考文献

8.2. 参考文献

Biryukov, A.、Dinu, D.、D. Khovratovich、「Argon2：パスワードハッシュおよびその他のアプリケーションのためのメモリハードな新世代関数」、Euro SnP 2016、DOI 10.1109/EuroSP.2016.31、2016年3月、

謝辞

この文書の作成とレビューにご協力いただいた以下の方々に深く感謝いたします。Jean-Philippe Aumasson、Samuel Neves、Joel Alwen、Jeremiah Blocki、Bill Cox、Arnold Reinhold、Solar Designer、Russ Housley、Stanislav Smyshlyaev、Kenny Paterson、Alexey Melnikov、Gwynne Raskind。

この文書に記載されている作業は、Daniel DinuがIntelに入社する前、ルクセンブルク大学在学中に行われました。

著者のアドレス

Alex Biryukov

ルクセンブルク大学

メールアドレス: alex.biryukov@uni.lu

Daniel Dinu

ルクセンブルク大学

メールアドレス: daniel.dinu@intel.com

Dmitry Khovratovich

ABDKコンサルティング

メールアドレス: khovratovich@gmail.com

Simon Josefsson

SJD AB

メールアドレス: simon@josefsson.org