Argon2
Argon2 is a key derivation function that was selected as the winner of the Password Hashing Competition in July 2015. It was designed by Alex Biryukov, Daniel Dinu, and Dmitry Khovratovich from University of Luxembourg. Argon2 is released under a Creative Commons CC0 license (i.e. public domain), and provides three related versions:
Contents
Description
- Argon2d maximizes resistance to GPU cracking attacks. It accesses the memory array in a password dependent order, which reduces the possibility of time–memory trade-off (TMTO) attacks, but introduces possible side-channel attacks.
- Argon2i is optimized to resist side-channel attacks. It accesses the memory array in a password independent order.
- Argon2id is a hybrid version. It follows the Argon2i approach for the first pass over memory and the Argon2d approach for subsequent passes. The Internet draft recommends using Argon2id except when there are reasons to prefer one of the other two modes.
All three modes allow specification by three parameters that control:
- execution time
- memory required
- degree of parallelism
Cryptanalysis
While there is no public cryptanalysis applicable to Argon2d, there are two published attacks on the Argon2i function.
The first attack shows that it is possible to compute a single-pass Argon2i function using between a quarter and a fifth of the desired space with no time penalty, and compute a multiple-pass Argon2i using only / < /2.71 space with no time penalty. According to the Argon2 authors, this attack vector was fixed in version 1.3.
The second attack shows that Argon2i can be computed by an algorithm which has complexity O(<sup>7/4</sup> log()) for all choices of parameters (space cost), (time cost), and thread-count such that =∗. The Argon2 authors claim that this attack is not efficient if Argon2i is used with three or more passes.
Algorithm
<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)
Variable-length hash function
Argon2 makes use of a hash function capable of producing digests up to 2<sup>32</sup> bytes long. This hash function is internally built upon .
<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>
External Links
- GitHub – phxql/argon2-jvm: Argon2 Binding for the JVM
- Argon2 Java implementation : java – Reddit
- Argon2 – Wikipedia
Twitter
Telegram
