Argon2
Argon2は2015年7月にPassword Hashing Competitionの優勝者に選ばれました。
Alex Biryukov、Daniel Dinu、およびドミトリー・ホブラトビッチ[ルクセンブルグ大学]。
Argon2はクリエイティブ・コモンズ[[(CC0)]ライセンス(パブリック・ドメイン)の下でリリースされ、3つの関連バージョンを提供します。
- Argon2dはGPUクラッキング攻撃に対する抵抗力を最大限に引き出します。パスワードに依存した順序でメモリアレイにアクセスするため、
TMTO(Time-Memory Trade-Off)攻撃の可能性は低くなりますが、side-channel attack攻撃が発生する可能性があります。
- Argon2iは、サイドチャネル攻撃に抵抗するように最適化されています。パスワードに依存しない順序でメモリアレイにアクセスします。
- Argon2idはハイブリッドバージョンです。これは、メモリ上の最初のパスのArgon2iの方法と、それに続くパスのためのArgon2dの方法に従います。
インターネットドラフトでは、他の2つのモードのいずれかを好む理由がある場合を除いて、Argon2idを使用することを推奨しています。
3つのモードはすべて、以下を制御する3つのパラメータで指定できます:
- 実行時間
- メモリが必要です
- 並列度
暗号解読[編集]
Argon2dに適用できるパブリック解読法はありませんが、Argon2i関数には2つの公表された攻撃があります。
第1の攻撃は、時間ペナルティなしで所望の空間の4分の1から5分の1を使用してシングルパスArgon2i関数を計算することが可能であることを示し、
/&ltのみのマルチパスArgon2iを計算する。時間ペナルティなしで/2.71スペース。 Argon2の著者によると、この攻撃ベクトルはバージョン1.3で修正されました。
第2の攻撃は、Argon2iが、パラメータ(空間コスト)、(時間コスト)、およびスレッドのすべての選択肢に対して複雑度O(π/ 4)を有するアルゴリズムによって計算できることを示している。= *のようなスレッド数を返します。
Argon2の著者は、Argon2iが3回以上のパスで使用される場合、この攻撃は効率的ではないと主張しています。
アルゴリズム[編集]
<span style="color:blue;">Function</span> Argon2 <span style="color:blue;">Inputs:</span> password (<strong>P</strong>): Bytes (0..2<sup>32</sup>-1) <span style="color:green;">Password (or message) to be hashed</span> salt (<strong>S</strong>): Bytes (8..2<sup>32</sup>-1) <span style="color:green;">Salt (16 bytes recommended for password hashing)</span> parallelism (<strong>p</strong>): Number (1..2<sup>24</sup>-1) <span style="color:green;">Degree of parallelism (i.e. number of threads)</span> tagLength (<strong>T</strong>): Number (4..2<sup>32</sup>-1) <span style="color:green;">Desired number of returned bytes</span> memorySizeKB (<strong>m</strong>): Number (8p..2<sup>32</sup>-1) <span style="color:green;">Amount of memory (in kibibytes) to use</span> iterations (<strong>t</strong>): Number (1..2<sup>32</sup>-1) <span style="color:green;">Number of iterations to perform</span> version (<strong>v</strong>): Number (0x13) <span style="color:green;">The current version is 0x13 (19 decimal)</span> key (<strong>K</strong>): Bytes (0..2<sup>32</sup>-1) <span style="color:green;">Optional key (Errata: PDF says 0..32 bytes, RFC says 0..2<sup>32</sup> bytes)</span> associatedData (<strong>X</strong>): Bytes (0..2<sup>32</sup>-1) <span style="color:green;">Optional arbitrary extra data</span> hashType (<strong>y</strong>): Number (0=Argon2d, 1=Argon2i, 2=Argon2id) <span style="color:blue;">Output:</span> tag: Bytes (tagLength) <span style="color:green;">The resulting generated bytes, tagLength bytes long</span> <span style="color:green;">Generate initial 64-byte block H<sub>0</sub>. All the input parameters are concatenated and input as a source of additional entropy. Errata: RFC says H<sub>0</sub> is 64-bits; PDF says H<sub>0</sub> is 64-bytes. Errata: RFC says the Hash is H^, the PDF says it's ℋ (but doesn't document what ℋ is). It's actually Blake2b. Variable length items are prepended with their length as 32-bit little-endian integers.</span> buffer ← parallelism ∥ tagLength ∥ memorySizeKB ∥ iterations ∥ version ∥ hashType ∥ Length(password) ∥ Password ∥ Length(salt) ∥ salt ∥ Length(key) ∥ key ∥ Length(associatedData) ∥ associatedData H<sub>0</sub> ← Blake2b(buffer, 64) <span style="color:green;">//default hash size of Blake2b is 64-bytes</span> <span style="color:green;">Calculate number of 1 KB blocks by rounding down memorySizeKB to the nearest multiple of 4*parallelism kilobytes</span> blockCount ← Floor(memorySizeKB, 4*parallelism) <span style="color:green;">Allocate two-dimensional array of 1 KiB blocks (parallelism rows x columnCount columns)</span> columnCount ← blockCount / parallelism; <span style="color:green;">//In the RFC, columnCount is referred to as q</span> <span style="color:green;">Compute the first and second block (i.e. column zero and one ) of each lane (i.e. row)</span> for i ← 0 to parallelism-1 do <span style="color:green;">for each row</span> B<sub>i</sub>[0] ← Hash(H<sub>0</sub> ∥ 0 ∥ i, 1024) <span style="color:green;">//Generate a 1024-byte digest</span> B<sub>i</sub>[1] ← Hash(H<sub>0</sub> ∥ 1 ∥ i, 1024) <span style="color:green;">//Generate a 1024-byte digest</span> <span style="color:green;">Compute remaining columns of each lane</span> for i ← 0 to parallelism-1 do <span style="color:green;">//for each row</span> for j ← 2 to columnCount-1 do <span style="color:green;">//for each subsequent column</span> <span style="color:green;">//i' and j' indexes depend if it's Argon2i, Argon2d, or Argon2id (See section 3.4)</span> i′, j′ ← GetBlockIndexes(i, j) B<sub>i</sub>[j] = G(B<sub>i</sub>[j-1], B<sub>i′</sub>[j′]) <span style="color:green;">Further passes when iterations > 1</span> for nIteration ← 2 to iterations do for i ← 0 to parallelism-1 do <span style="color:green;">for each row</span> for j ← 2 to columnCount-1 do <span style="color:green;">//for each subsequent column</span> <span style="color:green;">//i' and j' indexes depend if it's Argon2i, Argon2d, or Argon2id (See section 3.4)</span> i′, j′ ← GetBlockIndexes(i, j) B<sub>i</sub>[0] = G(B<sub>i</sub>[columnCount-1], B<sub>i′</sub>[j′]) B<sub>i</sub>[j] = G(B<sub>i</sub>[j-1], B<sub>i′</sub>[j′]) <span style="color:green;">Compute final block C as the XOR of the last column of each row</span> C ← B<sub>0</sub>[columnCount-1] for i ← 1 to parallelism-1 do C ← C xor B<sub>i</sub>[columnCount-1] <span style="color:green;">Compute output tag</span> return Hash(C, tagLength)
可変長ハッシュ関数[編集]
Argon2は、2 ^ 32までのダイジェストを生成することができるハッシュ関数を利用する。バイト長。このハッシュ関数は、Blake2に内部的に組み込まれています。
<span style="color:blue;">Function</span> Hash(message, digestSize) <span style="color:blue;">Inputs:</span> message: Bytes (0..2<sup>32</sup>-1) <span style="color:green;">Message to be hashed</span> digestSize: Integer (1..2<sup>32</sup>) <span style="color:green;">Desired number of bytes to be returned</span> <span style="color:blue;">Output:</span> digest: Bytes (digestSize) <span style="color:green;">The resulting generated bytes, digestSize bytes long</span> <span style="color:green;">Hash is a variable-length hash function, built using Blake2b, capable of generating digests up to 2<sup>32</sup> bytes.</span> <span style="color:green;">If the requested digestSize is 64-bytes or lower, then we use Blake2b directly</span> if (digestSize <= 64) then return Blake2b(digestSize ∥ message, digestSize) <span style="color:green;">//concatenate 32-bit little endian digestSize with the message bytes</span> <span style="color:green;">For desired hashes over 64-bytes (e.g. 1024 bytes for Argon2 blocks), we use Blake2b to generate twice the number of needed 64-byte blocks, and then only use 32-bytes from each block</span> <span style="color:green;">Calculate the number of whole blocks (knowing we're only going to use 32-bytes from each)</span> r ← Ceil(digestSize/32)-1; <span style="color:green;">Generate r whole blocks.</span> <span style="color:green;">Initial block is generated from message</span> V<sub>1</sub> ← Blake2b(digestSize ∥ message, 64); <span style="color:green;">Subsequent blocks are generated from previous blocks</span> for i ← 2 to r do V<sub>i</sub> ← Blake2b(V<sub>i-1</sub>, 64) <span style="color:green;">Generate the final (possibly partial) block</span> partialBytesNeeded ← digestSize – 32*r; V<sub>r+1</sub> ← Blake2b(V<sub>r</sub>, partialBytesNeeded) <span style="color:green;">Concatenate the first 32-bytes of each block V<sub>i</sub> (except the possibly partial last block, which we take the whole thing)</span> <span style="color:green;">Let A<sub>i</sub> represent the lower 32-bytes of block V<sub>i</sub></span> return A<sub>1</sub> ∥ A<sub>2</sub> ∥ ... ∥ A<sub>r</sub> ∥ V<sub>r+1</sub>