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

François Grieu

Relevant Pages

  • Re: Hash question
    ... suppose the strings and the hashes are the ... The first hash is a hash of the first string, I want to know whether the ... "difference", including XOR, subtraction, and subtraction ...
  • Re: People ~Fing with Life
    ... That is what the charge was. ... hash values and the like'. ... this data area had no corresponding entry in the allocation tables. ... Hashes are used for the purposes of error correction ...
  • Re: Passwords: to crypt or to hash?
    ... read recently that hashes are stored rather than crypted versions. ... Very few systems have ever stored crypted passwords. ... the hash function took over a second to compute. ...
  • Re: How to avoid rehashing?
    ... with strings. ... And keeping this in a hash. ... I use the words as keys since I want to find every occurence of the ... these hashes, which I need to do more than once. ...
  • RE: [7.8.2002 44916] Notice of Copyright Infringement]
    ... Appending a single bit onto the end of the file makes a different hash. ... and you no longer match the hashes. ... The only way to prove you're breaking copyright is to download at ... |"real" warezed version of whatever movie. ...