Network Working Group Crypto Forum Research Group
INTERNET DRAFT Uri Blumenthal, Intel
November 2005 C.S. Jutla, IBM
Expiration Date: May 2006 A. C. Patthak, UT Austin
SHA1-IME: A SHA-1 Variant with Provably Good
Message Expansion Code
Status of this Memo
By submitting this Internet-Draft, each author represents
that any applicable patent or other IPR claims of which he
or she is aware have been or will be disclosed, and any of
which he or she becomes aware will be disclosed, in accor-
dance with Section 6 of BCP 79.
This document is an Internet-Draft and is in full confor-
mance with all provisions of Section 10 of RFC2026.
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
This document describes a new cryptographic hash function
SHA1-IME with input and output parameters identical to SHA-
1. Further, the specification of SHA1-IME is identical to
that of SHA-1, except for an improved message expansion
code. The improved message expansion is proven to make
SHA1-IME resistant to recent differential attacks and their
natural extensions.
Moreover, SHA1-IME has only a 5% overhead when compared to
SHA-1 in a software implementation. The simplicity of the
design change, compatibility with SHA-1 parameters, and the
excellent speed/security tradeoff makes it an ideal candi-
date for SHA-1 replacement.
BJP 1
Table of Contents
1. Introduction ............................................ 3
2. BIT STRINGS AND INTEGERS ................................ 4
3. OPERATIONS ON WORDS ..................................... 4
4. MESSAGE PADDING ......................................... 5
5. FUNCTIONS USED .......................................... 6
6. CONSTANTS USED .......................................... 7
7. COMPUTING THE MESSAGE DIGEST ............................ 7
8. Intellectual Property Issues ............................ 8
9. TEST VECTORS ............................................ 8
10. Acknowledgments ........................................ 9
11. References ............................................. 9
12. Authors' Address ....................................... 9
13. Copyright Notice ....................................... 10
APPENDIX A, B & C (Reference Implementation)
BJP 2
Internet Draft Nov 2005
1. Introduction
In this document we propose a new cryptographic hash func-
tion SHA1-IME (SHA-1 with Improved Message Expansion). This
document will closely follow the specification of SHA-1
given in FIPS PUB 180-1 ([SHA1]).
As for SHA-1, the hash function SHA1-IME is used to compute
a condensed representation of a message or a data file. In
fact, SHA1-IME so closely resembles SHA-1, except for a
small modification in the code, that its usage in single
block, and in multi block settings is identical to SHA-1.
The small modification in the code leads to a huge gain in
security over SHA-1 w.r.t. differential attacks, making it
an ideal candidate for a SHA-1 replacement. Moreover, the
security claims are based on actual proofs (see [JP1], [JP2]
for extensive security analysis and proofs).
In a software implementation, SHA1-IME has only a 5% over-
head when compared to SHA-1. In a high performance hardware
implementation, we expect SHA1-IME to have a 10% overhead
(comparable to SHA-256 [SHA2]). Further, there are no Intel-
lectual Property claims on the new hash function SHA1-IME.
To give a brief overview of SHA1-IME, recall that in SHA-1,
a message expansion code is used to expand 512 bits (packed
in 16 words) to 80 words. This linear expansion code, how-
ever turned out to have a much smaller minimum hamming
weight than expected. This fact is an integral part of the
recent attack of Wang et al ([WYY]) on SHA-1. The message
expansion code in SHA1-IME (which is the only place where it
differs from SHA-1) has been proven to have a large minimum
hamming weight([JP1]). Further, it has been shown in [JP2]
that when the message expansion code has a large minimum
hamming weight then differential attacks (including Wang et
al [WYY] and its natural extensions) cannot be used to find
collisions.
The specification of SHA1-IME differs from SHA-1 in ONLY
step (b) of section 7 "Computing the Message Digest" of FIPS
PUB 180-1. This corresponds to step (b) of section 7 of this
document. Thus, replacing step (b) of section 7 of FIPS PUB
180-1 by step (b) of section 7 of the current document
would lead to a correct implementation of SHA1-IME. Test
Vectors for SHA1-IME are provided in section 9. It is
noteworthy that the description of SHA-1 in FIPS PUB 180-2
is identical to the description of SHA-1 in FIPS PUB 180-1.
A Reference Implementation is given in the appendix.
BJP 3
Internet Draft Nov 2005
For a message of length < 2^64 bits, SHA1-IME produces a 160
bit message digest.
2. 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.
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.
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 represented by the right-most hex
digit of the word representation. If z is an integer, 0
<= z < 2^64, then z = 2^32x + 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 may be represented as
a sequence of 16 words.
3. OPERATIONS ON WORDS
The following logical operators will be applied to words:
a.
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.
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.
BJP 4
Internet Draft Nov 2005
Then 0 <= z < 2^32. Convert z to a word, Z, and define
Z = X + Y.
c. The circular left shift operation ROLn(X), where X is
a word and n is an integer with 0 <= n^32, is defined
by ROLn(X) = (X << n) OR (X >> 32-n).
E.g. ROL21(A) = (A << 21) OR (A >> 11)
In the above, X << n is obtained as follows: discard
the left-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 ROLn(X) is equivalent to a circular
shift of X by n positions to the left.
4. MESSAGE PADDING
The SHA1-IME is used to compute a message digest for a mes-
sage 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.
The SHA1-IME 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" fol-
lowed 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 l, the length of the original
message. The padded message is then processed by the SHA1-
IME as n 512-bit blocks.
Suppose a message has length l < 2^64. Before it is input to
the SHA1-IME, 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.
BJP 5
Internet Draft Nov 2005
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
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 mes-
sage 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), ... , M(n), where each M(i) con-
tains 16 words and M(1) contains the first characters
(or bits) of the message.
5.
A sequence of logical functions f_0, f_1,..., f_{79} is used
in the SHA1-IME. 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,
BJP 6
Internet Draft Nov 2005
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).
6. CONSTANTS USED
A sequence of constant words K(0), K(1), ... , K(79) is used
in the SHA1-IME. 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 mes-
sage. 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 {Hi} are initialized as
follows: in hex,
H0 = 67452301
H1 = EFCDAB89
H2 = 98BADCFE
BJP 7
Internet Draft Nov 2005
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 35 let
W(t) = (W(t-3) XOR W(t-8) XOR W(t- 14) XOR W(t-16)) XOR
ROL13(W(i-1) XOR W(i-2) XOR W(i-15)).
For t = 36 to 79 let
W(t) = (W(t-3) XOR W(t-8) XOR W(t- 14) XOR W(t-16)) XOR
ROL13(W(i-1) XOR W(i-2) XOR W(i-15) XOR W(i-20)).
c. Let A = H0, B = H1, C = H2, D = H3, E = H4.
d. For t = 0 to 79 do
TEMP = ROL5(A) + f_t(B,C,D) + E + W(t) + K(t);
E = D; D = C; C = ROL30(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.
8. Intellectual Property Issues
There is no intellectual property filed on SHA1-IME.
9. TEST VECTORS
A. Let the message be the ASCII binary-coded form of "abc",
i.e.,
01100001 01100010 01100011
The Message Digest using the above SHA1-IME specification
is
3eae191e 555c3d4c 314bfcd7 09875b6e 518003f5
B. Let the message be the binary coded form of the ASCII string
"abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq".
The Message Digest is
e4b0ece7 052e65ed 6f52b66b b23d9f3d 1dcc177a
C. Let the message be the binary coded form of the ASCII string
BJP 8
Internet Draft Nov 2005
which consists of 1,000,000 repetitions of "a".
The Message digest is
3c006258 340db10b a3682770 a4cb6f30 efbc265c
10. Acknowledgments
The authors would like to thank Pankaj Rohatgi, Arjen Lens-
tra, Ron Rivest, and Hugo Krawczyk for helpful comments.
Source code of SHA1 provided by D. Eastlake [DE] was modified
to provide this reference code.
11. References
[SHA1] FIPS PUB 180-1, "Secure Hash Standard", May 1993.
[SHA2] FIPS PUB 180-2, "Secure Hash Standard", Aug 2002.
[JP1] C. S. Jutla, A. C. Patthak, "A Simple and Provably Good
Code for SHA Message Expansion", IACR eprint archive
2005/247, July 2005.
[JP2] C. S. Jutla, A. C. Patthak, "Is SHA-1 Conceptually Sound?",
IACR eprint archive 2005/350, Oct 2005.
[WYY] X. Wang, H. Yu, Y.L. Yin, "Finding Collisions in the full
SHA-1", Proc. Crypto 2005.
[DE] D. Eastlake, 3rd, P. Jones, "US Secure Hash Algorithm 1 (SHA1)",
RFC 3174, September 2001.
12. Author's Address
Uri Blumenthal
Intel Corporation
1515 State Route 10,
3PY1-3.536
Parsippany, NJ 07054
USA
Phone: +1.973.967.6446
Email: uri DOT blumenthal AT intel DOT com
Charanjit S. Jutla
IBM T.J. Watson Research Center,
Yorktown Heights, NY 10598-704.
Phone: 914-784-7890
Email: csjutla AT us DOT ibm DOT com
BJP 9
Internet Draft Nov 2005
Anindya Patthak
Department of Computer Science,
The University of Texas at Austin,
1 University Station C0500
Austin, TX 78712
Phone: (512) 471-9572.
Email: anindya AT cs DOT utexas DOT edu
Comments should be sent to C. S. Jutla at his
e-mail address above.
13. COPYRIGHT NOTICE
Copyright (C) The Internet Society (2005).
This document is subject to the rights, licenses and res-
trictions contained in BCP 78, and except as set forth
therein, the authors retain all their rights.
This document and the information contained herein are pro-
vided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZA-
TION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE
INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE
DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT
NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION
HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRAN-
TIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
BJP 10
Appendix A. sha1ime.h
/*
* sha1ime.h
*
* Description:
* This is the header file for code which implements the IME
* modification of Secure Hashing Algorithm 1 as defined in
* FIPS PUB 180-1 and 180-2.
*
* Please read the file sha1ime.c for more information.
*
*/
#ifndef _SHA1IME_H_
#define _SHA1IME_H_
#include
/*
* If you do not have the ISO standard stdint.h header file, then you
* must typdef the following:
* name meaning
* uint32_t unsigned 32 bit integer
* uint8_t unsigned 8 bit integer (i.e., unsigned char)
* int_least16_t integer of >= 16 bits
*
*/
#ifndef _SHA_enum_
#define _SHA_enum_
enum
{
shaSuccess = 0,
shaNull, /* Null pointer parameter */
shaInputTooLong, /* input data too long */
shaStateError /* called Input after Result */
};
#endif
#define SHA1IMEHashSize 20
/*
* This structure will hold context information for the SHA-1
* hashing operation
*/
typedef struct SHA1IMEContext
{
uint32_t Intermediate_Hash[SHA1IMEHashSize/4]; /* Message Digest */
uint32_t Length_Low; /* Message length in bits */
uint32_t Length_High; /* Message length in bits */
/* Index into message block array */
int_least16_t Message_Block_Index;
uint8_t Message_Block[64]; /* 512-bit message blocks */
int Computed; /* Is the digest computed? */
int Corrupted; /* Is the message digest corrupted? */
} SHA1IMEContext;
/*
* Function Prototypes
*/
int SHA1IMEReset( SHA1IMEContext *);
int SHA1IMEInput( SHA1IMEContext *,
const uint8_t *,
unsigned int);
int SHA1IMEResult( SHA1IMEContext *,
uint8_t Message_Digest[SHA1IMEHashSize]);
#endif
Appendix B. sha1ime.c
/*
* sha1ime.c
*
* Description:
* This file implements the IME modification to Secure Hashing
* Algorithm 1 as defined in FIPS PUB 180-1 and 180-2.
*
* The SHA1-IME, produces a 160-bit message digest for a given
* data stream. 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 with the same digest,
* when n is the digest size in bits. Therefore, this
* algorithm can serve as a means of providing a
* "fingerprint" for a message.
*
* Portability Issues:
* SHA1-IME is defined in terms of 32-bit "words". This code
* uses (included via "sha1.h" to define 32 and 8
* bit unsigned integer types. If your C compiler does not
* support 32 bit unsigned integers, this code is not
* appropriate.
*
* Caveats:
* SHA1-IME like SHA-1, is designed to work with messages less
* than 2^64 bits long. Although SHA1-IME allows a message digest
* to be generated for messages of any number of bits less than 2^64,
* this implementation only works with messages with a length that is
* a multiple of the size of an 8-bit character.
*
*/
#include "sha1ime.h"
/*
* Define the SHA1-IME circular left shift macro
*/
#define SHA1IMECircularShift(bits,word) \
(((word) << (bits)) | ((word) >> (32-(bits))))
/* Local Function Prototyptes */
void SHA1IMEPadMessage(SHA1IMEContext *);
void SHA1IMEProcessMessageBlock(SHA1IMEContext *);
/*
* SHA1IMEReset
*
* Description:
* This function will initialize the SHA1IMEContext in
* preparation for computing a new SHA1-IME message digest.
*
* Parameters:
* context: [in/out]
* The context to reset.
*
* Returns:
* sha Error Code.
*
*/
int SHA1IMEReset(SHA1IMEContext *context)
{
if (!context)
{
return shaNull;
}
context->Length_Low = 0;
context->Length_High = 0;
context->Message_Block_Index = 0;
context->Intermediate_Hash[0] = 0x67452301;
context->Intermediate_Hash[1] = 0xEFCDAB89;
context->Intermediate_Hash[2] = 0x98BADCFE;
context->Intermediate_Hash[3] = 0x10325476;
context->Intermediate_Hash[4] = 0xC3D2E1F0;
context->Computed = 0;
context->Corrupted = 0;
return shaSuccess;
}
/*
* SHA1IMEResult
*
* Description:
* This function will return the 160-bit message digest into the
* Message_Digest array 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]
* The context to use to calculate the SHA-1 hash.
* Message_Digest: [out]
* Where the digest is returned.
*
* Returns:
* sha Error Code.
*
*/
int SHA1IMEResult( SHA1IMEContext *context,
uint8_t Message_Digest[SHA1IMEHashSize])
{
int i;
if (!context || !Message_Digest)
{
return shaNull;
}
if (context->Corrupted)
{
return context->Corrupted;
}
if (!context->Computed)
{
SHA1IMEPadMessage(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 < SHA1IMEHashSize; ++i)
{
Message_Digest[i] = context->Intermediate_Hash[i>>2]
>> 8 * ( 3 - ( i & 0x03 ) );
}
return shaSuccess;
}
/*
* SHA1IMEInput
*
* Description:
* This function accepts an array of octets as the next portion
* of the message.
*
* Parameters:
* context: [in/out]
* The SHA1-IME context to update
* message_array: [in]
* An array of characters representing the next portion of
* the message.
* length: [in]
* The length of the message in message_array
*
* Returns:
* sha Error Code.
*
*/
int SHA1IMEInput( SHA1IMEContext *context,
const uint8_t *message_array,
unsigned length)
{
if (!length)
{
return shaSuccess;
}
if (!context || !message_array)
{
return shaNull;
}
if (context->Computed)
{
context->Corrupted = 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;
if (context->Length_Low == 0)
{
context->Length_High++;
if (context->Length_High == 0)
{
/* Message is too long */
context->Corrupted = 1;
}
}
if (context->Message_Block_Index == 64)
{
SHA1IMEProcessMessageBlock(context);
}
message_array++;
}
return shaSuccess;
}
/*
* SHA1IMEProcessMessageBlock
*
* 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 this code, especially the
* single character names, were used because those were the
* names used in the publication.
*
*
*/
void SHA1IMEProcessMessageBlock(SHA1IMEContext *context)
{
const uint32_t K[] = { /* Constants defined in SHA-1 */
0x5A827999,
0x6ED9EBA1,
0x8F1BBCDC,
0xCA62C1D6
};
int t; /* Loop counter */
uint32_t temp; /* Temporary word value */
uint32_t W[80]; /* Word sequence */
uint32_t 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;
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 < 36; t++)
{
W[t] = (W[t-3] ^ W[t-8] ^ W[t-14] ^ W[t-16]) ^
SHA1IMECircularShift(13,
(W[t-1] ^ W[t-2] ^ W[t-15]));
}
for(t = 36; t < 80; t++)
{
W[t] = (W[t-3] ^ W[t-8] ^ W[t-14] ^ W[t-16]) ^
SHA1IMECircularShift(13,
(W[t-1] ^ W[t-2] ^ W[t-15] ^ W[t-20]));
}
A = context->Intermediate_Hash[0];
B = context->Intermediate_Hash[1];
C = context->Intermediate_Hash[2];
D = context->Intermediate_Hash[3];
E = context->Intermediate_Hash[4];
for(t = 0; t < 20; t++)
{
temp = SHA1IMECircularShift(5,A) +
((B & C) | ((~B) & D)) + E + W[t] + K[0];
E = D;
D = C;
C = SHA1IMECircularShift(30,B);
B = A;
A = temp;
}
for(t = 20; t < 40; t++)
{
temp = SHA1IMECircularShift(5,A) + (B ^ C ^ D) + E + W[t] + K[1];
E = D;
D = C;
C = SHA1IMECircularShift(30,B);
B = A;
A = temp;
}
for(t = 40; t < 60; t++)
{
temp = SHA1IMECircularShift(5,A) +
((B & C) | (B & D) | (C & D)) + E + W[t] + K[2];
E = D;
D = C;
C = SHA1IMECircularShift(30,B);
B = A;
A = temp;
}
for(t = 60; t < 80; t++)
{
temp = SHA1IMECircularShift(5,A) + (B ^ C ^ D) + E + W[t] + K[3];
E = D;
D = C;
C = SHA1IMECircularShift(30,B);
B = A;
A = temp;
}
context->Intermediate_Hash[0] += A;
context->Intermediate_Hash[1] += B;
context->Intermediate_Hash[2] += C;
context->Intermediate_Hash[3] += D;
context->Intermediate_Hash[4] += E;
context->Message_Block_Index = 0;
}
/*
* SHA1IMEPadMessage
*
* 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 the ProcessMessageBlock function
* provided appropriately. When it returns, it can be assumed that
* the message digest has been computed.
*
* Parameters:
* context: [in/out]
* The context to pad
* ProcessMessageBlock: [in]
* The appropriate SHA*ProcessMessageBlock function
* Returns:
* Nothing.
*
*/
void SHA1IMEPadMessage(SHA1IMEContext *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;
}
SHA1IMEProcessMessageBlock(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)
{
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;
context->Message_Block[57] = context->Length_High >> 16;
context->Message_Block[58] = context->Length_High >> 8;
context->Message_Block[59] = context->Length_High;
context->Message_Block[60] = context->Length_Low >> 24;
context->Message_Block[61] = context->Length_Low >> 16;
context->Message_Block[62] = context->Length_Low >> 8;
context->Message_Block[63] = context->Length_Low;
SHA1IMEProcessMessageBlock(context);
}
Appendix C. sha1ime_test.c
/*
* sha1ime_test.c
*
* Description:
* This file will exercise the SHA-1 code performing the three
* tests documented in FIPS PUB 180-1 plus one which calls
* SHA1Input with an exact multiple of 512 bits, plus a few
* error test checks.
*
* Portability Issues:
* None.
*
*/
#include
#include
#include
#include "sha1ime.h"
/*
* Define patterns for testing
*/
#define TEST1 "abc"
#define TEST2a "abcdbcdecdefdefgefghfghighijhi"
#define TEST2b "jkijkljklmklmnlmnomnopnopq"
#define 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 repeatcount[4] = { 1, 1, 1000000, 10 };
char *resultarray[4] = {
"3E AE 19 1E 55 5C 3D 4C 31 4B FC D7 09 87 5B 6E 51 80 03 F5",
"E4 B0 EC E7 05 2E 65 ED 6F 52 B6 6B B2 3D 9F 3D 1D CC 17 7A",
"3C 00 62 58 34 0D B1 0B A3 68 27 70 A4 CB 6F 30 EF BC 26 5C",
"11 FD 36 AA 29 F6 9C 4C 90 4D 92 2C A3 7B FB C2 AA 63 5E 27"
};
int main()
{
SHA1IMEContext sha;
int i, j, err;
uint8_t Message_Digest[20];
/*
* Perform SHA1-IME tests
*/
for(j = 0; j < 4; ++j)
{
printf( "\nTest %d: %d, '%s'\n",
j+1,
repeatcount[j],
testarray[j]);
err = SHA1IMEReset(&sha);
if (err)
{
fprintf(stderr, "SHA1IMEReset Error %d.\n", err );
break; /* out of for j loop */
}
for(i = 0; i < repeatcount[j]; ++i)
{
err = SHA1IMEInput(&sha,
(const unsigned char *) testarray[j],
strlen(testarray[j]));
if (err)
{
fprintf(stderr, "SHA1IMEInput Error %d.\n", err );
break; /* out of for i loop */
}
}
err = SHA1IMEResult(&sha, Message_Digest);
if (err)
{
fprintf(stderr,
"SHA1IMEResult Error %d, could not compute message digest.\n",
err );
}
else
{
printf("\t");
for(i = 0; i < 20 ; ++i)
{
printf("%02X ", Message_Digest[i]);
}
printf("\n");
}
printf("Should match:\n");
printf("\t%s\n", resultarray[j]);
}
/* Test some error returns */
err = SHA1IMEInput(&sha,(const unsigned char *) testarray[1], 1);
printf ("\nError %d. Should be %d.\n", err, shaStateError );
err = SHA1IMEReset(0);
printf ("\nError %d. Should be %d.\n", err, shaNull );
return 0;
}