This show has been flagged as Clean by the host.
This series is dedicated to exploring little-known—and occasionally useful—trinkets lurking in the dusty corners of UNIX-like operating systems.
In UNIX Curio #8 (
HPR episode 4657
), I talked about using standard utilities to compare files. Left unmentioned, however, was a method commonly used today—the hash function.
As I've stated in previous entries, while I am an engineer, I don't have a background in computer science, so my understanding of the mathematics is limited. But I can give a practical description of what a hash function does. It takes an input, performs a set of calculations on it, and produces an output. As hash functions are practically used, the input is a set of bytes, such as a file or another piece of data like a password. The output is a numerical value in a fixed range—most often, expressed as hexadecimal characters. Because this "hash value" can always be represented in a certain number of bytes, its length as printed is usually a constant number of characters, padded with leading zeros if necessary. This episode will not cover the use of hashes in programming, focusing instead on using them to validate data.
A hash function, or more specifically, a cryptographic hash function, has an additional property. It should be very difficult to predict what changes to the input would be required to produce a specific change in the output.
An older, related concept is called a "checksum". While these are designed to vary when the input data is damaged or digits are transposed, they do not necessarily have that last property mentioned for cryptographic hashes. You have probably already encountered a checksum, even if you didn't recognize it. On a
16-digit number assigned to a Mastercard or Visa
1
credit or debit card, the first six digits identify the card issuer (such as a bank), the next nine digits are assigned to you by the issuer, and the last digit is a check digit. The check digit is calculated using the values of the previous 15 digits, and it is a simple way to avoid typos in entering a card number.
In another example, every
Ethernet frame that your devices send or receive includes a checksum
2
to help ensure that the contents weren't scrambled in transit. This is 32 bits long and is called a cyclical redundancy check, commonly referred to as a CRC. A CRC is also used in many other places—for example, the .zip file format includes one for each archive member, and this allows a program extracting files from the archive to identify if any were damaged.
Our UNIX Curio for today is another example,
the
cksum
utility
3
. It generates a 32-bit CRC based on the Ethernet algorithm. It operates on either a named file or standard input and outputs the CRC value, the length of the input, and the pathname if a file was given as an argument. Unlike most modern hashing programs, the checksum is printed as a decimal integer and is not padded, so it can be anywhere from one to ten digits long. The length value is the number of bytes in the input (actually specified as the number of
octets
, as systems could potentially use a byte that isn't eight bits long), also expressed as a decimal integer.
There are two major ways that one could use
cksum
to check the validity of a file. First, if you are transferring a file from one UNIX-like system to another, you could run
cksum
against it on both systems and check that the CRC and length are the same. The utility can also be given multiple filenames as arguments, which would generate a list that can then be compared. The second way would be for someone publishing a file or set of files to also publish the CRC values, lengths, and names so that people downloading them could verify that they match. However, I don't think the practice of publishing lists like this really started until more recent hash functions like MD5 and SHA-1 came about so it is unlikely that anyone would publish CRC values instead.
The advantage of these tools should be pretty obvious in comparison to
cmp
, one of the utilities discussed in UNIX Curio #8. To verify a file using
cmp
, you need two files to compare—if you're trying to check a large file you downloaded, you would need to spend the time and bandwidth to download a second copy. And if they didn't match, you would have no idea which of the two, if either, was correct. By contrast,
cksum
is quicker to run, doesn't require downloading a massive amount of excess data, and if run against the original file, makes clear what the correct value is.
This utility is a follow-on from a program called
sum
, which operated very much the same. I had a bit of trouble tracking down the exact development history, but what seems clear is that
two different variants
4
were popular: a BSD version and a System V version. Both output 16-bit checksums, but used different algorithms so they didn't give the same results. Also, the BSD version printed the length of the input data as the number of 1,024-byte blocks, while the System V version instead gave a count of 512-byte blocks. (Some sources
claim that System V
sum
generates a 32-bit checksum
5
, which could possibly be true internal to the algorithm, but I have tested several independent implementations of the utility and all of them output a 16-bit value for both the System V and BSD algorithms.)
From what I can tell,
the BSD version
6,7
came first; it was in 3BSD but probably appeared even earlier. An identical
copy of BSD's
sum
was included with UNIX/32V
8,9
, which was AT&T's 1979 port of Seventh Edition UNIX to the VAX and became one of the ancestors of System III. The divergence seems to have started with System III, released in 1980;
its version of the
sum
utility
10,11
changed to a new default algorithm, though it could be made to use the BSD algorithm via the
-r
option. System V looks to have kept the same behavior as System III. It's not clear to me why this algorithm is universally called the "System V algorithm" rather than the "System III algorithm"; perhaps it is because System V saw much more widespread use.
Instead of trying to reconcile these differences, the POSIX committee decided to create a new utility with a unique name, use a separate algorithm entirely, and avoid the block-length dispute by printing the length in octets instead of blocks. I should point out that POSIX states that the CRC algorithm for
cksum
does not strictly meet the mathematical definition of a "checksum". I don't know enough to say exactly
why
it doesn't qualify or to say whether either of the
sum
algorithms do. However, in less-formal usage the term "checksum" has gathered the meaning of any value used to represent or validate a set of data, so I am fine with using it no matter the technical details of the algorithm.
When two different inputs produce the same checksum or hash value, this is called a "collision". Because the output value has a limited range, there are an infinite number of possible inputs that could produce a collision. From a practical standpoint the possibilities are more limited—the majority of these inputs are larger than the number of atoms in the universe, which can't fit on any machine. Unlike a cryptographic hash algorithm, the CRC is not specifically designed to resist an attacker crafting a malicious input that would cause a collision. However, it should be sufficient to detect accidental damage.
Programs implementing more modern cryptographic hash algorithms are superior to the checksum utilities in avoiding collisions (whether malicious or accidental), but there are still three advantages that the older programs have. First, a system running a historical operating system might not have the hash programs available, but is more likely to have
cksum
or
sum
already included. Second, the checksum values are much shorter than the hashes output by the newer programs, making them easier for a user to compare by looking at them. This advantage is not as great as it might appear at first, because a common way to check a hash these days is to save a list of hashes and filenames—the hash programs can use that and do the comparison themselves, sparing the user from having to validate it character by character. The third advantage is that
cksum
prints the input length in bytes. This greatly limits the number of inputs that could be maliciously crafted to create a collision.
I did a moderate amount of research on implementations of modern cryptographic hash algorithms and found that some, such as MD5, SHA-1, and SHA-2, do use the length of the input (often termed "message length" in the literature) as part of the material fed in to the algorithm, but none of the hashing utilities present this length to the user as part of its output. There are two possible reasons for this that seem evident to me. First, if one is hashing a password, you would certainly not want to give a clear indication of its length—that would give any attacker a massive head start on guessing the password. However, that doesn't explain why one would avoid printing the input length for a file that is made publicly available. Second, it is convenient in many contexts, such as database entries or in software (such as
git
), for the hash to be a fixed length. Including an extra value that can be of variable length would complicate those use cases. However, the length value could simply be dropped and they would be no worse off than they are currently.
Historically on UNIX, password hashing was treated differently from checksumming files—
the
crypt()
function
12
was used for passwords while
sum
and later
cksum
were used to confirm a file's integrity. So even rather early on, these two use cases employed algorithms with different properties, but I haven't dived into the history deeply enough to know how intentional this was. My discussion in this episode focuses on the file use case, so understand that I'm largely avoiding the topic of password hashing. Digital signatures are yet another use case, one that I'm ignoring entirely.
Every few years, some security researcher declares a particular hash algorithm to be "broken" and that everyone should move over to a new one, which generally has a longer hash. While the larger hash space certainly reduces the opportunity for collisions, this disrupts workflows, such as publishing information about software releases by e-mail, which still tends to observe a
78-character limit on each line
13
, making it harder to include a list of hashes with filenames next to them. This is in addition to the work of modifying software and scripts to use the new algorithm and managing how to treat past data. It seems to me that publishing the input length along with the hash would make it far more difficult to craft a malicious input that matches both, but I haven't found discussion of that during my investigation. (See the Appendix for a possible implementation.) Perhaps someone listening can record a response episode for HPR explaining that.
References:
Payment card number
https://en.wikipedia.org/wiki/Payment_card_number
Ethernet frame: Frame check sequence
https://en.wikipedia.org/wiki/Ethernet_frame#Frame_check_sequence
Cksum specification
https://pubs.opengroup.org/onlinepubs/009695399/utilities/cksum.html
GNU coreutils manual: sum
https://www.gnu.org/software/coreutils/manual/html_node/sum-invocation.html
FreeBSD 15.0 sum manual page
https://man.freebsd.org/cgi/man.cgi?query=sum&sektion=1&manpath=FreeBSD+15.0-RELEASE+and+Ports
3BSD sum manual page
https://www.tuhs.org/cgi-bin/utree.pl?file=3BSD/usr/man/man1/sum.1
3BSD sum source
https://www.tuhs.org/cgi-bin/utree.pl?file=3BSD/usr/src/cmd/sum.c
UNIX/32V sum manual page
https://www.tuhs.org/cgi-bin/utree.pl?file=32V/usr/man/man1/sum.1
UNIX/32V sum source
https://www.tuhs.org/cgi-bin/utree.pl?file=32V/usr/src/cmd/sum.c
System III sum manual page
https://www.tuhs.org/cgi-bin/utree.pl?file=SysIII/usr/src/man/man1/sum.1
System III sum source
https://www.tuhs.org/cgi-bin/utree.pl?file=SysIII/usr/src/cmd/sum.c
Crypt specification
https://pubs.opengroup.org/onlinepubs/009695399/functions/crypt.html
RFC 2822: Internet Message Format: Line Length Limits
https://datatracker.ietf.org/doc/html/rfc2822#section-2.1.1
OpenSSH 10.1 released
https://lwn.net/ml/all/dd12623ae86aa5eb@cvs.openbsd.org/
Appendix
The MD5 hash algorithm was (and still is) widely used, but many people characterize it as being "broken" and discourage its use. Let us imagine a variant of this, called MD5.L, where the normal MD5 hash is followed by a "." character and the input length expressed as a hexadecimal number.
Take, for example, the
e-mail message announcing the release of OpenSSH 10.1
14
. At the bottom, it includes an SHA-1 hash and an SHA-2 256-bit hash for the available gzipped
tar
files. That longer hash is encoded with Base64 because if it were given as a hexadecimal number, it would make the line longer than 78 bytes. The MD5.L hash of the file would be one character shorter than the SHA-1 hash, as shown below. (The extra length of the
name
makes them both consume the same number of characters. The hashes shown are for the "portable" version of OpenSSH.)
Some people claim SHA-1 is also broken, seeking to have people use newer and longer hash functions. For an attacker to compromise MD5.L in this example, they would not only have to create a valid
tar
file compressed with
gzip
containing a malicious payload having the right MD5 hash, that file would have to be exactly 1,972,831 bytes long (the decimal equivalent of 1e1a5f). While there are still many possible inputs that could be tried (256
1972831
, to be exact*), this is far fewer than the infinite possibilities for plain MD5, SHA-1, or SHA-2.
If for some reason it is super important to have a fixed hash length, let's imagine another variation called MD5+L. In this one, instead of L being the input length, it is the input length
modulo
one terabyte (2
40
bytes), which can be represented by 10 hexadecimal characters, left-padded with zeros. While this approach substantially increases the number of possible inputs an attacker could try, it is likely that an intended victim would notice that the file they downloaded is larger (or smaller) than expected by that much. The MD5+L hash is longer than a SHA-1 hash, but still shorter than a 256-bit SHA-2 hash.
SHA1 (openssh-10.1p1.tar.gz) = 7fd17b99d1beffb47cd380d64079e920bb0bd91f
SHA256 (openssh-10.1p1.tar.gz) = ufx6K4JXlGem8vQ+SoHI4d/aYU3bT5slWq/XAgu/B1g=
MD5.L (openssh-10.1p1.tar.gz) = 80dd9bb00a86519934710d05903fdf07.1e1a5f
MD5+L (openssh-10.1p1.tar.gz) = 80dd9bb00a86519934710d05903fdf07+00001e1a5f
Of course, if MD5 is considered to be too weak even with the inclusion of the length, one could produce a ".L" or "+L" version of any hash function. However, longer hashes
will
end up running into the 78-character limit.
*This is a number with 4.75 million digits that the
bc
utility on my laptop took almost 5 minutes to calculate.
Provide feedback on this episode.
Netherlands