Skip to content

Instantly share code, notes, and snippets.

Last active Dec 20, 2015
What would you like to do?
function LoginHash(string password, byte[] salt, int memSize, int queryCount, int maxParallelism)
return KDF(password, salt, memSize, queryCount, maxParallelism, "LoginVerification", 16)
function KDF(string password, byte[] salt, int memSize, int queryCount, int maxParallelism, string info, int outputSize)
masterKey = ComputeMasterKey(password, salt, memSize, queryCount, maxParallelism)
return HKDF-Expand(masterKey, info, outputSize) // For short outputs this is simply HMAC-SHA-256(masterKey, info || 0x01).Truncate(outputSize)
function ComputeMasterKey(string password, byte[] salt, int memSize, int queryCount, int maxParallelism)
requires memSize mod 16 = 0
requires memSize > 0
requires queryCount > 0
inputKey = HMAC-SHA-256(salt, Utf8Encode(password)) // HKDF-Extract
for i = 1 to maxParallelism
key = HMAC-SHA-256(inputKey, "Key" || i)
partialHash[i] = Core(key, memSize, queryCount)
return HMAC-SHA-256(inputKey, "Out" || partialHash[1] || partialHash[2] || ... || partialHash[maxParallelism])
function Core(byte[32] key, int memSize, int queryCount)
streamKey = key[0, 16]
queryKey = key[16, 16]
// expansion phase
data = AES-OFB(key=streamKey, iv=0, outputSize=memSize)//identical to encrypting 0x00 bytes with AES-CBC or AES-CFB
// query phase
state = data[memSize-16, 16]
for i = 1 to queryCount do
queryIndex = state.First63Bits mod (memSize/16)
state = Last16Bytes(AES-CBC-Encrypt(key=queryKey, iv=state, input=data[queryIndex*16, 16]))
return state
A hash I designed a couple of months ago:
* Time/memory trade-offs are harmless as long as Time*Memory can't be decreased
* Time/parallelism trade-offs are bad once parallelism exceeds defender's maximum parallelism
* The basic construction is similar to scrypt, but the primitives are different
* Reuse existing schemes, like AES-CBC, SHA-256, HMAC and HKDF
* AES is fast is software when AES-NI is present
* ~128 bit security is enough, you typically only apply stretching to low entropy inputs like passwords. But hashing the original key together with the output of the strengthening operation avoids reducing entropy to 128 bits for strong passwords.
* Well defined character encoding: UTF-8
* When used as a KDF large outputs doesn't cause multiple invocations of the expensive part (unlike PBKDF2)
* Like in scrypt, only the query phase is supposed to be memory-hard. The expansion phase suffers from the same attacks as scrypt's expansion
* Random access to elements could enable cache timing attacks, but I don't think those are a big issue in practice, especially with unknown salts. But all schemes with predictable memory access I know are much weaker than scrypt.
* I'm not happy with how it treats parallelism and the attackable first phase isn't nice either. I hope to improve on those in a future version.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment