How unique is CRC32 checksum

Well, CRC32 generates a 32-bit checksum. Since there are only 2^32 possible values, if you have more than 2^32 files you're guaranteed to have a collision. My understanding is that CRC32 makes collisions unlikely, but that a determined attacker can deliberately generate two files with the same checksum pretty easily.

Here's more info than you ever wanted about checksums:

http://www.freesoft.org/CIE/RFC/bynum.cgi?1071

Enjoy!

ggainey at 2007-7-6 23:08:00 >

A coworker suggested MD5 hash. Any opinions or information on which algorithm better suits my purpose?Here is the code for MD5.

public static String computeHashForFile(File file) throws IOException,

NoSuchAlgorithmException, NoSuchProviderException

{

byte[] buf = new byte[1024];

int bytesRead;

FileInputStream fis = new FileInputStream(file);

MessageDigest md5 = MessageDigest.getInstance("MD5","SUN");

while (-1 != (bytesRead = fis.read(buf)))

{

md5.update(buf, 0, bytesRead);

}

fis.close();

return toHexString(md5.digest());

}

/**

* This method just assembles bytes into a hex represented string.

*/

public static String toHexString(byte[] data)

{

StringBuffer result = new StringBuffer();

String hexMap[] = {"0","1","2","3","4","5","6","7","8","9",

"a","b","c","d","e","f"};

for (int i = 0; i < data.length; i++)

{

int l = ((((int)data)) & 0xF0) >> 4;

int r = ((int)data) & 0x0F;

result.append(hexMap[l] + hexMap[r]);

}

return result.toString();

}

johnR at 2007-7-6 23:08:00 >

I believe MD5 has now been broken, although I'm not sure where I got that from. One technique which would work moderately well is to pick any block cipher you like and break your file into blocks. Then denoting C(N, K) as encrypting N under key K, you compute (assuming for the purposes of example, although it should work without subject to appropriate modifications, that the key length is the same as the block length)

E1 = C(D1, D1) where D1 is the first block of the file, etc.

E2 = C(D2, E1)

E3 = C(D3, E2)

...

En = C(Dn, En-1).

En is then your hash. If you're not worried about someone trying to deliberately mess you about, this should be fine. If you are, it'll need proper cryptanalysis for the cipher chosen. But if you are, most certainly don't use CRC32, because that's linear.

Alternatively, rather than use D1 as the initial key, use a randomly generated value, and use the same randomly generated value for all the files. By repeating with different randomly generated values, you can get the probability of collision extremely low. I venture to hope that if the block length is B, the probability of collision between two given, different, files is 1 in 2^B per key and keys are independent of each other. Thus the probability of collision between two given, different, files would be 1 in 2^(Bn) where n is the number of keys you use.

YATArchivist at 2007-7-6 23:08:00 >

There is no way that you can create a 'signature' for a file where it can't theoritically map to the same value for a different file. At least not if the signature is shorter than the original file.

However, the real question is how realistic it is for the given problem domain.

> In this case someone else creates and names the files so if they

> mistakenly named two different files the same on different days

So evaluate your problem domain. How many files are created in a single day? How likely is it that they will rename the same file on the same day? How likely is it that they will send the same file from a different day (yesterday, a week ago, 15 years ago.)

Say you have 100 files a day. And for any given day it they might only duplicate 1 file (1%) and 0.5% for the preceding day. And that is it.

So with 2^32 combinations there is a 1/2^32 chance that any file will have the same signature. And there is 1.5% chance that it could occur in any day. So in a single year that gives a probability of

(365 * 0.015)/2^32

And that (presuming my rusty skills at probability and my calculations are right) ends up as a one billionth (slightly more) chance for a whole year that a signature might be duplicated.

jschell at 2007-7-6 23:08:00 >