10

So in general, isn't this equivalent to what Bcrypt and PBKDF2 do in terms of password storage security? PBKDF2, yes, pretty much. The only real difference is that salt/password are used the other way around, with the password mixed in at every step. Bcrypt, however, is different. In your case an attacker only needs a small amount of memory compared to ...


8

What prevents an attacker from building a custom ASIC and buying off-the-shelf DRAM chips, and building systems that pair each ASIC with a DRAM chip? DRAM memory is already pretty optimized for random memory accesses per second per dollar. Since a memory bound PoW spends more time waiting for memory than doing computation, there's little point in using an ...


7

Yes, the argument is largely correct. A good memory-hard proof-of-work scheme can be fairly resistant to speedup using ASIC, if designed around a good primitive like Argon2 and parametrized appropriately; in particular, having a large fraction of its cost spent in un-cacheable accesses to enough memory that DRAM is the only economical choice for that. The ...


7

Memory-hard proof-of-work: are they ASIC-resistant? Theoretically, the answer is a clear “no”. Given enough resources (read: invested time and money) and the appropriate knowledge (ASICs don’t grow on trees, they have to be designed) all currently known and/or published “memory-hard PoW” solutions could be rendered into futile efforts. But theory ends ...


6

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 ...


6

There has been a huge amount of work on related questions in the past years. As Thomas Prest mention, this problem was considered for memory-hard function, which provably (in some idealized models) require some amount of space to be evaluated. However, MHF alone are only the weakest primitive of this kind; many primitives have been designed that enhance ...


5

In order to create such a function you fill up memory with results of some computation; the memory-hard function then reads these values to further the computation later on. Rather than saving the values, one could theoretically re-calculate them when needed. So the memory is not really a hard requirement. The memory hard functions are however build in such ...


5

TL;DR: No, this is not memory-hard and may not even be as computationally intense as you would have thought. Suppose we have a hash function $H:\{0,1\}^*\to\{0,1\}^n$, for example SHA-256. Now we can construct $H':\{0,1\}^*\to\{0,1\}^n:m\mapsto H(M\parallel m)$ for some fixed, pre-defined message $M$ and where $\parallel$ denotes concatenation. Note how $H'$...


5

The key idea of memory-hard functions like scrypt and Argon2, as I understand them, is to analyze the cost to the attacker in terms of a time-area product. Time is how much time the attacker spends. Area is how much silicon they use for the attack. The attacker is going to allocate a given area, but once that amount is fixed: More cores means less memory ...


5

Are there any memory-hard PBKDF constructions that can be implemented using only common standard crypto primitives, like (generic) hash functions and/or block ciphers? Of course there is one, and it even got a "special recognition" at PHC: Catena. I won't go into the details of Catena here (the paper does it much better on its 50+ pages), but it comes ...


4

I've been toying around with your function, and I've come to the conclusion it's not memory hard. The amount of required memory can be reduced to at maximum digestsize * 3 * rounds. The first problem is that the entropy does not avalanche throughout the state, but stays localized. For example, after 1 round the state of the 2nd block only depends on the ...


4

Collisions are not much of a concern, since you have to compute them to know they happen, and assuming your values are a typical hash size (256+ bits) they will never happen randomly anyway. But yes, having identical computation that use the same data is wasteful if you don't store the intermediate values. However, the main problem your function has is that ...


3

Memory hard functions are designed so that the internal calculations rely on a relatively large state. The functions should not have shortcuts that allow an adversary to calculate the result without using of the state at once (at least not without incurring a very high overhead). That way it is impossible for fast hardware to be developed that does not ...


3

The premise that people cannot make a memory intensive password hashing function is incorrect. scrypt does approximately what is described in the question. Of course you still want to limit the amount of memory, especially if many of these hashes are to be calculated in parallel. Furthermore, you could have a look at the password hashing competition where ...


3

I see at least one way of doing what you want to do: memory-hard functions. Alice just needs to store a value $m$ and its hash $H(m)$, where $H$ is a memory-hard function and where the parameters are scaled so that you cannot compute $H(m)$ unless you are above a certain memory threshold. See e.g. this article which provides a provably memory-hard hash ...


3

Tentative answer to my own question. Please criticize! All variables in capital are one 128-bit word, with $w=7$. Parameters are as in the question, and $k-4\le n\le128$. I use an auxiliary arbitrary public permutation $\large\mathscr P$ of one word; a simplistic one is constructed using Addition-Rotation-Xor. A function evaluation goes: set $D$ to the ...


3

Your key derivation function is not particularly memory hard. The second loop walks the array in order, so an optimized implementation which an attacker would use can avoid the whole array, keeping only some elements in memory at a time. For example, you can halve the memory use by only storing the second half of M initially. Then for the first N/2 ...


2

An alternative which appeared after the password hashing competition is Balloon hashing. It can use any standard cryptographic hash function as it's only crypto primitive; all other operations are simple concatenations or XOR which can be done in almost any high level language. I've even implemented it in Microsoft T-SQL using the HASHBYTES() function with ...


2

The signature for scrypt, straight from the source: /** * crypto_scrypt(passwd, passwdlen, salt, saltlen, N, r, p, buf, buflen): * Compute scrypt(passwd[0 .. passwdlen - 1], salt[0 .. saltlen - 1], N, r, * p, buflen) and write the result into buf. The parameters r, p, and buflen * must satisfy r * p < 2^30 and buflen <= (2^32 - 1) * 32. The ...


2

The measure of resource typically used to evaluate memory-hard functions is not the amount of work (i.e., $T$-complexity) but rather the space-time complexity (i.e., $ST$-complexity) of the computation. As the name suggests, it is the product of the maximum amount of space used and the time taken for the computation. (Strictly speaking, we have to also take ...


2

It is true that many memory-hard functions (MHFs) only give a time-space tradeoff. Take the example of scrypt, which was proven to have optimal cumulative memory complexity $\Omega(n^2)$ in: Joël Alwen and Binyi Chen and Krzysztof Pietrzak and Leonid Reyzin and Stefano Tessaro: Scrypt is Maximally Memory-Hard. Eurocrypt 2017 Cumulative memory complexity ...


1

Your goal is to minimize the hash rate of the attacker based on the resources you have. The cracker's goal is to maximize their hash rate. Find out what parameters work well for your hardware. Pick a few variants. (More passes with less memory, as much fast memory as possible with as many passes as that permits, as much slow memory with however many passes ...


1

It depends. There is no answer that is the only right one. Increasing the memory for Argon2 increases also time needed to process it. Test your system, what is the correlation. May be increasing memory usage 2x will reduce the performance not 2x but 6x or 10x. It depends on design/architecture of your system. Namely, do you need to use Argon2 in every ...


1

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 ...


1

I understand, using large memory (1GB or greater) prevent parallelism, because of the cost. I would like to support mobile and older browsers, so I use 16MB or 32MB memory maximum. This is true, but 32mb memory is fairly safely OK for most applications. Is it because my benchmarks wrong or is not generate a lot cache misses I thought or cache misses not ...


1

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 ...


1

Unless a fast AES is available on the combination of CPU and PHP instance being used (that is, something built with AES-NI), I strongly advise against using AES as the basis of entropy stretching. Number-1 rule in designing an entropy-stretching function is that it should put to the best possible use the computational resources available to the legitimate ...


Only top voted, non community-wiki answers of a minimum length are eligible