Argon2

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

Argon2 is a key derivation function that was selected as the winner of the Password Hashing Competition in July 2015.[1][2] It was designed by Alex Biryukov, Daniel Dinu, and Dmitry Khovratovich from the University of Luxembourg.[3] Argon2 is released under a Creative Commons CC0 license (i.e. public domain), and provides three related versions:

  • 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[4] 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[edit]

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 N/e < N/2.71 space with no time penalty.[5] According to the Argon2 authors, this attack vector was fixed in version 1.3.[6]

The second attack shows that Argon2i can be computed by an algorithm which has complexity O(n7/4 log(n)) for all choices of parameters σ (space cost), τ (time cost), and thread-count such that n=στ.[7] The Argon2 authors claim that this attack is not efficient if Argon2i is used with three or more passes.[6] However, Joël Alwen and Jeremiah Blocki improved the attack and showed that in order for the attack to fail, Argon2i 1.3 needs more than 10 passes over memory.[8]

Algorithm[edit]

Function Argon2
   Inputs:
      password (P):       Bytes (0..232-1)    Password (or message) to be hashed
      salt (S):           Bytes (8..232-1)    Salt (16 bytes recommended for password hashing)
      parallelism (p):    Number (1..224-1)   Degree of parallelism (i.e. number of threads)
      tagLength (T):      Number (4..232-1)   Desired number of returned bytes
      memorySizeKB (m):   Number (8p..232-1)  Amount of memory (in kilobytes) to use
      iterations (t):     Number (1..232-1)   Number of iterations to perform
      version (v):        Number (0x13)      The current version is 0x13 (19 decimal)
      key (K):            Bytes (0..232-1)    Optional key (Errata: PDF says 0..32 bytes, RFC says 0..232 bytes)
      associatedData (X): Bytes (0..232-1)    Optional arbitrary extra data
      hashType (y):       Number (0=Argon2d, 1=Argon2i, 2=Argon2id)
   Output:
      tag:                Bytes (tagLength)   The resulting generated bytes, tagLength bytes long

   Generate initial 64-byte block H0.
   All the input parameters are concatenated and input as a source of additional entropy.
   Errata: RFC says H0 is 64-bits; PDF says H0 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.
   buffer ← parallelism ∥ tagLength ∥ memorySizeKB ∥ iterations ∥ version ∥ hashType
         ∥ Length(password)       ∥ Password
         ∥ Length(salt)           ∥ salt
         ∥ Length(key)            ∥ key
         ∥ Length(associatedData) ∥ associatedData
   H0 ← Blake2b(buffer, 64) //default hash size of Blake2b is 64-bytes

   Calculate number of 1 KB blocks by rounding down memorySizeKB to the nearest multiple of 4*parallelism kilobytes
   blockCount ← Floor(memorySizeKB, 4*parallelism)

   Allocate two-dimensional array of 1 KiB blocks (parallelism rows x columnCount columns)
   columnCount ← blockCount / parallelism;   //In the RFC, columnCount is referred to as q

   Compute the first and second block (i.e. column zero and one ) of each lane (i.e. row)
   for i ← 0 to parallelism-1 do for each row
      Bi[0] ← Hash(H0 ∥ 0 ∥ i, 1024) //Generate a 1024-byte digest
      Bi[1] ← Hash(H0 ∥ 1 ∥ i, 1024) //Generate a 1024-byte digest

   Compute remaining columns of each lane
   for i ← 0 to parallelism-1 do //for each row
      for j ← 2 to columnCount-1 do //for each subsequent column
         //i' and j' indexes depend if it's Argon2i, Argon2d, or Argon2id (See section 3.4)
         i′, j′ ← GetBlockIndexes(i, j)
         Bi[j] = G(Bi[j-1], Bi′[j′])

   Further passes when iterations > 1
   for nIteration ← 2 to iterations do
      for i ← 0 to parallelism-1 do for each row
        for j ← 2 to columnCount-1 do //for each subsequent column
           //i' and j' indexes depend if it's Argon2i, Argon2d, or Argon2id (See section 3.4)
           i′, j′ ← GetBlockIndexes(i, j)
           Bi[0] = G(Bi[columnCount-1], Bi′[j′])
           Bi[j] = G(Bi[j-1], Bi′[j′])

   Compute final block C as the XOR of the last column of each row
   C ← B0[columnCount-1]
   for i ← 1 to parallelism-1 do
      C ← C xor Bi[columnCount-1]

   Compute output tag
   return Hash(C, tagLength)

Variable-length hash function[edit]

Argon2 makes use of a hash function capable of producing digests up to 232 bytes long. This hash function is internally built upon Blake2.

Function Hash(message, digestSize)
   Inputs:
      message:         Bytes (0..232-1)     Message to be hashed
      digestSize:      Integer (1..232)     Desired number of bytes to be returned
   Output:
      digest:          Bytes (digestSize)   The resulting generated bytes, digestSize bytes long

   Hash is a variable-length hash function, built using Blake2b, capable of generating
   digests up to 232 bytes.

   If the requested digestSize is 64-bytes or lower, then we use Blake2b directly
   if (digestSize <= 64) then
      return Blake2b(digestSize ∥ message, digestSize) //concatenate 32-bit little endian digestSize with the message bytes

   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

   Calculate the number of whole blocks (knowing we're only going to use 32-bytes from each)
   r ← Ceil(digestSize/32)-1;

   Generate r whole blocks.
   Initial block is generated from message
   V1 ← Blake2b(digestSize ∥ message, 64);
   Subsequent blocks are generated from previous blocks
   for i ← 2 to r do
      Vi ← Blake2b(Vi-1, 64)
   Generate the final (possibly partial) block
   partialBytesNeeded ← digestSize – 32*r;
   Vr+1 ← Blake2b(Vr, partialBytesNeeded)

   Concatenate the first 32-bytes of each block Vi
   (except the possibly partial last block, which we take the whole thing)
   Let Ai represent the lower 32-bytes of block Vi
   return A1 ∥ A2 ∥ ... ∥ Ar ∥ Vr+1

References[edit]

  1. ^ "Password Hashing Competition"
  2. ^ Jos Wetzels (2016-02-08). "Open Sesame: The Password Hashing Competition and Argon2" (PDF). 
  3. ^ Argon2: the memory-hard function for password hashing and other applications, Alex Biryukov, et al, October 1, 2015
  4. ^ https://datatracker.ietf.org/doc/draft-irtf-cfrg-argon2/ The memory-hard Argon2 password hash and proof-of-work function, draft-irtf-cfrg-argon2-03, accessed August 16, 2017
  5. ^ Henry Corrigan-Gibbs, Dan Boneh, Stuart Schechter (2016-01-14). "Balloon Hashing: Provably Space-Hard Hash Functions with Data-Independent Access Patterns" (PDF). 
  6. ^ a b "[Cfrg] Argon2 v.1.3". www.ietf.org. Retrieved 2016-10-30. 
  7. ^ Joel Alwen, Jeremiah Blocki (2016-02-19). "Efficiently Computing Data-Independent Memory-Hard Functions" (PDF). 
  8. ^ Joël Alwen, Jeremiah Blocki (2016-08-05). "Towards Practical Attacks on Argon2i and Balloon Hashing" (PDF). 

External links[edit]