0
$\begingroup$

Why aren't there memory-hard KDF functions that simply build a 1GB permutation and permute it? Then hash the 1GB result. For example, use a hash function (unfixed output mode) on the key+salt and use the output to populate the starting state of the permutation.

If you go crazy with the permutation by sacrificing side channel resistance you can make it extremely GPU or even ASIC unfriendly (use a lot of operations that would make such an ASIC resemble a CPU and not be much better).

Since some clarification was requested, let the permutation have a Feistel cipher component (in addition to something else that would provide it known cryptographic strength) that would use a lot of data-dependent branching which would require speculative execution for performance and utilize/stress other circuits found in a CPU - for example slice the 1GB chunk into 128 bits and do an AES round as an additional non-linearity in the permutation.

Then perhaps each round perform a hash of the permutation state and have the hash bits determine parameters in the algorithm of how to do the next permutation.

I think the idea is clear, just make sure that throughout the process there would be a structure present that would follow common cipher design principles of diffusion and confusion - which for a 1GB block of data would require a lot of rounds, but that's alright since we are dealing with a KDF that aspires to be memory-hard and also compute intensive.

| improve this question | |
$\endgroup$
  • 1
    $\begingroup$ I think you need to explain your question in more detail, but a preliminary answer would be that just because you have an algorithm that implements a 1GB permutation doesn't mean there isn't an alternative implementation that uses a lot less memory, at the cost of more time (the so-called time-memory tradeoff problem that memory-hard functions have to cope with). $\endgroup$ – Luis Casillas Nov 26 '19 at 22:36
  • $\begingroup$ A permutation is just to go from one value in a (giant) map to another. If you are talking about e.g. the construct in a block cipher then it will require an enormous state. If that's slow on a CPU (which it likely is) then it might be faster on specific hardware designed for it, and that doesn't sound like a good idea to me. I have to agree though, unless more detail is added this question is very broad; so please add more detail about the permutation without requiring a full scheme that requires crypt-analysis. $\endgroup$ – Maarten Bodewes♦ Nov 26 '19 at 23:02
  • $\begingroup$ @LuisCasillas Since the permutation is expected to adhere to the avalanche criterion (sensitivity to initial conditions) I don't see how it would be seen as reasonable to afford the time-memory tradeoff in this instance, the compute required should scale exponentially with the rounds. $\endgroup$ – user74730 Nov 27 '19 at 0:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy