7
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ any reason for not using scrypt? $\endgroup$
    – CodesInChaos
    Commented May 24, 2012 at 22:04
  • 1
    $\begingroup$ @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. $\endgroup$
    – Polynomial
    Commented May 24, 2012 at 22:06

1 Answer 1

Reset to default
6
$\begingroup$

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 (scalably) many of those S-boxes which all are accessed (and changed) often, to be memory-hard.

Improve this answer
$\endgroup$
2
  • $\begingroup$ So state = sha512(state) + state would work? $\endgroup$
    – Polynomial
    Commented Jul 23, 2012 at 18:47
  • 1
    $\begingroup$ 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. $\endgroup$
    – Paŭlo Ebermann
    Commented Jul 23, 2012 at 19:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.