User Tools

Site Tools


makwa

Makwa

Designer

  • Thomas Pornin

Download Submission

Strengths

  • Supports password hashing delegation
  • Server-specific shortcut
  • Server relief

Pseudocode

# *** 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)

Pseudocode written by Thomas Pornin, designer of Makwa.

makwa.txt · Last modified: 2014/05/26 09:48 (external edit)