doc/rfc3174.txt

   1
   2
   3
   4
   5
   6
   7 Network Working Group                                   D. Eastlake, 3rd
   8 Request for Comments: 3174                                      Motorola
   9 Category: Informational                                         P. Jones
  10                                                            Cisco Systems
  11                                                           September 2001
  12
  13
  14                    US Secure Hash Algorithm 1 (SHA1)
  15
  16 Status of this Memo
  17
  18    This memo provides information for the Internet community.  It does
  19    not specify an Internet standard of any kind.  Distribution of this
  20    memo is unlimited.
  21
  22 Copyright Notice
  23
  24    Copyright (C) The Internet Society (2001).  All Rights Reserved.
  25
  26 Abstract
  27
  28    The purpose of this document is to make the SHA-1 (Secure Hash
  29    Algorithm 1) hash algorithm conveniently available to the Internet
  30    community.  The United States of America has adopted the SHA-1 hash
  31    algorithm described herein as a Federal Information Processing
  32    Standard.  Most of the text herein was taken by the authors from FIPS
  33    180-1.  Only the C code implementation is "original".
  34
  35 Acknowledgements
  36
  37    Most of the text herein was taken from [FIPS 180-1].  Only the C code
  38    implementation is "original" but its style is similar to the
  39    previously published MD4 and MD5 RFCs [RFCs 1320, 1321].
  40
  41    The SHA-1 is based on principles similar to those used by Professor
  42    Ronald L. Rivest of MIT when designing the MD4 message digest
  43    algorithm [MD4] and is modeled after that algorithm [RFC 1320].
  44
  45    Useful comments from the following, which have been incorporated
  46    herein, are gratefully acknowledged:
  47
  48       Tony Hansen
  49       Garrett Wollman
  50
  51
  52
  53
  54
  55
  56
  57
  58 Eastlake & Jones             Informational                      [Page 1]
  59 \f
  60 RFC 3174           US Secure Hash Algorithm 1 (SHA1)      September 2001
  61
  62
  63 Table of Contents
  64
  65    1. Overview of Contents...........................................  2
  66    2. Definitions of Bit Strings and Integers........................  3
  67    3. Operations on Words............................................  3
  68    4. Message Padding................................................  4
  69    5. Functions and Constants Used...................................  6
  70    6. Computing the Message Digest...................................  6
  71    6.1 Method 1......................................................  6
  72    6.2 Method 2......................................................  7
  73    7. C Code.........................................................  8
  74    7.1 .h file.......................................................  8
  75    7.2 .c file....................................................... 10
  76    7.3 Test Driver................................................... 18
  77    8. Security Considerations........................................ 20
  78    References........................................................ 21
  79    Authors' Addresses................................................ 21
  80    Full Copyright Statement.......................................... 22
  81
  82 1. Overview of Contents
  83
  84    NOTE: The text below is mostly taken from [FIPS 180-1] and assertions
  85    therein of the security of SHA-1 are made by the US Government, the
  86    author of [FIPS 180-1], and not by the authors of this document.
  87
  88    This document specifies a Secure Hash Algorithm, SHA-1, for computing
  89    a condensed representation of a message or a data file.  When a
  90    message of any length < 2^64 bits is input, the SHA-1 produces a
  91    160-bit output called a message digest.  The message digest can then,
  92    for example, be input to a signature algorithm which generates or
  93    verifies the signature for the message.  Signing the message digest
  94    rather than the message often improves the efficiency of the process
  95    because the message digest is usually much smaller in size than the
  96    message.  The same hash algorithm must be used by the verifier of a
  97    digital signature as was used by the creator of the digital
  98    signature.  Any change to the message in transit will, with very high
  99    probability, result in a different message digest, and the signature
 100    will fail to verify.
 101
 102    The SHA-1 is called secure because it is computationally infeasible
 103    to find a message which corresponds to a given message digest, or to
 104    find two different messages which produce the same message digest.
 105    Any change to a message in transit will, with very high probability,
 106    result in a different message digest, and the signature will fail to
 107    verify.
 108
 109
 110
 111
 112
 113
 114 Eastlake & Jones             Informational                      [Page 2]
 115 \f
 116 RFC 3174           US Secure Hash Algorithm 1 (SHA1)      September 2001
 117
 118
 119    Section 2 below defines the terminology and functions used as
 120    building blocks to form SHA-1.
 121
 122 2. Definitions of Bit Strings and Integers
 123
 124    The following terminology related to bit strings and integers will be
 125    used:
 126
 127    a. A hex digit is an element of the set {0, 1, ... , 9, A, ... , F}.
 128       A hex digit is the representation of a 4-bit string.  Examples:  7
 129       = 0111, A = 1010.
 130
 131    b. A word equals a 32-bit string which may be represented as a
 132       sequence of 8 hex digits.  To convert a word to 8 hex digits each
 133       4-bit string is converted to its hex equivalent as described in
 134       (a) above.  Example:
 135
 136       1010 0001 0000 0011 1111 1110 0010 0011 = A103FE23.
 137
 138    c. An integer between 0 and 2^32 - 1 inclusive may be represented as
 139       a word.  The least significant four bits of the integer are
 140       represented by the right-most hex digit of the word
 141       representation.  Example: the integer 291 = 2^8+2^5+2^1+2^0 =
 142       256+32+2+1 is represented by the hex word, 00000123.
 143
 144       If z is an integer, 0 <= z < 2^64, then z = (2^32)x + y where 0 <=
 145       x < 2^32 and 0 <= y < 2^32.  Since x and y can be represented as
 146       words X and Y, respectively, z can be represented as the pair of
 147       words (X,Y).
 148
 149    d. block = 512-bit string.  A block (e.g., B) may be represented as a
 150       sequence of 16 words.
 151
 152 3. Operations on Words
 153
 154    The following logical operators will be applied to words:
 155
 156    a. Bitwise logical word operations
 157
 158       X AND Y  =  bitwise logical "and" of  X and Y.
 159
 160       X OR Y   =  bitwise logical "inclusive-or" of X and Y.
 161
 162       X XOR Y  =  bitwise logical "exclusive-or" of X and Y.
 163
 164       NOT X    =  bitwise logical "complement" of X.
 165
 166
 167
 168
 169
 170 Eastlake & Jones             Informational                      [Page 3]
 171 \f
 172 RFC 3174           US Secure Hash Algorithm 1 (SHA1)      September 2001
 173
 174
 175       Example:
 176
 177                01101100101110011101001001111011
 178          XOR   01100101110000010110100110110111
 179                --------------------------------
 180            =   00001001011110001011101111001100
 181
 182    b. The operation X + Y is defined as follows:  words X and Y
 183       represent integers x and y, where 0 <= x < 2^32 and 0 <= y < 2^32.
 184       For positive integers n and m, let n mod m be the remainder upon
 185       dividing n by m.  Compute
 186
 187          z  =  (x + y) mod 2^32.
 188
 189       Then 0 <= z < 2^32.  Convert z to a word,  Z, and define Z = X +
 190       Y.
 191
 192    c. The circular left shift operation S^n(X), where X is a word and n
 193       is an integer with 0 <= n < 32, is defined by
 194
 195          S^n(X)  =  (X << n) OR (X >> 32-n).
 196
 197       In the above, X << n is obtained as follows: discard the left-most
 198       n bits of X and then pad the result with n zeroes on the right
 199       (the result will still be 32 bits).  X >> n is obtained by
 200       discarding the right-most n bits of X and then padding the result
 201       with n zeroes on the left.  Thus S^n(X) is equivalent to a
 202       circular shift of X by n positions to the left.
 203
 204 4. Message Padding
 205
 206    SHA-1 is used to compute a message digest for a message or data file
 207    that is provided as input.  The message or data file should be
 208    considered to be a bit string.  The length of the message is the
 209    number of bits in the message (the empty message has length 0).  If
 210    the number of bits in a message is a multiple of 8, for compactness
 211    we can represent the message in hex.  The purpose of message padding
 212    is to make the total length of a padded message a multiple of 512.
 213    SHA-1 sequentially processes blocks of 512 bits when computing the
 214    message digest.  The following specifies how this padding shall be
 215    performed.  As a summary, a "1" followed by m "0"s followed by a 64-
 216    bit integer are appended to the end of the message to produce a
 217    padded message of length 512 * n.  The 64-bit integer is the length
 218    of the original message.  The padded message is then processed by the
 219    SHA-1 as n 512-bit blocks.
 220
 221
 222
 223
 224
 225
 226 Eastlake & Jones             Informational                      [Page 4]
 227 \f
 228 RFC 3174           US Secure Hash Algorithm 1 (SHA1)      September 2001
 229
 230
 231    Suppose a message has length l < 2^64.  Before it is input to the
 232    SHA-1, the message is padded on the right as follows:
 233
 234    a. "1" is appended.  Example: if the original message is "01010000",
 235       this is padded to "010100001".
 236
 237    b. "0"s are appended.  The number of "0"s will depend on the original
 238       length of the message.  The last 64 bits of the last 512-bit block
 239       are reserved
 240
 241       for the length l of the original message.
 242
 243       Example:  Suppose the original message is the bit string
 244
 245          01100001 01100010 01100011 01100100 01100101.
 246
 247       After step (a) this gives
 248
 249          01100001 01100010 01100011 01100100 01100101 1.
 250
 251       Since l = 40, the number of bits in the above is 41 and 407 "0"s
 252       are appended, making the total now 448.  This gives (in hex)
 253
 254          61626364 65800000 00000000 00000000
 255          00000000 00000000 00000000 00000000
 256          00000000 00000000 00000000 00000000
 257          00000000 00000000.
 258
 259    c. Obtain the 2-word representation of l, the number of bits in the
 260       original message.  If l < 2^32 then the first word is all zeroes.
 261       Append these two words to the padded message.
 262
 263       Example: Suppose the original message is as in (b).  Then l = 40
 264       (note that l is computed before any padding).  The two-word
 265       representation of 40 is hex 00000000 00000028.  Hence the final
 266       padded message is hex
 267
 268          61626364 65800000 00000000 00000000
 269          00000000 00000000 00000000 00000000
 270          00000000 00000000 00000000 00000000
 271          00000000 00000000 00000000 00000028.
 272
 273       The padded message will contain 16 * n words for some n > 0.
 274       The padded message is regarded as a sequence of n blocks M(1) ,
 275       M(2), first characters (or bits) of the message.
 276
 277
 278
 279
 280
 281
 282 Eastlake & Jones             Informational                      [Page 5]
 283 \f
 284 RFC 3174           US Secure Hash Algorithm 1 (SHA1)      September 2001
 285
 286
 287 5. Functions and Constants Used
 288
 289    A sequence of logical functions f(0), f(1),..., f(79) is used in
 290    SHA-1.  Each f(t), 0 <= t <= 79, operates on three 32-bit words B, C,
 291    D and produces a 32-bit word as output.  f(t;B,C,D) is defined as
 292    follows: for words B, C, D,
 293
 294       f(t;B,C,D) = (B AND C) OR ((NOT B) AND D)         ( 0 <= t <= 19)
 295
 296       f(t;B,C,D) = B XOR C XOR D                        (20 <= t <= 39)
 297
 298       f(t;B,C,D) = (B AND C) OR (B AND D) OR (C AND D)  (40 <= t <= 59)
 299
 300       f(t;B,C,D) = B XOR C XOR D                        (60 <= t <= 79).
 301
 302    A sequence of constant words K(0), K(1), ... , K(79) is used in the
 303    SHA-1.  In hex these are given by
 304
 305       K(t) = 5A827999         ( 0 <= t <= 19)
 306
 307       K(t) = 6ED9EBA1         (20 <= t <= 39)
 308
 309       K(t) = 8F1BBCDC         (40 <= t <= 59)
 310
 311       K(t) = CA62C1D6         (60 <= t <= 79).
 312
 313 6. Computing the Message Digest
 314
 315    The methods given in 6.1 and 6.2 below yield the same message digest.
 316    Although using method 2 saves sixty-four 32-bit words of storage, it
 317    is likely to lengthen execution time due to the increased complexity
 318    of the address computations for the { W[t] } in step (c).  There are
 319    other computation methods which give identical results.
 320
 321 6.1 Method 1
 322
 323    The message digest is computed using the message padded as described
 324    in section 4.  The computation is described using two buffers, each
 325    consisting of five 32-bit words, and a sequence of eighty 32-bit
 326    words.  The words of the first 5-word buffer are labeled A,B,C,D,E.
 327    The words of the second 5-word buffer are labeled H0, H1, H2, H3, H4.
 328    The words of the 80-word sequence are labeled W(0), W(1),..., W(79).
 329    A single word buffer TEMP is also employed.
 330
 331    To generate the message digest, the 16-word blocks M(1), M(2),...,
 332    M(n) defined in section 4 are processed in order.  The processing of
 333    each M(i) involves 80 steps.
 334
 335
 336
 337
 338 Eastlake & Jones             Informational                      [Page 6]
 339 \f
 340 RFC 3174           US Secure Hash Algorithm 1 (SHA1)      September 2001
 341
 342
 343    Before processing any blocks, the H's are initialized as follows: in
 344    hex,
 345
 346       H0 = 67452301
 347
 348       H1 = EFCDAB89
 349
 350       H2 = 98BADCFE
 351
 352       H3 = 10325476
 353
 354       H4 = C3D2E1F0.
 355
 356    Now M(1), M(2), ... , M(n) are processed.  To process M(i), we
 357    proceed as follows:
 358
 359       a. Divide M(i) into 16 words W(0), W(1), ... , W(15), where W(0)
 360          is the left-most word.
 361
 362       b. For t = 16 to 79 let
 363
 364          W(t) = S^1(W(t-3) XOR W(t-8) XOR W(t-14) XOR W(t-16)).
 365
 366       c. Let A = H0, B = H1, C = H2, D = H3, E = H4.
 367
 368       d. For t = 0 to 79 do
 369
 370          TEMP = S^5(A) + f(t;B,C,D) + E + W(t) + K(t);
 371
 372          E = D;  D = C;  C = S^30(B);  B = A; A = TEMP;
 373
 374       e. Let H0 = H0 + A, H1 = H1 + B, H2 = H2 + C, H3 = H3 + D, H4 = H4
 375          + E.
 376
 377    After processing M(n), the message digest is the 160-bit string
 378    represented by the 5 words
 379
 380          H0 H1 H2 H3 H4.
 381
 382 6.2 Method 2
 383
 384    The method above assumes that the sequence W(0), ... , W(79) is
 385    implemented as an array of eighty 32-bit words.  This is efficient
 386    from the standpoint of minimization of execution time, since the
 387    addresses of W(t-3), ...  ,W(t-16) in step (b) are easily computed.
 388    If space is at a premium, an alternative is to regard { W(t) } as a
 389
 390
 391
 392
 393
 394 Eastlake & Jones             Informational                      [Page 7]
 395 \f
 396 RFC 3174           US Secure Hash Algorithm 1 (SHA1)      September 2001
 397
 398
 399    circular queue, which may be implemented using an array of sixteen
 400    32-bit words W[0], ... W[15].  In this case, in hex let
 401
 402    MASK = 0000000F.  Then processing of M(i) is as follows:
 403
 404       a. Divide M(i) into 16 words W[0], ... , W[15], where W[0] is the
 405          left-most word.
 406
 407       b. Let A = H0, B = H1, C = H2, D = H3, E = H4.
 408
 409       c. For t = 0 to 79 do
 410
 411          s = t AND MASK;
 412
 413          if (t >= 16) W[s] = S^1(W[(s + 13) AND MASK] XOR W[(s + 8) AND
 414          MASK] XOR W[(s + 2) AND MASK] XOR W[s]);
 415
 416          TEMP = S^5(A) + f(t;B,C,D) + E + W[s] + K(t);
 417
 418          E = D; D = C; C = S^30(B); B = A; A = TEMP;
 419
 420       d. Let H0 = H0 + A, H1 = H1 + B, H2 = H2 + C, H3 = H3 + D, H4 = H4
 421          + E.
 422
 423 7. C Code
 424
 425    Below is a demonstration implementation of SHA-1 in C.  Section 7.1
 426    contains the header file, 7.2 the C code, and 7.3 a test driver.
 427
 428 7.1 .h file
 429
 430 /*
 431  *  sha1.h
 432  *
 433  *  Description:
 434  *      This is the header file for code which implements the Secure
 435  *      Hashing Algorithm 1 as defined in FIPS PUB 180-1 published
 436  *      April 17, 1995.
 437  *
 438  *      Many of the variable names in this code, especially the
 439  *      single character names, were used because those were the names
 440  *      used in the publication.
 441  *
 442  *      Please read the file sha1.c for more information.
 443  *
 444  */
 445
 446
 447
 448
 449
 450 Eastlake & Jones             Informational                      [Page 8]
 451 \f
 452 RFC 3174           US Secure Hash Algorithm 1 (SHA1)      September 2001
 453
 454
 455 #ifndef _SHA1_H_
 456 #define _SHA1_H_
 457
 458 #include <stdint.h>
 459 /*
 460  * If you do not have the ISO standard stdint.h header file, then you
 461  * must typdef the following:
 462  *    name              meaning
 463  *  uint32_t         unsigned 32 bit integer
 464  *  uint8_t          unsigned 8 bit integer (i.e., unsigned char)
 465  *  int_least16_t    integer of >= 16 bits
 466  *
 467  */
 468
 469 #ifndef _SHA_enum_
 470 #define _SHA_enum_
 471 enum
 472 {
 473     shaSuccess = 0,
 474     shaNull,            /* Null pointer parameter */
 475     shaInputTooLong,    /* input data too long */
 476     shaStateError       /* called Input after Result */
 477 };
 478 #endif
 479 #define SHA1HashSize 20
 480
 481 /*
 482  *  This structure will hold context information for the SHA-1
 483  *  hashing operation
 484  */
 485 typedef struct SHA1Context
 486 {
 487     uint32_t Intermediate_Hash[SHA1HashSize/4]; /* Message Digest  */
 488
 489     uint32_t Length_Low;            /* Message length in bits      */
 490     uint32_t Length_High;           /* Message length in bits      */
 491
 492                                /* Index into message block array   */
 493     int_least16_t Message_Block_Index;
 494     uint8_t Message_Block[64];      /* 512-bit message blocks      */
 495
 496     int Computed;               /* Is the digest computed?         */
 497     int Corrupted;             /* Is the message digest corrupted? */
 498 } SHA1Context;
 499
 500 /*
 501  *  Function Prototypes
 502  */
 503
 504
 505
 506 Eastlake & Jones             Informational                      [Page 9]
 507 \f
 508 RFC 3174           US Secure Hash Algorithm 1 (SHA1)      September 2001
 509
 510
 511 int SHA1Reset(  SHA1Context *);
 512 int SHA1Input(  SHA1Context *,
 513                 const uint8_t *,
 514                 unsigned int);
 515 int SHA1Result( SHA1Context *,
 516                 uint8_t Message_Digest[SHA1HashSize]);
 517
 518 #endif
 519
 520 7.2 .c file
 521
 522 /*
 523  *  sha1.c
 524  *
 525  *  Description:
 526  *      This file implements the Secure Hashing Algorithm 1 as
 527  *      defined in FIPS PUB 180-1 published April 17, 1995.
 528  *
 529  *      The SHA-1, produces a 160-bit message digest for a given
 530  *      data stream.  It should take about 2**n steps to find a
 531  *      message with the same digest as a given message and
 532  *      2**(n/2) to find any two messages with the same digest,
 533  *      when n is the digest size in bits.  Therefore, this
 534  *      algorithm can serve as a means of providing a
 535  *      "fingerprint" for a message.
 536  *
 537  *  Portability Issues:
 538  *      SHA-1 is defined in terms of 32-bit "words".  This code
 539  *      uses <stdint.h> (included via "sha1.h" to define 32 and 8
 540  *      bit unsigned integer types.  If your C compiler does not
 541  *      support 32 bit unsigned integers, this code is not
 542  *      appropriate.
 543  *
 544  *  Caveats:
 545  *      SHA-1 is designed to work with messages less than 2^64 bits
 546  *      long.  Although SHA-1 allows a message digest to be generated
 547  *      for messages of any number of bits less than 2^64, this
 548  *      implementation only works with messages with a length that is
 549  *      a multiple of the size of an 8-bit character.
 550  *
 551  */
 552
 553
 554
 555
 556
 557
 558
 559
 560
 561
 562 Eastlake & Jones             Informational                     [Page 10]
 563 \f
 564 RFC 3174           US Secure Hash Algorithm 1 (SHA1)      September 2001
 565
 566
 567 #include "sha1.h"
 568
 569 /*
 570  *  Define the SHA1 circular left shift macro
 571  */
 572 #define SHA1CircularShift(bits,word) \
 573                 (((word) << (bits)) | ((word) >> (32-(bits))))
 574
 575 /* Local Function Prototyptes */
 576 void SHA1PadMessage(SHA1Context *);
 577 void SHA1ProcessMessageBlock(SHA1Context *);
 578
 579 /*
 580  *  SHA1Reset
 581  *
 582  *  Description:
 583  *      This function will initialize the SHA1Context in preparation
 584  *      for computing a new SHA1 message digest.
 585  *
 586  *  Parameters:
 587  *      context: [in/out]
 588  *          The context to reset.
 589  *
 590  *  Returns:
 591  *      sha Error Code.
 592  *
 593  */
 594 int SHA1Reset(SHA1Context *context)
 595 {
 596     if (!context)
 597     {
 598         return shaNull;
 599     }
 600
 601     context->Length_Low             = 0;
 602     context->Length_High            = 0;
 603     context->Message_Block_Index    = 0;
 604
 605     context->Intermediate_Hash[0]   = 0x67452301;
 606     context->Intermediate_Hash[1]   = 0xEFCDAB89;
 607     context->Intermediate_Hash[2]   = 0x98BADCFE;
 608     context->Intermediate_Hash[3]   = 0x10325476;
 609     context->Intermediate_Hash[4]   = 0xC3D2E1F0;
 610
 611     context->Computed   = 0;
 612     context->Corrupted  = 0;
 613
 614
 615
 616
 617
 618 Eastlake & Jones             Informational                     [Page 11]
 619 \f
 620 RFC 3174           US Secure Hash Algorithm 1 (SHA1)      September 2001
 621
 622
 623     return shaSuccess;
 624 }
 625
 626 /*
 627  *  SHA1Result
 628  *
 629  *  Description:
 630  *      This function will return the 160-bit message digest into the
 631  *      Message_Digest array  provided by the caller.
 632  *      NOTE: The first octet of hash is stored in the 0th element,
 633  *            the last octet of hash in the 19th element.
 634  *
 635  *  Parameters:
 636  *      context: [in/out]
 637  *          The context to use to calculate the SHA-1 hash.
 638  *      Message_Digest: [out]
 639  *          Where the digest is returned.
 640  *
 641  *  Returns:
 642  *      sha Error Code.
 643  *
 644  */
 645 int SHA1Result( SHA1Context *context,
 646                 uint8_t Message_Digest[SHA1HashSize])
 647 {
 648     int i;
 649
 650     if (!context || !Message_Digest)
 651     {
 652         return shaNull;
 653     }
 654
 655     if (context->Corrupted)
 656     {
 657         return context->Corrupted;
 658     }
 659
 660     if (!context->Computed)
 661     {
 662         SHA1PadMessage(context);
 663         for(i=0; i<64; ++i)
 664         {
 665             /* message may be sensitive, clear it out */
 666             context->Message_Block[i] = 0;
 667         }
 668         context->Length_Low = 0;    /* and clear length */
 669         context->Length_High = 0;
 670         context->Computed = 1;
 671
 672
 673
 674 Eastlake & Jones             Informational                     [Page 12]
 675 \f
 676 RFC 3174           US Secure Hash Algorithm 1 (SHA1)      September 2001
 677
 678
 679     }
 680
 681     for(i = 0; i < SHA1HashSize; ++i)
 682     {
 683         Message_Digest[i] = context->Intermediate_Hash[i>>2]
 684                             >> 8 * ( 3 - ( i & 0x03 ) );
 685     }
 686
 687     return shaSuccess;
 688 }
 689
 690 /*
 691  *  SHA1Input
 692  *
 693  *  Description:
 694  *      This function accepts an array of octets as the next portion
 695  *      of the message.
 696  *
 697  *  Parameters:
 698  *      context: [in/out]
 699  *          The SHA context to update
 700  *      message_array: [in]
 701  *          An array of characters representing the next portion of
 702  *          the message.
 703  *      length: [in]
 704  *          The length of the message in message_array
 705  *
 706  *  Returns:
 707  *      sha Error Code.
 708  *
 709  */
 710 int SHA1Input(    SHA1Context    *context,
 711                   const uint8_t  *message_array,
 712                   unsigned       length)
 713 {
 714     if (!length)
 715     {
 716         return shaSuccess;
 717     }
 718
 719     if (!context || !message_array)
 720     {
 721         return shaNull;
 722     }
 723
 724     if (context->Computed)
 725     {
 726         context->Corrupted = shaStateError;
 727
 728
 729
 730 Eastlake & Jones             Informational                     [Page 13]
 731 \f
 732 RFC 3174           US Secure Hash Algorithm 1 (SHA1)      September 2001
 733
 734
 735         return shaStateError;
 736     }
 737
 738     if (context->Corrupted)
 739     {
 740          return context->Corrupted;
 741     }
 742     while(length-- && !context->Corrupted)
 743     {
 744     context->Message_Block[context->Message_Block_Index++] =
 745                     (*message_array & 0xFF);
 746
 747     context->Length_Low += 8;
 748     if (context->Length_Low == 0)
 749     {
 750         context->Length_High++;
 751         if (context->Length_High == 0)
 752         {
 753             /* Message is too long */
 754             context->Corrupted = 1;
 755         }
 756     }
 757
 758     if (context->Message_Block_Index == 64)
 759     {
 760         SHA1ProcessMessageBlock(context);
 761     }
 762
 763     message_array++;
 764     }
 765
 766     return shaSuccess;
 767 }
 768
 769 /*
 770  *  SHA1ProcessMessageBlock
 771  *
 772  *  Description:
 773  *      This function will process the next 512 bits of the message
 774  *      stored in the Message_Block array.
 775  *
 776  *  Parameters:
 777  *      None.
 778  *
 779  *  Returns:
 780  *      Nothing.
 781  *
 782  *  Comments:
 783
 784
 785
 786 Eastlake & Jones             Informational                     [Page 14]
 787 \f
 788 RFC 3174           US Secure Hash Algorithm 1 (SHA1)      September 2001
 789
 790
 791  *      Many of the variable names in this code, especially the
 792  *      single character names, were used because those were the
 793  *      names used in the publication.
 794  *
 795  *
 796  */
 797 void SHA1ProcessMessageBlock(SHA1Context *context)
 798 {
 799     const uint32_t K[] =    {       /* Constants defined in SHA-1   */
 800                             0x5A827999,
 801                             0x6ED9EBA1,
 802                             0x8F1BBCDC,
 803                             0xCA62C1D6
 804                             };
 805     int           t;                 /* Loop counter                */
 806     uint32_t      temp;              /* Temporary word value        */
 807     uint32_t      W[80];             /* Word sequence               */
 808     uint32_t      A, B, C, D, E;     /* Word buffers                */
 809
 810     /*
 811      *  Initialize the first 16 words in the array W
 812      */
 813     for(t = 0; t < 16; t++)
 814     {
 815         W[t] = context->Message_Block[t * 4] << 24;
 816         W[t] |= context->Message_Block[t * 4 + 1] << 16;
 817         W[t] |= context->Message_Block[t * 4 + 2] << 8;
 818         W[t] |= context->Message_Block[t * 4 + 3];
 819     }
 820
 821     for(t = 16; t < 80; t++)
 822     {
 823        W[t] = SHA1CircularShift(1,W[t-3] ^ W[t-8] ^ W[t-14] ^ W[t-16]);
 824     }
 825
 826     A = context->Intermediate_Hash[0];
 827     B = context->Intermediate_Hash[1];
 828     C = context->Intermediate_Hash[2];
 829     D = context->Intermediate_Hash[3];
 830     E = context->Intermediate_Hash[4];
 831
 832     for(t = 0; t < 20; t++)
 833     {
 834         temp =  SHA1CircularShift(5,A) +
 835                 ((B & C) | ((~B) & D)) + E + W[t] + K[0];
 836         E = D;
 837         D = C;
 838         C = SHA1CircularShift(30,B);
 839
 840
 841
 842 Eastlake & Jones             Informational                     [Page 15]
 843 \f
 844 RFC 3174           US Secure Hash Algorithm 1 (SHA1)      September 2001
 845
 846
 847         B = A;
 848         A = temp;
 849     }
 850
 851     for(t = 20; t < 40; t++)
 852     {
 853         temp = SHA1CircularShift(5,A) + (B ^ C ^ D) + E + W[t] + K[1];
 854         E = D;
 855         D = C;
 856         C = SHA1CircularShift(30,B);
 857         B = A;
 858         A = temp;
 859     }
 860
 861     for(t = 40; t < 60; t++)
 862     {
 863         temp = SHA1CircularShift(5,A) +
 864                ((B & C) | (B & D) | (C & D)) + E + W[t] + K[2];
 865         E = D;
 866         D = C;
 867         C = SHA1CircularShift(30,B);
 868         B = A;
 869         A = temp;
 870     }
 871
 872     for(t = 60; t < 80; t++)
 873     {
 874         temp = SHA1CircularShift(5,A) + (B ^ C ^ D) + E + W[t] + K[3];
 875         E = D;
 876         D = C;
 877         C = SHA1CircularShift(30,B);
 878         B = A;
 879         A = temp;
 880     }
 881
 882     context->Intermediate_Hash[0] += A;
 883     context->Intermediate_Hash[1] += B;
 884     context->Intermediate_Hash[2] += C;
 885     context->Intermediate_Hash[3] += D;
 886     context->Intermediate_Hash[4] += E;
 887
 888     context->Message_Block_Index = 0;
 889 }
 890
 891
 892 /*
 893  *  SHA1PadMessage
 894  *
 895
 896
 897
 898 Eastlake & Jones             Informational                     [Page 16]
 899 \f
 900 RFC 3174           US Secure Hash Algorithm 1 (SHA1)      September 2001
 901
 902
 903  *  Description:
 904  *      According to the standard, the message must be padded to an even
 905  *      512 bits.  The first padding bit must be a '1'.  The last 64
 906  *      bits represent the length of the original message.  All bits in
 907  *      between should be 0.  This function will pad the message
 908  *      according to those rules by filling the Message_Block array
 909  *      accordingly.  It will also call the ProcessMessageBlock function
 910  *      provided appropriately.  When it returns, it can be assumed that
 911  *      the message digest has been computed.
 912  *
 913  *  Parameters:
 914  *      context: [in/out]
 915  *          The context to pad
 916  *      ProcessMessageBlock: [in]
 917  *          The appropriate SHA*ProcessMessageBlock function
 918  *  Returns:
 919  *      Nothing.
 920  *
 921  */
 922
 923 void SHA1PadMessage(SHA1Context *context)
 924 {
 925     /*
 926      *  Check to see if the current message block is too small to hold
 927      *  the initial padding bits and length.  If so, we will pad the
 928      *  block, process it, and then continue padding into a second
 929      *  block.
 930      */
 931     if (context->Message_Block_Index > 55)
 932     {
 933         context->Message_Block[context->Message_Block_Index++] = 0x80;
 934         while(context->Message_Block_Index < 64)
 935         {
 936             context->Message_Block[context->Message_Block_Index++] = 0;
 937         }
 938
 939         SHA1ProcessMessageBlock(context);
 940
 941         while(context->Message_Block_Index < 56)
 942         {
 943             context->Message_Block[context->Message_Block_Index++] = 0;
 944         }
 945     }
 946     else
 947     {
 948         context->Message_Block[context->Message_Block_Index++] = 0x80;
 949         while(context->Message_Block_Index < 56)
 950         {
 951
 952
 953
 954 Eastlake & Jones             Informational                     [Page 17]
 955 \f
 956 RFC 3174           US Secure Hash Algorithm 1 (SHA1)      September 2001
 957
 958
 959             context->Message_Block[context->Message_Block_Index++] = 0;
 960         }
 961     }
 962
 963     /*
 964      *  Store the message length as the last 8 octets
 965      */
 966     context->Message_Block[56] = context->Length_High >> 24;
 967     context->Message_Block[57] = context->Length_High >> 16;
 968     context->Message_Block[58] = context->Length_High >> 8;
 969     context->Message_Block[59] = context->Length_High;
 970     context->Message_Block[60] = context->Length_Low >> 24;
 971     context->Message_Block[61] = context->Length_Low >> 16;
 972     context->Message_Block[62] = context->Length_Low >> 8;
 973     context->Message_Block[63] = context->Length_Low;
 974
 975     SHA1ProcessMessageBlock(context);
 976 }
 977
 978 7.3 Test Driver
 979
 980    The following code is a main program test driver to exercise the code
 981    in sha1.c.
 982
 983 /*
 984  *  sha1test.c
 985  *
 986  *  Description:
 987  *      This file will exercise the SHA-1 code performing the three
 988  *      tests documented in FIPS PUB 180-1 plus one which calls
 989  *      SHA1Input with an exact multiple of 512 bits, plus a few
 990  *      error test checks.
 991  *
 992  *  Portability Issues:
 993  *      None.
 994  *
 995  */
 996
 997 #include <stdint.h>
 998 #include <stdio.h>
 999 #include <string.h>
1000 #include "sha1.h"
1001
1002 /*
1003  *  Define patterns for testing
1004  */
1005 #define TEST1   "abc"
1006 #define TEST2a  "abcdbcdecdefdefgefghfghighijhi"
1007
1008
1009
1010 Eastlake & Jones             Informational                     [Page 18]
1011 \f
1012 RFC 3174           US Secure Hash Algorithm 1 (SHA1)      September 2001
1013
1014
1015 #define TEST2b  "jkijkljklmklmnlmnomnopnopq"
1016 #define TEST2   TEST2a TEST2b
1017 #define TEST3   "a"
1018 #define TEST4a  "01234567012345670123456701234567"
1019 #define TEST4b  "01234567012345670123456701234567"
1020     /* an exact multiple of 512 bits */
1021 #define TEST4   TEST4a TEST4b
1022 char *testarray[4] =
1023 {
1024     TEST1,
1025     TEST2,
1026     TEST3,
1027     TEST4
1028 };
1029 long int repeatcount[4] = { 1, 1, 1000000, 10 };
1030 char *resultarray[4] =
1031 {
1032     "A9 99 3E 36 47 06 81 6A BA 3E 25 71 78 50 C2 6C 9C D0 D8 9D",
1033     "84 98 3E 44 1C 3B D2 6E BA AE 4A A1 F9 51 29 E5 E5 46 70 F1",
1034     "34 AA 97 3C D4 C4 DA A4 F6 1E EB 2B DB AD 27 31 65 34 01 6F",
1035     "DE A3 56 A2 CD DD 90 C7 A7 EC ED C5 EB B5 63 93 4F 46 04 52"
1036 };
1037
1038 int main()
1039 {
1040     SHA1Context sha;
1041     int i, j, err;
1042     uint8_t Message_Digest[20];
1043
1044     /*
1045      *  Perform SHA-1 tests
1046      */
1047     for(j = 0; j < 4; ++j)
1048     {
1049         printf( "\nTest %d: %d, '%s'\n",
1050                 j+1,
1051                 repeatcount[j],
1052                 testarray[j]);
1053
1054         err = SHA1Reset(&sha);
1055         if (err)
1056         {
1057             fprintf(stderr, "SHA1Reset Error %d.\n", err );
1058             break;    /* out of for j loop */
1059         }
1060
1061         for(i = 0; i < repeatcount[j]; ++i)
1062         {
1063
1064
1065
1066 Eastlake & Jones             Informational                     [Page 19]
1067 \f
1068 RFC 3174           US Secure Hash Algorithm 1 (SHA1)      September 2001
1069
1070
1071             err = SHA1Input(&sha,
1072                   (const unsigned char *) testarray[j],
1073                   strlen(testarray[j]));
1074             if (err)
1075             {
1076                 fprintf(stderr, "SHA1Input Error %d.\n", err );
1077                 break;    /* out of for i loop */
1078             }
1079         }
1080
1081         err = SHA1Result(&sha, Message_Digest);
1082         if (err)
1083         {
1084             fprintf(stderr,
1085             "SHA1Result Error %d, could not compute message digest.\n",
1086             err );
1087         }
1088         else
1089         {
1090             printf("\t");
1091             for(i = 0; i < 20 ; ++i)
1092             {
1093                 printf("%02X ", Message_Digest[i]);
1094             }
1095             printf("\n");
1096         }
1097         printf("Should match:\n");
1098         printf("\t%s\n", resultarray[j]);
1099     }
1100
1101     /* Test some error returns */
1102     err = SHA1Input(&sha,(const unsigned char *) testarray[1], 1);
1103     printf ("\nError %d. Should be %d.\n", err, shaStateError );
1104     err = SHA1Reset(0);
1105     printf ("\nError %d. Should be %d.\n", err, shaNull );
1106     return 0;
1107 }
1108
1109 8. Security Considerations
1110
1111    This document is intended to provide convenient open source access by
1112    the Internet community to the United States of America Federal
1113    Information Processing Standard Secure Hash Function SHA-1 [FIPS
1114    180-1].  No independent assertion of the security of this hash
1115    function by the authors for any particular use is intended.
1116
1117
1118
1119
1120
1121
1122 Eastlake & Jones             Informational                     [Page 20]
1123 \f
1124 RFC 3174           US Secure Hash Algorithm 1 (SHA1)      September 2001
1125
1126
1127 References
1128
1129    [FIPS 180-1] "Secure Hash Standard", United States of American,
1130                 National Institute of Science and Technology, Federal
1131                 Information Processing Standard (FIPS) 180-1, April
1132                 1993.
1133
1134    [MD4]        "The MD4 Message Digest Algorithm," Advances in
1135                 Cryptology - CRYPTO '90 Proceedings, Springer-Verlag,
1136                 1991, pp. 303-311.
1137
1138    [RFC 1320]   Rivest, R., "The MD4 Message-Digest Algorithm", RFC
1139                 1320, April 1992.
1140
1141    [RFC 1321]   Rivest, R., "The MD5 Message-Digest Algorithm", RFC
1142                 1321, April 1992.
1143
1144    [RFC 1750]   Eastlake, D., Crocker, S. and J. Schiller, "Randomness
1145                 Requirements for Security", RFC 1750, December 1994.
1146
1147 Authors' Addresses
1148
1149    Donald E. Eastlake, 3rd
1150    Motorola
1151    155 Beaver Street
1152    Milford, MA 01757 USA
1153
1154    Phone:   +1 508-634-2066 (h)
1155             +1 508-261-5434 (w)
1156    Fax:     +1 508-261-4777
1157    EMail:   Donald.Eastlake@motorola.com
1158
1159
1160    Paul E. Jones
1161    Cisco Systems, Inc.
1162    7025 Kit Creek Road
1163    Research Triangle Park, NC 27709 USA
1164
1165    Phone:   +1 919 392 6948
1166    EMail:   paulej@packetizer.com
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178 Eastlake & Jones             Informational                     [Page 21]
1179 \f
1180 RFC 3174           US Secure Hash Algorithm 1 (SHA1)      September 2001
1181
1182
1183 Full Copyright Statement
1184
1185    Copyright (C) The Internet Society (2001).  All Rights Reserved.
1186
1187    This document and translations of it may be copied and furnished to
1188    others, and derivative works that comment on or otherwise explain it
1189    or assist in its implementation may be prepared, copied, published
1190    and distributed, in whole or in part, without restriction of any
1191    kind, provided that the above copyright notice and this paragraph are
1192    included on all such copies and derivative works.  However, this
1193    document itself may not be modified in any way, such as by removing
1194    the copyright notice or references to the Internet Society or other
1195    Internet organizations, except as needed for the purpose of
1196    developing Internet standards in which case the procedures for
1197    copyrights defined in the Internet Standards process must be
1198    followed, or as required to translate it into languages other than
1199    English.
1200
1201    The limited permissions granted above are perpetual and will not be
1202    revoked by the Internet Society or its successors or assigns.
1203
1204    This document and the information contained herein is provided on an
1205    "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
1206    TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING
1207    BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION
1208    HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF
1209    MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
1210
1211 Acknowledgement
1212
1213    Funding for the RFC Editor function is currently provided by the
1214    Internet Society.
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234 Eastlake & Jones             Informational                     [Page 22]
1235 \f