Subject: Minor editorial NSEC3 comments

From: Roy Badami <[email-masked]>
Date: Fri, 11 Mar 2005 00:42:23 +0000

6.4.2 says....

    A collision resistant hash function has a second-preimage resistance
    property.  The second-preimage resistance property means that

I am not a cryptographer, but...  While true, I don't think this is
relevent. I would reword this to say

    A cryptographic hash function has a ...

Collision resistance is another specific property of cyrtographic
hashes, namely that it is computationally infeasable to construct a
pair of messages that hash to the same value, and AFAICS NSEC3 doesn't
actually require a collision resitant hash function.

Collision restistance implies second pre-image resitance: if you've
managed to break second pre-image resitance then you have necessarily
constructed a collision, but second pre-image resitance is a weaker
property of a hash than collision resitance.

Weaker in the sense that it is possible to break the collision
resistance of a hash without breaking second pre-image resistance (ie
I may be able to construct one or more pairs of messages that hash
to the same value, assuming I get to choose both messages, but that
doesn't mean I can construct a message that hashes to the same value
as a message _you_ choose...

   The probability of finding a second preimage is 1 in 2^160 for
   SHA-1 on average

This is clearly not true, unless the adversary simply tries one
possible preimage at random and gives up if he hasn't succeeded.  Just
by trying two random preimages you can increase the probability to 1
in 2^159, and perfoming two SHA-1 operations within a reasonably
timeframe is possible even on the most modest of hardware :-)

An attacker can clearly attempt a very large number of test hashes,
but also cryptanalysis of SHA-1 may allow less computationally
intensive attacks than random tests...

You can't put a figure on the probability of breaking second preimage
resistance; cryptography doesn't work that way.  It's conceivable
(though incredibly inplausible) that someone (perhaps the NSA?) is
capable of producing a second preimage with probablility 1.

   -roy

--
to unsubscribe send a message to [email-masked] with
the word 'unsubscribe' in a single line as the message text body.
archive: <http://ops.ietf.org/lists/namedroppers/>

---

From: Alex Bligh <[email-masked]>
Date: Fri, 11 Mar 2005 16:48:50 +0000

--On 12 March 2005 03:24 +1100 Mark Andrews <[email-masked]> wrote:

>> You are right in another way though: NSEC3 doesn't (well IMHO shouldn't)
>> require ANY of those properties of its hash function, UNLESS you
>> care about enumeration. NSEC3 should be able to cope with ANY function
>> (whatsoever) as the hash function, though the worse hash function it
>> is (and the smaller its range is compared to its domain), the more
>> important a functional fall-back to the identity hash becomes.
>
> 	Not quite ANY function.  The size of the hash space must be
> 	bigger than the number of records in the NSEC3 chain.

Correct - I said I hadn't had enough caffeine - else you cannot create the
signed file in the first place. In fact the requirement is stricter than
that: the function must, with a suitable salt value, produce unique [*]
values for each record in the NSEC3 hash chain, and it must be possible to
find such a salt value with a reasonable period of time. Of course having
the range of the hash function larger than the size of the domain of the
existent input values (as you suggest) is a necessary condition, but it is
not sufficient. Trivial example:

  H(x) = SHA-512(x, salt) if x is even
         1                if x is odd

Such a hash function satisfies your criterion, but is no use.

[*] note that this type of potential collision between hashes of
two existent labels is entirely different from the label / QNAME
collision problem - I know you know that, this is for the benefit
of those reading the archives...

Alex