sha1-compress.c

   1 /* sha1-compress.c
   2  *
   3  * The compression function of the sha1 hash function.
   4  */
   5
   6 /* nettle, low-level cryptographics library
   7  *
   8  * Copyright (C) 2001, 2004 Peter Gutmann, Andrew Kuchling, Niels Möller
   9  *
  10  * The nettle library is free software; you can redistribute it and/or modify
  11  * it under the terms of the GNU Lesser General Public License as published by
  12  * the Free Software Foundation; either version 2.1 of the License, or (at your
  13  * option) any later version.
  14  *
  15  * The nettle library is distributed in the hope that it will be useful, but
  16  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  17  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  18  * License for more details.
  19  *
  20  * You should have received a copy of the GNU Lesser General Public License
  21  * along with the nettle library; see the file COPYING.LIB.  If not, write to
  22  * the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  23  * MA 02111-1307, USA.
  24  */
  25
  26 /* Here's the first paragraph of Peter Gutmann's posting,
  27  * <30ajo5$oe8@ccu2.auckland.ac.nz>:
  28  *
  29  * The following is my SHA (FIPS 180) code updated to allow use of the "fixed"
  30  * SHA, thanks to Jim Gillogly and an anonymous contributor for the information on
  31  * what's changed in the new version.  The fix is a simple change which involves
  32  * adding a single rotate in the initial expansion function.  It is unknown
  33  * whether this is an optimal solution to the problem which was discovered in the
  34  * SHA or whether it's simply a bandaid which fixes the problem with a minimum of
  35  * effort (for example the reengineering of a great many Capstone chips).
  36  */
  37
  38 #if HAVE_CONFIG_H
  39 # include "config.h"
  40 #endif
  41
  42 #ifndef SHA1_DEBUG
  43 # define SHA1_DEBUG 0
  44 #endif
  45
  46 #if SHA1_DEBUG
  47 # include <stdio.h>
  48 # define DEBUG(i) \
  49   fprintf(stderr, "%2d: %8x %8x %8x %8x %8x\n", i, A, B, C, D ,E)
  50 #else
  51 # define DEBUG(i)
  52 #endif
  53
  54 #include <assert.h>
  55 #include <stdlib.h>
  56 #include <string.h>
  57
  58 #include "sha.h"
  59
  60 #include "macros.h"
  61
  62 /* A block, treated as a sequence of 32-bit words. */
  63 #define SHA1_DATA_LENGTH 16
  64
  65 /* The SHA f()-functions.  The f1 and f3 functions can be optimized to
  66    save one boolean operation each - thanks to Rich Schroeppel,
  67    rcs@cs.arizona.edu for discovering this */
  68
  69 /* FIXME: Can save a temporary in f3 by using ( (x & y) + (z & (x ^
  70    y)) ), and then, in the round, compute one of the terms and add it
  71    into the destination word before computing the second term. Credits
  72    to George Spelvin for pointing this out. Unfortunately, gcc
  73    doesn't seem to be smart enough to take advantage of this. */
  74
  75 /* #define f1(x,y,z) ( ( x & y ) | ( ~x & z ) )            Rounds  0-19 */
  76 #define f1(x,y,z)   ( z ^ ( x & ( y ^ z ) ) )           /* Rounds  0-19 */
  77 #define f2(x,y,z)   ( x ^ y ^ z )                       /* Rounds 20-39 */
  78 /* #define f3(x,y,z) ( ( x & y ) | ( x & z ) | ( y & z ) ) Rounds 40-59 */
  79 #define f3(x,y,z)   ( ( x & y ) | ( z & ( x | y ) ) )   /* Rounds 40-59 */
  80 #define f4 f2
  81
  82 /* The SHA Mysterious Constants */
  83
  84 #define K1  0x5A827999L                                 /* Rounds  0-19 */
  85 #define K2  0x6ED9EBA1L                                 /* Rounds 20-39 */
  86 #define K3  0x8F1BBCDCL                                 /* Rounds 40-59 */
  87 #define K4  0xCA62C1D6L                                 /* Rounds 60-79 */
  88
  89 /* 32-bit rotate left - kludged with shifts */
  90
  91 #define ROTL(n,X)  ( ( (X) << (n) ) | ( (X) >> ( 32 - (n) ) ) )
  92
  93 /* The initial expanding function.  The hash function is defined over an
  94    80-word expanded input array W, where the first 16 are copies of the input
  95    data, and the remaining 64 are defined by
  96
  97         W[ i ] = W[ i - 16 ] ^ W[ i - 14 ] ^ W[ i - 8 ] ^ W[ i - 3 ]
  98
  99    This implementation generates these values on the fly in a circular
 100    buffer - thanks to Colin Plumb, colin@nyx10.cs.du.edu for this
 101    optimization.
 102
 103    The updated SHA changes the expanding function by adding a rotate of 1
 104    bit.  Thanks to Jim Gillogly, jim@rand.org, and an anonymous contributor
 105    for this information */
 106
 107 #define expand(W,i) ( W[ i & 15 ] = \
 108                       ROTL( 1, ( W[ i & 15 ] ^ W[ (i - 14) & 15 ] ^ \
 109                                  W[ (i - 8) & 15 ] ^ W[ (i - 3) & 15 ] ) ) )
 110
 111
 112 /* The prototype SHA sub-round.  The fundamental sub-round is:
 113
 114         a' = e + ROTL( 5, a ) + f( b, c, d ) + k + data;
 115         b' = a;
 116         c' = ROTL( 30, b );
 117         d' = c;
 118         e' = d;
 119
 120    but this is implemented by unrolling the loop 5 times and renaming the
 121    variables ( e, a, b, c, d ) = ( a', b', c', d', e' ) each iteration.
 122    This code is then replicated 20 times for each of the 4 functions, using
 123    the next 20 values from the W[] array each time */
 124
 125 #define subRound(a, b, c, d, e, f, k, data) \
 126     ( e += ROTL( 5, a ) + f( b, c, d ) + k + data, b = ROTL( 30, b ) )
 127
 128 /* Perform the SHA transformation.  Note that this code, like MD5, seems to
 129    break some optimizing compilers due to the complexity of the expressions
 130    and the size of the basic block.  It may be necessary to split it into
 131    sections, e.g. based on the four subrounds. */
 132
 133 void
 134 _nettle_sha1_compress(uint32_t *state, const uint8_t *input)
 135 {
 136   uint32_t data[SHA1_DATA_LENGTH];
 137   uint32_t A, B, C, D, E;     /* Local vars */
 138   int i;
 139
 140   for (i = 0; i < SHA1_DATA_LENGTH; i++, input+= 4)
 141     {
 142       data[i] = READ_UINT32(input);
 143     }
 144
 145   /* Set up first buffer and local data buffer */
 146   A = state[0];
 147   B = state[1];
 148   C = state[2];
 149   D = state[3];
 150   E = state[4];
 151
 152   DEBUG(-1);
 153   /* Heavy mangling, in 4 sub-rounds of 20 interations each. */
 154   subRound( A, B, C, D, E, f1, K1, data[ 0] ); DEBUG(0);
 155   subRound( E, A, B, C, D, f1, K1, data[ 1] ); DEBUG(1);
 156   subRound( D, E, A, B, C, f1, K1, data[ 2] );
 157   subRound( C, D, E, A, B, f1, K1, data[ 3] );
 158   subRound( B, C, D, E, A, f1, K1, data[ 4] );
 159   subRound( A, B, C, D, E, f1, K1, data[ 5] );
 160   subRound( E, A, B, C, D, f1, K1, data[ 6] );
 161   subRound( D, E, A, B, C, f1, K1, data[ 7] );
 162   subRound( C, D, E, A, B, f1, K1, data[ 8] );
 163   subRound( B, C, D, E, A, f1, K1, data[ 9] );
 164   subRound( A, B, C, D, E, f1, K1, data[10] );
 165   subRound( E, A, B, C, D, f1, K1, data[11] );
 166   subRound( D, E, A, B, C, f1, K1, data[12] );
 167   subRound( C, D, E, A, B, f1, K1, data[13] );
 168   subRound( B, C, D, E, A, f1, K1, data[14] );
 169   subRound( A, B, C, D, E, f1, K1, data[15] ); DEBUG(15);
 170   subRound( E, A, B, C, D, f1, K1, expand( data, 16 ) ); DEBUG(16);
 171   subRound( D, E, A, B, C, f1, K1, expand( data, 17 ) ); DEBUG(17);
 172   subRound( C, D, E, A, B, f1, K1, expand( data, 18 ) ); DEBUG(18);
 173   subRound( B, C, D, E, A, f1, K1, expand( data, 19 ) ); DEBUG(19);
 174
 175   subRound( A, B, C, D, E, f2, K2, expand( data, 20 ) ); DEBUG(20);
 176   subRound( E, A, B, C, D, f2, K2, expand( data, 21 ) ); DEBUG(21);
 177   subRound( D, E, A, B, C, f2, K2, expand( data, 22 ) );
 178   subRound( C, D, E, A, B, f2, K2, expand( data, 23 ) );
 179   subRound( B, C, D, E, A, f2, K2, expand( data, 24 ) );
 180   subRound( A, B, C, D, E, f2, K2, expand( data, 25 ) );
 181   subRound( E, A, B, C, D, f2, K2, expand( data, 26 ) );
 182   subRound( D, E, A, B, C, f2, K2, expand( data, 27 ) );
 183   subRound( C, D, E, A, B, f2, K2, expand( data, 28 ) );
 184   subRound( B, C, D, E, A, f2, K2, expand( data, 29 ) );
 185   subRound( A, B, C, D, E, f2, K2, expand( data, 30 ) );
 186   subRound( E, A, B, C, D, f2, K2, expand( data, 31 ) );
 187   subRound( D, E, A, B, C, f2, K2, expand( data, 32 ) );
 188   subRound( C, D, E, A, B, f2, K2, expand( data, 33 ) );
 189   subRound( B, C, D, E, A, f2, K2, expand( data, 34 ) );
 190   subRound( A, B, C, D, E, f2, K2, expand( data, 35 ) );
 191   subRound( E, A, B, C, D, f2, K2, expand( data, 36 ) );
 192   subRound( D, E, A, B, C, f2, K2, expand( data, 37 ) );
 193   subRound( C, D, E, A, B, f2, K2, expand( data, 38 ) ); DEBUG(38);
 194   subRound( B, C, D, E, A, f2, K2, expand( data, 39 ) ); DEBUG(39);
 195
 196   subRound( A, B, C, D, E, f3, K3, expand( data, 40 ) ); DEBUG(40);
 197   subRound( E, A, B, C, D, f3, K3, expand( data, 41 ) ); DEBUG(41);
 198   subRound( D, E, A, B, C, f3, K3, expand( data, 42 ) );
 199   subRound( C, D, E, A, B, f3, K3, expand( data, 43 ) );
 200   subRound( B, C, D, E, A, f3, K3, expand( data, 44 ) );
 201   subRound( A, B, C, D, E, f3, K3, expand( data, 45 ) );
 202   subRound( E, A, B, C, D, f3, K3, expand( data, 46 ) );
 203   subRound( D, E, A, B, C, f3, K3, expand( data, 47 ) );
 204   subRound( C, D, E, A, B, f3, K3, expand( data, 48 ) );
 205   subRound( B, C, D, E, A, f3, K3, expand( data, 49 ) );
 206   subRound( A, B, C, D, E, f3, K3, expand( data, 50 ) );
 207   subRound( E, A, B, C, D, f3, K3, expand( data, 51 ) );
 208   subRound( D, E, A, B, C, f3, K3, expand( data, 52 ) );
 209   subRound( C, D, E, A, B, f3, K3, expand( data, 53 ) );
 210   subRound( B, C, D, E, A, f3, K3, expand( data, 54 ) );
 211   subRound( A, B, C, D, E, f3, K3, expand( data, 55 ) );
 212   subRound( E, A, B, C, D, f3, K3, expand( data, 56 ) );
 213   subRound( D, E, A, B, C, f3, K3, expand( data, 57 ) );
 214   subRound( C, D, E, A, B, f3, K3, expand( data, 58 ) ); DEBUG(58);
 215   subRound( B, C, D, E, A, f3, K3, expand( data, 59 ) ); DEBUG(59);
 216
 217   subRound( A, B, C, D, E, f4, K4, expand( data, 60 ) ); DEBUG(60);
 218   subRound( E, A, B, C, D, f4, K4, expand( data, 61 ) ); DEBUG(61);
 219   subRound( D, E, A, B, C, f4, K4, expand( data, 62 ) );
 220   subRound( C, D, E, A, B, f4, K4, expand( data, 63 ) );
 221   subRound( B, C, D, E, A, f4, K4, expand( data, 64 ) );
 222   subRound( A, B, C, D, E, f4, K4, expand( data, 65 ) );
 223   subRound( E, A, B, C, D, f4, K4, expand( data, 66 ) );
 224   subRound( D, E, A, B, C, f4, K4, expand( data, 67 ) );
 225   subRound( C, D, E, A, B, f4, K4, expand( data, 68 ) );
 226   subRound( B, C, D, E, A, f4, K4, expand( data, 69 ) );
 227   subRound( A, B, C, D, E, f4, K4, expand( data, 70 ) );
 228   subRound( E, A, B, C, D, f4, K4, expand( data, 71 ) );
 229   subRound( D, E, A, B, C, f4, K4, expand( data, 72 ) );
 230   subRound( C, D, E, A, B, f4, K4, expand( data, 73 ) );
 231   subRound( B, C, D, E, A, f4, K4, expand( data, 74 ) );
 232   subRound( A, B, C, D, E, f4, K4, expand( data, 75 ) );
 233   subRound( E, A, B, C, D, f4, K4, expand( data, 76 ) );
 234   subRound( D, E, A, B, C, f4, K4, expand( data, 77 ) );
 235   subRound( C, D, E, A, B, f4, K4, expand( data, 78 ) ); DEBUG(78);
 236   subRound( B, C, D, E, A, f4, K4, expand( data, 79 ) ); DEBUG(79);
 237
 238   /* Build message digest */
 239   state[0] += A;
 240   state[1] += B;
 241   state[2] += C;
 242   state[3] += D;
 243   state[4] += E;
 244
 245 #if SHA1_DEBUG
 246   fprintf(stderr, "99: %8x %8x %8x %8x %8x\n",
 247           state[0], state[1], state[2], state[3], state[4]);
 248 #endif
 249 }