Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

0
votes
1answer
40 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 ...
6
votes
2answers
143 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 ...
5
votes
1answer
139 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 ...
14
votes
0answers
444 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). ...
6
votes
1answer
709 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 ...
7
votes
1answer
248 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 ...
1
vote
1answer
230 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. ...
-3
votes
2answers
283 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 ...
1
vote
0answers
84 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 ...
12
votes
2answers
215 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 ...
12
votes
1answer
242 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 ...
7
votes
1answer
297 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 ...
4
votes
0answers
72 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. ...
3
votes
0answers
88 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 ...
6
votes
2answers
268 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 ...
10
votes
1answer
951 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 ...
6
votes
1answer
353 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 ...
4
votes
1answer
152 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 ...
3
votes
3answers
376 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 ...
17
votes
3answers
5k 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. ...
3
votes
2answers
358 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 ...
1
vote
0answers
57 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 ...
4
votes
2answers
223 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 ...