SELECTION OF HASHING ALGORITHMS 

 Tim Boland 

 Gary Fisher 

JUNE 30, 2000 

INTRODUCTION 

The National Software Reference Library (NSRL) Reference Data Set (RDS) is built on 

file signature generation technology that is used primarily in cryptography. The selection 

of the specific file signature generation routines is based on customer requirements and 

the necessity to provide a level of confidence in the reference data that will allow it to be 

used in the U.S. Courts. This document gives an overview of the various hashing 

algorithms considered, as well as implementations of those algorithms. It also gives 

factors regarding their selection and use. 

Hashing is an extremely good way to verify the integrity of a sequence of data bits (e.g., 

to make sure the contents of the sequence haven’t been changed inadvertently). The 

sequence might make up a character string, a file, a directory, or a message representing 

data (binary 1s or 0s) stored in a computer system. The word “hash” means to “chop into 

small pieces” (REF1). A hashing algorithm is a mathematical function (or a series of 

functions) taking as input the aforementioned sequence of bits and generating as output a 

code (value) produced from the data bits and possibly including both code and data bits. 

Two files with exactly the same bit patterns should hash to the same code using the same 

hashing algorithm. If a hash for a file stays the same, there is only an extremely small 

probability that the file has been changed. On the other hand, if the hashes for the files do 

not match, then the files are not the same. Thus, hashes could be used as a primary 

verification tool to find identical files. The output code of the hash function should have a 

“random” property, so that different sequences of bits hash to different values as much as 

possible. Hashes are used in “scatter storage” systems, in digital signature applications, 

and recently in computer forensics applications, to determine whether the contents of a 

suspect machine have been modified maliciously. Hashing algorithms can be efficiently 

implemented on modern computers. 

Hashing algorithms fall within the realm of error detection techniques. In a general sense, 

the aim of an error detection technique is to enable the receiver of a message transmitted 

through a noisy (error-introducing) channel to determine whether the message has been 

corrupted. Some hashing algorithms perform complex transformations on the message to 

inject it with redundant information, while others leave the data intact and append a hash 

value on the end of a message. In any case, the transmitter may construct a hash value 

that is a function of the message. The receiver can then use the same hashing algorithm to 

compute the hash value of the received message and compare it with the transmitted hash 

value to see if the message was correctly received. If the hash values match, then the 
message was correctly received; if not, then there must have been an error in one or more 

of the data bits of the message. 

The National Institute of Standards and Technology (NIST) of the U.S. Department of 

Commerce has been asked to investigate commonly-used hashing algorithms in support 

of the National Software Reference Library (NSRL). There are several algorithms 

available, differing in complexity, robustness, ease of use, and machine efficiency. 

Generally, “hardware (physical device)” methods of computing hashes involve extensive 

bit manipulations, and are relatively inefficient for a software (programmatic) 

computation, so the algorithms discussed contain software methodologies to streamline 

the hashing process. What is involved in all the algorithms is a method to break up the 

input into manageable portions, and manipulate the input in a systematic way over and 

over (iteratively). The algorithms generally differ in the degree to which they do this, and 

the number of iterations involved. 

 

Given the above, NIST investigated available implementations of four different hashing 

algorithms and tested the algorithm output on some test data. The purpose of this exercise 

was to define some “reference” implementations for verifying the correctness of entries 

in the NSRL Reference Data Set (RDS). Multiple algorithms were considered because of 

the need for “double-checking” results and because many facilities use multiple hashing 

algorithms simultaneously. Performance metrics mentioned above were used in 

evaluating candidate implementations. 

For each algorithm, the authorities (official sources and sanctions) of the source programs 

and tests used for testing accuracy will be described. Algorithms mentioned in this report 

may have limitations (clashes found, performance, etc.), which will be mentioned as 

appropriate. All implementations evaluated are freely available from the Internet. Each of 

the four algorithms will be described below, starting with a high-level overview and 

progressing to more detail as appropriate. 

CRC32 

The cyclic redundancy code (CRC) algorithm is the simplest of the four hashing 

algorithm choices, but also the least robust. The name means that the algorithm operates 

in repetitive (cyclic) redundant cycles to produce an output hash code. The “32” indicates 

the number of bits being considered to produce the hash code (explained below). The 

CRC algorithm is a key component in the error-detecting capabilities of many 

communications protocols. In a CRC algorithm, the transmitter of a message constructs a 

value (called the checksum) and appends it to the message. The receiver can then use the 

same function to compute the checksum of the received message and compare it with the 

appended checksum to see if the message was correctly received. For example, if we 

chose a checksum function which was the sum of the decimal numbers in a message, it 

might go something as follows: Message-1 2 3, Message with checksum – 1 2 3 6 (6 is 

sum of 1 and 2 and 3), Message after transmission – 1 2 4 6. Here the third decimal 

number was corrupted from 3 to 4, and the receiver can detect this by computing the 

checksum (7=1+2+4) from the message, and compare it with the transmitted checksum of 

6. Obviously, both sender and receiver must be using the same algorithm to be consistent. 
If the checksum itself is corrupted, a correctly transmitted message might be incorrectly 

identified as a corrupted one. However, this is a side-safe failure. A dangerous-side 

failure occurs where the message and/or checksum is corrupted in a manner that results in 

a transmission that is internally consistent. Unfortunately, this possibility is completely 

unavoidable and the best that can be done is to minimize its probability by increasing the 

amount of information in the checksum (REF2). 

The above example is obviously very simple, and would not suffice for rigorous error 

detection. A more complex checksum function is needed. While addition is clearly not 

strong enough to form an effective checksum, it turns out that division is, so long as the 

divisor (number to divide by) is about as wide as the checksum register (place to store the 

checksum value). 

 

The basic idea behind CRC algorithms is simply to treat the message as an enormous 

binary number, to divide it by another fixed binary number, get a quotient, and make the 

remainder from this division the checksum. Upon receipt of the message, the receiver can 

perform the same division and compare the remainder with the “checksum” (transmitted 

remainder). For example, when dividing decimal 11 (message) by 4 (divisor) we get a 

value of 2 (quotient) with a remainder of 3. 

With CRC division, instead of viewing the numbers mentioned above as positive 

integers, they are viewed as polynomials with binary coefficients. This is done by treating 

each number as a bit-string whose bits are the coefficients of a polynomial. For example, 

the ordinary number 23 (decimal) is 10111 (binary) and so it corresponds to the 

polynomial x**4 + x**2 + x**1 + x**0. Polynomials are used because they provide 

useful mathematical machinery in the calculations. CRC arithmetic is primarily about 

XORing (exclusive-ORing) particular values at various shifting offsets, which has the 

effect of doing the binary division. An exclusive-OR function produces 1 if the two input 

bits are different; otherwise it produces 0. 

The CRC algorithm can be applied to messages of different widths (12, 16, or 32 bits). 

We are considering the 32-bit (CRC32) algorithm here because it is the most robust. 

In this case the polynomial is 32 bits wide and the CRC32 checksum is also 32 bits. 

This also simplifies the calculation on most modern computers. Other CRC polynomials 

used besides CRC32 are CRC12, CRC16, and CRC-CCITT, from the Consultative 

Committee for Telephone and Telegraph (CCITT). 

 

On PCs one can deal with binary numbers of only 32 bits or fewer, so one must break up 

the enormous binary number mentioned above into manageable chunks. That’s exactly 

what the two CRC algorithms mentioned below do. In order to speed up the process, the 

algorithms use a pre-calculated look-up table; the table contains a CRC for each character 

code between 0 and 255, so that the calculation doesn’t need to be repeated as the text 

strings are processed. This process has the effect of performing the division of the 

enormous binary number by the generator polynomial, but in increments, due to the 

limitations of modern computing. In other words, instead of computing the CRC bit by 
bit, a 256-element lookup table can be used to perform the equivalent of 8 bit operations 

at a time. 

 

To perform a CRC calculation, the user needs to choose a divisor. Generally the divisor is 

called the “generator polynomial” or simply the “polynomial”, and is a key parameter of 

any CRC algorithm. One can choose any polynomial and come up with a CRC algorithm. 

However, some polynomials are better then others. An example of a polynomial used 

might be 79,764,919 decimal, or 0x04c11db7 hexadecimal. Theoretical mathematicians 

have calculated certain polynomials to provide the least duplications in remainders. 

CRC Implementation 

To implement a CRC algorithm is to implement CRC division. There are two reasons 

why the divide instruction of the host machine cannot be used. The first is that the 

division must be in CRC arithmetic. The second is that the dividend might be ten 

megabytes (1 byte=8 bits) long, and today’s processors do not have registers large 

enough to hold a dividend of this size. To implement CRC division, we have to feed the 

message in smaller chunks through a division register. 

Originally there were seven candidate CRC32 implementations (using C or C++ highlevel programming languages) under consideration (which represents nearly all of the 

researched CRC32 implementations publicly available). Performance metrics used to 

evaluate these implementations were the following (in no particular order of importance): 

speed of execution, ease of use, accuracy, ability to operate on entire files, and choice of 

generator polynomial. One implementation was rejected because it did not produce 

accurate results, two were not set up to operate on entire files (only text strings), and two 

were slow (because they were not “table-driven”). Only two were reasonably fast, 

produced accurate information, were table driven, and used generally accepted generator 

polynomials. Both are table-driven, but one uses a polynomial is from an American 

National Standards Institute (ANSI) X3 Committee, while the other polynomial is not 

explicitly specified in code, but the table entries are the same as compared to the other. 

The two implementations are about the same number of programming statements. Slight 

preference was given for the algorithm that computes values for directories of files as 

well as individual files. 

The test data used to verify the routines was from commonly used PKZIP (REF3) and 

WINZIP (REF4) products, and other various test character strings and file directories. 

Since these products are commonly used and routinely generate CRCs, they would be 

valid benchmarks of accuracy. The CRC outputs are in hex. Both implementations 

verified correctly against the data. There are no apparent limitations in the 

implementations, other than the inherent CRC32 limitations, although one 

implementation produces more cursory output on only one file at a time. More 

information on each of these implementations is given below. 

The first candidate CRC program (using the C language) computes the 32-bit CRC used 

as the frame check (error-detection) sequence in FIPS 71 (REF5) This source code is 

from the Snippets file collection (REF6). It consists of a header file, crc.h, and a main 
program crc_32.c. For this driver routine, first the polynomial itself and its table of 

feedback terms is provided. The polynomial is: 

x**32 + x**26 + x**23 + x**22 + x**16 + x**12 + x**11 + x**10 + x**8 + 

x**7 + x**5 + x**4 + x**2 + x**1 + x**0. 

The polynomial is taken backwards and the highest-order term is placed in the lowestorder bit. The x**32 term is “implied; the least significant bit is the x**31 term, etc. The 

x**0 term (usually shown as “+1”) results in the most significant bit being 1. A hardware 

shift register implementation shifts bits into the lowest-order term (to the right). It is 

optimized here by shifting eight-bit chunks at a time. The calculated CRC must be 

transmitted in order from highest-order term to lowest-order term. The feedback terms 

table consists of 256 32-bit entries. The feedback terms represent the results of eight 

shift/XOR operations for all combinations of data and CRC register values. The CRC 

accumulation logic is the same for all CRC polynomials; the appropriate table just needs 

to be chosen. The table can also be generated at runtime. The values must be right-shifted 

by eight bits by the logic in the updateCRC routine called from the main program; the 

shift must be unsigned (masked with zeroes in the high-order bits). On some hardware 

the shift could probably be optimized by using byte-swap instructions. Unsigned 

variables need to be used consistently. 

The second candidate CRC program (also using the C language) computes a composite 

CRC that is not dependent on the endian type of the machine executing the program. 

“Endian” refers to the order in which received bits are stored. This means the composite 

CRC-32 can be used to test the transfer of a set of files, when transferred in binary mode, 

between machines of different architecture. It is adapted from the “charcnt.c” program 

and “crc16.u” unit modified to include a CRC32 table from Microsoft Systems Journal 

(MSJ) (REF16). “crc32” gives the same values as the PKZIP utility, and has been 

verified using (1) Borland C/C++ (REF14) and (2) Sun C++ (REF15). This source code 

was copyrighted by Earl F. Glynn in 1998 and is available from efg’s Computer Lab 

Mathematics site (REF7). This implementation consists of several files: a driver program 

crc32.c, and several header files. The driver program first defines a table used for bytewise calculation of CRC32. The routine in the main program executes very quickly as 

follows: (1) the input byte is XORed with the low-order byte of the CRC “register” to get 

an index into the table, (2) the CRC “register” is shifted eight bits to the right, and (3) the 

CRC register is XORed with the contents of Table[Index]. Steps (1) through (3) are 

executed for all input bytes. The result in the CRC register is the CRC. 

In sum, CRC hashes are the simplest of those considered, but are also the weakest, in that 

CRC values can be compromised in terms of verification and error detection. (The final 

decision of which form of the algorithm to use will be based on compatibility with 

software provided by the customer. The software is still an unknown in this equation.) 

MD4 

MD4 (message digest level 4) is a one-way hash function designed by Ron Rivest. Oneway hash functions (see REF8) have certain characteristics, in addition to the 
characteristic of taking an arbitrary-length input and returning an output of fixed length; 

they are able to provide a “fingerprint” of a message that is unique. Thus, the MD4 

algorithm takes as input a message of arbitrary length; the algorithm produces as output a 

128-bit hash, or message digest, of the input message. MD4 is more complex than 

CRC32 mentioned above, so it is more “computer-intensive,” but it performs 

transformations on the data itself instead of just appending a checksum as in CRC32, so it 

is more robust, and provides a greater verification and error-detection ability at the price 

of greater complexity. The design goal was that it would be computationally infeasible to 

find two messages that hashed to the same value, or produced the same message digest. It 

would also be computationally infeasible to produce any message having a given prespecified target message digest. 

The MD4 message-digest algorithm provides a “fingerprint” of a message of arbitrary 

length. The difficulty of coming up with two messages having the same message digest is 

on the order of 2**64 operations, and the difficulty of coming up with any message 

having a given message digest is on the order of 2**128 operations. 

The MD4 algorithm is intended for digital signature applications, where a large file must 

be “compressed” in a secure manner before being encrypted with a private (secret) key 

under a public-key cryptosystem. This involves disguising the contents of a file so that it 

may be read only by intended recipients. The MD4 algorithm is designed to be quite fast 

on 32-bit machines. In addition, the MD4 algorithm does not require any large 

substitution tables; the algorithm can be coded compactly. MD4’s security is not based on 

any assumption, such as the difficulty of factoring. MD4 is suitable for high-speed 

software implementations; it is based on a simple set of bit manipulations on 32-bit 

operands. 

MD4 is as simple as possible, without large data structures or a complicated program, and 

is optimized for microprocessor architectures. The MD4 implementation (in the C 

language) chosen was from Internet Engineering Task Force (IETF) RFC1320 (REF9). It 

was chosen because it faithfully reproduces the MD4 algorithm (also found in RFC1320) 

and is portable. In summary form, the MD4 algorithm works as follows: (1) padding bits 

are appended to the file, (2) the length is appended, (3) the MD buffer is initialized, the 

message is processed in 16-word blocks, and (5) output is produced. A detailed 

description of these steps follows. 

Suppose there is a b-bit message as input, and desired message digest from that input as 

output. Here b is an arbitrary nonnegative integer, and it may be arbitrarily large. Thus 

the message may be written down as follows: m_0 m_1 .... M(b-1). 

For (1) above, the message is then padded (extended) so that its length (in bits) is just 64 

bits shy of being a multiple of 512 bits long. Padding is performed as follows: a single 

“1” bit is appended to the message, and then “0” bits are appended subject to the 

requirement above. In all, at least 1 bit and at most 512 bits are appended. 
For (2) above, a 64-bit representation of b (the length of the message before the padding 

bits were added) is appended to the result of the previous step. At this point, the resulting 

message (after padding with bits and with b) has a length that is an exact multiple of 512 

bits (meaning that the message length divided by 512 is an integer). Equivalently, this 

message has a length that is an exact multiple of 16 (32-bit) words. 

For (3) above, a four-word buffer (A,B,C,D) is used to compute the message digest. Here 

each of A, B, C, and D is a 32-bit register (high-speed storage unit), initialized as follows: 

Word A: 01 23 45 67, Word B: 89 ab cd ef, Word C: fe dc ba 98, Word D: 76 54 32 10. 

For (4) above, three auxiliary functions (F, G, H) are defined that each take as input three 

32-bit words and produce as output one 32-bit word. In each bit position F acts as a 

conditional: if X then Y else Z. In each bit position G acts as a majority function: if at 

least two of X, Y, and Z are on, then G has a “1” bit in that bit position; otherwise, G has 

a “0” bit. The function H is the bit-wise XOR or “parity (error checking)” function; it has 

properties similar to those of F and G. Then each 16-word block is processed in three 

rounds as outlined below. Each round uses a different operation 16 times, and each round 

involves one of the functions F, G, or H (e.g., round 1 uses F, round 2 uses G, and round 

3 uses H). Each operation performs a function on three of A, B, C, and D. Then it adds 

that result to the fourth variable, a sub-block of the text, and a constant (which could be 

0). It then rotates that result to the right a variable number of bits. Then the result replaces 

one of A, B, C, or D. Finally, each of the four registers A, B, C, D mentioned above, is 

incremented by the values held before processing. This concludes the processing of a 16-

word block; then it’s time to move on to the next 16-word block until there are none left. 

For (5) above, the resultant message digest produced is the values contained in A, B, C, 

and D. These values are “concatenated”, such that the digest starts with the first bit of A 

and ends with the last bit of D. 

In summary, the MD4 algorithm produces a “fingerprint,” or message digest of a 

message of arbitrary length. It has been carefully scrutinized for weaknesses; however, 

further security analysis is justified. It may be used if a greater degree of error detection 

than CRC32 is desired. 

The MD4 implementation chosen consists of four files: global.h, md4.h, md4c.c, and 

mddriver.c. The driver compiles for MD5 by default but can compile for MD2 or MD4 if 

the symbol MD is defined on the C compiler command lines as 2 or 4. The file global.h 

defines data types and constants. The file md4.h is a header file for md4c.c. In md4c.c, 

other constants are defined, and then steps (1) through (5) are implemented as described 

above. The program mddriver.c is a test driver for MD4. 

The implementation is portable and should work on many different platforms. It is not 

difficult to optimize the implementation on particular platforms. 

MD4 test results were compared against sample data from the Handbook of Applied 

Cryptography (REF10), as well as test data in the program from IETF RFC1320, and 
were found to be in agreement with test data. There are no known limitations of the 

implementation other than inherent limitations in the MD4 algorithm. Researchers have 

shown that clashes, or duplicate hash strings, can be generated from different files. 

MD-5 

Message Digest level 5 (MD5) is an improved version of MD4. Although more complex 

than MD4, it is similar in design and also produces a 128-bit hash. After some initial 

processing, MD5 processes the input text in 512-bit blocks, divided into 16 32-bit subblocks. The output of the algorithm is a set of four 32-bit blocks, which concatenate to 

form a single 128-bit hash value. The MD5 algorithm potentially offers a greater degree 

of error detection than does MD4, at the price of slightly more complication. 

The MD5 message-digest algorithm takes as input a message of arbitrary length and 

produces as output a 128-bit “fingerprint” or “message digest” of the input. It is 

computationally infeasible to produce two messages having the same message digest, or 

to produce any message having a given pre-specified target message digest. The MD5 

algorithm is intended for digital signature applications, where a large file must be 

“compressed” in a secure manner before being encrypted with a private (secret) key 

under a public-key cryptosystem. This involves disguising the contents of a file so that it 

is recognizable only by intended recipients. 

The MD5 algorithm is designed to be very fast on 32-bit machines. In addition, the MD5 

algorithm does not require any large substitution tables; the algorithm can be coded quite 

compactly. 

The MD5 algorithm is an extension of the MD4 message-digest algorithm. MD5 is 

slightly slower than MD4, but is more “conservative” in design. MD5 was designed 

because it was felt that MD4 was perhaps being adopted for use more quickly than 

justified by the existing critical review; because MD4 was designed to be exceptionally 

fast, it was “at the edge” in terms of risking successful cryptanalytic attack (meaning that 

someone, if they tried enough times, could “break” the code, or recognize a message 

from its code). MD5 backs off somewhat, giving up a little in speed for a much greater 

likelihood of ultimate security. It incorporates some suggestions made by various 

reviewers, and contains additional optimizations. 

The MD5 implementation (using the C language) chosen was from IETF RFC1321 

(REF11) . It was chosen because it faithfully reproduces the MD4 algorithm (also found 

in IETF RFC1321) and is portable. 

The MD5 message-digest algorithm performs the following five steps: (1) append 

padding bits, (2) append length, (3) initialize MD buffer, (4) process message in 16-word 

blocks, and (5) generate output. These steps are described in detail below. 

Suppose there is a b-bit message as input, and desired message digest from that input as 

output. Here b is an arbitrary nonnegative integer, and it may be arbitrarily large. Thus 

the message may be written down as follows: m_0 m_1 .... M(b-1). 
For (1) above, the message is then padded (extended) so that its length (in bits) is just 64 

bits shy of being a multiple of 512 bits long. Padding is performed as follows: a single 

“1” bit is appended to the message, and then “0” bits are appended subject to the 

requirement above. In all, at least 1 bit and at most 512 bits are appended 

For (2) above, a 64-bit representation of b (the length of the message before the padding 

bits were added) is appended to the result of the previous step. At this point, the resulting 

message (after padding with bits and with b) has a length that is an exact multiple of 512 

bits (meaning that the message length divided by 512 is an integer). Equivalently, this 

message has a length that is an exact multiple of 16 (32-bit) words. 

For (3) above, a four-word buffer (A, B, C, and D) is used to compute the message digest. 

Here each of A, B, C, and D is a 32-bit register (high-speed storage unit), initialized as 

follows: 

Word A: 01 23 45 67, Word B: 89 ab cd ef, Word C: fe dc ba 98, Word D: 76 54 32 10. 

For (4) above, four auxiliary functions (F, G, H, and I) are defined such that each takes as 

input three 32-bit words and produces as output one 32-bit word. In each bit position, F 

acts as a conditional: if X then Y else Z. The functions G, H, and I are similar to the 

function F. 

The function H is the bit-wise XOR(exclusive-OR, or “parity”) function of its inputs. 

This step uses a 64-element table constructed from the sine trigonometric function. Then 

each 16-word block is processed in four rounds as outlined below. Each round involves 

using a different operation 16 times, and each round involves one of the functions F, G, 

H, or I, plus the table T (e.g., round 1 uses F and T, round 2 uses G and T, round 3 uses H 

and T, and round 4 uses I and T). Each operation performs a nonlinear function on three 

of A, B, C, and D. Then it adds that result to the fourth variable, a sub-block of the text 

and a constant. It then rotates that result to the right a variable number of bits and adds 

the result to one of A, B, C, or D. The result replaces one of A, B, C, or D. Finally, each 

of the four registers A, B, C, and D is incremented by the values held before processing. 

This concludes the processing of the 16-word block, and it’s time to move to the next one 

until there are none left. 

For (5) above, the resultant message digest produced is A, B, C, D. These values are 

“concatenated” such that the digest starts with the first bit of A and ends with the last bit 

of D. 

The following are the differences between MD4 and MD5: (1) a fourth round has been 

added in MD5; (2) each step in MD5 has a unique additive constant; (3) the function G in 

round 2 was changed to make G less symmetric (balanced); (4) each step in MD5 adds in 

the result of the previous step (promoting a faster “avalanche effect”); (5) the order in 

which input words are accessed in rounds 2 and 3 is changed, to make these patterns less 

like each other; and (6) the shift amounts in each round have been approximately 
optimized to yield a faster “avalanche effect”, and the shifts in different rounds are 

distinct. 

The MD5 message-digest algorithm is relatively simple to implement, and provides a 

“fingerprint” or message digest of a message of arbitrary length. The difficulty of coming 

up with two messages having the same message digest is on the order of 264 operations, 

and that the difficulty of coming up with any message having a given message digest is 

on the order of 2128 operations. 

The MD5 implementation chosen consists of four files: global.h, md5.h, md5c.c, and 

mddriver.c, The file global.h defines common data types and constants. The file md5.h is 

a header file for md5c.c. The file md5c.c defines other constants and then performs the 

processing defined in steps (1) through (5) above. The file mddriver.c is a test driver for 

MD5. The implementation is portable and should work on many different platforms. It is 

not difficult to optimize the implementation on particular platforms. 

MD5 test results were compared against sample data from the Handbook of Applied 

Cryptography, as well as test data in the program from IETF RFC1321, and were found 

to be in agreement with this test data.. There are no known limitations of the 

implementation other than the inherent limitations of the MD5 algorithm. The MD5 

algorithm has been susceptible to sustained attacks in the past, but it still is the most 

robust choice so far. 

SHA-1 

NIST, along with the National Security Agency (NSA), designed the Secure Hash 

Algorithm Revision 1 (SHA-1) for use with the Digital Signature Standard (DSS) 

(REF12); this standard is the Secure Hash Standard; SHA-1 is the algorithm used in the 

standard. Additionally, for applications not requiring a digital signature, the SHA-1 can 

be used whenever a secure hash algorithm is required. The SHA-1 is specified by NIST 

Federal Information Processing Standard (FIPS) 180-1 (REF13). The SHA-1 is a 

technical revision of the SHA (specified by FIPS 180, which has been superseded). The 

SHA-1 can be used to generate a condensed representation of a message called a message 

digest. The SHA-1 is used by both the transmitter and intended receiver of a message in 

computing and verifying a digital signature. 

When a message of any length less than 264 bits is input, the SHA-1 produces a 160-bit 

output called a message digest; this output is longer than that of MD5.. The message 

digest is usually much smaller in size than the message. The SHA-1 is called secure 

because it is computationally infeasible to find a message which corresponds to a given 

message digest, or to find two different messages which produce the same message 

digest. Any change to a message in transit will, with a very high probability, result in a 

different message digest. The SHA-1 is based on principles similar to those used in the 

development of MD4, and is closely modeled after MD4. The SHA-1 may be 

implemented in software, firmware, hardware, or any combination thereof. 

Implementations of the SHA-1 may be validated by NIST in accordance with a reference 
implementation produced at NIST. It is this reference implementation that is selected in 

this study. 

In summary, the SHA-1 is more complex than the choices considered thus far, but 

presents a more robust solution than the other hashing algorithms considered. Thus far 

the SHA-1 has been impervious to compromise. 

Input to the SHA-1 should be considered to be a bit string. The length of the message is 

the number of bits in the message. The purpose of message padding is to make the total 

length of a padded message a multiple of 512. The SHA-1 sequentially processes blocks 

of 512 bits when computing the message digest. A sequence of logical functions f(0), 

f(1), ... , f(79) is used in the SHA-1. The message digest is computed using the final 

padded message. The computation uses two buffers, each consisting of five 32-bit words, 

and a sequence of eighty 32-bit words. A more detailed description of the SHA-1 

algorithm is given below. 

First, the message is padded to make it a multiple of 512 bits long. Padding is exactly the 

same as in MD5: first append a one, then as many zeros as necessary to make it 64 bits 

short of a multiple of 512, and finally a 64-bit representation of the length of the message 

before padding. Then five 32-bit variables (in contrast to the four for MD5) are initialized 

as follows (in hexadecimal): 

A=0x67452301, B=0xefcdab89, C=0x98badcfe, D=0x10325476, and 

E=0xc3d2e1f0. 

The main loop of the algorithm then begins. It processes the message 512 bits at a time 

and continues for as many 512-bit blocks as are in the message. First the five variables 

are copied into different variables: a gets A, b gets B, c gets C, d gets D, and e gets E. 

The main loop has four rounds of 20 operations each (in contrast to MD5, which has four 

rounds of 16 operations each). Each operation performs a nonlinear function on three of 

a, b, c, d, and e, and then does shifting and adding similar to MD5. Shifting the variables 

accomplishes the same purpose as in MD5 by using different variables in different 

locations. After all of this, a, b, c, d, and e are added to A, B, C, D, and E respectively, 

and the algorithm continues with the next block of data. The final output is the 

concatenation of A, B, C, D, and E. 

The SHA is MD5 with the addition of an expanded transformation, and extra round, and 

better “avalanche” effect. There are no known cryptographic attacks against the SHA-1. 

Because it produces a 160-bit hash, it is more resistant to brute-force attacks than 128-bit 

hash functions. 

The NIST SHA-1 implementation (using the C language) consists of nine files: Sha.h, 

Main.c, Config.h, Shautil.obj, Sha.c, Shautil.c, Sha.obj, makefile, and Main.obj. The file 

Main.c is the driver program for the implementation; it indicates whether to test against 

FIPS180, to hash a string, or to hash one or more files. The routine Shautil.c merely 
computes the SHA of the string “abc” and checks the result against the known hash of 

“abc”. The file Sha.c is the routine that actually implements the SHA. The 

implementation is conformant to FIPS180-1, and was tested against reference data in the 

FIPS, as well as test data from the Handbook of Applied Cryptography. Results verified 

against all test data. 

Conclusion 

In this document we have provided information concerning our selection of 

implementations for the hashing algorithms CRC32, MD4, MD5, and SHA-1, as well as 

background and information on the hashing algorithms themselves. Various products use 

one or more of the hashing algorithms MD4, MD5, SHA-1, and CRC32. In summary, 

moving from CRC32 to MD4 to MD5 to SHA-1, complexity increases, but so does 

robustness and degree of error-detection. Which algorithm to use (and which 

implementation of an algorithm) depends on a number of factors, including degree of 

security required and machine limitations. 

Bibliography 

(REF1) Webster’s Ninth New Collegiate Dictionary, 1984, Merriam Webster Inc. 

(REF2) A Painless Guide to CRC Error Detection Algorithms Index V3.00, September 

1996, http://www.repairfaq.org/filipg/LINK/F_crc_v3.html 

(REF3) PKZIP Program, http://www.pkzip.com

(REF4) WINZIP Program, http://www.winzip.com

(REF5) NIST FIPS 71, May 1980 

(REF6) Snippets Collection, http://www.brokersys.com/snippets/ 

(REF7) efg’s Computer Lab Mathematics, Cyclic Redundancy Code Calculator, 

http://www.efg2.com/lab/Mathematics/CRC.htm

(REF8) Schneier, Bruce: Applied Cryptography, Second Edition, 1996, John Wiley & 

Sons. 

(REF9) IETF RFC1320, R.L.Rivest, “The MD4 Message Digest Algorithm, April 1992 

(REF10) A.J.Menezes, P. van Oorschot, S.Vanstone, The Handbook of Applied 

Cryptography, CRC Press, October 1996 

(REF11) IETF RFC1321, R.L.Rivest, “The MD5 Message Digest Algorithm, April 1992 

(REF12) NIST FIPS 186, Digital Signature Standard, U.S. Department of Commerce, 

May 1994 

(REF13) NIST FIPS 180-1, Secure Hash Standard, U.S. Department of Commerce, April 

1995 (supersedes FIPS 180) 

(REF14) Borland Corporation, http://www.borland.com

(REF15) Sun Microsystems Corporation, http://www.sun.com

(REF16) Microsoft Systems Journal, http://www.microsoft.com/msj