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 scheme is as follows:

state = sha512(message);
salt = sha512(salt);
for(int i = 0; i < 4096; i++)
{
  state ^= hmac_sha512(state, salt);
  state ^= hmac_ripemd256(state, salt);
  state ^= hmac_salsa20(state, salt);
}
return sha512(state);

The idea was to modify this to something like:

state = sha512(message);
salt = sha512(salt);

sbox = array(65536);
for(int i = 0; i < 65536) sbox[i] = i % 256;

for(int i = 0; i < 4096; i++)
{
  if(i % 64 == 0) shuffle(sbox, state); // shuffle sbox based on state
  state ^= hmac_sha512(state, salt);
  state ^= hmac_ripemd256(state, salt);
  state ^= hmac_salsa20(state, salt);
  for(int n = 0; n < 63; n++)
    state[n] = sbox[state[n]*256 + state[n+1]];
}
return sha512(state);

Is such a scheme guaranteed to require a lot of memory, or can it be optimised? Are there other simple operations that provide such guarantees?

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?