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 (nonzero)
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) = SHA256(x0xFFFFFFFF)^(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 collisionresistance, and 224 bit of
preimageresistance for the standard definitions of these
properties.
François Grieu
.
 FollowUps:
 Re: Hash question
 From: Peter Fairbrother
 Re: Hash question
 References:
 Hash question
 From: Peter Fairbrother
 Hash question
 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):
Relevant Pages
