Why Argon2 Beats Traditional Password Hashes: A Deep Dive into Memory‑Hard Functions

Argon2 is a slow hash function that won the PHC competition in 2015, using large amounts of memory to resist GPU and other custom‑hardware attacks and improve hash security.

This article is mainly based on the Argon2 paper[1] and other sources; it may contain misunderstandings, and corrections are welcome.

Password

Password is one of the main authentication methods for web services.

Passwords are usually stored in databases after hashing. If such databases are leaked, a dictionary attack can easily crack them because passwords have low entropy. The same password may be reused by different users or by the same user across systems.

To mitigate this, designers add a salt to the password‑hashing process.

Dictionary Attack uses a file containing words, phrases, common passwords and their hash results; comparing a password's hash to these results can crack it[2].

Brute Force Attack tries every possible character combination of a given length, which is very inefficient.

Salting solves most problems but cannot stop brute‑force attacks; GPUs, FPGAs, ASICs can still compute hashes at very low cost. Moreover, if the salt and password are leaked together (or even the code), the cracking cost further decreases.

The core issue is that traditional hash functions perform computation without requiring memory, allowing specialized hardware to compute them extremely fast. When a hash function needs a large amount of memory, such hardware becomes ineffective. Hence memory‑hard hash functions were designed.

Memory‑hard hash functions can also be used in cryptocurrency proof‑of‑work to suppress GPU and ASIC abuse; for example, scrypt is used by Litecoin.

Problems with Existing Algorithms

To improve password security, a simple approach is to use keyed hashes such as HMAC. If designers prefer not to manage keys, they may use PBKDF2, bcrypt, or scrypt.

Among these, only scrypt targets high memory usage. However, a time‑space trade‑off can shift memory consumption to computational resources (scrypt was originally designed to save CPU cycles by using memory).

Designing a memory‑hard hash function is difficult. Early attempts in the 1980s could be bypassed by time‑space trade‑offs: attackers convert memory usage into time, allowing low‑memory hardware to crack the hash, albeit with extra cost.

Argon2

Argon2 is the winner of the Password Hashing Competition (PHC)[3] and uses large memory and computation resources for hashing. It provides three variants:

Argon2d : faster, uses data‑dependent memory accesses (data = password + salt). Suitable for cryptocurrency and applications not vulnerable to side‑channel timing attacks.

Argon2i : uses data‑independent memory accesses, better for password hashing. It is slower because it requires more passes to protect against trade‑off attacks.

Argon2id : a hybrid of Argon2i and Argon2d; the first pass uses Argon2i, subsequent passes use Argon2d. Recommended when no specific reason to choose otherwise.

Definition of Memory‑Hard Hash Function

Memory‑hardness is measured by time‑area complexity, where "area" refers to the number of components on a circuit board; increasing components reduces computation time, so the product of area and time is used as a composite metric.

Let the attacker’s ASIC memory size be area

A

and runtime be

T

. The goal of a hash algorithm

H

is to maximize

A·T

.

If an attacker reduces memory to a fraction

αM

(

α < 1

), a time‑space trade‑off forces a computational penalty

C(α)

and increases runtime by at least a factor

D(α)

. The maximum possible gain

ε

is:

The gain is defined as the ratio of the before‑and‑after

A·T

products. Attackers aim to minimize the denominator, i.e., maximize

ε

. Therefore, a memory‑hard hash function must satisfy:

D(α) > 1/α,  α → 0

Only then does reducing memory not lower the

A·T

complexity (i.e.,

ε < 1

).

Additional factors influencing the

A·T

value include:

The penalty C(α) on computational resources when memory is reduced, which can increase area A .

If the trade‑off heavily relies on communication between computational resources, memory‑bandwidth limits add extra runtime constraints.

Argon2 Implementation

Inputs

Primary inputs are the message

P

(password) and nonce

S

(salt).

Secondary inputs include:

Parallelism degree

p

Tag length

τ

(desired output length in bytes)

Memory size

m

(kilobytes)

Iteration count

t

(adjusts runtime independently of memory)

Version number

v

Secret value

K

(optional key)

Associated data

X

Argon2 type

y

(0 = Argon2d, 1 = Argon2i, 2 = Argon2id)

Computation

First, hash

P

and

S

together with all other parameters; the lengths of

P

,

S

,

K

, and

X

are prefixed.

The hash function

H

is Blake2b[4].

Argon2 then fills memory with

m'

blocks, where

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

.

Memory is organized as a matrix

B[i][j]

with

p

rows and

q = m'/p

columns. The

t

-th pass processes each block as shown:

Block computation rule:

Where:

The block index

[i'][j']

depends on whether Argon2d or Argon2i is used; it may refer to any block outside the current slice.

G

is a permutation function derived from Blake2b’s round function.

H'

is a variable‑length hash built on top of

H

.

If

t > 1

, the process repeats, XOR‑ing the new block with the old one:

After completing

t

iterations, the final block

B_final

is obtained by XOR‑ing all values in the last column.

The final tag is produced by applying

H'

to

B_final

:

Features

Performance : Argon2 fills memory very quickly, increasing the area component A . Argon2i uses 2 CPU cycles per byte, while Argon2d is about three times faster.

Trade‑off Resistance : With default pass settings (Argon2d = 1, Argon2i = 3), ASICs cannot reduce the time‑area complexity even when memory is cut to α = 1/4 or less. Increasing the number of passes raises the time penalty further.

Scalability : Argon2 can scale independently in both time and memory dimensions, guaranteeing that a given amount of time always fills a given amount of memory.

Parallelism : Argon2 can use up to 2^24 concurrent threads; in experiments, eight threads already saturated all computational resources and bandwidth.

GPU/FPGA/ASIC‑unfriendly : Argon2 is heavily optimized for x86, so custom hardware does not gain speed or cost advantages.

Support for Additional Inputs : Besides the message and nonce, secret keys, environment variables, and user data can be supplied as extra parameters.

Security Analysis

Trade‑off Attack

The conclusion is that with a data‑dependent one‑pass configuration, an attacker can reduce memory by a factor of three while keeping the time‑area complexity unchanged. The relevant table is:

As stated earlier, a function must satisfy

D(α) > 1/α, α → 0

to be considered memory‑hard.

After publication, two public attacks against Argon2i were reported[5]. The authors released an updated version with the following summary:

For 1‑ and 2‑pass Argon2i (v1.3), the time‑area complexity can be reduced to

α = 1/5

.

For

t

‑pass (t > 2) Argon2i, the complexity can be reduced to

α = 1/3

.

For

t

-pass Argon2d, the complexity can be reduced to

α = 1/1.33

.

The paper contains further analyses of memory‑optimisation attacks, iteration‑compression attacks, and generic attacks, which are omitted here.

For more details, see the source code[6] and the original papers.

References

Argon2: the memory‑hard function for password hashing and other applications: https://github.com/P-H-C/phc-winner-argon2/blob/master/argon2-specs.pdf

Salted Password Hashing – Doing it Right: https://crackstation.net/hashing-security.htm

Password Hashing Competition: https://password-hashing.net/

Blake2b: https://en.wikipedia.org/wiki/BLAKE_(hash_function)

Argon2 – Wikipedia: https://en.wikipedia.org/wiki/Argon2

phc-winner-argon2: https://github.com/P-H-C/phc-winner-argon2