view Side-By-Side changes
INTERNET-DRAFT Motorola
Paul E. Jones
Cisco Systems
Expires: September October 2001 March April 2001
US Secure Hash Algorithm 1 (SHA1)
-- ------ ---- --------- - ------
<draft-eastlake-sha1-00.txt>
<draft-eastlake-sha1-01.txt>
Status of This Document
This draft is intended to be become an Informational RFC.
Distribution of this document is unlimited. Comments should be sent
to the authors.
This document is an Internet-Draft and is in full conformance with
all provisions of Section 10 of RFC 2026. Internet-Drafts are
working documents of the Internet Engineering Task Force (IETF), its
areas, and its working groups. Note that other groups may also
distribute working documents as Internet-Drafts.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet- Drafts as reference
material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
Abstract
The United States of America has adopted the SHA-1 hash algorithm
described herein as a Federal Information Processing Standard. The
purpose of this document is to make it conveniently available to the
Internet community. Most of the text herein was taken by the authors
from FIPS 180-1. Only the C code implementation is "original" and
that is patterned after similar to the MD2/MD4/MD5 RFCs.
D. Eastlake 3rd, P. Jones [Page 1]
INTERNET-DRAFT US SHA-1 March April 2001
Acknowledgements
Almost all of the text herein was taken by the authors from [FIPS
180-1]. Only the C code implementation is "original" but its style
is similar to the previously published MD2, MD4, and MD5 RFCs [RFCs
1319, 1320, 1321].
The SHA-1 is based on principles similar to those used by Professor
Ronald L. Rivest of MIT when designing the MD4 message digest
algorithm [MD4] and is closely modelled after that algorithm [RFC
1320].
Table of Contents
Status of This Document....................................1
Abstract...................................................1
Acknowledgements...........................................2
Table of Contents..........................................2
1. Overview of Contents....................................3
2. Definitions.............................................3
2.1 Bit Strings and Integers..............................3
3. Operations on Words.....................................4
4. Message Padding.........................................5
5. Functions and Constants Used............................6
6. Computing the Message Digest............................7
6.1 Method 1...............................................7
6.2 Method 2...............................................8
7. C Code..................................................9
7.1 .h file................................................9
7.2 .c file...............................................10
7.3 Test Driver...........................................17 Driver...........................................19
8. Security Considerations................................19
References................................................19 Considerations................................21
References................................................21
Author's Address..........................................21 Address..........................................22
Expiration and File Name..................................21 Name..................................22
D. Eastlake 3rd, P. Jones [Page 2]
INTERNET-DRAFT US SHA-1 March April 2001
1. Overview of Contents
This document specifies a Secure Hash Algorithm, SHA-1, for computing
a condensed representation of a message or a data file. When a
message of any length < 2^64 bits is input, the SHA-1 produces a
160-bit output called a message digest. The message digest can then,
for example, be input to a signature algorithm which generates or
verifies 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 in size than the
message. The same hash algorithm must be used by the verifier of a
digital signature as was used by the creator of the digital
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-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 very high probability,
result in a different message digest, and the signature will fail to
verify.
Section 2 below defines the terminology and functions used as
building blocks to form SHA-1.
2. Definitions
2.1 Bit Strings and Integers
The following terminology related to bit strings and integers will be
used:
a. A hex digit is an element of the set {0, 1, ... , 9, A, ... , F}.
A hex digit is the representation of a 4-bit string. Examples:
7 = 0111, A = 1010.
b. A word equals a 32-bit string which may be represented as a
sequence of 8 hex digits. To convert a word to 8 hex digits each
4-bit string is converted to its hex equivalent as described in
(a) above. Example:
1010 0001 0000 0011 1111 1110 0010 0011 = A103FE23.
c. An integer between 0 and 2^32 - 1 inclusive may be represented as
a word. The least significant four bits of the integer are
D. Eastlake 3rd, P. Jones [Page 3]
INTERNET-DRAFT US SHA-1 March April 2001
represented by the right-most hex digit of the word
representation. Example: the integer 291 = 2^8+2^5+2^1+2^0 =
256+32+2+1 is represented by the hex word, 00000123.
If z is an integer, 0 <= z < 2^64, then z = (2^32)x + y where 0
<= x < 2^32 and 0 <= y < 2^32. Since x and y can be represented
as words X and Y, respectively, z can be represented as the pair
of words (X,Y).
d. block = 512-bit string. A block (e.g., B) may be represented as
a sequence of 16 words.
3. Operations on Words
The following logical operators will be applied to words:
a. Bitwise logical word operations
X AND Y = bitwise logical "and" of X and Y.
X OR Y = bitwise logical "inclusive-or" of X and Y.
X XOR Y = bitwise logical "exclusive-or" of X and Y.
NOT X = bitwise logical "complement" of X.
Example:
01101100101110011101001001111011
XOR 01100101110000010110100110110111
--------------------------------
= 00001001011110001011101111001100
b. The operation X + Y is defined as follows: words X and Y
represent integers x and y, where 0 <= x < 2^32 and 0 <= y <
2^32. For positive integers n and m, let n mod m be the
remainder upon dividing n by m. Compute
z = (x + y) mod 2^32.
Then 0 <= z < 2^32. Convert z to a word, Z, and define Z = X +
Y.
c. The circular left shift operation S^n(X), where X is a word and n
is an integer with 0 <= n < 32, is defined by
S^n(X) = (X << n) OR (X >> 32-n).
In the above, X << n is obtained as follows: discard the left-
D. Eastlake 3rd, P. Jones [Page 4]
INTERNET-DRAFT US SHA-1 March April 2001
most n bits of X and then pad the result with n zeroes on the
right (the result will still be 32 bits). X >> n is obtained by
discarding the right-most n bits of X and then padding the
result with n 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
SHA-1 is used to compute a message digest for a message or data file
that is provided as input. The message or data file should be
considered to be a bit string. The length of the message is the
number of bits in the message (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. The purpose of message padding
is to make the total length of a padded message a multiple of 512.
SHA-1 sequentially processes blocks of 512 bits when computing the
message digest. The following specifies how this padding shall be
performed. As a summary, a "1" followed by m "0"s followed by a 64-
bit integer are appended to the end of the message to produce a
padded message of length 512 * n. The 64-bit integer is the length
of the original message. The padded message is then processed by the
SHA-1 as n 512-bit blocks.
Suppose a message has length l < 2^64. Before it is input to the
SHA-1, the message is padded on the right as follows:
a. "1" is appended. Example: if the original message is "01010000",
this is padded to "010100001".
b. "0"s are appended. The number of "0"s will depend on the
original length of the message. The last 64 bits of the last
512-bit block are reserved
for the length l of the original message.
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.
Since l = 40, the number of bits in the above is 41 and 407 "0"s
are appended, making the total now 448. This gives (in hex)
61626364 65800000 00000000 00000000
00000000 00000000 00000000 00000000
D. Eastlake 3rd, P. Jones [Page 5]
INTERNET-DRAFT US SHA-1 March April 2001
00000000 00000000 00000000 00000000
00000000 00000000.
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 padded message will contain 16 * n words for some n > 0.
The padded message is regarded as a sequence of n blocks M(1) ,
M(2), first characters (or bits) of the message.
5. Functions and Constants Used
A sequence of logical functions f(0), f(1),..., f(79) is used in
SHA-1. Each f(t), 0 <= t <= 79, operates on three 32-bit words B, C,
D and produces a 32-bit word as output. f(t;B,C,D) is defined as
follows: for words B, C, D,
f(t;B,C,D) = (B AND C) OR ((NOT B) AND D) ( 0 <= t <= 19)
f(t;B,C,D) = B XOR C XOR D (20 <= t <= 39)
f(t;B,C,D) = (B AND C) OR (B AND D) OR (C AND D) (40 <= t <= 59)
f(t;B,C,D) = B XOR C XOR D (60 <= t <= 79).
A sequence of constant words K(0), K(1), ... , K(79) is used in the
SHA-1. 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).
D. Eastlake 3rd, P. Jones [Page 6]
INTERNET-DRAFT US SHA-1 March April 2001
6. Computing the Message Digest
The methods given in 6.1 and 6.2 below yield the same message digest.
Although using method 2 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 (c). There are
other computation methods which give identical results.
6.1 Method 1
The message digest is computed using the message padded as described
in section 4. The computation is described using 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 H's 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 left-most word.
b. For t = 16 to 79 let
W(t) = S^1(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
D. Eastlake 3rd, P. Jones [Page 7]
INTERNET-DRAFT US SHA-1 March April 2001
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.
6.2 Method 2
The method 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:
a. Divide M(i) into 16 words W[0], ... , W[15], where W[0] is the
left-most word.
b. Let A = H0, B = H1, C = H2, D = H3, E = H4.
c. For t = 0 to 79 do
s = t AND MASK;
if (t >= 16) W[s] = S^1(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;
d. Let H0 = H0 + A, H1 = H1 + B, H2 = H2 + C, H3 = H3 + D, H4 = H4
+ E.
D. Eastlake 3rd, P. Jones [Page 8]
INTERNET-DRAFT US SHA-1 March April 2001
7. C Code
Below is a demonstration implementation of SHA-1 in C. Section 7.1
contains the header file, 7.2 the C code, and 7.3 a test driver.
7.1 .h file
/*
* sha1.h
*
* Description:
* This class is the header file for code which implements the Secure
* Hashing Standard Algorithm 1 as defined
* in FIPS PUB 180-1 published
* April 17, 1995.
*
* Many of the variable names in the SHA1Context, this code, especially the
* single character names, were used because those were the names
* used in the publication.
*
* Please read the file sha1.c for more information.
*
*/
#ifndef _SHA1_H_
#define _SHA1_H_
#ifndef _SHA_enum_
#define _SHA_enum_
enum
{
shaSuccess = 0,
shaNull, /* Null pointer parameter*/
shaInputTooLong, /* input data too long */
shaStateError, /* called Input after Result */
shaTypeError /* SHA1ui4 is not at least 4 bytes */
};
#endif
#define SHA1HashSize 20
/*
* Define SHA1ui4 MUST be >= 32 bits.
* On 64 bit processors, it may be possible to dispense with the circular shift macro "long"
* depending on the C compiler
*/
#define SHA1CircularShift(bits,word) \
((((word) << (bits)) & 0xFFFFFFFF) | \
(((word) & 0xFFFFFFFF) >> (32-(bits))))
typedef unsigned long int SHA1ui4;
/*
D. Eastlake 3rd, P. Jones [Page 9]
INTERNET-DRAFT US SHA-1 April 2001
* This structure will hold context information for the hashing SHA
* hashing operation
*/
typedef struct SHA1Context
{
unsigned Message_Digest[5];
SHA1ui4 Intermediate_Hash[SHA1HashSize/4]; /* Message Digest (output) */
unsigned
SHA1ui4 Length_Low; /* Message length in bits */
unsigned
SHA1ui4 Length_High; /* Message length in bits */
unsigned char Message_Block[64]; /* 512-bit message blocks */
int Message_Block_Index; /* Index into message block array */
int Computed; /* Is the digest computed? */
int Corrupted; /* Is the message digest corruped? */
D. Eastlake 3rd, P. Jones [Page 9]
INTERNET-DRAFT US SHA-1 March 2001
} SHA1Context;
/*
* Function Prototypes
*/
void SHA1Reset(SHA1Context *);
int SHA1Result(SHA1Context SHA1Reset( SHA1Context *);
void
int SHA1Input( SHA1Context *,
const unsigned char *,
unsigned int );
void SHA1ProcessMessageBlock(SHA1Context *);
void SHA1PadMessage(SHA1Context *);
int SHA1Result( SHA1Context *,
unsigned char Message_Digest[SHA1HashSize]);
#endif
7.2 .c file
/*
* sha1.c
*
* Description:
* This file implements the Secure Hashing Standard Algorithm 1 as defined
* defined in FIPS PUB 180-1 published April 17, 1995.
*
* The Secure Hashing Standard, which uses the Secure Hashing
* Algorithm (SHA), SHA-1, produces a 160-bit message digest for a
* given
* data stream. In theory, it is highly improbable that It should take about 2**n steps to find a
* message with the same digest as a given message and
* 2**(n/2) to find any two messages will produce with the same message digest. Therefore, digest,
* when n is the digest size in bits. Therefore, this
* algorithm can serve as a means of providing a "fingerprint"
* "fingerprint" for a message.
*
D. Eastlake 3rd, P. Jones [Page 10]
INTERNET-DRAFT US SHA-1 April 2001
* Portability Issues:
* SHA-1 is defined in terms of 32-bit "words". This code was
* written with the expectation that the processor has at least
* a 32-bit machine word size. If the machine word size is larger,
* the code should still function properly. One caveat to that
* is that the input functions taking characters and character
* arrays assume that only 8 bits of information are stored in each
* each character.
*
* Caveats:
* SHA-1 is designed to work with messages less than 2^64 bits
* long. Although SHA-1 allows a message digest to be generated for
* for messages of any number of bits less than 2^64, this
* implementation only works with messages with a length that is a
* a multiple of the size of an 8-bit character.
*
*/
D. Eastlake 3rd, P. Jones [Page 10]
INTERNET-DRAFT US SHA-1 March 2001
#include "sha1.h"
/*
* Define the SHA1 circular left shift macro
*/
#define SHA1CircularShift(bits,word) \
((((word) << (bits)) & 0xFFFFFFFF) | \
((word) >> (32-(bits))))
/* Local Prototyptes */
void SHA1PadMessage(SHA1Context *);
void SHA1ProcessMessageBlock(SHA1Context *);
/*
* SHA1Reset
*
* Description:
* This function will initialize the SHA1Context in preparation
* for computing a new SHA1 message digest.
*
* Parameters:
* context: [in/out]
* The context to reset.
*
* Returns:
* Nothing. sha Error Code.
*
* Comments:
*
*/
void
int SHA1Reset(SHA1Context *context)
{
D. Eastlake 3rd, P. Jones [Page 11]
INTERNET-DRAFT US SHA-1 April 2001
if (!context)
{
return shaNull;
}
if (sizeof (SHA1ui4) < 4)
{
context->Corrupted = shaTypeError;
return shaTypeError;
}
context->Length_Low = 0;
context->Length_High = 0;
context->Message_Block_Index = 0;
context->Message_Digest[0]
context->Intermediate_Hash[0] = 0x67452301;
context->Message_Digest[1]
context->Intermediate_Hash[1] = 0xEFCDAB89;
context->Message_Digest[2]
context->Intermediate_Hash[2] = 0x98BADCFE;
context->Message_Digest[3]
context->Intermediate_Hash[3] = 0x10325476;
context->Message_Digest[4]
context->Intermediate_Hash[4] = 0xC3D2E1F0;
context->Computed = 0;
context->Corrupted = 0;
return shaSuccess;
}
/*
* SHA1Result
*
* Description:
* This function will return the 160-bit message digest into the
* Message_Digest array within the SHA1Context provided by the caller.
* NOTE: The first octet of hash is stored in the 0th element,
* the last octet of hash in the 19th element.
*
* Parameters:
* context: [in/out] [in]
* The context to use to calculate the SHA-1 hash.
* Message_Digest: [out]
* Where the digest is returned.
*
* Returns:
* 1 if successful, 0 if it failed. sha Error Code.
*
* Comments:
*
*/
int SHA1Result( SHA1Context *context,
unsigned char Message_Digest[SHA1HashSize])
D. Eastlake 3rd, P. Jones [Page 11] 12]
INTERNET-DRAFT US SHA-1 March April 2001
*
*/
{
int SHA1Result(SHA1Context *context) i;
if (!context || !Message_Digest)
{
return shaNull;
}
if (context->Corrupted)
{
return 0; context->Corrupted;
}
if (!context->Computed)
{
SHA1PadMessage(context);
for(i=0; i<64; ++i)
{ /* message may be sensitive, clear it out */
context->Message_Block[i] = 0;
}
context->Length_Low = 0; /* and clear length */
context->Length_High = 0;
context->Computed = 1;
}
for(i = 0; i < SHA1HashSize; ++i)
{
Message_Digest[i] = context->Intermediate_Hash[i>>2]
>> 8 * ( 3 - ( i & 0x03 ) );
}
return 1; shaSuccess;
}
/*
* SHA1Input
*
* Description:
* This function accepts an array of octets as the next portion of
* of the message.
*
* Parameters:
* context: [in/out]
* The SHA-1 SHA context to update
* message_array: [in]
* An array of characters representing the next portion of the
* the message.
* length: [in]
* The length of the message in message_array
*
D. Eastlake 3rd, P. Jones [Page 13]
INTERNET-DRAFT US SHA-1 April 2001
* Returns:
* Nothing. sha Error Code.
*
* Comments:
*
*/
void
int SHA1Input( SHA1Context *context,
const unsigned char *message_array,
unsigned length)
{
if (!length)
{
return;
return shaSuccess;
}
D. Eastlake 3rd, P. Jones [Page 12]
INTERNET-DRAFT US SHA-1 March 2001
if (context->Computed (!context || context->Corrupted) !message_array)
{
return shaNull;
}
if (context->Computed)
{
context->Corrupted = 1;
return; shaStateError;
return shaStateError;
}
if (context->Corrupted)
{
return context->Corrupted;
}
while(length-- && !context->Corrupted)
{
context->Message_Block[context->Message_Block_Index++] =
(*message_array & 0xFF);
context->Length_Low += 8;
/* Force it to 32 bits */
context->Length_Low &= 0xFFFFFFFF;
if (context->Length_Low == 0)
{
context->Length_High++;
/* Force it to 32 bits */
context->Length_High &= 0xFFFFFFFF;
if (context->Length_High == 0)
{
/* Message is too long */
context->Corrupted = 1;
}
}
D. Eastlake 3rd, P. Jones [Page 14]
INTERNET-DRAFT US SHA-1 April 2001
if (context->Message_Block_Index == 64)
{
SHA1ProcessMessageBlock(context);
}
message_array++;
}
return shaSuccess;
}
/*
* SHA1ProcessMessageBlock
*
* Description:
* This function will process the next 512 bits of the message
* stored in the Message_Block array.
*
* Parameters:
* None.
*
* Returns:
* Nothing.
*
* Comments:
* Many of the variable names in the SHAContext, this code, especially the
D. Eastlake 3rd, P. Jones [Page 13]
INTERNET-DRAFT US SHA-1 March 2001
* single character names, were used because those were the names
* names used in the publication.
*
*
*/
void SHA1ProcessMessageBlock(SHA1Context *context)
{
const unsigned SHA1ui4 K[] = { /* Constants defined in SHA-1 */
0x5A827999,
0x6ED9EBA1,
0x8F1BBCDC,
0xCA62C1D6
};
int t; /* Loop counter */
unsigned
SHA1ui4 temp; /* Temporary word value */
unsigned
SHA1ui4 W[80]; /* Word sequence */
unsigned
SHA1ui4 A, B, C, D, E; /* Word buffers */
/*
* Initialize the first 16 words in the array W
*/
for(t = 0; t < 16; t++)
{
W[t] = context->Message_Block[t * 4] << 24;
D. Eastlake 3rd, P. Jones [Page 15]
INTERNET-DRAFT US SHA-1 April 2001
W[t] |= context->Message_Block[t * 4 + 1] << 16;
W[t] |= context->Message_Block[t * 4 + 2] << 8;
W[t] |= context->Message_Block[t * 4 + 3];
}
for(t = 16; t < 80; t++)
{
W[t] = SHA1CircularShift(1,W[t-3] ^ W[t-8] ^ W[t-14] ^ W[t-16]);
}
A = context->Message_Digest[0]; context->Intermediate_Hash[0];
B = context->Message_Digest[1]; context->Intermediate_Hash[1];
C = context->Message_Digest[2]; context->Intermediate_Hash[2];
D = context->Message_Digest[3]; context->Intermediate_Hash[3];
E = context->Message_Digest[4]; context->Intermediate_Hash[4];
for(t = 0; t < 20; t++)
{
temp = SHA1CircularShift(5,A) +
((B & C) | ((~B) & D)) + E + W[t] + K[0];
temp &= 0xFFFFFFFF;
E = D;
D = C;
C = SHA1CircularShift(30,B);
B = A;
A = temp;
D. Eastlake 3rd, P. Jones [Page 14]
INTERNET-DRAFT US SHA-1 March 2001
}
for(t = 20; t < 40; t++)
{
temp = SHA1CircularShift(5,A) + (B ^ C ^ D) + E + W[t] + K[1];
temp &= 0xFFFFFFFF;
E = D;
D = C;
C = SHA1CircularShift(30,B);
B = A;
A = temp;
}
for(t = 40; t < 60; t++)
{
temp = SHA1CircularShift(5,A) +
((B & C) | (B & D) | (C & D)) + E + W[t] + K[2];
temp &= 0xFFFFFFFF;
E = D;
D = C;
C = SHA1CircularShift(30,B);
B = A;
A = temp;
}
D. Eastlake 3rd, P. Jones [Page 16]
INTERNET-DRAFT US SHA-1 April 2001
for(t = 60; t < 80; t++)
{
temp = SHA1CircularShift(5,A) + (B ^ C ^ D) + E + W[t] + K[3];
temp &= 0xFFFFFFFF;
E = D;
D = C;
C = SHA1CircularShift(30,B);
B = A;
A = temp;
}
context->Message_Digest[0]
context->Intermediate_Hash[0] =
(context->Message_Digest[0]
(context->Intermediate_Hash[0] + A) & 0xFFFFFFFF;
context->Message_Digest[1]
context->Intermediate_Hash[1] =
(context->Message_Digest[1]
(context->Intermediate_Hash[1] + B) & 0xFFFFFFFF;
context->Message_Digest[2]
context->Intermediate_Hash[2] =
(context->Message_Digest[2]
(context->Intermediate_Hash[2] + C) & 0xFFFFFFFF;
context->Message_Digest[3]
context->Intermediate_Hash[3] =
(context->Message_Digest[3]
(context->Intermediate_Hash[3] + D) & 0xFFFFFFFF;
context->Message_Digest[4]
context->Intermediate_Hash[4] =
(context->Message_Digest[4]
(context->Intermediate_Hash[4] + E) & 0xFFFFFFFF;
context->Message_Block_Index = 0;
}
D. Eastlake 3rd, P. Jones [Page 15]
INTERNET-DRAFT US SHA-1 March 2001
/*
* SHA1PadMessage
*
* Description:
* According to the standard, the message must be padded to an even
* 512 bits. The first padding bit must be a '1'. The last 64
* bits represent the length of the original message. All bits in
* between should be 0. This function will pad the message
* according to those rules by filling the Message_Block array
* accordingly. It will also call SHA1ProcessMessageBlock() the ProcessMessageBlock function
* provided appropriately. When it returns, it can be assumed that the
* the message digest has been computed.
*
* Parameters:
* context: [in/out]
* The context to pad
* ProcessMessageBlock: [in]
* The appropriate SHA*ProcessMessageBlock function
* Returns:
* Nothing.
*
* Comments:
*
*/
D. Eastlake 3rd, P. Jones [Page 17]
INTERNET-DRAFT US SHA-1 April 2001
void SHA1PadMessage(SHA1Context *context)
{
/*
* Check to see if the current message block is too small to hold
* the initial padding bits and length. If so, we will pad the
* block, process it, and then continue padding into a second
* block.
*/
if (context->Message_Block_Index > 55)
{
context->Message_Block[context->Message_Block_Index++] = 0x80;
while(context->Message_Block_Index < 64)
{
context->Message_Block[context->Message_Block_Index++] = 0;
}
SHA1ProcessMessageBlock(context);
while(context->Message_Block_Index < 56)
{
context->Message_Block[context->Message_Block_Index++] = 0;
}
}
else
{
context->Message_Block[context->Message_Block_Index++] = 0x80;
while(context->Message_Block_Index < 56)
D. Eastlake 3rd, P. Jones [Page 16]
INTERNET-DRAFT US SHA-1 March 2001
{
context->Message_Block[context->Message_Block_Index++] = 0;
}
}
/*
* Store the message length as the last 8 octets
*/
context->Message_Block[56] = (context->Length_High >> 24) & 0xFF;
context->Message_Block[57] = (context->Length_High >> 16) & 0xFF;
context->Message_Block[58] = (context->Length_High >> 8) & 0xFF;
context->Message_Block[59] = (context->Length_High) & 0xFF;
context->Message_Block[60] = (context->Length_Low >> 24) & 0xFF;
context->Message_Block[61] = (context->Length_Low >> 16) & 0xFF;
context->Message_Block[62] = (context->Length_Low >> 8) & 0xFF;
context->Message_Block[63] = (context->Length_Low) & 0xFF;
SHA1ProcessMessageBlock(context);
}
D. Eastlake 3rd, P. Jones [Page 18]
INTERNET-DRAFT US SHA-1 April 2001
7.3 Test Driver
The following code is a main program test driver to exercise the code
in sha1.c.
/*
* shatest.c
*
* Description:
* This file will exercise the SHA1 class and perform SHA-1 code performing the three
* tests documented in FIPS PUB 180-1. 180-1 plus one which calls
* SHA1Input with an exact multiple of 512 bits, plus a couple
* error test checks.
*
* Portability Issues:
* None.
*
*/
#include <stdio.h>
#include <string.h>
#include "sha1.h"
/*
* Define patterns for testing
*/
#define TESTA TEST1 "abc"
#define TESTB TEST2a "abcdbcdecdefdefgefghfghighijhi" \
#define TEST2b "jkijkljklmklmnlmnomnopnopq"
#define TESTC TEST2 TEST2a TEST2b
#define TEST3 "a"
#define TEST4a "01234567012345670123456701234567"
#define TEST4b "01234567012345670123456701234567"
/* an exact multiple of 512 bits */
#define TEST4 TEST4a TEST4b
char *testarray[4] =
{
TEST1,
TEST2,
TEST3,
TEST4
};
long int main() repeatcount[4] = { 1, 1, 1000000, 10 };
char *resultarray[4] =
{
"A9 99 3E 36 47 06 81 6A BA 3E 25 71 78 50 C2 6C 9C D0 D8 9D",
"84 98 3E 44 1C 3B D2 6E BA AE 4A A1 F9 51 29 E5 E5 46 70 F1",
"34 AA 97 3C D4 C4 DA A4 F6 1E EB 2B DB AD 27 31 65 34 01 6F",
"DE A3 56 A2 CD DD 90 C7 A7 EC ED C5 EB B5 63 93 4F 46 04 52"
};
D. Eastlake 3rd, P. Jones [Page 17] 19]
INTERNET-DRAFT US SHA-1 March April 2001
int main()
{
SHA1Context sha;
int i; i, j, err;
unsigned char Message_Digest[20];
/*
* Perform test A SHA-1 tests
*/
for(j = 0; j < 4; ++j)
{
printf("\nTest A: 'abc'\n"); %d: %d, '%s'\n", j+1, repeatcount[j], testarray[j]);
err = SHA1Reset(&sha);
SHA1Input(&sha, (const unsigned char *) TESTA, strlen(TESTA));
if (!SHA1Result(&sha)) (err)
{
fprintf(stderr, "ERROR-- could not compute message digest\n"); "SHA1Reset Error %d.\n", err );
break; /* out of for j loop */
}
else
{
printf("\t");
for(i = 0; i < 5 ; i++) repeatcount[j]; ++i)
{
printf("%X ", sha.Message_Digest[i]);
}
printf("\n");
printf("Should match:\n");
printf("\tA9993E36 4706816A BA3E2571 7850C26C 9CD0D89D\n");
}
/*
* Perform test B
*/
printf("\nTest B:\n");
SHA1Reset(&sha);
err = SHA1Input(&sha,
(const unsigned char *) TESTB, strlen(TESTB)); testarray[j],
strlen(testarray[j]));
if (!SHA1Result(&sha)) (err)
{
fprintf(stderr, "ERROR-- "SHA1Input Error %d.\n", err );
break; /* out of for i loop */
}
}
err = SHA1Result(&sha, Message_Digest);
if (err)
{
fprintf(stderr,
"SHA1Result Error %d, could not compute message digest\n"); digest.\n",
err );
}
else
{
printf("\t");
for(i = 0; i < 5 20 ; i++) ++i)
{
printf("%X
printf("%02X ", sha.Message_Digest[i]); Message_Digest[i]);
}
printf("\n");
}
printf("Should match:\n");
printf("\t84983E44 1C3BD26E BAAE4AA1 F95129E5 E54670F1\n");
}
printf("\t%s\n", resultarray[j]);
D. Eastlake 3rd, P. Jones [Page 18] 20]
INTERNET-DRAFT US SHA-1 March April 2001
}
/*
* Perform test C Test some error returns */
printf("\nTest C: One million 'a' characters\n");
SHA1Reset(&sha);
for(i
err = 1; i <= 1000000; i++) {
SHA1Input(&sha, (const SHA1Input(&sha,(const unsigned char *) TESTC, testarray[1], 1);
}
if (!SHA1Result(&sha))
{
fprintf(stderr, "ERROR-- could not compute message digest\n");
}
else
{
printf("\t");
for(i
printf ("\nError %d. Should be %d.\n", err, shaStateError );
err = 0; i < 5 ; i++)
{
printf("%X ", sha.Message_Digest[i]);
}
printf("\n");
printf("Should match:\n");
printf("\t34AA973C D4C4DAA4 F61EEB2B DBAD2731 6534016F\n");
} SHA1Reset(0);
printf ("\nError %d. Should be %d.\n", err, shaNull );
return 0;
}
8. Security Considerations
This document is intended to provide convenient open source access by
the Internet community to the United States of America Federal
Information Processing Standard Secure Hash Function. No independent
assertion of the security of this hash function by the authors for
any particular use is intended.
References
[FIPS 180-1] - "Secure Hash Standard", United States of American,
National Institute of Science and Technology, Federal Information
Processing Standard (FIPS) 180-1, April 1993.
[MD4] - "The MD4 Message Digest Algorithm," Advances in Cryptology -
CRYPTO '90 Proceedings, Springer-Verlag, 1991, pp. 303-311.
D. Eastlake 3rd, P. Jones [Page 19]
INTERNET-DRAFT US SHA-1 March 2001
[RFC 1319] - "The MD2 Message-Digest Algorithm", B. Kaliski, April
1992.
[RFC 1320] - "The MD4 Message-Digest Algorithm", R. Rivest, April
1992.
[RFC 1321] - "The MD5 Message-Digest Algorithm", R. Rivest, April
1992.
[RFC 1750] - "Randomness Requirements for Security", D. Eastlake, S.
Crocker, J. Schiller, December 1994.
D. Eastlake 3rd, P. Jones [Page 20] 21]
INTERNET-DRAFT US SHA-1 March April 2001
Author's Address
Donald E. Eastlake, 3rd
Motorola
155 Beaver Street
Milford, MA 01757 USA
Telephone: +1 508-634-2066 (h)
+1 508-261-5434 (w)
FAX: +1 508-261-4777
EMail: Donald.Eastlake@motorola.com
Paul E. Jones
Cisco Systems, Inc.
7025 Kit Creek Road
Research Triangle Park, NC 27709
Telephone: +1 919 392 6948
Email: paulej@packetizer.com
Expiration and File Name
This draft expires September October 2001.
Its file name is draft-eastlake-sha1-00.txt. draft-eastlake-sha1-01.txt.
D. Eastlake 3rd, P. Jones [Page 21] 22]
----