>From: Dennis Branstad, NIST Fellow
On January 31, 1992, NIST published in the Federal Register a proposed
Secure Hash Standard (SHS) designed to work with the proposed Digital
Signature Standard (DSS). I am taking the liberty to send you an electronic
copy of the proposed standard's announcement section, technical
specifications and appendix A. Because of mail limitations, I left off
appendix B which is just a second example and the federal register
solication for comments. Miles Smid is the point of contact for comments
which are due in 90 days. The following is the core of the proposed
standard. Note that the name implies only that the algorithm, to the best
of our knowledge, exhibits the qualities needed for a hashing algorithm
acceptable to work with the DSS. Also note the credit to Ron Rivest.
SECURE HASH STANDARD (SHS)
Abstract
This standard specifies a Secure Hash Algorithm (SHA) which can
be used to generate a message digest for a message. A message
digest is a condensed version of the original message. This
algorithm can be used with the Digital Signature Standard (DSS).
Key words: ADP security, computer security, digital signatures,
Federal Information Processing Standard, hash algorithm.
Name of Standard: Secure Hash Standard.
Category of Standard: ADP Operations, Computer Security.
Explanation: This Standard specifies a Secure Hash Algorithm (SHA),
which is necessary to ensure the security of the Digital Signature
Algorithm (DSA). When a message of any length < 2^64 bits is input,
the SHA produces a 160-bit output called a message digest. The
message digest is then input to the DSA which computes the
signature for the message. Signing the message digest rather than
the message often improves the efficiency of the process, because
the message digest is usually much smaller than the message. The
same message digest should be obtained by the verifier of the
signature when the received version of the message is used as input
to the SHA. The SHA is called secure because it is designed to be
computationally infeasible to recover a message corresponding 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 very high probability, result in a different
message digest, and the signature will fail to verify. The SHA is
based on principles similar to those used by Professor Ronald L. Rivest
of MIT when designing the MD4 hash algorithm ("The MD4 Message Digest
Algorithm," Advances in Cryptology - CRYPTO '90 Proceedings,
Springer-Verlag, 1991, pp. 303-311).
Approving Authority: Secretary of Commerce.
Maintenance Agency: Computer Systems Laboratory, National
Institute of Standards and Technology.
Applicability: This standard is applicable to all Federal
departments and agencies for the protection of unclassified
information that is not subject to section 2315 of Title 10, United
States Code, or section 3502(2) of Title 44, United States Code.
This standard is required for use with the Digital Signature
Standard and whenever a secure hash algorithm is required for
federal applications. Private and commercial organizations are
encouraged to adopt and use this standard.
Applications: The SHA is appropriate for use with the Digital
Signature Standard, which in turn may be used in electronic mail,
electronic funds transfer, software distribution, data storage, and
other applications which require data integrity assurance and data
origin authentication. The SHA can also be used whenever it is
necessary to generate a condensed version of a message.
Implementations: The SHA may be implemented in software, firmware,
hardware, or any combination thereof. Only implementations of the
SHA that are validated by NIST will be considered as complying with
this standard. Information about the requirements for validating
implementations of this standard can be obtained from the National
Institute of Standards and Technology, Computer Systems Laboratory,
Attn: SHS Validation, Gaithersburg, MD 20899.
Export Control: Implementations of this standard are subject to
Federal Government export controls as specified in Title 15, Code
of Federal Regulations, Parts 768 through 799. Exporters are
advised to contact the Department of Commerce, Bureau of Export
Administration for more information.
Patents: Implementations of the SHA in this standard may be covered
by U.S. and foreign patents.
Implementation Schedule: This standard becomes effective six months
after the publication date of this FIPS PUB.
Specifications: Federal Information Processing Standard (FIPS YY)
Secure Hash Standard (affixed).
Cross Index:
a. FIPS PUB 46-1, Data Encryption Standard.
b. FIPS PUB 73, Guidelines for Security of Computer
Applications.
c. FIPS PUB 140-1, Security Requirements for Cryptographic
Modules.
d. FIPS PUB XX, Digital Signature Standard.
Qualifications: While it is the intent of this standard to specify
a secure hash algorithm, conformance to this standard does not
assure that a particular implementation is secure. The responsible
authority in each agency or department shall assure that an overall
implementation provides an acceptable level of security. This
standard will be reviewed every five years in order to assess its
adequacy.
Waiver Procedure: Under certain exceptional circumstances, the
heads of Federal departments and agencies may approve waivers to
Federal Information Processing Standards (FIPS). The head of such
agency may redelegate such authority only to a senior official
designated pursuant to section 3506(b) of Title 44, United States
Code. Waiver shall be granted only when:
a. Compliance with a standard would adversely affect the
accomplishment of the mission of an operator of a Federal
computer system; or
b. Compliance with a standard would cause a major adverse
financial impact on the operator which is not offset by
Government-wide savings.
Agency heads may act upon a written waiver request containing the
information detailed above. Agency heads may also act without a
written waiver request when they determine that conditions for
meeting the standard cannot be met. Agency heads may approve
waivers only by a written decision which explains the basis on
which the agency head made the required finding(s). A copy of
each decision, with procurement sensitive or classified portions
clearly identified, shall be sent to: National Institute of
Standards and Technology; ATTN: FIPS Waiver Decisions, Technology
Building, Room B-154, Gaithersburg, MD 20899.
In addition, notice of each waiver granted and each delegation of
authority to approve waivers shall be sent promptly to the
Committee on Government Operations of the House of Representatives
and the Committee on Government Affairs of the Senate and shall be
published promptly in the Federal Register.
When the determination on a waiver applies to the procurement of
equipment and/or services, a notice of the waiver determination
must be published in the Commerce Business Daily as a part of the
notice of solicitation for offers of an acquisition or, if the
waiver determination is made after that notice is published, by
amendment to such notice.
A copy of the waiver, any supporting documents, the document
approving the waiver and any accompanying documents, with such
deletions as the agency is authorized and decides to make under 5
United States Code Section 552(b), shall be part of the procurement
documentation and retained by the agency.
Specifications for a
SECURE HASH STANDARD (SHS)
1. INTRODUCTION
The Secure Hash Algorithm (SHA) specified in this standard is
necessary to ensure the security of the Digital Signature Standard.
When a message of length < 2^64 bits is input, the SHA produces a
160-bit representation of the message called the message digest.
The message digest is used during generation of a signature for the
message. The same message digest should be computed for the
received version of the message, during the process of verifying
the signature. Any change to the message in transit will, with
very high probability, result in a different message digest, and
the signature will fail to verify.
The SHA is designed to have the following properties: it is
computationally infeasible to recover a message corresponding to a
given message digest, or to find two different messages which
produce the same message digest.
2. BIT STRINGS AND INTEGERS
The following terminology related to bit strings and integers
will be used:
a. hex digit = 0, 1, ... , 9, a, ... , f. A hex digit is the
representation of a 4-bit string. Examples: 7 = 0111, a =
1010.
b. word = 32-bit string b(31) b(30) ... b(0). A word may be represented
as a sequence of 8 hex digits. To convert the latter to
a 32-bit string, each hex digit is converted to a 4-bit
string as in (a). Example:
a103fe23 = 1010 0001 0000 0011 1111 1110 0010 0011.
A word is also the representation of an unsigned integer
between 0 and 2^32 - 1, inclusive, with the most significant
bit first. Example: the hex string a103fe23 represents
the decimal integer 2701393443.
c. block = 512-bit string. A block may be represented as a
sequence of 16 words.
d. integer: each integer x in the standard will satisfy 0 <=
x < 2^64. For the purpose of this standard, "integer" and
"unsigned integer" are equivalent. If an integer x
satisfies 0 <= x < 2^32, x may be represented as a word as in
(b). If 2^32 <= x < 2^64, then x = 2^32 y + z where 0 <= y < 2^32
and 0 <= z < 2^32. Hence y and z can be represented as words A and B,
respectively, and x can be represented as the pair of
words (A,B).
Suppose 0 <= x < 2^32. To convert x to a 32-bit string, the
following algorithm may be employed:
y(0) = x;
for i = 0 to 31 do
{
b(i) = 1 if y(i) is odd, b(i) = 0 if y(i) is even;
y(i+1) = (y(i) - b(i))/2;
}
Then x has the 32-bit representation b(31) b(30) ... b(0). Example:
25 = 00000000 00000000 00000000 00011001
= hex 00000019.
If 2^32 <= x < 2^64, the 2-word representation of x is obtained
similarly.
Example:
2^35 + 25 = 8 * 2^32 + 25
= 00000000 00000000 00000000 00001000
00000000 00000000 00000000 00011001
= hex 00000008 00000019.
Conversely, the string b(31) b(30) ... b(0) represents the integer
b(31) * 2^31 + b(30) * 2^30 + ... + b(1) * 2 + b(0).
3. OPERATIONS ON WORDS
The following logical operators will be applied to words:
AND = bitwise logical and.
OR = bitwise logical inclusive-or.
XOR = bitwise logical exclusive-or.
~x = bitwise logical complement of x.
Example:
01101100101110011101001001111011
XOR 01100101110000010110100110110111
--------------------------------
= 00001001011110001011101111001100.
Another operation on words is A + B. This is defined as
follows: words A and B represent integers x and y, where 0 <= x < 2^32
and 0 <= y < 2^32. Compute
z = (x + y) mod 2^32.
Then 0 <= z < 2^32. Convert z to a word, C, and define A + B = C.
Another function on words is S(n,X), where X is a word and n is
an integer with 0 <= n < 32. This is defined by
S(n,X) = (X << n) OR (X >> 32-n).
In the above, X << n is obtained as follows: discard the
leftmost n bits of X and then pad the result with n zeroes on the
right (the result will still be 32 bits). X >> m is obtained by
discarding the rightmost m bits of X and then padding the result
with m zeroes on the left. Thus S(n,X) is equivalent to a circular
shift of X by n positions to the left.
4. MESSAGE PADDING
The SHA takes bit strings as input. Thus, for the purpose of
this standard, a message will be considered to be a bit string.
The length of the message is the number of bits (the empty message
has length 0). If the number of bits in a message is a multiple of
8, for compactness we can represent the message in hex.
Suppose a message has length L < 2^64. Before it is input to the
SHA, the message is padded on the right as follows:
a. "1" is appended. Example: if the original message is
"01010011", this is padded to "010100111".
b. If necessary, "0"s are then appended until the number of bits
in the padded message is congruent to 448 modulo 512.
Example: suppose the original message is the bit string
01100001 01100010 01100011 01100100 01100101.
After step (a) this gives
01100001 01100010 01100011 01100100 01100101 1.
The number of bits in the above is 41; we pad with 407 "0"s
to make the length of the padded message congruent to 448
modulo 512. This gives (in hex)
61626364 65800000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000.
Note that the padding is arranged so that at this point
the padded message contains 16s + 14 words, for some s >=
0.
c. Obtain the 2-word representation of L = the number of bits in
the original message. If L < 2^32 then the first word is all
zeroes. Append these two words to the padded message.
Example: suppose the original message is as in (b). Then L =
40 (note that L is computed before any padding). The two-word
representation of 40 is hex 00000000 00000028. Hence the
final padded message is hex
61626364 65800000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000028.
The final padded message will contain 16N words for some N > 0.
Example: in (c) above, the final padded message has N = 1. The
final padded message may be regarded as a sequence of N blocks M(1)
, M(2), ... , M(N), where each M(i) contains 16 words and M(1) is leftmost.
5. FUNCTIONS USED
A sequence of logical functions f(0,x,y,z), ... , f(79,x,y,z) is used in
the
SHA. Each f operates on three 32-bit words {x,y,z} and produces a 32-bit
word as output. f(t,x,y,z) is defined as follows: for words x,y,z,
f(t,x,y,z) = (x AND y) OR (~x AND z) (0 <= t <= 19)
f(t,x,y,z) = x XOR y XOR z (20 <= t <= 39)
f(t,x,y,z) = (x AND y) OR (x AND z) OR (y AND z) (40 <= t <= 59)
f(t,x,y,z) = x XOR y XOR z (60 <= t <= 79).
6. CONSTANTS USED
A sequence of constant words K(0), K(1), ... , K(79) is used in the SHA.
In hex these are given by
K(t) = 5a827999 (0 <= t <= 19)
K(t) = 6ed9eba1 (20 <= t <= 39)
K(t) = 8f1bbcdc (40 <= t <= 59)
K(t) = ca62c1d6 (60 <= t <= 79).
7. COMPUTING THE MESSAGE DIGEST
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. The words of the
first 5-word buffer are labeled A,B,C,D,E. The words of the second
5-word buffer are labeled h0, h1, h2, h3, h4. The words of the 80-
word sequence are labeled W(0), W(1), ... , W(79). A single word buffer
TEMP is also employed.
To generate the message digest, the 16-word blocks M(1), M(2), ...
, M(N) defined in Section 4 are processed in order. The processing
of each M(i) involves 80 steps.
Before processing any blocks, the {hj} are initialized as
follows: in hex,
h0 = 67452301
h1 = efcdab89
h2 = 98badcfe
h3 = 10325476
h4 = c3d2e1f0.
Now M(1), M(2), ... , M(N) are processed. To process M(i), we proceed as
follows:
a. Divide M(i) into 16 words W(0), W(1), ... , W(15), where W(0) is the
leftmost word.
b. For t = 16 to 79 let W(t) = W(t-3) XOR W(t-8) XOR W(t-14) XOR W(t-16).
c. Let A = h0, B = h1, C = h2, D = h3, E = h4.
d. For t = 0 to 79 do
TEMP = S(5,A) + f(t,B,C,D) + E + W(t) + K(t);
E = D; D = C; C = S(30,B); B = A; A = TEMP;
e. Let h0 = h0 + A, h1 = h1 + B, h2 = h2 + C, h3 = h3 + D, h4
= h4 + E.
After processing M(N), the message digest is the 160-bit string
represented by the 5 words
h0 h1 h2 h3 h4.
The above assumes that the sequence W(0), ... , W(79) is implemented
as an array of eighty 32-bit words. This is efficient from the
standpoint of minimization of execution time, since the addresses
of W(t-3), ... , W(t-16) in step (b) are easily computed. If space is at
a premium, an alternative is to regard { W(t) } as a circular queue,
which may be implemented using an array of sixteen 32-bit words
W[0], ... W[15]. In this case, in hex let MASK = 0000000f. Then
processing of M(i) is as follows:
aa. Divide M(i) into 16 words W[0], ... , W[15], where W[0] is the
leftmost word.
bb. Let A = h0, B = h1, C = h2, D = h3, E = h4.
cc. For t = 0 to 79 do
s = t AND MASK;
if (t >= 16) W[s] = W[(s + 13) AND MASK] XOR W[(s + 8) AND
MASK] XOR W[(s + 2) AND MASK] XOR W[s];
TEMP = S(5,A) + f(t,B,C,D) + E + W[s] + K(t);
E = D; D = C; C = S(30,B); B = A; A = TEMP;
dd. Let h0 = h0 + A, h1 = h1 + B, h2 = h2 + C, h3 = h3 + D, h4
= h4 + E.
Both (a) - (d) and (aa) - (dd) yield the same message digest.
Although using (aa) - (dd) saves sixty-four 32-bit words of
storage, it is likely to lengthen execution time due to the
increased complexity of the address computations for the { W[t] }
in step (cc). Other computation methods which give identical
results may be implemented in conformance with the standard.
Examples are given in the appendices.
APPENDIX A. A SAMPLE MESSAGE AND ITS MESSAGE DIGEST
This appendix is for informational purposes only and is not
required to meet the standard.
Let the message be the ASCII binary-coded form of "abc", i.e.
01100001 01100010 01100011.
This message has length L = 24. In step (a) of Section 4, we
append "1", giving a new length of 25. In step (b) we append 423
"0"s. In step (c) we append hex 00000000 00000018, the 2-word
representation of 24. Thus the final padded message consists of
one block, so that N = 1 in the notation of Section 4. The single