Prev: Troll "Researchers" and the Creationists
Next: Using an Asymmetric cipher the opposite way round.
From: Peter Fairbrother on 20 Jul 2010 10:08
The problem:

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?


Now resistance against that is not quite in the usual properties of a
hash - preimage resistance and so on - but I'm not very up on hashes, so
maybe someone has done some work on that problem. If so, can someone
give me a pointer to it please?


If not, any thoughts?

Thanks,

-- Peter Fairbrother
From: Tom St Denis on 20 Jul 2010 10:52
On Jul 20, 10:08 am, Peter Fairbrother <zenadsl6...(a)zen.co.uk> wrote:
> The problem:
>
> 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?
>
> Now resistance against that is not quite in the usual properties of a
> hash - preimage resistance and so on - but I'm not very up on hashes, so
> maybe someone has done some work on that problem. If so, can someone
> give me a pointer to it please?
>
> If not, any thoughts?

You're literally asking for a differential attack on the hash.
Cryptographic hashes are designed to not emit useful differentials.

Tom
From: Francois Grieu on 20 Jul 2010 11:43
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
From: Peter Fairbrother on 21 Jul 2010 11:49
Francois Grieu wrote:
> 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.

I don't understand that last bit - could you explain a bit more please?


Thanks

-- Peter Fairbrother

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
From: Francois Grieu on 21 Jul 2010 12:28
Le 21/07/2010 17:49, Peter Fairbrother a �crit :
> Francois Grieu wrote:
>> 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 *IS* the difference or not.
>
> I don't understand that last bit - could you explain a bit more please?

[At typo crept: *IS* was missing in the above]

I construct a hash function H(x) accepting a 256-bit input x
and producing a 256-bit output H(x). The right 32 bits of x
are replaced by ones, hashed by SHA-256, and the right 32 bits
of that XOR-ed with the right 32 bits of x.
H(x) = SHA-256(x|0xFFFFFFFF)^(x&0xFFFFFFFF)

H(x) is a fair hash, except that a difference in the right
32 bits of x change only the right 32 bits of H(x), and do
so linearly (thru XOR). This greatly simplifies testing the
property you are looking after: XOR the two hashes, and
compare with the known difference.

Francois Grieu
 | 
Pages: 1
Prev: Troll "Researchers" and the Creationists
Next: Using an Asymmetric cipher the opposite way round.