Path: csiph.com!newsfeed.hal-mli.net!feeder3.hal-mli.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!newsreader4.netcologne.de!news.netcologne.de!newsfeed.freenet.ag!news2.euro.net!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
MIME-Version: 1.0
In-Reply-To: <51007BD0.1030105@davea.name>
References: <8deb6f5d-ff10-4b36-bdd6-36f9eed58e1e@googlegroups.com> <5dd4babd-716d-4542-ad36-e6a841b73ec3@googlegroups.com> <mailman.684.1358586035.2939.python-list@python.org> <03581a24-9330-4019-bde9-61a607000d3d@googlegroups.com> <mailman.729.1358752818.2939.python-list@python.org> <187d77e0-e948-46bf-acc5-668c446cf3aa@googlegroups.com> <mailman.733.1358760692.2939.python-list@python.org> <239abe33-fa5b-41a9-ae80-5260b9b1bd9c@googlegroups.com> <CAHVvXxRGXiSAnzGqra5Rek47peYXzTscB8-Xj-UAxyurDqVgpA@mail.gmail.com> <mailman.743.1358772477.2939.python-list@python.org> <e5a1d698-bf58-46af-8295-ba2d1c277558@googlegroups.com> <mailman.844.1358898919.2939.python-list@python.org> <2391171e-e170-4647-8924-8e446ea1c6b1@googlegroups.com> <9d9b287c-ca2a-49c1-a16b-e42cb2a5db38@q16g2000pbt.googlegroups.com> <6f3e7d20-3005-4d1e-b949-d90a78e7bbf6@googlegroups.com> <50FFD9B8.3090304@davea.name> <CAPTjJmpp9uJDz2qTf4sAKBj12dF7g=tJKDFDW4_1jh7RJcNs-Q@mail.gmail.com> <51007BD0.1030105@davea.name>
Date: Thu, 24 Jan 2013 11:39:16 +1100
Subject: Re: Uniquely identifying each & every html template
From: Chris Angelico <rosuav@gmail.com>
To: python-list@python.org
Content-Type: text/plain; charset=ISO-8859-1
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.936.1358987959.2939.python-list@python.org>
Lines: 53
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:37523

On Thu, Jan 24, 2013 at 11:09 AM, Dave Angel <d@davea.name> wrote:
> I certainly can't disagree that it's easy to produce a very long hash that
> isn't at all secure.  But I would disagree that longer hashes
> *automatically* reduce chances of collision.

Sure. But by and large, longer hashes give you a better chance at
avoiding collisions.

Caveat: I am not a cryptography expert. My statements are based on my
own flawed understanding of what's going on. I use the stuff but I
don't invent it.

> Wikipedia - http://en.wikipedia.org/wiki/Cryptographic_hash_function
>
> seems to say that there are four requirements.
> it is easy to compute the hash value for any given message
> it is infeasible to generate a message that has a given hash
> it is infeasible to modify a message without changing the hash
> it is infeasible to find two different messages with the same hash
>
> Seems to me a small hash wouldn't be able to meet the last 3 conditions.

True, but the definition of "small" is tricky. Of course the one-byte
hash I proposed isn't going to be difficult to break, since you can
just brute-force a bunch of message changes until you find one that
has the right hash.

But it's more about the cascade effect - that any given message has
equal probability of having any of the possible hashes. Make a random
change, get another random hash. So for a perfect one-byte hash, you
have exactly one chance in 256 of getting any particular hash.

By comparison, a simple/naive hash that just XORs together all the
byte values fails these checks. Even if you take the message 64 bytes
at a time (thus producing a 512-bit hash), you'll still be insecure,
because it's easy to predict what hash you'll get after making a
particular change.

This property of the hash doesn't change as worldwide computing power
improves. A hashing function might go from being "military-grade
security" to being "home-grade security" to being "two-foot fence
around your property", while still being impossible to predict without
brute-forcing. But when an algorithm is found that generates
collisions faster than the hash size indicates, it effectively reduces
the hash size to the collision rate - MD5 is 128-bit, but (if I
understand the Wikipedia note correctly) a known attack cuts that to
20.96 bits of "real hash size". So MD5 is still better than a perfect
16-bit hash, but not as good as a perfect 32-bit hash. (And on today's
hardware, that's not good enough.)

http://en.wikipedia.org/wiki/Collision_resistant

ChrisA