# Memory-hard operations in work-factor hash functions

I'm playing around with work-factor hash functions, and I'm looking for a memory-hard operation to make it resistant to GPU / parallel hardware attacks. I considered a very large (i.e. 64K) s-box that gets shuffled based on the state per round, but I have a feeling that there are ways to optimise such an operation for minimal memory usage.

My current best scheme is as follows:

state = pass
while(length(state) < 32768)
{
state += sha512(state);
}


Is such a scheme guaranteed to require a lot of memory, or can it be optimised? I know there are tricks to reduce memory usage when computing hashes. Are there other simple operations that provide such guarantees?

-
any reason for not using scrypt? – CodesInChaos May 24 '12 at 22:04
@CodeInChaos I am using scrypt, in my production code. This is just something I'm playing with out of interest, to see how I might go about creating a memory-hard hash function. – Polynomial May 24 '12 at 22:06

The pseudocode you are showing here is not "memory-hard" - one can recreate the long sbox from the short "pass" when needed, by only 512 SHA-512 calls.

These calls are of increasing input length (i.e. need more time), but even this can be cut short by conserving part of the hash state during the loop (as SHA-512 is an iterative hash function and not a random oracle), allowing to calculate the result in $O(n)$ time ($n$ being the output length, in your case 32768). This shortcut can be removed by appending the new hash result in front instead of at the end (or by another kind of shuffling between the rounds of your loop), but there might be other ones I can't think of right now.

Also, 64 KB of memory is not "very much" - you would need (scalable) many of those S-boxes which all are accessed (and changed) often, to be memory-hard.

-
So state = sha512(state) + state would work? – Polynomial Jul 23 '12 at 18:47
At least it would not have this "length extension" weakness I found, but of course I can't guarantee there won't be any other ones. – Paŭlo Ebermann Jul 23 '12 at 19:44