Simple password KDF. Parallelizable. Efficient in high-level languages.

cbckdf.py

#!/usr/bin/env python
"""
Experimental password KDF using AES256-CBC.
Written by Trevor Perrin.
Hereby placed in the public domain.
Thanks to Joe Bonneau and Marsh Ray for feeback.

Requires pycrypto.  Try "easy_install pycrypto".

Ex:
  P = 2
  M = 64 * 1024
  I = 300
  salt = os.urandom(16)
  output = cbckdf(P, M, I, salt, "password")

Runs 2 parallel loops.  Each allocates a 64 KB buffer of zeros, and encrypts
its buffer 300 times using AES256-CBC.  For the first encryption the key is
HMAC-SHA256(salt, password).  The last 32 bytes of the buffer are copied as
the new key for subsequent encryptions.  After all loops are finished, the 
encryption keys are XOR'd into an output key.
"""
import hmac, hashlib, os, sys, time, binascii
from Crypto.Cipher import AES

def encrypt(key, iv, buf):
    "Encrypts buf with AES256-CBC and no padding"
    key, iv, buf = bytes(key), bytes(iv), bytes(buf)
    output = AES.new(key, AES.MODE_CBC, iv).encrypt(buf)
    return bytearray(output)


def cbckdf(P, M, I, salt, password):
    """
    Input:
        P         : Parallel loops count (<= 65535)
        M         : Memory buffer size for each loop (multiple of 16, >= 32)
        I         : Iterations for each loop
        salt      : 16 randomly-chosen bytes
        password  : arbitrary length password

    Output:
        32 byte key
    """
    assert(M % 16 == 0 and M >= 32 and len(salt) == 16)
    k = hmac.new(key=salt, msg=password, digestmod=hashlib.sha256).digest()
    kout = bytearray(32)               # Output key : 32 bytes of zeros
    iv = bytearray(16)                 # 16 bytes of zeros
    for p in range(P):                 # P parallel loops
        buf = bytearray(M)             # M bytes of zeros
        iv[0] = p / 256                # Encode p in IV to differentiate loops
        iv[1] = p % 256
        for i in range(I):             # I loop iterations
            buf = encrypt(k, iv, buf)  # CBC-encrypt the buffer
            k = buf[-32:]              # Rekey with last 32 bytes
        for x in range(32):
            kout[x] = kout[x] ^ k[x]   # XOR key into the output key
    return kout

# Run with 'cbckdf.py <P> <M>["M"|"K"] <I> <password>' for timing
# E.g. "cbckdf.py 2 64K 300 password"
if __name__ == "__main__":
    salt = binascii.a2b_hex("000102030405060708090a0b0c0d0e0f")
    P = int(sys.argv[1])
    mem = sys.argv[2]
    memFactor = 1
    if mem[-1].upper() == 'K':
        memFactor = 1024
        mem = mem[:-1]
    elif mem[-1].upper() == 'M':
        memFactor = 1024 * 1024
        mem = mem[:-1]
    M = int(mem) * memFactor
    I = int(sys.argv[3])
    password = sys.argv[4]
    t1 = time.time()
    output = cbckdf(P, M, I, salt, password)
    elapsedTime = time.time() - t1
    mbProcessed = P * (M / 1048576.0) * I
    print("Salt   : %s" % binascii.b2a_hex(salt))
    print("Output : %s" % binascii.b2a_hex(output))
    print("Time   : %.2f" % elapsedTime)
    print("MB/sec : %.2f" % (mbProcessed / elapsedTime))

August 6, new version: Removed the variable-length-output feature. It was distracting and inessential. Now just return 32 bytes.

August 21, new version: removed zeroization of the part of the buffer containing the key, it was pointless.