Questions tagged [memory-hard]
Memory-hardness is a property that, if proven to be possesed, makes an algorithm "immune" to time-memory tradeoffs, by "punishing" memory reductions. Usually algorithms possesing this property can't easily be computed with significantly less memory than intended by the author without accepting a severe performance penalty. This property is often used to counter ASICs and FPGAs for password-hashing.
44 questions
1 vote
1 answer
125 views
Assess this TMTO resistance strategy for a KDF's LUT (Look Up Table) [closed]
So the challenge with memory-hard KDFs is to have a large - preferrably tunable - piece of data that should be stored in memory in its entirety for the duration of the computation, thereby taking up ...
- 21
1 vote
0 answers
55 views
How do side channel attacks on memory hard key derivation work?
Is it solely by exploiting that accessing a given memory address depends on its location? E.g. column hit? Or is it just the CPU cache pre-fetching? Or is it something else (or more)? Also, how ...
- 721
1 vote
1 answer
68 views
How is pseudo-randomly key-independently picked dependencies better than a sequential arithmetic order one?
In Balloon, a salt is used seed a CSPRNG that picks dependency blocks pseudo-randomly. This salt is obviously not a secret, and an adversary can know that it would pick a given sequence. For example, ...
- 721
2 votes
0 answers
96 views
What's the current state of password bruteforcing ASICs in relation to memory hard key derivation functions?
Even though this sounds hardware related, it's essential to understand the actual security one obtains from memory hard key derivation functions, such as Balloon, as its strongest security guarantee ...
- 721
1 vote
1 answer
89 views
What does Balloon's theorem really mean?
Balloon's theorem says: Questions: Am I understanding the variables correctly? $n$ is number of blocks the user chooses. $r$ is number of rounds the user chooses. $\delta$ is number of pseudorandom ...
- 721
2 votes
1 answer
174 views
What's the use of the `delta` parameter in Balloon's hash?
The image below shows Balloon's pseudo code from its paper, and relevant parameters to my question is delta. Question: What is its impact on memory hardness?
- 721
2 votes
0 answers
60 views
Is there any quantum memory hard key derivation?
Current memory hard key derivation techniques rely on functions that allow for serialisation on tiny memory, except for requiring a quadratic time penalty. But, with Quantum's light-speed defying ...
- 721
2 votes
0 answers
90 views
Is parallelism really useful for memory-hard key derivation functions?
Argon2 has a parallolism parameter, that basically works like this: In a given pass, threads work alone, independent of other threads. Within this pass, there isn't much memory-hardness, as each ...
- 721
5 votes
1 answer
166 views
Should the salt be used for data-independent memory access in password hashing algorithms?
For password hashing, is it better to compute a pseudorandom data-independent memory access pattern using the salt, the cost parameters (memory size, iterations, and parallelism), or some other way? ...
- 2,270
6 votes
1 answer
622 views
Cache-hard or memory-hard password hashing algorithms?
bscrypt is a cache-hard password hashing algorithm/KDF from Steve Thomas (aka Sc00bz/TobTu), who was on the Password Hashing Competition (PHC) panel. He argues it is better than the alternative ...
- 2,270
5 votes
0 answers
168 views
Are Memory-Hard Functions de-facto quantum resistant?
Searches have returned absolutely no results on this question. With that in mind, I assume the answer is either painfully obvious ('of course quantum computers get no advantage when it comes to ...
- 160
1 vote
0 answers
147 views
Memory-hard key derivation algorithm where all requested memory is needed at every time moment
Background. All MKDF (memory-hard KDF) algorithms that I know (Scrypt, Argon2, Balloon) don't really require all the memory at every moment during the run time of algorithm's implementation, but ...
- 721
3 votes
1 answer
240 views
What's the ideal memory hard function?
This says $f_n$ is memory hard if, for any space $S$ and time $T$, $S\cdot T \in \Omega(n^2)$. My questions: What is $S$? Space? E.g. bytes of available memory? What is $n$? Bytes of requested ...
- 721
6 votes
1 answer
2k views
Why does the GPU get a comparatively bigger advantage to the CPU when using higher parallelism in Argon2id?
My understanding is that the memory bandwidth of CPUs and GPUs is roughly one order of magnitude difference4, unlike cores which a GPU has many of and a CPU a handful. That is why PBKDF2-HMAC-SHA1 ...
- 1,558
6 votes
0 answers
225 views
Is Argon2 "sequential memory hard"?
The Scrypt paper here defines memory-hard and sequential memory hard functions as follows: Definition 1. A memory-hard algorithm on a Random Access Machine is an algorithm which uses $S(n)$ space and ...
- 1,473