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).
Background: 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 reliably change 1s to 0s using special hardware, but not the other way around (0s to 1s).
I can modify a portion of the firmware image and the hash itself. I need to modify a few relevant bits in the firmware image to "backdoor" it without a mismatch between the stored hash and the computed hash. If it weren't for the fact that I can partially modify the stored hash, doing this would be impossible.