Re: Question about checksums

[Holger Kiehl <Holger.Kiehl@dwd.de>]

On Thu, 21 Aug 2003, Jeff Woods wrote:

> At +0000 04:36 PM 8/21/2003, Holger Kiehl wrote:
> >On Thu, 21 Aug 2003, Luciano Miguel Ferreira Rocha wrote:
> >>On Thu, Aug 21, 2003 at 12:48:05PM +0000, Holger Kiehl wrote:
> [snip]
> >>>I think md5sum could do the job but, think it is a bit of an overkill to 
> >>>generate a 128 Bit checksum for such small input data. Also storing such 
> >>>huge numbers is a bit of a pain. Would a 32 or 64 Bit checksum 
> >>>sufficient, or would I be running into problems when these are to short?
> >>
> >>CRC-32 is normally sufficient. It's designed for data corruption on 
> >>transmission, though, but it should be OK as long as you don't expect 
> >>people to try and break your code with equal checksums.
> >
> >I am not trying to make anything more secure. Will a CRC-32 be sufficient 
> >to always generate a different sum if a single bit changes within the 
> >maximum 5120 Bytes?
> 
> In general, X bits of storage can take on 2^X distinct values.  So CRC-32 
> can take a maximum of  approximately four billion possible values.  That's 
> a number with three commas in US notation; I suppose that's twelve periods 
> or spaces on your side of the pond.  A 128 bit value can store 
> approximately 64 trillion trillion trillion distinct values. That's a 
> number with *twelve* commas.  And a 5120 byte file has 40960 bits so it can 
> have roughly 1*10^4096 distinct values.  There will always be the 
> possibility for duplicate values when you take a checksum on arbitrary data 
> longer then the checksum length.
> 
> You have to make a tradeoff of how much risk you're willing to accept for a 
> duplicate based on how that would affect you.  A 32 bit checksum has a 
> *minimum* of one in 4 billion chance of two files sharing the same 
> checksum.  For most non-security applications, that's ample.  The same 
> possibility exists with 128 bit md5 checksums (or any other hash) but the 
> larger the checksum the less often you'll get duplicate checksums for 
> different data (assuming comparable quality hash algorithms).
> 
> One way to make such use of checksums fail-safe is to use the checksum as 
> proof that files are different but not as proof they are the same.  When 
> the checksum matches you don't really know the files are the same unless 
> their contents are actually the same and once every four billion times you 
> probably can afford to go check if it's really critical to know for certain.
> 
Thanks for the very good explanation! I will try one of the CRC-32 checksums.
I am always checking for double entries in any case so I will discover it
when there is one checksum for two or more jobs.

Thanks,
Holger