0

What I am interested is the similarities and differences between the two. It is my understanding to present time that Luhn algorithm is a type of checksum function same as some cryptographic hash functions.

From what I have read, the hash functions cannot be reversed as it is a "one-way" function, mathematically speaking, where's it seems same does not apply with the Luhn algorithm.

I would appreciate any input on this particular subject matter. Your insight is very much appreciated.

  • 5
    on wikipedia: " It is not intended to be a cryptographically secure hash function; it was designed to protect against accidental errors, not malicious attacks." – ratchet freak Aug 16 '15 at 17:11
  • Q. is also answered on SO: "Hash Code and Checksum - what's the difference?". – outis Aug 16 '15 at 22:48
  • A Luhn checksum certainly cannot be reversed. It definitely is a "one-way" function. – Blorgbeard Aug 17 '15 at 3:25
  • @Blorgbeard if I know checksum is 70, I can create a sequence of numbers that will also result in 70 - that's called collision tolerance which should not be acceptable when compared with crypographic hash functions. – e.doroskevic Aug 17 '15 at 11:51
  • That's true, but different from a one-way function. You can't recreate the original sequence of numbers. I am not suggesting Luhn is at all suitable for crypto. – Blorgbeard Aug 17 '15 at 20:08
2

The difference is in usage and properties necessary for the usages.

Checksums basically detect (and sometimes correct) small amounts of non-malicious, unintentional data corruption:

In all uses, a checksum and data are combined so that the original data can be recovered. In most encodings, the checksum is appended to the original, but you could have a checksum function that is more hash-like, where the original data doesn't appear directly in the output. Base-64 encoding, while not a checksum or hash, is an example of an encoding that doesn't include unmodified input in its output.

Numeric data can be viewed as a point in some space (sometimes called a "code space"), with each digit a coordinate. Checksums generally work by spreading out valid data (in more formal terms, it maximizes the Hamming distance between strings) in the space. Around each valid datapoint is a sphere of invalid points that are closest to it. Creating a code can also be viewed as finding an efficient sphere packing.

If received data isn't a valid datapoint, it indicates an error; the nearest valid datapoint is assumed to be the transmitted value (if there is a nearest; sometimes, the received data may be equidistant to two or more, in which case the error can't be corrected). In particular, the amount of error must be ≤ 1/2 the minimum distance between data points.

Like hashes, checksums lack inverses in terms of the generated check digits. This usually doesn't matter, as the original data are transmitted along with the check digits and the whole point of a checksum is to find the inverse of the coded representation.

Hash function uses:

  • index data for storage & retrieval (hash tables, caches)-
    • if similar data have similar hashes, the hash function can be used in algorithms to find matching or similar data
    • file IDs in P2P networks and (document or code) repositories
  • data integrity: detect invalid data; detect (but not correct) whether data has been changed/corrupted. Allows for a much higher amount of corruption than checksums, and can be used to detect tampering (intentional changes)-
    • shorten digital signatures. The signature is the actual detection mechanism, but the digest (sc. the hash of a document or message) can be encrypted instead of the document to reduce the signature size
  • verification-
    • passwords
  • proof-of-work: some problems involving hashes (e.g. finding pre-images or collisions) have high resource costs (e.g. processor time), so finding an answer can indicate the system spent resources to do the work-
    • crypto-currency
    • P2P defense measures
  • key derivation (e.g. in WPA/WPA2)

Depending on the usage, the hash and original data may be kept separate, unlike checksums. Each usages of hashes also imply a number of properties (e.g. pre-image resistances) that don't matter with checksums.

The discipline that combines all this and more is coding theory.

  • thank you for the time you took to write this answer. It is much appreciated. – e.doroskevic Aug 16 '15 at 22:41

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.