-2
votes
$\begingroup$

I know the problem of memory-hard password-based key derivation functions is better left to the likes of scrypt, argon2, etc...

But validated implementations of those algorithims are not always available (hell, .NET's standard library only includes PBKDF2-HMAC-SHA1). So while i was toying with password storage i came up with the following very simple, very memory-hard(?) "algorithm":


string expansionString = veryLongPseudoRandomInitializerConstant;
for (int i = 0; i < 3849; i++)
{
    passwd = GetSha384HashString(GetSha384HashString(passwd + originalpass) + GetSha384HashString(user + saltString));
    expansionString = expansionString + GetSha384HashString(passwd) + GetSha384HashString(passwd + passwd) + GetSha384HashString(passwd + passwd + passwd);
}
passwd = GetSha384HashString(GetSha384HashString(passwd) + GetSha384HashString(expansionString));
That's obviously not the complete source code (part of my effort to avoid this question being considered off-topic.), but upon running the "algorithm" with those exact parameters (it's C#) it peaked at about ~2 Megabytes (very rough estimate) of memory consumption.

This type of constuction seems way too simple to be any good, but i couldn't break it myself, so (barring the usual "don't roll your own crypto" caveat):

If the usual assumptions one makes about SHA-384 hold, how would one go about breaking this (recovering the original password without going through the complete algorithm) or even just defeating it's memory-hardness ?

$\endgroup$

locked by e-sushi Dec 3 '16 at 16:00

This question exists because it has historical significance, but it is not considered a good, on-topic question for this site so please do not use it as evidence that you can ask similar questions here. This question and its answers are frozen and cannot be changed. See the help center for guidance on writing a good question.

Read more about locked posts here.

  • $\begingroup$ Even a naive implementation that stores the whole expansionString in memory only needs $3849 \cdot 384b \approx 185kB$ for this. Much of your slowness and memory use is because you append to an immutable string, which allocates a whole new string instead of a StringBuilder. $\endgroup$ – CodesInChaos Dec 2 '16 at 11:08
  • 1
    $\begingroup$ Also your code contains a lot of pointless silly stuff, like all those variations of the password you hash. $\endgroup$ – CodesInChaos Dec 2 '16 at 11:11
  • $\begingroup$ @CodesInChaos the memory-hardness can then surely be increased by simply having more iterations...? $\endgroup$ – cipher Dec 2 '16 at 11:13
  • $\begingroup$ Even using a naive implementation it only increases slowly. Since you're usually limited by how much time you can spend on hashing (e.g. a server might limit it to 50ms, a disk encryption software to a second), you won't reach decent amounts of memory (100MB+) with code as inefficient as that. (And as my answer shows, the memory use is constant and doesn't increase with the number of iterations at all, so the point is moot anyways) $\endgroup$ – CodesInChaos Dec 2 '16 at 11:17
  • $\begingroup$ @cipher even if it did, it wouldn't do so in a way that decouples it from running time. The idea of memory-hard functions is that they can be computed quickly if you are willing to spend memory on them, or very slowly if you aren't. Are you really happy to make your user sit around for an hour while your "memory hard" KDF does a trillion iterations just so that it can meet its target 500MB memory usage? That's not solving the correct problem. $\endgroup$ – Thomas Dec 2 '16 at 11:19
6
votes
$\begingroup$

Leaving out the silly stuff, your algorithm amounts to:

$x_0=\mathrm{const}$
$m_0=\mathrm{empty}$

$x_i=h(x_{i-1}||\mathrm{password}||\mathrm{salt})$
$m_i=m_{i-1}||x_i$

$\mathrm{result} = h(x_n||h(m_n))$

You only do two things with expansionString:

  • Append to it
  • In the very end, hash it once, front-to-back.

An attacker doesn't need to store expansionString at all, they can simply update the hasher that computes hash(expansionString) incrementally, whenever you append to expansionString.

This means the whole algorithm only needs a small constant amount of memory and isn't memory hard at all.

$\endgroup$
  • $\begingroup$ The attacker would still need to store expansionString somewhere in order to be able to compute the final instance of passwd, no ? $\endgroup$ – cipher Dec 2 '16 at 11:08
  • $\begingroup$ No. They can simply update the GetSha384HashString(expansionString) hasher on the fly after each iteration, instead of first constructing the long string and hashing it. See What is the purpose of update() in popular hash APIs? $\endgroup$ – CodesInChaos Dec 2 '16 at 11:13
  • $\begingroup$ Ok, I understand that they don't actually need to have a string to store the values, but i still don't understand how they can "simply update the hasher on the fly after each iteration"...where is the attacker getting the contents of expansionString from ? (not trying to be thick, i knew my homebrew "algorithm" was most likely no good before i posted it.). $\endgroup$ – cipher Dec 2 '16 at 11:26
  • 2
    $\begingroup$ @cipher The attacker can simply run the iterated hash twice. In the first run they compute only passwd, ignoring expansionString, giving them the final value of passwd. Then knowing the prefix for the final hash they can compute expansionString iteratively like before in the second run. This only slows them down by a factor 2 and still eliminates the memory requirement completely. $\endgroup$ – CodesInChaos Dec 2 '16 at 11:44
  • 1
    $\begingroup$ You can fix that issue, simply by reversing expansionString before hashing it. But even with that fix there are attacks, that reduce memory usage to $\sqrt{n}$ while still being cheap to compute on a parallel computer. But that becomes to complex for this question. $\endgroup$ – CodesInChaos Dec 2 '16 at 11:49
1
vote
$\begingroup$

Taking a step back from CodesInChaos' excellent answer and comments, I believe your bigger-picture problem here is that you're misunderstanding the term "memory-hard function." Functions like scrypt and Argon2 are often presented to beginners in oversimplified, incorrect manner, as algorithms that use a lot of memory; but that is not the truth.

Putting this very roughly, a memory-hard function (MHF):

  • Is a function, not an algorithm. I.e., the definition of the MHF determines what's the correct output for every possible input, but does not prescribe any particular algorithm (sequence of steps) for computing it. (The definition of an MHF may be presented as a recommended algorithm, but there is no obligation for the attacker to implement it the same way.)
  • An MHF must have an adverse time-memory tradeoff. The following is an oversimplification, but it'll do:
    • The fastest algorithms for the MHF have a memory cost that's prohibitive for the attacker;
    • The most memory-efficient algorithms for the MHF have a time cost that's prohibitive for the attacker.

In real-life, it's possible to compute the same results as scrypt or Argon2 using a lot less memory than the "official" algorithms. But that's OK as long as there's a slowdown that appropriately punishes attackers who go for any memory-reduction tricks.

$\endgroup$

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