NetNews Usenet Archive 1992 #20

home *** CD-ROM | disk | FTP | other *** search

/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / sci / crypt / 3240 < prev next >

Wrap

Internet Message Format | 1992-09-14 | 23.6 KB

Path: sparky!uunet!usc!wupost!waikato.ac.nz!aukuni.ac.nz!cs18.cs.aukuni.ac.nz!pgut1 Newsgroups: sci.crypt Subject: SHS/SHA document Message-ID: <1992Sep15.071041.3309@cs.aukuni.ac.nz> From: pgut1@cs.aukuni.ac.nz (Peter Gutmann) Date: Tue, 15 Sep 1992 07:10:41 GMT Sender: pgut1@cs.aukuni.ac.nz (PeterClaus Gutmann ) Organization: Computer Science Dept. University of Auckland Lines: 598 So many people asked for this after my recent postings that I've decided to post it here.... ------------- 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 block has hex words W[ 0] = 61626380 W[ 1] = 00000000 W[ 2] = 00000000 W[ 3] = 00000000 W[ 4] = 00000000 W[ 5] = 00000000 W[ 6] = 00000000 W[ 7] = 00000000 W[ 8] = 00000000 W[ 9] = 00000000 W[10] = 00000000 W[11] = 00000000 W[12] = 00000000 W[13] = 00000000 W[14] = 00000000 W[15] = 00000018 Initial hex values of h: h0 h1 h2 h3 h4 67452301 efcdab89 98badcfe 10325476 c3d2e1f0 Hex values of A,B,C,D,E after pass t of the "for t = 0 to 79" loop (step (d) or (cc)) in Section 7: A B C D E t = 0: 0116fc33 67452301 7bf36ae2 98badcfe 10325476 t = 1: 8990536d 0116fc33 59d148c0 7bf36ae2 98badcfe t = 2: a1390f08 8990536d c045bf0c 59d148c0 7bf36ae2 t = 3: cdd8e11b a1390f08 626414db c045bf0c 59d148c0 t = 4: cfd499de cdd8e11b 284e43c2 626414db c045bf0c t = 5: 3fc7ca40 cfd499de f3763846 284e43c2 626414db t = 6: 993e30c1 3fc7ca40 b3f52677 f3763846 284e43c2 t = 7: 9e8c07d4 993e30c1 0ff1f290 b3f52677 f3763846 t = 8: 4b6ae328 9e8c07d4 664f8c30 0ff1f290 b3f52677 t = 9: 8351f929 4b6ae328 27a301f5 664f8c30 0ff1f290 t = 10: fbda9e89 8351f929 12dab8ca 27a301f5 664f8c30 t = 11: 63188fe4 fbda9e89 60d47e4a 12dab8ca 27a301f5 t = 12: 4607b664 63188fe4 7ef6a7a2 60d47e4a 12dab8ca t = 13: 9128f695 4607b664 18c623f9 7ef6a7a2 60d47e4a t = 14: 196bee77 9128f695 1181ed99 18c623f9 7ef6a7a2 t = 15: 20bdd62f 196bee77 644a3da5 1181ed99 18c623f9 t = 16: ed2ff4a3 20bdd62f c65afb9d 644a3da5 1181ed99 t = 17: 565df73c ed2ff4a3 c82f758b c65afb9d 644a3da5 t = 18: 550b1e7f 565df73c fb4bfd28 c82f758b c65afb9d t = 19: fe0f9e4b 550b1e7f 15977dcf fb4bfd28 c82f758b t = 20: b4d4c943 fe0f9e4b d542c79f 15977dcf fb4bfd28 t = 21: 43993572 b4d4c943 ff83e792 d542c79f 15977dcf t = 22: f7106486 43993572 ed353250 ff83e792 d542c79f t = 23: 775924e6 f7106486 90e64d5c ed353250 ff83e792 t = 24: 45a7ef23 775924e6 bdc41921 90e64d5c ed353250 t = 25: ccead674 45a7ef23 9dd64939 bdc41921 90e64d5c t = 26: 02d0c6d1 ccead674 d169fbc8 9dd64939 bdc41921 t = 27: 070c437f 02d0c6d1 333ab59d d169fbc8 9dd64939 t = 28: 301e90be 070c437f 40b431b4 333ab59d d169fbc8 t = 29: b898c685 301e90be c1c310df 40b431b4 333ab59d t = 30: 669723e2 b898c685 8c07a42f c1c310df 40b431b4 t = 31: d9316f96 669723e2 6e2631a1 8c07a42f c1c310df t = 32: db81a5c7 d9316f96 99a5c8f8 6e2631a1 8c07a42f t = 33: 99c8dfb2 db81a5c7 b64c5be5 99a5c8f8 6e2631a1 t = 34: 6be6ae07 99c8dfb2 f6e06971 b64c5be5 99a5c8f8 t = 35: c01cc62c 6be6ae07 a67237ec f6e06971 b64c5be5 t = 36: 6433fdd0 c01cc62c daf9ab81 a67237ec f6e06971 t = 37: 0a33ccf7 6433fdd0 3007318b daf9ab81 a67237ec t = 38: 4bf58dc8 0a33ccf7 190cff74 3007318b daf9ab81 t = 39: ebbd5233 4bf58dc8 c28cf33d 190cff74 3007318b t = 40: 825a3460 ebbd5233 12fd6372 c28cf33d 190cff74 t = 41: b62cbb93 825a3460 faef548c 12fd6372 c28cf33d t = 42: aa3f9707 b62cbb93 20968d18 faef548c 12fd6372 t = 43: fe1d0273 aa3f9707 ed8b2ee4 20968d18 faef548c t = 44: 57ad526b fe1d0273 ea8fe5c1 ed8b2ee4 20968d18 t = 45: 93ebbe3f 57ad526b ff87409c ea8fe5c1 ed8b2ee4 t = 46: f9adf47b 93ebbe3f d5eb549a ff87409c ea8fe5c1 t = 47: 875586d2 f9adf47b e4faef8f d5eb549a ff87409c t = 48: d0a22ffb 875586d2 fe6b7d1e e4faef8f d5eb549a t = 49: c12b6426 d0a22ffb a1d561b4 fe6b7d1e e4faef8f t = 50: ebc90281 c12b6426 f4288bfe a1d561b4 fe6b7d1e t = 51: e7d0ec05 ebc90281 b04ad909 f4288bfe a1d561b4 t = 52: 7cb98e55 e7d0ec05 7af240a0 b04ad909 f4288bfe t = 53: 0d48dba2 7cb98e55 79f43b01 7af240a0 b04ad909 t = 54: c2d477bf 0d48dba2 5f2e6395 79f43b01 7af240a0 t = 55: 236bd48d c2d477bf 835236e8 5f2e6395 79f43b01 t = 56: 9b4364d6 236bd48d f0b51def 835236e8 5f2e6395 t = 57: 5b8c33c9 9b4364d6 48daf523 f0b51def 835236e8 t = 58: be2a4656 5b8c33c9 a6d0d935 48daf523 f0b51def t = 59: 8ff296db be2a4656 56e30cf2 a6d0d935 48daf523 t = 60: c10c8993 8ff296db af8a9195 56e30cf2 a6d0d935 t = 61: 6ac23cbf c10c8993 e3fca5b6 af8a9195 56e30cf2 t = 62: 0708247d 6ac23cbf f0432264 e3fca5b6 af8a9195 t = 63: 35d201f8 0708247d dab08f2f f0432264 e3fca5b6 t = 64: 969b2fc8 35d201f8 41c2091f dab08f2f f0432264 t = 65: 3cac6514 969b2fc8 0d74807e 41c2091f dab08f2f t = 66: 14cd9a35 3cac6514 25a6cbf2 0d74807e 41c2091f t = 67: ba564047 14cd9a35 0f2b1945 25a6cbf2 0d74807e t = 68: c241f74d ba564047 4533668d 0f2b1945 25a6cbf2 t = 69: 2896b70f c241f74d ee959011 4533668d 0f2b1945 t = 70: 564bbed1 2896b70f 70907dd3 ee959011 4533668d t = 71: 8fa15d5a 564bbed1 ca25adc3 70907dd3 ee959011 t = 72: 9a226c11 8fa15d5a 5592efb4 ca25adc3 70907dd3 t = 73: f0b94489 9a226c11 a3e85756 5592efb4 ca25adc3 t = 74: 1809d5e2 f0b94489 66889b04 a3e85756 5592efb4 t = 75: b86c5a40 1809d5e2 7c2e5122 66889b04 a3e85756 t = 76: dfe7e487 b86c5a40 86027578 7c2e5122 66889b04 t = 77: 70286c07 dfe7e487 2e1b1690 86027578 7c2e5122 t = 78: 24ff7ed5 70286c07 f7f9f921 2e1b1690 86027578 t = 79: 9a1f95a8 24ff7ed5 dc0a1b01 f7f9f921 2e1b1690 After processing, values of h: h0 h1 h2 h3 h4 0164b8a9 14cd2a5e 74c4f7ff 082c4d97 f1edf880 Message digest = 0164b8a9 14cd2a5e 74c4f7ff 082c4d97 f1edf880