# Making attacks on password hashes less economical

Perhaps an abstract question on complexity given the trade offs between memory vs runtime, I was wondering if it's possible to constrain only either extremes approaches to be optimally efficient, thus making attacks on hashes less economical.

### Background

I attended a seminar on recent publication, Scrypt is Maximally Memory-Hard 1, where the authors focus on scrypt, a simple candidate Memory-hard function (MHF) designed by Percival, and described in RFC 7914.

From the abstract:

We prove that scrypt is optimally memory hard, i.e., its cumulative memory complexity (cmc) in the parallel random oracle model is $\Omega(n^2 \cdot w)$, where $w$ and $n$ are the output length and number of invocations of the underlying hash function, respectively.

In this work, in Section 5, we also prove an optimal $\Omega(n^2 \cdot w)$ lower bound on the parallel cumulative pebbling complexity for a game which abstracts the evaluation of scrypt: we consider a path of length $n$, and an adversary must pebble $n$ randomly chosen nodes on this graph, where the ith challenge node is only revealed once the node of challenge $i − 1$ is pebbled. This already gives an optimal $\Omega(n^2 \cdot w)$ lower bound on $cc_{mem}$ for scrypt for adversaries who are only allowed to store entire labels, but not any functions thereof.

From my understanding, it would be possible for an adversary to formulate a strategy that is a suitable compromise between memory and runtime complexity, e.g. where pebbles for $X_0, X_1, \dots , X_{n−1}$ are stored for only the even $i$, thus halving the worst case memory usage, while also having the worst case runtime, but yet leaving the total memory·time cost the same as before.

### Question

For a single system, I'd say hardware cost is nonlinear with respect to CPU performance or size of onboard memory, i.e components representing the extreme of either spectrum may be exponentially more expensive. Thus to lessen the rate of return or increase the necessary capital investment an attacker would expect, we might like to mitigate the usability of midrange hardware that would otherwise be the most economical to use.

To visualize my rudimentary thoughts, I've included a crude graph below, where x and y axis are memory and time usage. The volume of the orange rectangle intersecting the purple line at the green point represents the total memory·time cost for any configuration, e.g. if you had sufficient memory one could compute the hash in $\frac{1}{2}$ time units. I was wondering if a problem could be formulated such make the memory·time cost follow the red curve instead, thus pushing an adversary further towards hardware extremes to achieve optimal memory·time costs while to the detriment of hardware cost.

Perhaps there are studies some of you may know that touch on optimal efficient outcomes from an economic standpoint, i.e. considering hardware investment, operational costs, expected return per solution. I guess this sounds like a miners optimization problem when working with crypto currencies that require proof of work, but I'm slightly more interested in the economics the motivate attackers or scammers.

@misc{cryptoeprint:2016:989,
author = {Jo\"el Alwen and Binyi Chen and Krzysztof Pietrzak and Leonid Reyzin and Stefano Tessaro},
title = {Scrypt is Maximally Memory-Hard},
howpublished = {Cryptology ePrint Archive, Report 2016/989},
year = {2016},
note = {\url{https://eprint.iacr.org/2016/989}},
}


## Basically

Are there any functions that render a linear combination of memory or runtime approaches less efficient than committing solely to either a memory or compute speed optimizations, thus always making midrange hardware unsuitable for profitable attacks?

• You don't mention the existence of argon2 or balloon hashing at all, is there some reason those are unsatisfactory? – Ella Rose Feb 7 '18 at 21:49
• Hey, have you seen crypto.stackexchange.com/q/20675. It's not hard to make an algorithm that requires MB or even GB of RAM, can take ages to run and is not paralliseabley (how do you spell it?) – Paul Uszak Feb 8 '18 at 3:11
• @PaulUszak The word you were looking for is spelled "parallelizable". – e-sushi Feb 8 '18 at 4:23
• i can get 4GiB on die so the economic questions are a real consideration, but money is a practical solution. do you have a boundary for this? – b degnan Feb 8 '18 at 21:26