sha1-compress.c

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