0
$\begingroup$

I'm in an Intro to Computer Security class, and one concept I'm having trouble understanding is how two different files could produce the same checksum. How would you produce the same checksum given two different files? So far, through reading the book, I found mention of something called the "pidgeonhole principle" that seems to indicate this is possible, but I'm not sure how.

$\endgroup$
1
$\begingroup$

Think of it this way:

  • How many possible files are there?

  • How many possible checksums are there?

If the number of possible files is larger than the number of possible checksums, then there must be at least two files with the same checksum.

This is one of the things known as the "pigeon-hole principle"; the idea is that if you are placing pigeons in pigeon holes, and there are more pigeons than holes, then some hole somewhere will have two pigeons.

Now, if you go on further, you'll find that, if you know the MAC key, it's actually quite easy, with DES-MAC, to produce two files with the same checksum (or, for that matter, a file with a specific checksum). However, you're not quite ready for that.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.