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:

• The Makwa specification 1.0.
• The original Makwa PHC submission package.