Cryptographic Checksums Are Not Certificates

A cryptographic checksum is a many-to-one (or surjective) mathematical function from the integers onto some subset of the integers. The integer that is the result of applying this function to the input is also called the checksum of that input.

The idea, such as it is, of a cryptographic checksum, is to provide a certificate of possession of the input number, but without revealing anything about what that input number might be.

Such a certificate, if only it existed, would have a number of uses. For example, it could be used to verify that the data received was indeed exactly the same data that was transmitted over some communications channel. A cryptographic checksum could also be used, along with a cryptographic key, to digitally sign a message,  providing a receiver with a proof that the data it contains is exactly that which the signer intended. In these examples, the message, a stream of binary digits, say, is considered to be just one single integer, albeit usually a huge one.

The ideal cryptographic checksum has two properties, which are in fact mutually exclusive. They are called collision resistance and irreversibility.

To be an effective certificate, the cryptographic checksum must provide some degree of collision resistance. That is to say that it must not map one message, and any other "similar" message, to the same checksum. Otherwise a "small" modification of the input could result in the modified message having the same checksum as the original, and then the certificate would not be useful, because it would be ambiguous, certifying that the message was merely one of many possible messages.

Clearly the idea of collision resistance depends crucially on how one defines the terms "similar" and "small" when referred respectively to messages and to the changes made to messages. In particular, collision resistance is always with respect to some specific encoding of the data in the message, in terms of which the words "similar" and "small" must be defined.

The second requirement, that of irreversibility, means that knowledge of the checksum alone cannot be translated into knowlege of "any part" of the input data which it certifies. Irreversibility too is therefore necessarily in respect of some particular encoding, in terms of which the phrase "any part" must be defined.

In general, collision resistance and irreversibility are clearly mutually contradictory requirements, and the only way to satisfy them both is to qualify the two requirements as being "practical". And again, one needs to define precisely what one means by the terms "practically collision resistant" and "practically irreversible".

Consequently, whenever you see an analysis of the effectiveness of any cryptographic checksum, you will be able to recognise the explicit statements concerning the particular class of encodings, and the definitions of "similar message" and "small change", as well as the definitions of "practically collision resistant" and "practically irreversible", all of which will be given with respect to the particular class of encodings under consideration.