RFC-to-be - SHA Message-Digest Algorithm

[[e-mail]]

Jeff,

The RFC Editor has received an "Informational" RFC-to-be on, 
"SHA Message-Digest Algorithm".  Two week timeout is initiated: 
2 April 96.

Joyce

------------------------------------------------------------


Network Working Group                                          D. Worley
Request for Comments: nnnn                                       Ariadne
Category:  Informational                                          [date]


                    The SHA Message-Digest Algorithm

Status of this Memo

   This memo provides information for the Internet community.  This memo
   does not specify an Internet standard of any kind.  Distribution of
   this memo is unlimited.

Abstract

   This document describes the SHA (secure hash algorithm), part of the
   SHS (secure hash standard) adopted by the United States federal
   government [FIPS PUB 180-1].  The algorithm computes a condensed
   representation of a message or a data file.  The representation is
   160 bits long, and is called a message digest.  A reference
   implementation of SHA is included; however it is restricted to
   messages containing an integral number of octets less than 2^32.

Acknowledgments

   This RFC is based on [FIPS PUB 180-1] and is inspired by Professor
   Ronald L. Rivest's [RFC 1321] on the MD5 message-digest algorithm.
   SHA is based on principles similar to those used by Rivest when
   designing the MD4 message-digest algorithm [FIPS PUB 180-1, p. 1]
   [MD4] [RFC 1320], and is closely modeled after that algorithm.

   The author would like to thank Kenneth Graves of Graves Consulting
   for his assistance in checking the correctness of the reference
   implementation.

Introduction

   This document describes the SHA (secure hash algorithm), part of the
   SHS (secure hash standard) adopted by the United States federal
   government [FIPS PUB 180-1].  The algorithm computes a condensed
   representation of a message or a data file.  The representation is
   160 bits long, and is called a message digest.  SHA is defined on
   messages of less than 2^64 bits, or 2^61 octets.

   Throughout this document, the term "SHA" is used interchangeably with
   "SHA-1" to denote the second version of the algorithm, described in
   [FIPS PUB 180-1].  The term "SHA" is also used to denote the first
   (and presumably less secure) version of the algorithm described in



Worley                                                          [Page 1]

RFC nnnn            The SHA Message-Digest Algorithm              [date]


   [FIPS PUB 180].  As SHA-1 is being used in preference to SHA by the
   U.S. federal government [FIPS PUB 180-1, p. 1] and in Internet
   standards (see, e.g., [RFC 1852]), we follow [RFC 1852] and use the
   terms "SHA" and "SHA-1" interchangeably for the second version.

   It is believed that SHA is cryptographically strong, that is, that it
   is computationally infeasible to produce a message having a given SHA
   digest, to produce two different messages having the same SHA digest,
   or to derive any useful information at all about a message from its
   SHA digest, other than by discovering that the SHA digest in question
   is that of an already known message.  Any change to the message will,
   with very high probability, result in a different message digest.

   The algorithm is intended for digital signature applications where
   signing the message digest rather than the message itself improves
   the efficiency of the process, since the message digest is usually
   much smaller in size than the message.

   In addition, the algorithm can be used for authenticating messages by
   transmitting, along with the message, the SHA digest of the
   concatenation of the message and a private key known to both the
   sender and recipient of the message [RFC 1852].

   The algorithm is extraordinarily compact, requiring only ten fixed
   constants and a small amount of scratch memory.

   A reference implementation of SHA is included; however it is
   restricted to messages containing an integral number of octets less
   than 2^32.

   For OSI-based applications, SHA's object identifier is [OSI, pp. 12
   and 36 to 39]:

        sha1 OBJECT IDENTIFIER ::=
             { iso(1) identified-organization(3) oiw(14) secsig(3)
               algorithm(2) 26 }

   In the X.509 type AlgorithmIdentifier [X.509], the parameters for SHA
   should have type NULL.

Description of the Algorithm

   SHA is defined on messages of any number of bits less than 2^64.  It
   groups bits into 32-bit (unsigned) words in the big-endian manner --
   the first bit is the highest order bit of the first word, etc.  Words
   are generally written as 8 hexadecimal digits in big-endian order.

   First, bits are appended to the end of the message so that the



Worley                                                          [Page 2]

RFC nnnn            The SHA Message-Digest Algorithm              [date]


   message is an integral number of 512-bit (16-word) blocks.  The
   padding is done by appending a '1' bit, 0 to 511 '0' bits, and then
   the 64-bit big-endian binary representation of the length of the
   original message.

   Each 512-bit block of the padded message is then processed in
   sequence.  Before processing any blocks, five words H[i] are
   initialized as follows:

           H[0] = 67452301
           H[1] = EFCDAB89
           H[2] = 98BADCFE
           H[3] = 10325476
           H[4] = C3D2E1F0

   The processing of each block takes as input the values of the H[i]
   and produces as output new values of the H[i].  The SHA message
   digest of the message is the 160-bit string obtained by concatenating
   the five words H[0], H[1], H[2], H[3], and H[4] resulting after
   processing all blocks of the padded message.  The message digest is
   often written as five strings of eight hexadecimal digits, separated
   by spaces, or as one string of 40 hexadecimal digits.

Definitions

   SHA uses the following auxiliary functions and constants:

   Addition is represented by "+", and is "unsigned" -- that is, carries
   from the highest-order position are ignored, or equivalently,
   addition is done modulo 2^32.

   Bitwise logical AND, OR, NOT, and XOR operations on words are denoted
   by "&", "|", "~", and "^", respectively, as in the C language.

   S1, S5, and S30 are the 1-bit, 5-bit, and 30-bit (respectively)
   circular left shift functions on 32-bit words.  Using C notation and
   assuming that the operands are unsigned 32-bit integers:

           S<n>(X) = (X << n) | (X >> (32-n))

   SHA uses a series of bitwise mixing functions f[t] and a
   corresponding series of 32-bit constants K[t].  For every t, 0 <= t
   <= 79, f[t] and K[t] are used in round t of SHA.  Using C notation:

   For 0 <= t <= 19:

           f[t](B, C, D) = (B & C) | (~B & D)
           K[t] = 0x5A827999



Worley                                                          [Page 3]

RFC nnnn            The SHA Message-Digest Algorithm              [date]


   For 20 <= t <= 39:

           f[t](B, C, D) = B ^ C ^ D
           K[t] = 0x6ED9EBA1

   For 40 <= t <= 59:

           f[t](B, C, D) = (B & C) | (B & D) | (C & D)
                                         -- the majority operator
           K[t] = 0x8F1BBCDC

   For 60 <= t <= 79:

           f[t](B, C, D) = B ^ C ^ D
           K[t] = 0xCA62C1D6

Block Processing

   The processing of a block is as follows:

   a. Divide the block into 16 words W[0], W[1], ..., W[15], where W[0]
      is the first (leftmost) word.

   b. For t from 16 to 79, set

           W[i] = S1(W[t-3] ^ W[t-8] ^ W[t-14] ^ W[t-16]).

   c. Let A = H[0], B = H[1], C = H[2], D = H[3], and E = H[4].

   d. For t from 0 to 79, do:

           TEMP = S5(A) + f[t](B, C, D) + E + W[t] + K[t];
           E = D;
           D = C;
           C = S30(B);
           B = A;
           A = TEMP.

   e. Let

           H[0] = H[0] + A;
           H[1] = H[1] + B;
           H[2] = H[2] + C;
           H[3] = H[3] + D;
           H[4] = H[4] + E.

Sample values




Worley                                                          [Page 4]

RFC nnnn            The SHA Message-Digest Algorithm              [date]


   The SHA digests of the following messages (considered as ASCII
   codings) are:

   The null string:

           DA39A3EE 5E6B4B0D 3255BFEF 95601890 AFD80709

   The string 'abc':

           A9993E36 4706816A BA3E2571 7850C26C 9CD0D89D

   The string
   'abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq':

           84983E44 1C3BD26E BAAE4AA1 F95129E5 E54670F1

   The string of one million 'a' characters:

           34AA973C D4C4DAA4 F61EEB2B DBAD2731 6534016F

Reference implementation

   The following implementation of SHA is donated to the public domain
   by the author.

/* Program to calculate the SHA message digest of files. */

/*
 * Donated to the public domain by Dale R. Worley, Ariadne Internet
 * Services <[e-mail]>.
 */

/*
 * Usage:
 *      sha file file ...
 * Produces the SHA digest of the given files.  If no file name is given,
 * standard input is used.
 *      sha -x
 * Produces the SHA digest of test strings.  The test strings are the
 * null string and the test strings given in FIPS PUB 180-1:
 *          DA39A3EE5E6B4B0D3255BFEF95601890AFD80709    ""
 *          A9993E364706816ABA3E25717850C26C9CD0D89D    "abc"
 *          84983E441C3BD26EBAAE4AA1F95129E5E54670F1    "abcdbcde..."
 *          34AA973CD4C4DAA4F61EEB2BDBAD27316534016F    1,000,000*'a'
 *      sha -s string
 * Produces the SHA digest of 'string'.
 *      sha -- ...
 * Option '--' prevents the interpretation of later arguments as options.



Worley                                                          [Page 5]

RFC nnnn            The SHA Message-Digest Algorithm              [date]


 */

#include <stdio.h>

#ifndef BUFSIZ
#define BUFSIZ 1024
#endif

/* Define 'VERSION0' to use the original SHA defined in FIPS PUB 180.
 * Otherwise, SHA-1 defined in FIPS PUB 180-1 is used. */
/* #define VERSION0 */

/* The type WORD must be unsigned, and should be 32 bits long.
 * Replace u_int32_t with the correct type, and insert any needed
 * #include's here. */
#include <machine/types.h>
typedef u_int32_t WORD;
#define TRIM32(x) (x)
/* If a 32 bit unsigned type is unavailable, use a longer unsigned type and
 * use this definition of TRIM32(): */
/* #define TRIM32(x) ((x) & 0xFFFFFFFFu) */

typedef unsigned char uchar;
struct sha_state {
  WORD H[5];                    /* Buffer to accumulate digest in. */
  WORD length;                  /* Number of bytes accumulated so far, limited
                                   to 2^32 - 1. */
  uchar fractional_block[64];   /* Fraction of a block not incorporated into
                                   the digest yet. */
  WORD fractional_length;       /* Number of bytes in fractional_block.
                                   Equal to length & 63. */
};
/* A full buffer of zeros. */
uchar zeros[64] = { 0, 0, 0, 0, 0, 0, 0, 0,
                    0, 0, 0, 0, 0, 0, 0, 0,
                    0, 0, 0, 0, 0, 0, 0, 0,
                    0, 0, 0, 0, 0, 0, 0, 0,
                    0, 0, 0, 0, 0, 0, 0, 0,
                    0, 0, 0, 0, 0, 0, 0, 0,
                    0, 0, 0, 0, 0, 0, 0, 0,
                    0, 0, 0, 0, 0, 0, 0, 0};

void test(void);
void sha_string(const uchar *, struct sha_state *);
void sha_file(const char *);
void sha_initialize(struct sha_state *);
void sha_accumulate(struct sha_state *, const uchar *, WORD);
void sha_finish(struct sha_state *);



Worley                                                          [Page 6]

RFC nnnn            The SHA Message-Digest Algorithm              [date]


void sha_transform(WORD[5], const uchar[64]);

main(int argc, char **argv) {
  int i;

  /* Check for -x. */
  if (argc >= 2 && strcmp(argv[1], "-x") == 0) {
    test();
    exit(0);
  }

  /* Check for -s. */
  if (argc >= 2 && strcmp(argv[1], "-s") == 0) {
    struct sha_state state;

    sha_string((argc >= 3 ? argv[2] : "") , &state);
    printf("%08X%08X%08X%08X%08X0,
           state.H[0], state.H[1], state.H[2], state.H[3], state.H[4]);
    exit(0);
  }

  /* Skip a -- argument. */
  if (argc >= 2 && strcmp(argv[1], "--") == 0) {
    argv++;
    argc--;
  }

  if (argc == 1) {
    /* No arguments means read stdin. */
    sha_file(NULL);
  } else {
    /* Process each argument as a file name. */
    for (i = 1; i < argc; i++) {
      sha_file(argv[i]);
    }
  }
  exit(0);
}

uchar test_string1[] = "";
uchar test_string2[] = "abc";
uchar test_string3[] =
  "abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq";

void test() {
  struct sha_state state;
  uchar test_string4[1000001];




Worley                                                          [Page 7]

RFC nnnn            The SHA Message-Digest Algorithm              [date]


  /* Null string. */
  sha_string(test_string1, &state);
  printf("%08X%08X%08X%08X%08X
         state.H[0], state.H[1], state.H[2], state.H[3], state.H[4],
         test_string1);
  /* abc */
  sha_string(test_string2, &state);
  printf("%08X%08X%08X%08X%08X
         state.H[0], state.H[1], state.H[2], state.H[3], state.H[4],
         test_string2);
  /* abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq */
  sha_string(test_string3, &state);
  printf("%08X%08X%08X%08X%08X
         state.H[0], state.H[1], state.H[2], state.H[3], state.H[4],
         test_string3);
  /* 1,000,000 a's */
  memset(&test_string4, 'a', (size_t) 1000000);
  test_string4[1000000] = ' ';
  sha_string(test_string4, &state);
  printf("%08X%08X%08X%08X%08X1,000,000*'a'0,
         state.H[0], state.H[1], state.H[2], state.H[3], state.H[4]);
}

void sha_string(const uchar *string, struct sha_state *state) {
  sha_initialize(state);
  sha_accumulate(state, string, strlen(string));
  sha_finish(state);
}

void sha_file(const char *file) {
  struct sha_state state;
  FILE *f;
  uchar buffer[BUFSIZ];
  int i;

  if (file == NULL) {
    f = stdin;
  } else {
    f = fopen(file, "r");
    if (f == NULL) {
      perror(file);
      return;
    }
  }
  sha_initialize(&state);
  while ((i = fread(buffer, sizeof(uchar), BUFSIZ, f)) != 0) {
    sha_accumulate(&state, buffer, i);
  }



Worley                                                          [Page 8]

RFC nnnn            The SHA Message-Digest Algorithm              [date]


  if (ferror(f)) {
    perror(file);
    return;
  }
  if (fclose(f) == EOF) {
    perror(file);
    return;
  }
  sha_finish(&state);
  printf("%08X%08X%08X%08X%08X",
         state.H[0], state.H[1], state.H[2], state.H[3], state.H[4]);
  if (file != NULL) {
    printf("%s", file);
  }
  printf("0);
}

void sha_initialize(struct sha_state *state) {
  state->H[0] = 0x67452301u;
  state->H[1] = 0xEFCDAB89u;
  state->H[2] = 0x98BADCFEu;
  state->H[3] = 0x10325476u;
  state->H[4] = 0xC3D2E1F0u;
  state->length = 0;
  state->fractional_length = 0;
}

/* Accumulate some bytes into a buffer.  When the buffer fills to 16 words,
   execute the SHA transformation on the words, using the buffer H.
        state   the intermediate state of SHA processing
        bytes   the input bytes
        length  number of input bytes, limited to 2^32 - 1
 */
void sha_accumulate(struct sha_state *state, const uchar *bytes, WORD length) {
  /* Update the length count. */
  state->length += length;
  /* Make the fractional block into a full block and accumulate it,
     if possible. */
  if (state->fractional_length + length >= 64) {
    WORD i = 64 - state->fractional_length;

    memcpy(&(state->fractional_block[state->fractional_length]),
           bytes, i);
    bytes += i;
    length -= i;
    sha_transform(state->H, state->fractional_block);
    state->fractional_length = 0;
  }



Worley                                                          [Page 9]

RFC nnnn            The SHA Message-Digest Algorithm              [date]


  /* Accumulate as many full blocks as possible. */
  while (length >= 64) {
    sha_transform(state->H, bytes);
    bytes += 64;
    length -= 64;
    /* state->fractional_length will always be 0 here */
  }
  /* Append any remaining fraction of a block into the fractional buffer. */
  memcpy(&(state->fractional_block[state->fractional_length]),
         bytes, length);
  state->fractional_length += length;
}

void sha_finish(struct sha_state *state) {
  WORD length = state->length;  /* Length of the input string */
  uchar one_bit = 0x80;
  uchar b[8];
  int z;

  /* Append a byte containing a one bit. */
  sha_accumulate(state, &one_bit, 1);
  /* Calculate the number of zeros to append. */
  z = 64 - 8 - state->fractional_length;
  if (z >= 0) {
    /* We can pad out this block and put in the length. */
    sha_accumulate(state, zeros, z);
  } else {
    /* We have to pad out this block and put the length in the next block. */
    sha_accumulate(state, zeros, 64 - state->fractional_length);
    sha_accumulate(state, zeros, 64 - 8);
  }
  /* Insert the length. */
  b[0] = 0;
  b[1] = 0;
  b[2] = 0;
  b[3] = length >> 29;
  b[4] = (length >> 21) & 0xFF;
  b[5] = (length >> 13) & 0xFF;
  b[6] = (length >> 5) & 0xFF;
  b[7] = (length << 3) & 0xFF;
  sha_accumulate(state, b, 8);
}

#define S1(x)   (TRIM32((x) << 1) | (x) >> 31)
#define S5(x)   (TRIM32((x) << 5) | (x) >> 27)
#define S30(x)  (TRIM32((x) << 30) | (x) >> 2)

/* Since we know the arguments are variables, we can use fewer parentheses



Worley                                                         [Page 10]

RFC nnnn            The SHA Message-Digest Algorithm              [date]


   here than we otherwise might have to. */
#define f0(B, C, D)     (B & C | ~B & D)
#define f20(B, C, D)    (B ^ C ^ D)
#define f40(B, C, D)    (B & C | B & D | C & D)
#define f60(B, C, D)    (B ^ C ^ D)

#define K0      0x5A827999u
#define K20     0x6ED9EBA1u
#define K40     0x8F1BBCDCu
#define K60     0xCA62C1D6u

/* Execute the SHA transformation on a block of 16 words.
        H       the 5-word buffer (input and output)
        bytes   the 64-byte input block
 */
void sha_transform(WORD H[5], const uchar bytes[64]) {
  WORD W[80];                   /* The 16 input words, followed by the
                                   64 expansion words. */
  int i, j, t;
  WORD A, B, C, D, E, TEMP;

  /* Assemble the 64 bytes into 16 words. */
  for (i = 0, j = 0; j < 64; i += 1, j += 4) {
    W[i] = ((WORD)bytes[j] << 24) | ((WORD)bytes[j+1] << 16) |
      ((WORD)bytes[j+2] << 8) | (WORD)bytes[j+3];
  }
  for (t = 16; t <= 79; t++) {
#ifdef VERSION0
    W[t] = W[t-3] ^ W[t-8] ^ W[t-14] ^ W[t-16];
#else
    W[t] = S1(W[t-3] ^ W[t-8] ^ W[t-14] ^ W[t-16]);
#endif
  }
  A = H[0];
  B = H[1];
  C = H[2];
  D = H[3];
  E = H[4];
  for (t = 0; t < 20; t++) {
    TEMP = TRIM32(S5(A) + f0(B, C, D) + E + W[t] + K0);
    E = D;
    D = C;
    C = S30(B);
    B = A;
    A = TEMP;
  }
  for (t = 20; t < 40; t++) {
    TEMP = TRIM32(S5(A) + f20(B, C, D) + E + W[t] + K20);



Worley                                                         [Page 11]

RFC nnnn            The SHA Message-Digest Algorithm              [date]


    E = D;
    D = C;
    C = S30(B);
    B = A;
    A = TEMP;
  }
  for (t = 40; t < 60; t++) {
    TEMP = TRIM32(S5(A) + f40(B, C, D) + E + W[t] + K40);
    E = D;
    D = C;
    C = S30(B);
    B = A;
    A = TEMP;
  }
  for (t = 60; t < 80; t++) {
    TEMP = TRIM32(S5(A) + f60(B, C, D) + E + W[t] + K60);
    E = D;
    D = C;
    C = S30(B);
    B = A;
    A = TEMP;
  }
  H[0] = TRIM32(H[0] + A);
  H[1] = TRIM32(H[1] + B);
  H[2] = TRIM32(H[2] + C);
  H[3] = TRIM32(H[3] + D);
  H[4] = TRIM32(H[4] + E);
}

Security Considerations

   As a cryptographic hash algorithm, the level of security provided by
   SHA is considered to be sufficient by the United States federal
   government for applications not involving military classified
   information [FIPS PUB 180-1, p. 2].

   Users need to understand that the quality of the security provided by
   this specification depends on the strength of the SHA algorithm, the
   correctness of that algorithm's implementation, the strength of the
   security system within which it is used, and the strength of any key
   management mechanisms used.

References

   [FIPS PUB 180] Computer Systems Laboratory, "Secure Hash Standard",
   FIPS PUB 180, National Institute of Standards and Technology, May
   1993.  <URL:ftp://csrc.ncsl.nist.gov/pub/fips/fips180.txt>




Worley                                                         [Page 12]

RFC nnnn            The SHA Message-Digest Algorithm              [date]


   [FIPS PUB 180-1] Computer Systems Laboratory, "Secure Hash Standard",
   FIPS PUB 180-1, National Institute of Standards and Technology,
   April, 1995.  <URL:ftp://csrc.ncsl.nist.gov/pub/fips/fip180-1.txt>

   [MD4] "The MD4 Message Digest Algorithm," Advances in Cryptology -
   CRYPTO '90 Proceedings, Springer-Verlag, 1991, pp. 303-311.

   [OSI] Computer Systems Laboratory, "Stable Implementation Agreements
   for Open Systems Interconnection Protocols:  Part 12 - OS Security",
   National Institute of Standards and Technology, June 1995.
   <URL:ftp://nemo.ncsl.nist.gov/pub/oiw/agreements/stable/
        OSI/12s_9506.txt>

   [RFC 1320] Rivest, R., "The MD4 Message-Digest Algorithm", RFC 1320,
   MIT LCS and RSA Data Security, April 1992.
   <URL:ftp://ds.internic.net/rfc/rfc1320.txt>

   [RFC 1321] Rivest, R., "The MD5 Message-Digest Algorithm", RFC 1321,
   MIT LCS and RSA Data Security, April 1992.
   <URL:ftp://ds.internic.net/rfc/rfc1321.txt>

   [RFC 1852] Metzger, P., and W. Simpson, "IP Authentication using
   Keyed SHA", RFC 1852, Piermont and Daydreamer, September 1995.
   <URL:ftp://ds.internic.net/rfc/rfc1852.txt>

   [X.509] CCITT, "Recommendation X.509 (1988): The Directory -
   Authentication Framework", 1988.

Author's Address

   Dale R. Worley
   Ariadne Internet Services
   738 Main St., Suite 241
   Waltham, MA  02154
   [e-mail]