crc32 to be used as hash

Nick Craig-Wood nick at craig-wood.com
Fri Nov 12 07:47:47 CET 2004


Tim Peters <tim.peters at gmail.com> wrote:
[snip interesting info about CRC tests]
>  BTW, it's possible to design CRC polynomials with better hash
>  statistics, but that's not what binascii.crc32 was designed for.
>  Like most CRC polynomials in wide use, it was designed to catch
>  common forms of data corruption (single-bit errors, bursts of 0 or
>  1 bits at either end, stuff like that).

[Digression] Amongst other properties, data with CRC32(data) appended
is guaranteed a Hamming distance of 3. You can actually use the CRC32
to correct single bit errors (at the cost of some of its error
detection properties).  That isn't usually worth it though! (I spent a
long time (a long time ago now) analysing and coding CRC (and FEC)
polynomials ;-)

Anyway, another reason why you'd not want to use it as a hash is that
its linear and its trivial to find things which have the same crc32
value. Its really easy to run backwards and forwards.  This may or may
not be important for the application depending on whether you are
expecting malicious attack on the hashes.  Probably better safe than
sorry though!

-- 
Nick Craig-Wood <nick at craig-wood.com> -- http://www.craig-wood.com/nick



More information about the Python-list mailing list