Is this simple memory-hard function good?

Question

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 R1, R2 such that sha256(M++R1) and sha256(M++R2) share at least d binary digits. R1, R2 is the proof of work, which is sent along with the message. Replace sha256 with any cryptographic hash function you'd like.

I'm assuming this function is memory-hard since you'd want to store all R and their corresponding hash to increase the likelyhood of a match. If you don't store them all, you decrease the probability of a match, which saves memory, but requires more cpu time on average. Also, only storing a part of a hash, like the first half of each hash, should save memory but decrease the probability of a match by orders of magnitude.

Is there an obvious flaw in this algorithm? Is this a known algorithm? Is there a standard algorithm that is roughly as simple to implement?

Answer 1

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'$ is a normal hash function.

Now the task is to find $r_1\neq r_2$ such that $\Delta (H'(r_1),H'(r_2))\leq n-d$ for some work-factor $d$ with $\Delta(\cdot,\cdot)$ denoting the Hamming-Distance. If you have such $r_1,r_2$, this is called a near-collision with a difference of $k:=n-d$.

Now note that for $d=n$ this equals having to find a collision on $H'$, which can be done in time $2^{n/2}$ with negliglible memory. The algorithms for this are Floyd's cycle finding (to see that it can actually be done with negligible memory) and Pollard-$\rho$ (which is state-of-the-art and descriptions can be found in this PDF by Bernstein, even though it mostly talks about how classical collision finding is better than quantum-based). Also see Section 9.7 of the Handbook of Applied Cryptography (PDF).

Now the first obvious optimization one can make is to only consider the first $d$ bits of $H'$ and try to find a collision on them, ie try to find a collision on $H'':\{0,1\}^*\to\{0,1\}^d$ where $H''(m)$ is the first $d$-bits of $H'(m)$. Now we can do the proof-of-work with $2^{d/2}$ instead of $2^{n/2}$ operations and without memory.

Now if we wanted to optimize for time a bit more, we could notice that essentially all bits of $H'$ are independent random variables that take the values $0,1$ with 50% probability each and pretty much independently of each other. So we basically get $d/2$ for free! Furthermore we can apply the math of Binomial-Disitributions to get an estimate for the required amount of samples for 2nd-pre-images. The details of this are explained in this answer, but the TL;DR is $l:=\frac{2^n}{\sum_{i=0}^k\binom{n}{i}}$ messages are needed for a 2nd-pre-image for a fixed message and and $\sqrt l$ messages for a "simple" near-collision. Of course this requires the storage you hoped for, but it's probably less than expected. The complexity $\sqrt l$ is actually proven as Lemma 1 in the second paper below.

Now if we want to leave the land of "simple" strategies to this, there is academic research on how to find such near-collisions with "Using Random Error Correcting Codes in Near-Collision Attacks on Generic Hash-Functions" by Inna Polak and Adi Shamir seeming to be the newest contribution (which also uses a bit of memory) and "Memoryless Near-Collisions via Coding Theory" by Mario Lamberger, Florian Mendel, Vincent Rijmen and Koen Simoens (PDF) being a somewhat older one. Complexities for the algorithms of these papers are hard to estimate, but it's brought up that $n=160,k=33,d=127$ was carried out with a single PC.