sha1-compress.c 10 KB
Newer Older
1 2 3 4 5 6 7
/* sha1-compress.c
 *
 * The compression function of the sha1 hash function.
 */

/* nettle, low-level cryptographics library
 *
Niels Möller's avatar
Niels Möller committed
8
 * Copyright (C) 2001, 2004 Peter Gutmann, Andrew Kuchling, Niels Möller
9 10 11 12 13 14 15 16 17 18 19 20 21
 *  
 * The nettle library is free software; you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License as published by
 * the Free Software Foundation; either version 2.1 of the License, or (at your
 * option) any later version.
 * 
 * The nettle library is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
 * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
 * License for more details.
 * 
 * You should have received a copy of the GNU Lesser General Public License
 * along with the nettle library; see the file COPYING.LIB.  If not, write to
22 23
 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
 * MA 02111-1301, USA.
24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41
 */

/* Here's the first paragraph of Peter Gutmann's posting,
 * <30ajo5$oe8@ccu2.auckland.ac.nz>: 
 *
 * The following is my SHA (FIPS 180) code updated to allow use of the "fixed"
 * SHA, thanks to Jim Gillogly and an anonymous contributor for the information on
 * what's changed in the new version.  The fix is a simple change which involves
 * adding a single rotate in the initial expansion function.  It is unknown
 * whether this is an optimal solution to the problem which was discovered in the
 * SHA or whether it's simply a bandaid which fixes the problem with a minimum of
 * effort (for example the reengineering of a great many Capstone chips).
 */

#if HAVE_CONFIG_H
# include "config.h"
#endif

42 43 44 45 46 47 48 49 50 51 52 53
#ifndef SHA1_DEBUG
# define SHA1_DEBUG 0
#endif

#if SHA1_DEBUG
# include <stdio.h>
# define DEBUG(i) \
  fprintf(stderr, "%2d: %8x %8x %8x %8x %8x\n", i, A, B, C, D ,E)
#else
# define DEBUG(i)
#endif

54 55 56 57 58 59 60 61 62 63 64 65 66 67 68
#include <assert.h>
#include <stdlib.h>
#include <string.h>

#include "sha.h"

#include "macros.h"

/* A block, treated as a sequence of 32-bit words. */
#define SHA1_DATA_LENGTH 16

/* The SHA f()-functions.  The f1 and f3 functions can be optimized to
   save one boolean operation each - thanks to Rich Schroeppel,
   rcs@cs.arizona.edu for discovering this */

69 70 71 72 73 74
/* FIXME: Can save a temporary in f3 by using ( (x & y) + (z & (x ^
   y)) ), and then, in the round, compute one of the terms and add it
   into the destination word before computing the second term. Credits
   to George Spelvin for pointing this out. Unfortunately, gcc
   doesn't seem to be smart enough to take advantage of this. */

75 76 77 78 79
/* #define f1(x,y,z) ( ( x & y ) | ( ~x & z ) )            Rounds  0-19 */
#define f1(x,y,z)   ( z ^ ( x & ( y ^ z ) ) )           /* Rounds  0-19 */
#define f2(x,y,z)   ( x ^ y ^ z )                       /* Rounds 20-39 */
/* #define f3(x,y,z) ( ( x & y ) | ( x & z ) | ( y & z ) ) Rounds 40-59 */
#define f3(x,y,z)   ( ( x & y ) | ( z & ( x | y ) ) )   /* Rounds 40-59 */
80
#define f4 f2
81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103

/* The SHA Mysterious Constants */

#define K1  0x5A827999L                                 /* Rounds  0-19 */
#define K2  0x6ED9EBA1L                                 /* Rounds 20-39 */
#define K3  0x8F1BBCDCL                                 /* Rounds 40-59 */
#define K4  0xCA62C1D6L                                 /* Rounds 60-79 */

/* The initial expanding function.  The hash function is defined over an
   80-word expanded input array W, where the first 16 are copies of the input
   data, and the remaining 64 are defined by

        W[ i ] = W[ i - 16 ] ^ W[ i - 14 ] ^ W[ i - 8 ] ^ W[ i - 3 ]

   This implementation generates these values on the fly in a circular
   buffer - thanks to Colin Plumb, colin@nyx10.cs.du.edu for this
   optimization.

   The updated SHA changes the expanding function by adding a rotate of 1
   bit.  Thanks to Jim Gillogly, jim@rand.org, and an anonymous contributor
   for this information */

#define expand(W,i) ( W[ i & 15 ] = \
Niels Möller's avatar
Niels Möller committed
104 105
		      ROTL32( 1, ( W[ i & 15 ] ^ W[ (i - 14) & 15 ] ^ \
				   W[ (i - 8) & 15 ] ^ W[ (i - 3) & 15 ] ) ) )
106 107 108 109


/* The prototype SHA sub-round.  The fundamental sub-round is:

Niels Möller's avatar
Niels Möller committed
110
        a' = e + ROTL32( 5, a ) + f( b, c, d ) + k + data;
111
        b' = a;
Niels Möller's avatar
Niels Möller committed
112
        c' = ROTL32( 30, b );
113 114 115 116 117 118 119 120 121
        d' = c;
        e' = d;

   but this is implemented by unrolling the loop 5 times and renaming the
   variables ( e, a, b, c, d ) = ( a', b', c', d', e' ) each iteration.
   This code is then replicated 20 times for each of the 4 functions, using
   the next 20 values from the W[] array each time */

#define subRound(a, b, c, d, e, f, k, data) \
Niels Möller's avatar
Niels Möller committed
122
    ( e += ROTL32( 5, a ) + f( b, c, d ) + k + data, b = ROTL32( 30, b ) )
123 124 125 126

/* Perform the SHA transformation.  Note that this code, like MD5, seems to
   break some optimizing compilers due to the complexity of the expressions
   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 135
  int i;

136
  for (i = 0; i < SHA1_DATA_LENGTH; i++, input+= 4)
137 138 139
    {
      data[i] = READ_UINT32(input);
    }
140 141 142 143 144 145 146 147

  /* Set up first buffer and local data buffer */
  A = state[0];
  B = state[1];
  C = state[2];
  D = state[3];
  E = state[4];

148
  DEBUG(-1);
149
  /* Heavy mangling, in 4 sub-rounds of 20 interations each. */
150 151
  subRound( A, B, C, D, E, f1, K1, data[ 0] ); DEBUG(0);
  subRound( E, A, B, C, D, f1, K1, data[ 1] ); DEBUG(1);
152 153 154 155 156 157 158 159 160 161 162 163 164
  subRound( D, E, A, B, C, f1, K1, data[ 2] );
  subRound( C, D, E, A, B, f1, K1, data[ 3] );
  subRound( B, C, D, E, A, f1, K1, data[ 4] );
  subRound( A, B, C, D, E, f1, K1, data[ 5] );
  subRound( E, A, B, C, D, f1, K1, data[ 6] );
  subRound( D, E, A, B, C, f1, K1, data[ 7] );
  subRound( C, D, E, A, B, f1, K1, data[ 8] );
  subRound( B, C, D, E, A, f1, K1, data[ 9] );
  subRound( A, B, C, D, E, f1, K1, data[10] );
  subRound( E, A, B, C, D, f1, K1, data[11] );
  subRound( D, E, A, B, C, f1, K1, data[12] );
  subRound( C, D, E, A, B, f1, K1, data[13] );
  subRound( B, C, D, E, A, f1, K1, data[14] );
165 166 167 168 169 170 171 172
  subRound( A, B, C, D, E, f1, K1, data[15] ); DEBUG(15);
  subRound( E, A, B, C, D, f1, K1, expand( data, 16 ) ); DEBUG(16);
  subRound( D, E, A, B, C, f1, K1, expand( data, 17 ) ); DEBUG(17);
  subRound( C, D, E, A, B, f1, K1, expand( data, 18 ) ); DEBUG(18);
  subRound( B, C, D, E, A, f1, K1, expand( data, 19 ) ); DEBUG(19);

  subRound( A, B, C, D, E, f2, K2, expand( data, 20 ) ); DEBUG(20);
  subRound( E, A, B, C, D, f2, K2, expand( data, 21 ) ); DEBUG(21);
173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188
  subRound( D, E, A, B, C, f2, K2, expand( data, 22 ) );
  subRound( C, D, E, A, B, f2, K2, expand( data, 23 ) );
  subRound( B, C, D, E, A, f2, K2, expand( data, 24 ) );
  subRound( A, B, C, D, E, f2, K2, expand( data, 25 ) );
  subRound( E, A, B, C, D, f2, K2, expand( data, 26 ) );
  subRound( D, E, A, B, C, f2, K2, expand( data, 27 ) );
  subRound( C, D, E, A, B, f2, K2, expand( data, 28 ) );
  subRound( B, C, D, E, A, f2, K2, expand( data, 29 ) );
  subRound( A, B, C, D, E, f2, K2, expand( data, 30 ) );
  subRound( E, A, B, C, D, f2, K2, expand( data, 31 ) );
  subRound( D, E, A, B, C, f2, K2, expand( data, 32 ) );
  subRound( C, D, E, A, B, f2, K2, expand( data, 33 ) );
  subRound( B, C, D, E, A, f2, K2, expand( data, 34 ) );
  subRound( A, B, C, D, E, f2, K2, expand( data, 35 ) );
  subRound( E, A, B, C, D, f2, K2, expand( data, 36 ) );
  subRound( D, E, A, B, C, f2, K2, expand( data, 37 ) );
189 190
  subRound( C, D, E, A, B, f2, K2, expand( data, 38 ) ); DEBUG(38);
  subRound( B, C, D, E, A, f2, K2, expand( data, 39 ) ); DEBUG(39);
191

192 193
  subRound( A, B, C, D, E, f3, K3, expand( data, 40 ) ); DEBUG(40);
  subRound( E, A, B, C, D, f3, K3, expand( data, 41 ) ); DEBUG(41);
194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209
  subRound( D, E, A, B, C, f3, K3, expand( data, 42 ) );
  subRound( C, D, E, A, B, f3, K3, expand( data, 43 ) );
  subRound( B, C, D, E, A, f3, K3, expand( data, 44 ) );
  subRound( A, B, C, D, E, f3, K3, expand( data, 45 ) );
  subRound( E, A, B, C, D, f3, K3, expand( data, 46 ) );
  subRound( D, E, A, B, C, f3, K3, expand( data, 47 ) );
  subRound( C, D, E, A, B, f3, K3, expand( data, 48 ) );
  subRound( B, C, D, E, A, f3, K3, expand( data, 49 ) );
  subRound( A, B, C, D, E, f3, K3, expand( data, 50 ) );
  subRound( E, A, B, C, D, f3, K3, expand( data, 51 ) );
  subRound( D, E, A, B, C, f3, K3, expand( data, 52 ) );
  subRound( C, D, E, A, B, f3, K3, expand( data, 53 ) );
  subRound( B, C, D, E, A, f3, K3, expand( data, 54 ) );
  subRound( A, B, C, D, E, f3, K3, expand( data, 55 ) );
  subRound( E, A, B, C, D, f3, K3, expand( data, 56 ) );
  subRound( D, E, A, B, C, f3, K3, expand( data, 57 ) );
210 211
  subRound( C, D, E, A, B, f3, K3, expand( data, 58 ) ); DEBUG(58);
  subRound( B, C, D, E, A, f3, K3, expand( data, 59 ) ); DEBUG(59);
212

213 214
  subRound( A, B, C, D, E, f4, K4, expand( data, 60 ) ); DEBUG(60);
  subRound( E, A, B, C, D, f4, K4, expand( data, 61 ) ); DEBUG(61);
215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230
  subRound( D, E, A, B, C, f4, K4, expand( data, 62 ) );
  subRound( C, D, E, A, B, f4, K4, expand( data, 63 ) );
  subRound( B, C, D, E, A, f4, K4, expand( data, 64 ) );
  subRound( A, B, C, D, E, f4, K4, expand( data, 65 ) );
  subRound( E, A, B, C, D, f4, K4, expand( data, 66 ) );
  subRound( D, E, A, B, C, f4, K4, expand( data, 67 ) );
  subRound( C, D, E, A, B, f4, K4, expand( data, 68 ) );
  subRound( B, C, D, E, A, f4, K4, expand( data, 69 ) );
  subRound( A, B, C, D, E, f4, K4, expand( data, 70 ) );
  subRound( E, A, B, C, D, f4, K4, expand( data, 71 ) );
  subRound( D, E, A, B, C, f4, K4, expand( data, 72 ) );
  subRound( C, D, E, A, B, f4, K4, expand( data, 73 ) );
  subRound( B, C, D, E, A, f4, K4, expand( data, 74 ) );
  subRound( A, B, C, D, E, f4, K4, expand( data, 75 ) );
  subRound( E, A, B, C, D, f4, K4, expand( data, 76 ) );
  subRound( D, E, A, B, C, f4, K4, expand( data, 77 ) );
231 232
  subRound( C, D, E, A, B, f4, K4, expand( data, 78 ) ); DEBUG(78);
  subRound( B, C, D, E, A, f4, K4, expand( data, 79 ) ); DEBUG(79);
233 234 235 236 237 238 239

  /* Build message digest */
  state[0] += A;
  state[1] += B;
  state[2] += C;
  state[3] += D;
  state[4] += E;
240 241 242 243 244

#if SHA1_DEBUG
  fprintf(stderr, "99: %8x %8x %8x %8x %8x\n",
	  state[0], state[1], state[2], state[3], state[4]);
#endif
245
}