Re: Hash question



On 20/07/2010 16:08, Peter Fairbrother wrote:
I have two unknown strings which differ by a known amount, and two
hashes. To make it easier, suppose the strings and the hashes are the
same length, 256 bits, and the strings differ in 32 bits.

The first hash is a hash of the first string, I want to know whether the
second hash is a hash of the second string, with good probability. How
hard is it?

If the hash can be modeled by a random oracle (a fairly
standard assumption), and the location of the (non-zero)
difference is known, the best method has demonstrably a
cost of 2^^256 hashes for a "no" answer, or on average
about half that for a "yes there is this solution" answer.
Memory needed is negligible for usual definitions of
"difference", including XOR, subtraction, and subtraction
modulo 2^^32.

There conceivably could be better methods for a particular
hash functions. For example, with the hash defined by
H(x) = SHA-256(x|0xFFFFFFFF)^(x&0xFFFFFFFF)
and the difference by XOR in the rightmost 32 bits,
the answer is "yes" or "no" depending on if the XOR of
the two hashes the difference or not. Still, H has about
112 bit of collision-resistance, and 224 bit of
preimage-resistance for the standard definitions of these
properties.

François Grieu
.