5
$\begingroup$

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.

Additionally in the introduction:

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.

enter image description here https://www.desmos.com/calculator/rpjseuy0sj

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?

$\endgroup$
  • $\begingroup$ You don't mention the existence of argon2 or balloon hashing at all, is there some reason those are unsatisfactory? $\endgroup$ – Ella Rose Feb 7 '18 at 21:49
  • $\begingroup$ 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?) $\endgroup$ – Paul Uszak Feb 8 '18 at 3:11
  • $\begingroup$ @PaulUszak The word you were looking for is spelled "parallelizable". $\endgroup$ – e-sushi Feb 8 '18 at 4:23
  • $\begingroup$ 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? $\endgroup$ – b degnan Feb 8 '18 at 21:26
1
$\begingroup$

I had been thinking of this question for quite a time, but without a satisfying answer: it seemed to be a problem that had never really been considered in the literature (at least, not in the theoretical cryptography community).

Incidentally, I was just checking the ePrint archive this morning, and stumbled upon this paper which was added today to the archive, which focuses exactly on your question. It introduces a new complexity measure that accounts for the fact that time-memory trade-off do not scale linearly with respect to the hardware cost. I've not read it in details yet (I plan to), but the authors are among the leading researchers on memory-hard functions (subsets of the authors developed the theoretical model for analyzing MHFs, described the best known attacks on Argon and Balloon, gave new constructions, and proved the maximal memory hardness of Scrypt). It should be worth reading.

$\endgroup$
  • $\begingroup$ Awesome! I'll take a look. This reminds me of the Indifference Curve in economics, where in the scenario we'd like to prevent perfect complements of memory and compute power for attackers existing near the origin, perhaps even making it bow outwards instead. $\endgroup$ – ruffsl Feb 9 '18 at 23:08

Your Answer

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

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