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., 51 Franklin Street, Fifth Floor, Boston,
  23  * MA 02111-1301, 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 "sha1.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 /* The initial expanding function.  The hash function is defined over an
  90    80-word expanded input array W, where the first 16 are copies of the input
  91    data, and the remaining 64 are defined by
  92
  93         W[ i ] = W[ i - 16 ] ^ W[ i - 14 ] ^ W[ i - 8 ] ^ W[ i - 3 ]
  94
  95    This implementation generates these values on the fly in a circular
  96    buffer - thanks to Colin Plumb, colin@nyx10.cs.du.edu for this
  97    optimization.
  98
  99    The updated SHA changes the expanding function by adding a rotate of 1
 100    bit.  Thanks to Jim Gillogly, jim@rand.org, and an anonymous contributor
 101    for this information */
 102
 103 #define expand(W,i) ( W[ i & 15 ] = \
 104                       ROTL32( 1, ( W[ i & 15 ] ^ W[ (i - 14) & 15 ] ^ \
 105                                    W[ (i - 8) & 15 ] ^ W[ (i - 3) & 15 ] ) ) )
 106
 107
 108 /* The prototype SHA sub-round.  The fundamental sub-round is:
 109
 110         a' = e + ROTL32( 5, a ) + f( b, c, d ) + k + data;
 111         b' = a;
 112         c' = ROTL32( 30, b );
 113         d' = c;
 114         e' = d;
 115
 116    but this is implemented by unrolling the loop 5 times and renaming the
 117    variables ( e, a, b, c, d ) = ( a', b', c', d', e' ) each iteration.
 118    This code is then replicated 20 times for each of the 4 functions, using
 119    the next 20 values from the W[] array each time */
 120
 121 #define subRound(a, b, c, d, e, f, k, data) \
 122     ( e += ROTL32( 5, a ) + f( b, c, d ) + k + data, b = ROTL32( 30, b ) )
 123
 124 /* Perform the SHA transformation.  Note that this code, like MD5, seems to
 125    break some optimizing compilers due to the complexity of the expressions
 126    and the size of the basic block.  It may be necessary to split it into
 127    sections, e.g. based on the four subrounds. */
 128
 129 void
 130 _nettle_sha1_compress(uint32_t *state, const uint8_t *input)
 131 {
 132   uint32_t data[SHA1_DATA_LENGTH];
 133   uint32_t A, B, C, D, E;     /* Local vars */
 134   int i;
 135
 136   for (i = 0; i < SHA1_DATA_LENGTH; i++, input+= 4)
 137     {
 138       data[i] = READ_UINT32(input);
 139     }
 140
 141   /* Set up first buffer and local data buffer */
 142   A = state[0];
 143   B = state[1];
 144   C = state[2];
 145   D = state[3];
 146   E = state[4];
 147
 148   DEBUG(-1);
 149   /* Heavy mangling, in 4 sub-rounds of 20 interations each. */
 150   subRound( A, B, C, D, E, f1, K1, data[ 0] ); DEBUG(0);
 151   subRound( E, A, B, C, D, f1, K1, data[ 1] ); DEBUG(1);
 152   subRound( D, E, A, B, C, f1, K1, data[ 2] );
 153   subRound( C, D, E, A, B, f1, K1, data[ 3] );
 154   subRound( B, C, D, E, A, f1, K1, data[ 4] );
 155   subRound( A, B, C, D, E, f1, K1, data[ 5] );
 156   subRound( E, A, B, C, D, f1, K1, data[ 6] );
 157   subRound( D, E, A, B, C, f1, K1, data[ 7] );
 158   subRound( C, D, E, A, B, f1, K1, data[ 8] );
 159   subRound( B, C, D, E, A, f1, K1, data[ 9] );
 160   subRound( A, B, C, D, E, f1, K1, data[10] );
 161   subRound( E, A, B, C, D, f1, K1, data[11] );
 162   subRound( D, E, A, B, C, f1, K1, data[12] );
 163   subRound( C, D, E, A, B, f1, K1, data[13] );
 164   subRound( B, C, D, E, A, f1, K1, data[14] );
 165   subRound( A, B, C, D, E, f1, K1, data[15] ); DEBUG(15);
 166   subRound( E, A, B, C, D, f1, K1, expand( data, 16 ) ); DEBUG(16);
 167   subRound( D, E, A, B, C, f1, K1, expand( data, 17 ) ); DEBUG(17);
 168   subRound( C, D, E, A, B, f1, K1, expand( data, 18 ) ); DEBUG(18);
 169   subRound( B, C, D, E, A, f1, K1, expand( data, 19 ) ); DEBUG(19);
 170
 171   subRound( A, B, C, D, E, f2, K2, expand( data, 20 ) ); DEBUG(20);
 172   subRound( E, A, B, C, D, f2, K2, expand( data, 21 ) ); DEBUG(21);
 173   subRound( D, E, A, B, C, f2, K2, expand( data, 22 ) );
 174   subRound( C, D, E, A, B, f2, K2, expand( data, 23 ) );
 175   subRound( B, C, D, E, A, f2, K2, expand( data, 24 ) );
 176   subRound( A, B, C, D, E, f2, K2, expand( data, 25 ) );
 177   subRound( E, A, B, C, D, f2, K2, expand( data, 26 ) );
 178   subRound( D, E, A, B, C, f2, K2, expand( data, 27 ) );
 179   subRound( C, D, E, A, B, f2, K2, expand( data, 28 ) );
 180   subRound( B, C, D, E, A, f2, K2, expand( data, 29 ) );
 181   subRound( A, B, C, D, E, f2, K2, expand( data, 30 ) );
 182   subRound( E, A, B, C, D, f2, K2, expand( data, 31 ) );
 183   subRound( D, E, A, B, C, f2, K2, expand( data, 32 ) );
 184   subRound( C, D, E, A, B, f2, K2, expand( data, 33 ) );
 185   subRound( B, C, D, E, A, f2, K2, expand( data, 34 ) );
 186   subRound( A, B, C, D, E, f2, K2, expand( data, 35 ) );
 187   subRound( E, A, B, C, D, f2, K2, expand( data, 36 ) );
 188   subRound( D, E, A, B, C, f2, K2, expand( data, 37 ) );
 189   subRound( C, D, E, A, B, f2, K2, expand( data, 38 ) ); DEBUG(38);
 190   subRound( B, C, D, E, A, f2, K2, expand( data, 39 ) ); DEBUG(39);
 191
 192   subRound( A, B, C, D, E, f3, K3, expand( data, 40 ) ); DEBUG(40);
 193   subRound( E, A, B, C, D, f3, K3, expand( data, 41 ) ); DEBUG(41);
 194   subRound( D, E, A, B, C, f3, K3, expand( data, 42 ) );
 195   subRound( C, D, E, A, B, f3, K3, expand( data, 43 ) );
 196   subRound( B, C, D, E, A, f3, K3, expand( data, 44 ) );
 197   subRound( A, B, C, D, E, f3, K3, expand( data, 45 ) );
 198   subRound( E, A, B, C, D, f3, K3, expand( data, 46 ) );
 199   subRound( D, E, A, B, C, f3, K3, expand( data, 47 ) );
 200   subRound( C, D, E, A, B, f3, K3, expand( data, 48 ) );
 201   subRound( B, C, D, E, A, f3, K3, expand( data, 49 ) );
 202   subRound( A, B, C, D, E, f3, K3, expand( data, 50 ) );
 203   subRound( E, A, B, C, D, f3, K3, expand( data, 51 ) );
 204   subRound( D, E, A, B, C, f3, K3, expand( data, 52 ) );
 205   subRound( C, D, E, A, B, f3, K3, expand( data, 53 ) );
 206   subRound( B, C, D, E, A, f3, K3, expand( data, 54 ) );
 207   subRound( A, B, C, D, E, f3, K3, expand( data, 55 ) );
 208   subRound( E, A, B, C, D, f3, K3, expand( data, 56 ) );
 209   subRound( D, E, A, B, C, f3, K3, expand( data, 57 ) );
 210   subRound( C, D, E, A, B, f3, K3, expand( data, 58 ) ); DEBUG(58);
 211   subRound( B, C, D, E, A, f3, K3, expand( data, 59 ) ); DEBUG(59);
 212
 213   subRound( A, B, C, D, E, f4, K4, expand( data, 60 ) ); DEBUG(60);
 214   subRound( E, A, B, C, D, f4, K4, expand( data, 61 ) ); DEBUG(61);
 215   subRound( D, E, A, B, C, f4, K4, expand( data, 62 ) );
 216   subRound( C, D, E, A, B, f4, K4, expand( data, 63 ) );
 217   subRound( B, C, D, E, A, f4, K4, expand( data, 64 ) );
 218   subRound( A, B, C, D, E, f4, K4, expand( data, 65 ) );
 219   subRound( E, A, B, C, D, f4, K4, expand( data, 66 ) );
 220   subRound( D, E, A, B, C, f4, K4, expand( data, 67 ) );
 221   subRound( C, D, E, A, B, f4, K4, expand( data, 68 ) );
 222   subRound( B, C, D, E, A, f4, K4, expand( data, 69 ) );
 223   subRound( A, B, C, D, E, f4, K4, expand( data, 70 ) );
 224   subRound( E, A, B, C, D, f4, K4, expand( data, 71 ) );
 225   subRound( D, E, A, B, C, f4, K4, expand( data, 72 ) );
 226   subRound( C, D, E, A, B, f4, K4, expand( data, 73 ) );
 227   subRound( B, C, D, E, A, f4, K4, expand( data, 74 ) );
 228   subRound( A, B, C, D, E, f4, K4, expand( data, 75 ) );
 229   subRound( E, A, B, C, D, f4, K4, expand( data, 76 ) );
 230   subRound( D, E, A, B, C, f4, K4, expand( data, 77 ) );
 231   subRound( C, D, E, A, B, f4, K4, expand( data, 78 ) ); DEBUG(78);
 232   subRound( B, C, D, E, A, f4, K4, expand( data, 79 ) ); DEBUG(79);
 233
 234   /* Build message digest */
 235   state[0] += A;
 236   state[1] += B;
 237   state[2] += C;
 238   state[3] += D;
 239   state[4] += E;
 240
 241 #if SHA1_DEBUG
 242   fprintf(stderr, "99: %8x %8x %8x %8x %8x\n",
 243           state[0], state[1], state[2], state[3], state[4]);
 244 #endif
 245 }