Second preimage attack complexity when the digest is malleable

An attacker has a hash $$h$$ and a message $$m$$. He wants to find $$m^\prime$$ with the same length as $$m$$ which hashes to $$h^\prime$$. However, $$m^\prime$$ can only differ from $$m$$ in the 1 bits (i.e. binary 1 can be changed binary 0, but not the other way around). Additionally, $$h$$ is malleable, and $$h^\prime$$ differs from $$h$$ in the same way.

In other words, the attacker has a message and a hash and can convert any 1 bit to a 0 bit in both the message and the hash. What is the complexity of a generic second preimage attack in this scenario?

The variables in this case are the length of the message, the hamming weight of the message, and the size of the digest (assumed to have a hamming weight half that of its length in bits, on average).

• @MaartenBodewes I've tried simplifying the definition to take into account only the complexity of the attack for an arbitrary message and a random hash (adding the probability that the hash is all 1s, meaning I can change the hash to whatever I want, plus the probability that all but one bit of the hash are 1s, etc.). Unfortunately my math is pretty bad so I'm not sure where to go from there. – forest Aug 15 at 8:43
• Why $h$ is malleable? Well, you can encode all possible $m'$s then hash them and look for the difference between $h$ and $h'$. Instead of complexity, the probability is more interesting, since there can be no such $m'$. – kelalaka Aug 15 at 9:06
• @kelalaka I wrote about that on The Side Channel. From that link: I am working on a project where I have hardware write-protected data (holding firmware) that I wish to modify to bypass security controls. The write-protected medium holds both the data that I wish to modify, as well as a cryptographic hash over the data. Although the medium is ostensibly read-only, I can change 1s to 0s using special hardware. – forest Aug 15 at 9:07
• I think you can reach plenty of $m'$ so brute force is not a problem, given large enough $m$, i.e. message space that can be altered. If you can change any result of 1 of hash function $H$ then you only need to make the zero bits match (at the correct position). So I think you've simply halved your security level. Note that there is some chance that there are more 1's than 0's in a specific resulting hash, so that's an average. – Maarten Bodewes Aug 15 at 9:38
• I'm bad at math as well, but division by 2 should be in the realm of possibility :P – Maarten Bodewes Aug 15 at 9:41

Assume the length of the message $$m$$ is $$n$$, thus the expected number of $$1$$'s is $$n/2$$ and we have $$2^{n/2}$$ options for $$m'$$, each of which are equally likely to match $$h=H(m)$$.
Let $$d$$ be the number of bits in $$h$$, and $$d_0$$ the number of 0 bits, thus the probability for a random $$h'$$ to match h is exactly $$2^{-d_0}$$. On average, $$d_0 = d/2$$ thus the probability for any legal $$m'$$ to be a second preimage is $$2^{-d/2}$$. When $$n\gg d$$ there will be a solution with a very high probability, and the expected time will be $$O(d\cdot 2^{d/2})$$ (by enumerating the $$m'$$'s and checking whether each $$h'$$ is valid in $$O(d)$$ time), which is much better than the generic attack which takes $$O(d\cdot 2^d)$$.
Note: the time required to compare the hashes is often omitted, giving the bound $$O(2^{d/2})$$.