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