Skip to main content

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.

Filter by
Sorted by
Tagged with
6 votes
1 answer
346 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 ...
samuel-lucas6's user avatar
4 votes
0 answers
140 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 ...
user7778287's user avatar
1 vote
0 answers
121 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 ...
caveman's user avatar
  • 573
3 votes
1 answer
178 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 ...
caveman's user avatar
  • 573
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 ...
Luc's user avatar
  • 1,528
6 votes
0 answers
197 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 ...
Modal Nest's user avatar
  • 1,453
1 vote
1 answer
398 views

What does "sequential memory-hard" mean?

I found this term in Scrypt's paper. I have several questions about its meaning, ranging from how to parse it, to theoretical bounds: Q1: How to parse it? Is it read ...
caveman's user avatar
  • 573
3 votes
1 answer
70 views

Industry standard recommendations for memory usage defaults for a password hashing function?

I've been looking around for any studies done on this topic with respect to memory-hard password hashing. I'm inclined to simply impose no extra overhead by default, to be honest, but I'd really like ...
Sir Galahad's user avatar
4 votes
1 answer
1k views

"Memory-Hard" vs. "Memory-Bound" Functions?

One of the approaches in order to prevent Sybil or DoS attacks is CPU-bound PoW. However, because of the influence of Moore’s law, the memory-based approaches are suggested. As actually there are two ...
Questioner's user avatar
0 votes
0 answers
133 views

memory-hard KDF that's just a giant permutation?

Why aren't there memory-hard KDF functions that simply build a 1GB permutation and permute it? Then hash the 1GB result. For example, use a hash function (unfixed output mode) on the key+salt and use ...
user avatar
2 votes
2 answers
301 views

Optimal memory-hard KDF parameters when faced with small, slow memory

I am developing for a low-power embedded system. It has two ARM9 processors at 48 MHz each. One of the processors has access to 6 MiB of "fast" memory as well as access to 26 MiB of "...
forest's user avatar
  • 15.3k
3 votes
1 answer
82 views

Estimating difficulty of "Memory-Hard Proof-of-Work" based on "size of memory"?

In Bitcoin proof-of-work, the difficulty of Proof-of-Work is estimated and calculated based on total hashing power of the participants. If total hashing power of the participants is higher, then PoW ...
Questioner's user avatar
1 vote
1 answer
51 views

What are the approaches to private computations?

I'm talking about the ability to safely run a virtual machine on a physical device that is not trusted. It is necessary that the owner can not access the data that the virtual machine operates on. I ...
John L.'s user avatar
  • 11
6 votes
2 answers
321 views

Why do memory-hard functions rely on a time-space trade-off?

I was reading about memory-hard functions recently. In those papers I read, they almost always introduce a time-space trade-off like this: $$ S(n) \times T(n) \in \Omega(\mathrm{Poly}(n)) $$ I ...
Cyker's user avatar
  • 729
5 votes
1 answer
226 views

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 ...
ruffsl's user avatar
  • 201
24 votes
1 answer
1k views

Memory-hard password hash in practice?

Dan Boneh, Henry Corrigan-Gibbs, and Stuart Schechter have proposed Balloon Hashing: A Memory-Hard Function Providing Provable Protection Against Sequential Attacks (in proceedings of AsiaCrypt 2016). ...
fgrieu's user avatar
  • 142k
6 votes
1 answer
1k views

Is this simple memory-hard function good?

I'm trying to come up with a simple memory-hard function for a proof-of-work system to protect against spam. Is the one below secure? For a message M, append a random number R. Repeat until you find ...
Filip Haglund's user avatar
6 votes
1 answer
508 views

What is the role played by cache misses in memory-hard password hashing?

I experiment with argon2 and build a web application. In browser, I use one threaded hashing with not too much memory. I want to protect my short length input data from parallel brute-force attack. I ...
mlaci's user avatar
  • 61
1 vote
1 answer
1k views

Is there a recommendation or standard for using SCRYPT as an unbounded length KDF and not a fixed length authentication hash?

How would I go about this? I don't want to roll my own but I do really want to use SCRYPT as a KDF for several algorithms, some of which require an output length longer than the SHA-256 hash. ...
dt_slash's user avatar
  • 105
-2 votes
2 answers
367 views

Very simple, very memory-hard (?) password-based key derivation

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 ...
cipher's user avatar
  • 90
1 vote
0 answers
107 views

Fill-and-question as a proof of space

This question follows from my previous one on proofs of space. Proof of space mechanisms rely on the computation of some proof that is easy to verify and requires from the prover an arbitrary amount ...
Matteo Monti's user avatar
  • 1,417
12 votes
2 answers
302 views

Prove that you have $K$ bytes of memory

Alice has bought a brand new hard disk, $K$ (with $K \sim 10^{12}$) bytes in size. She is very happy about her purchase, and tells Bob about it. Bob claims he also bought a $K$ bytes hard disk. Alice ...
Matteo Monti's user avatar
  • 1,417
12 votes
1 answer
321 views

Minimalist memory-hard function?

What would be a minimalist memory-hard function, reasonably conjecturable to require $\approx2^k$ bits of memory per running evaluation, $k\approx32$; require $\approx2^n$ R/W accesses to $2^w$-bit ...
fgrieu's user avatar
  • 142k
7 votes
1 answer
441 views

Are coprocessors (Intel Phi) a threat for modern key stretching functions?

Modern key stretching functions (password-based key derivation functions, also used for password hashing) are memory-hard to mitigate parallel attacks, and as far as I know this is working well. Last ...
refex's user avatar
  • 221
4 votes
0 answers
92 views

Is there a sufficiently memory-hard asymmetric encryption available? [closed]

The Password Hashing Competition offers several memory-hard hashing algorithms that are aware of time memory trade-off and essentially try to make it hard for ASICs and FPGAs to brute-force hashes. ...
Oipo's user avatar
  • 41
3 votes
1 answer
168 views

Attacking Scrypt Under Access Pattern Leakage

Could cache-timing channels (such as exist for certain block ciphers) somehow be made use of in order to extract memory-access pattern information if both the attacker and user are NOT in a shared ...
McJohnson's user avatar
  • 243
6 votes
2 answers
660 views

Are there any high level memory-hard PBKDF constructions?

The PBKDF2 construction from PKCS #5 v2 has the convenient feature that it can be implemented using only standard interchangeable cryptographic primitives. Specifically, it only requires the ...
Ilmari Karonen's user avatar
11 votes
1 answer
1k views

Does a big salt have the same memory effects as Bcrypt?

Citing Thomas Pornin on the question Why can't one implement bcrypt in Cuda?: bcrypt is a variant of the Blowfish key scheduling, which is defined over a table (a few kilobytes) which is constantly ...
Luc's user avatar
  • 1,528
8 votes
1 answer
430 views

Big block cipher as memory-hard function

I'm wondering, if something like block cipher with big block size is a good memory-hard function? All memory-hard key derivation functions I've seen look more complex than that, which made me ...
LightBit's user avatar
  • 1,659
4 votes
1 answer
214 views

Memory hardness of key derivation function through XOR-ring multiple matrix values

For theoretical purposes in order to enhance my own understanding, and NOT in order to create my own cryptography, I am asking a question about the memory-hardness of a key derivation function ...
azren's user avatar
  • 751
3 votes
3 answers
562 views

Memory hard key derivation (password hash) using AES encryption

I am restricted on a certain environment involving PHP and am currently unable to implement new memory hard hashes such as scrypt (and I am not trying to compete with the likes of scrypt). My ...
azren's user avatar
  • 751
21 votes
3 answers
7k views

Memory-hard proof-of-work: are they ASIC-resistant?

Is a memory-hard proof-of-work scheme necessarily resistant to speedups from custom ASICS? Background: Bitcoin uses a proof-of-work scheme based on SHA256 hashing. The scheme is compute-bound. ...
D.W.'s user avatar
  • 36.5k
5 votes
2 answers
945 views

Memory-hard password-based key derivation functions?

How are memory hard functions designed for the purpose of password based key derivation? To protect against a brute force attack from a parallel machine. What design could work well with Skein? The ...
Brennan.Tobias's user avatar
1 vote
0 answers
74 views

Security of simple Skein PBKDF mentioned in the paper

From the Skein 1.3 paper section 4.8, Skein as a Password-Based Key Derivation Function (PBKDF), it mentions the following as a simple PBKDF (S = seed and P = password): An even simpler PBKDF is to ...
504811E's user avatar
  • 41
4 votes
2 answers
445 views

Memory-expensive hash from an array of hashes?

Why can't people make a hash function that requires dozens of mega bytes of memory instead of cpu to avoid all the cracking and hacking? What I have in mind myself is this: We have an input $X$, we ...
Behrooz's user avatar
  • 143