# Makwa

**News (2015-07-20):** The
Password Hashing Competition
has selected a winner and four "special recognitions", one of which
being Makwa. Makwa was the only PHC candidate to offer support for
delegation.

**News (2015-05-18):** Optimized implementations on
GPU (AMD Radeon HD 7990 with OpenCL) and CPU (using AVX2 opcodes) have
been benchmarked. The report is available
here, along with the
OpenCL source code.

**News (2015-04-22):** A new specification (1.1) and PHC
submission package have been published. The Makwa function itself has
not changed; the new package includes code and description for alternate
delegation methods that offer "information theoretic" security (at a
cost).

## What is Makwa ?

Makwa is a *password hashing function*. It is a hash function
dedicated at processing passwords into tokens for password verification
purposes, and exanding them into symmetric keys appropriate for
symmetric cryptographic algorithms.

Makwa has been submitted as candidate to the Password Hashing Competition.

Makwa's selling point is its support for *delegation*.

## What is delegation ?

Password hashing functions try to cope with the inherent weakness of passwords: since passwords are chosen and remembered by humans, they tend to be guessable by enumerating possible passwords (that's called a "dictionary attack"). Good password hashing functions strengthen passwords by applying two tricks:

- An extra input called
*salt*is used. The salt is not secret, but a new one is used for each password hashing instance. Salts prevent cost-sharing by attackers, in particular use of precomputed tables. With salts, so-called "rainbow tables" are no longer to be feared. - The function is made arbitrarily expensive by using, for instance,
numerous internal iterations. The computational cost of the function
is adjusted through a configurable
*work factor*.

The problem with making the function expensive is that it becomes
expensive for *everybody*. We want to make it as expensive as
possible for the attacker, but not too expensive since the defender must
also use it on a regular basis, e.g. to verify the passwords of
connecting users. Higher work factors increase the bill on the
defender's side, and make it more vulnerable to Denial-of-Service
attacks. The password security then becomes an arms race between the
attacker and the defender; the defender will try to get faster servers
in order to allow for a higher work factor.

**Delegation** is a way to enlist other systems for the
bulk of the processing cost, but *without trusting them*. When
delegation is possible, then higher work factors, hence higher security,
can be used, by enlisting extra systems, e.g. rented cloud-based systems
or even other connected clients.

## How can delegation be applied to a password hashing function ?

Delegation cannot be simply applied to any arbitrary password hashing
function; it takes *mathematics*. Makwa offers support for
delegation through its internal algebraic structure.

In a nutshell: the core of Makwa is repeated squarings modulo a Blum integer (a specific kind of RSA modulus). Delegation can then be done with techniques similar to RSA blind signatures.

## Pseudocode for Makwa

# *** Functions/symbols *** # || Concatenate two strings # len(string) Byte length of a string # len(bigint) Byte length of a big integer (unsigned) # square_mod Modular squaring # STR_TO_BIGINT_BE Convert a string to a bigint (big-endian, unsigned) # BIGINT_TO_STR_BE Encode a bigint into a string (big-endian) with a definite output length # BYTE(integer) Encode an integer into a string of exactly one byte # HMAC(h, k, v) Compute HMAC with hash function h and key k over value v # trunc(m, j) Truncate string m to its first j bytes # *** Inputs *** string password string salt integer m_cost boolean pre_hashing integer post_hashing_length # *** Parameters *** # These parameters are supposed to be server-wide. bigint modulus # a Blum integer (product p*q, p = 3 mod 4, q = 3 mod 4) function h # a hash function, e.g. SHA-256 # *** Algorithm *** if m_cost < 0 return ERROR k = len(modulus) if k < 160 return ERROR # Pre-hash input password (optional) if pre_hashing password = KDF(password, 64) # Salt-derived padding for password u = len(password) if u > 255 OR u > (k - 32) return ERROR sb = KDF(salt || password || BYTE(u), k - 2 - u) xb = BYTE(0x00) || sb || password || BYTE(u) # Main loop: repeated modular squarings. x = STR_TO_BIGINT_BE(xb) for i = 0 to m_cost x = square_mod(x, N) out = BIGINT_TO_STR_BE(x, len(N)) # Post-hashing (optional) if post_hashing_length > 0 out = KDF(out, post_hashing_length) # Finish return out # *** Helper function *** KDF(data, out_len) r = output length of h() in bytes V = BYTE(0x01) || BYTE(0x01) || ... || BYTE(0x01) # such that len(V) = r K = BYTE(0x00) || BYTE(0x00) || ... || BYTE(0x00) # such that len(K) = r K = HMAC(h, K, V || BYTE(0x00) || data) V = HMAC(h, K, V) K = HMAC(h, K, V || BYTE(0x01) || data) V = HMAC(h, K, V) T = empty while len(T) < out_len V = HMAC(h, K, V) T = T || V return trunc(T, out_len)

(That pseudocode can also be found on the PHC wiki.)

## Downloads

- The Makwa specification (1.1).
- The Makwa PHC submission package (1.1) (includes the specification, reference implementations in C and Java, supporting tools, and test vectors).
- The slides for the presentation at Passwords14 Las Vegas (on August 6th, 2014).
- The Report on optimizing Makwa on GPU and CPU and its accompanying OpenCL source code.

Older versions: