# Re: Hash question

*From*: Francois Grieu <fgrieu@xxxxxxxxx>*Date*: Tue, 20 Jul 2010 17:43:38 +0200

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

.

**Follow-Ups**:**Re: Hash question***From:*Peter Fairbrother

**References**:**Hash question***From:*Peter Fairbrother

- Prev by Date:
**Re: Is there a Mathematician Cryptographr in the House.** - Next by Date:
**Re: Using an Asymmetric cipher the opposite way round.** - Previous by thread:
**Re: Hash question** - Next by thread:
**Re: Hash question** - Index(es):