Re: Collision in SHA-0

From: Vernon Schryver (vjs_at_calcite.rhyolite.com)
Date: 08/17/04 

Date: Tue, 17 Aug 2004 10:00:44 -0600 (MDT)

In article <I3pUc.783$d5.6006@newsb.telia.net>,
Henrick Hellström <henrick.hellstrm@telia.com> wrote:

>> And of course, we're not talking about 2**50 operations to forge a
>> digital signature or cause some other real problem, but merely to find
>> a useless collision.
>
>Wrong. I can think of a lot of things that would be insecure if a method
>existed to find a collision in the compression function of the hash
>function:
>
>1. Certificate Issuance. The entity requesting the certificate can often
>predict what the CA will put in the final certificate. If that entity is
>able to find collisions in the underlying hash function, and is also
>allowed to enter custom fields into the final certificate, it would be
>perfectly possible for that entity to e.g. create a CSR that would
>result in a certificate with the exact same signature as a forge CA
>certificate, server certificate for microsoft.com or whatever.
>
>2. Time Stamping. For the same reason.

There are collisions and then there are collisions. Your entity
requesting a cert must not merely find a string of bits with the
same length as a cert and the same hash. The new string must have
desired bits such as "microsoft.com" or your public key in the
non-custom fields.

Finding that "asdfl230984asdf signed at 3247/88/99 83:67" and
"2390487fdsdf33f signed at 5617/88/34 38:31" have the same hashes
is not very interesting. You need to find that a useful text, date,
and time with the same hash value as the target text, date, and time.
Randomly jumbling some bits in the target might be a useful attack,
but the jumbled bits better be not be the bits that you need to be the
same as in the original. It might even be useful to find a pair of
texts and times that same hash value, but only if they are usefully
related and make sense.

As I understand it, the SHA0 result is a sequence of close to random
pairs with common hash values. Starting from your original cert
and producing strings with the same length as your cert and with a
common hash value that differs from the hash value of your cert
doesn't seem immediately useful.

Yes, attacks can often be improved, but often not. Were you around
years ago for the announcement of the almost sort of not really
"break" of MD5?

Of course you should probably be using SHA1 instead of SHA0, but that's
not exactly headline news.

Vernon Schryver vjs@rhyolite.com

Relevant Pages

  • Re: Certificate Thumbprint using Win32
    ... Note that the "Thumbprint" of a "Certificate" is the SHA1 hash of the raw ... if you have a certificate file on your ... haven't spotted how to get at it with one of the Cert... ...
    (microsoft.public.platformsdk.security)
  • Re: When will md5crk complete?
    ... and in that case birthday attack ... > His core message is correct however: you shouldn't be using MD5. ... Collisions DO exist for every hash algorithm... ...
    (sci.crypt)
  • Re: Hashing
    ... Computing the hash function, which is handled by the instructions: ... reserved word/identifier when searching through the reserved words ... collisions and four slots that have four collisions. ...
    (alt.lang.asm)
  • Re: Hashing
    ... A good hash ... > greater is it better performance due to less collisions". ... then the probability that you need a rehash on any scan is something ... > 'hash method' simply because they use hash codes, ...
    (alt.lang.asm)
  • Re: CHECKSUM() question
    ... Let's assume for a moment that you use CHECKSUM and that there are hash collisions. ... If you stage the answer in a temporary table, you can use that to join to your source table, then filter out the few collisions. ... Remember absolutely no hash that reduces the size of data for searching can be guaranteed to avoid a collision. ... However, from a private discussion, Steve Kass pointed out that HASHBYTES with MD5 for 300 million rows probably has a lower chance of collision than the the possibility that some bit will get randomly changed by some other influence. ...
    (microsoft.public.sqlserver.programming)
Loading