md5sum is a program used primarily to verify the integrity of files. That is, it is used to detect any change in the contents of a file, either an accidental change or a change that somebody made on purpose. It is a checksum program, which works by generating a number which serves as a "benchmark" or "fingerprint" for a file. At any later time, md5sum can be run again on that file, and if it generates the same benchmark number you can be sure that the file has not changed in the meanwhile.
For example, an md5sum checksum of a file might be generated before it is transmitted over a noisy phone line to another computer. When md5sum is run again on that file as it was received at the second computer, a new checksum number will be generated. If this second checksum matches the first, you will know that the file arrived ok. If the second checksum is different than the first, you will know that the file was changed somehow, and you will need to retransmit it.
Here is an example showing how to generate an md5 checksum on a Unix or Linux system which has the md5sum program available. The "cat" program just displays the contents of the file. We'll run the md5sum program twice on each of two different files which differ by only a single character:
Example 1: Using md5sum.
$ cat myfile1 abcdef $ md5sum myfile1 5ab557c937e38f15291c04b7e99544ad myfile1 $ md5sum myfile1 5ab557c937e38f15291c04b7e99544ad myfile1 $ cat myfile2 abcdefg $ md5sum myfile2 020861c8c3fe177da19a7e9539a5dbac myfile2 $ md5sum myfile2 020861c8c3fe177da19a7e9539a5dbac myfile2
The md5sum program returns two fields: a checksum of 32 hexidecimal digits followed by the name of the file. Note that the md5sum checksums are identical as long as they are generated for the same identical file. But if even one character is added (or otherwise changed) in the file, the checksum is not only different, it is very different. A changed md5sum checksum does not tell you how different the changed file is, or what the differences are. (In Unix/Linux you can use the diff program for that.) md5sum just tells you that there is or isn't a difference--and often that is all you need to know.
Since the md5sum checksums are 32 hex digits long, and since it takes 4 bits to represent a single hex digit, md5sum generates a 128-bit checksum. (This means that there are 2128 possible different checksums--about 340 bilion billion billion billion!--though it is not clear that md5sum will generate all of them even if it is applied to every possible file.)
As with all other checksum programs, there is no way to use md5sum to determine if a change has been made to a file unless md5sum was already run on that file earlier, before the file was placed in jeopardy. And, of course, the benchmark checksum must itself be saved unchanged for that later comparison. If the comparison is to be made on a different computer, then the benchmark checksum must also be transmitted to that computer in a reliable way. (And if it comes to this, it is not very hard to write down 32 characters on a piece of paper.)
md5sum is a "message digest" program, hence the "md" in the name. (Several technical terms, such as checksum and message digest will be defined in the next section.) The core algorithm for the md5sum program is known as the md5 algorithm, and md5sum combines that algorithm with a sort of a "front end" to make it a bit easier to use. (On some systems, the program available to users is called md5 and not md5sum.)
The md5 algorithm was created by Ronald L. Rivest, a professor of electrical engineering and computer science at MIT. It is one of several "message digest" functions that he constructed, and improves on the md4 version which is a little faster but more vulnerable to cryptanalysis. Rivest was also one of the founders of the RSA Data Security Corporation (he's the "R" in the name), and has made numerous other contributions to cryptography. (See the links section below for the link to his very interesting web page.)
The definitive paper on md5, RFC1321, "The MD5 Message-Digest Algorithm", was published by Rivest in April 1992, and is available on numerous sites on the Internet. In that paper he not only presents the algorithm but explains its design philosophy. Both md5 and md5sum are widely discussed in books and on the Internet. One of the best discussions is in Bruce Schneier's well-known book, Applied Cryptography.[1]
There are several terms to define here: summarizing programs, hash functions, one-way hash functions, cryptographic checksums and message digests. The most general of these is a summarizing program, so let's start with that.
A summarizing program is simply a program that somehow summarizes the contents of a file, no matter in what way. The summation may be a number or a text string of some kind--even ordinary English sentences. That number or character string may or may not provide information that is in itself useful to you about the contents of the file. Among the familiar summarizing programs on various Unix and Linux systems are: wc, sum, cksum and md5sum.
The "wc" program (for "word count", not "water closet"!) summarizes a text file by displaying the number of words, lines, or characters in the file. This sort of summary program provides some useful information about the contents of the file being summarized, even if (as with wc) the information is rather simple. It would be very nice to have a program that can actually "understand" the meaning of the words in a text file, and provide a natural language summary (or synopsis or abstract) of it. Such artificial intelligence programs are being worked on, but are not yet very reliable or commonly available.
Other kinds of summarizing programs do not provide information about the contents of files that is itself meaningful, but rather are used to verify the integrity of the file. This is done by generating a number or character string at two different times. If the number or string is the same each time, the presumption is that the file did not change in the interim. The programs sum, cksum and md5sum are designed for this purpose.
The term hash in computers originally meant electrical noise which causes random, meaningless information (garbage) to appear in memory.[2] Hashing then came to mean the application of an algorithm to separate data records into random symmetrical groups for easy storage and retrieval.[3] A hash total in traditional computer programming is "A sum formed for error-checking purposes by adding fields or other items that normally are not related, such as the total of invoice serial numbers."[4]
From these concepts came the notion of a hash function, which is a program (or program function) that generates something like a "hash total" for a data set, or file, as a whole, though not usually through any simple process of addition. The Unix programs sum, cksum and md5sum are hash functions. All three are also checksum programs, which means more or less the same thing as hash function in this context. (A checksum is a computational procedure applied to a data set, or file, which gives a result which depends on the specific data.)[5]
Simple programs such as sum and cksum usually suffice for some purposes, such as checking whether a file was accidentally changed in transmission through a noisy or error-prone network. But if any serious possibility of purposeful human change to files is to be eliminated, a cryptographic checksum program must be employed. This is a program which in practice guarantees that any tampering with a file will result in a different checksum, and which also guarantees that in practice no one will be able to come up with any different file which also produces the same original checksum. Cryptographic checksum programs do not hide a file's contents from outside inspection; that is, they do not encrypt the contents of the file. They simple prevent anyone from changing a file in any way without leaving evidence that they have done so (in the form of a changed checksum).
One-way hash functions are one method (the only method I know of!) to create cryptographic checksum programs. They are designed so that no one can construct any different file that produces the same checksum as the given file. (And therefore no one can replace a given file with a different file that has the same checksum.) They are "one-way" functions in that it is easy to go from the file to a checksum for that file, but impossible (at least in practice) to go from a given checksum to one or more files that will produce that checksum.
Of the programs mentioned in this section, only md5sum is a one-way hash function and a cryptographic checksum program.
Finally, we come to the term message digest: This is most often used as simply another name for a cryptographic checksum program, although some authors seem to use it in a more restricted sense to mean: a cryptographic checksum program of the type of md5sum (i.e., one with a similar algorithm). Here is a one, fairly formal, definition of 'message digest' by Burt Kaliski of RSA Laboratories:
| |
A message-digest algorithm maps a message of arbitrary length to a "digest" of fixed length, and has three properties: Computing the digest is easy, finding a message with a given digest--"inversion"--is hard, and finding two messages with the same digest--"collision"--is also hard.[6] |
|
In section one above, we gave one example of using md5sum to generate a checksum for a particular file. Let's do a few variations.
Example 2: Using md5sum to prove that file2 is a perfect copy of file1. Copying a file is a pretty simple process and ordinarily is not at all error prone. Yet it is possible (due to defective hardware for instance) that a copy may be defective. How can you be absolutely sure that the copy is perfect? Let's construct a file, make a copy of it, and then create another file that is almost the same as a true copy:
$ echo 'Hello, World!' > file1 $ cp file1 file2 $ echo 'Hello, World! ' > file3 $ diff file1 file2 $ diff file1 file3 1c1 < Hello, World! --- > Hello, World! $ md5sum file1 file2 file3 bea8252ff4e80f41719ea13cdf007273 file1 bea8252ff4e80f41719ea13cdf007273 file2 d23370f46cb343ebe5f31abbd56c3392 file3
In the above, we used both the diff command and md5sum to compare the files. Both do tell us that file1 and file2 are identical, and that file3 is different (it has the added space character at the end). The way diff signals that file1 and file2 are identical is by doing nothing! The way diff tells us that file1 and file3 are different is by displaying the lines in the two files which are different. But, in this case, the difference is only a single space character, which doesn't show up on the screen! In contrast, md5sum gives us a checksum for each file, and it is easy to see that the checksums for file1 and file2 are identical. (Well, fairly easy to see! I suppose that it would be best to very carefully check each character in both checksums. However, the odds that two different checksums might differ by only one, or a few, characters are vanishingly small.) Note also that in the above example we used a single command to generate checksums for 3 different files.
Through the use of "pipes" in Unix/Linux, it is also easy to generate an md5sum checksum of any string (such as the contents of a shell variable), even if it is not in a file. Here are a couple examples:
Example 3:
$ echo "abcdef" | md5sum 5ab557c937e38f15291c04b7e99544ad -
Example 4:
$ echo $string abcdef $ echo $string | md5sum 5ab557c937e38f15291c04b7e99544ad -
Note that since no file name was available to the md5sum program, it provides only a dash instead.
You could use the method in example 4 above to first create a "fingerprint" of some shell variable (in some complex shell script for instance), and then do it again later to verify that the string did not change.
These days it is useful, and even necessary, to be able to download programs and other files from the Internet. Companies and individuals who provide software often make the programs, and bug-fixes for the programs, available on the Web. But how can you make sure that these programs and patches will be downloaded to your computer without any errors?
If the Web site also provides md5sum checksums for the program files, it is easy. All you do is download the program (using ftp, or the ftp protocol built into your web browser). Then run md5sum on the program, and compare the checksum with that published on the web site. If they match, you know you got a good copy.
However, how can you be sure that the web site itself has not been "hacked"? How can you be sure that someone has not replaced the legitimate copy of the program you want to download with a modified version (with a back door perhaps!), and also supplied their own md5 checksum of that spurious program so you'll never know the difference?!
Most of the time that may not be a serious enough possibility that you have to take steps to make sure it didn't happen. If the site is that of a major software manufacturer (such as Microsoft) or a sophisticated Internet software supplier (such as MIT), probably you are ok. But the only way to be entirely sure is for the trusted source of that software to generate a checksum (using md5 say), and for you to get a copy of that checksum via a trusted channel.
Simson Garfinkel provides an example of this in his book on Pretty Good Privacy. He reprints part of a 1994 email message from CERT (Computer Emergency Response Team) notifying interested parties (such as system administrators) that a serious security bug had been found in the ftp program itself. This bug could allow someone to gain root access to a Unix computer, and then do pretty much anything they wanted to. The message says that a new version of ftp is available, and gives the filename and site (wuarchive.wustl.edu, in this case) from which it can be downloaded. And it also gives an md5 checksum for the new ftp file. Garfinkel remarks:
| |
Why does CERT use MD5 codes? So people can verify the authenticity of the patch before they install it. After receiving the message from CERT and downloading the patch, system administrators are supposed to compute the MD5 of the binary, which provides two indications. First, if the MD5 of the binary matches the one published in the CERT message, a system administrator knows the file wasn't damaged during the download; and second, and more importantly, if the two MD5 codes match, a system administrator can be sure hackers haven't broken into the computer wuarchive.wustl.edu and replaced the patch with a program that contains security holes.[7] |
|
Garfinkel goes on to note, however, that there is a flaw in CERT's approach. How do we know the email message we're getting is really from them? CERT, he says, does provide a separate ASCII-armored signature file that allows you to check on the authenticity of each alert message. But it would have been much simpler to just include a digital signature (using PGP, for example) in the alert message itself.[8]
Traditionally passwords on Unix systems are kept (in encrypted form) in the file /etc/passwd. These passwords are encrypted with the crypt() function. The original Unix encryption algorithm, known as "crypt(1)" is easy for a cryptanalyst to break, and, in fact, there is a public-domain Unix program called Crypt Breakers Workbench (CBW) which can be used to break files (and passwords) encrypted with crypt(1).[9] The version of crypt() now widely used, "CRYPT(3)", is a one-way hash function and a variant of the DES (Data Encryption Standard) algorithm. CRYPT(3) is much more secure than crypt(1).
But there are still problems with this traditional Unix password scheme. One problem is just that the encrypted passwords are in a publicly-accessable file. /etc/passwd needs to be readable by every user so that various Unix programs can determine a user's name given their userid, and so forth. Although it is very difficult to go from the encrypted password to the actual password, it is still dangerous to publicly show encrypted passwords. Attackers can run whole dictionaries full of possible passwords through crypt(), and compare all the encrypted passwords they generate with the existing /etc/passwd file. Since many users continue to use poorly chosen passwords, some of these will match. The attacker will then know the passwords for those userids. There is even a program called crack that automates the process for hackers. Lincoln Stein says that crack "typically recovers 20 percent to 25 percent of passwords."[10]
The solution to this particular problem is to use a "shadow" password scheme which removes even the encrypted passwords from /etc/passwd and puts them in the /etc/shadow file which only the Superuser can read.
But DES and crypt() themselves have become more than just somewhat questionable. In January 1997, the RSA Data Security Corporation posted on their Web site a short English phrase which had been encrypted with DES and offered $10,000 to the first person to crack the message. Five months later a concerted effort by a large group of volunteers decyphered the message and won the prize. Lincoln Stein remarks that "Although it made headlines, the result was hardly surprising to cryptographers, who had been warning for years that DES was no longer a match for modern computers."[11]
The logical choice to replace DES as an encryption algorithm for passwords was md5, which is a much stronger one-way hash function than CRYPT(3). This has been implemented on many Unix and Linux systems, though many older Unix systems haven't yet been updated. Both shadow passwords and md5 encrypted passwords are now the default on Red Hat Linux installations.
Strictly speaking, we should not call md5 checksums of passwords "encrypted passwords", even though loosely speaking that is a convenient term. Ordinarily when you talk about encryption you imply that the information in the plain text data is still there in the encrypted data, and that some conceivable decryption method could recover it. But with most one-way hash functions (including md5) this is simply not true. Actually, the way Unix/Linux systems work, it is never necessary to recover a plain text password from an "encrypted password". When a user logs in, the system does not "decrypt" the stored checksum and compare it to the plain text password supplied by the user. Instead, it takes that user-supplied plain text password, generates a new md5 checksum, and then compares that new checksum with the stored checksum. If they match, the user must have supplied the correct password, and the login is allowed to proceed.
What do md5 "encrypted passwords" (loosely speaking!) look like? Here is a portion of the password database on the CCSF Springfield NIS Cluster, where some (not all) of the passwords are encrypted using md5sum. (Presumably the password setup has been changed from time to time on this network system.)
$ ypcat passwd ykim06:yiVLuFbWYSzP.:631:100:yuseung kim:/home/ykim06:/bin/bash rlum01:9sCdA9GNebQb6:576:100:rose lum:/home/rlum01:/bin/bash ... awong22:$1$vHKd8.CI$GdL2nEXv61Pp14BJ9JJ0A0:663:663::/home/awong22:/bin/bash opietr01:XMn0WSKVBmWHg:682:682::/home/opietr01:/bin/bash jlam01:$1$3EkCpxZb$S4PbEN9XUzc1mbAs2piAh.:703:703::/home/jlam01:/bin/bash souyan01:$1$a.iR1avo$Y9v0/Iq/aiqyp70q2i3o4.:709:709::/home/souyan01:/bin/bash tkassi01:wMOr./VjPWwxQ:634:100:tatiana m kassianik:/home/tkassi01:/bin/bash rgonza11:$1$8QHk/85r$rVg6DD8V91HnkGf026cGH/:686:686::/home/rgonza11:/bin/bash dlee22:8aOcvXALDDQG.:543:100:david h. lee:/home/dlee22:/bin/bash ...
In the above listing, you can think of the second field in each line (between the first and second colons) as the "encrypted password". The passwords encrypted with the DES standard are 13 characters long, while the md5 encrypted passwords are 34 characters long. Note that all the md5 encrypted passwords start with the 3-character string $1$ and also have a $ in position 12, which separates the encrypted password into two pieces. (I don't know why this is done, but see below.) This means that the effective length of an md5 encrypted password is 30 characters, compared to the 13 characters using the DES method.
Both DES and md5 encrypted passwords are actually numbers expressed in base-64 (also known as radix-64), using the characters: 0-9, a-z, A-Z, / and . (period). You might think that this means there could be 1364 possible DES passwords, and 3064 possible md5 passwords. But neither of these is probably really the case. Remember that md5 only generates a 128 bit checksum, which is 32 hex digits, or 22 base-64 digits. Note that there are exactly 22 base-64 digits after the $ at position 12. This suggests to me that the actual checksum for the password is really only the characters from position 13 through 34, and that characters 4 through 11 are used for some other purpose (such as possibly some kind of a checksum of the md5 checksum). But I'm just speculating here.
In any case, it is clear that md5 encrypted passwords are far more numerous, and far more secure, than DES/crypt() encrypted passwords. Using md5 encrypted passwords is definitely the better option, especially in this age of ever more powerful computers, and ever more adept hackers--not to mention ever more sinister governments!
The md5 algorithm has also found a use in generating digital signatures. It is used within Pretty Good Privacy (PGP) for this purpose, for example. Let's look briefly at how PGP digital signatures make use of md5.
Recall that PGP is a two key encryption system: each person has both a public key and a private key. When Alice encrypts a message for Bob, she uses Bob's public key. Then only Bob can decrypt it, using his private key. But what if Alice doesn't care if anybody else can read her message, and merely wants Bob to be able to know for certain that the message came from her? One way she could do this is by encrypting the message with her private key. Then Bob (or anyone else who gets ahold of the message!) will be able to decrypt it with Alice's public key, and by doing so they will know it is in fact from Alice, since she alone could have encrypted it with her private key.
But there is another variation on this scheme. Suppose, once again, that Alice has prepared a message for Bob which she doesn't need to encrypt, but which she wants Bob to be sure was from her, and also to be sure was not altered in transit. Suppose the message is in her file "message1". She can digitally sign the message (in a form appropriate for email) by entering:
pgp -sta message1This will generate a text file with the name message1.asc, which will consist of her original message followed by a PGP digital signature block. The whole thing might look like this:
-----BEGIN PGP SIGNED MESSAGE----- Hi Bob, Don't forget you owe me $50! - --Alice -----BEGIN PGP SIGNATURE----- Version: PGP 6.5.2 iQCVAwUBOkQFXUigJmnQ/mSjAQHA0AP+Pa3AQSeBEPfF6PvL5NHP/6sE59gXX/7e 9K5ttgWPqSNPF4oOJ1ITMu4QJDOEwvyzLfW3M/VoWfdf40PfmyiSebTX4UhrZSHr 5ryIaET/v7EtA3yTpnpgQMKHzAeLzGE20VGxFOWn8TNOmNKjjX1RuddjTRqmXFEO x3QmxMyT/Dg= =1a5B -----END PGP SIGNATURE-----
Now here's the good part. That signature block at the end of the message is actually the md5 checksum for the preceding text message, which is then encrypted with Alice's private key. When Bob gets this message (and assuming he has Alice's public key on his key chain), he can then run it through pgp as in the following example:
Return to My Home Page