sha256-compress.c

   1 /* sha256-compress.c
   2
   3    The compression function of the sha256 hash function.
   4
   5    Copyright (C) 2001, 2010 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 #if HAVE_CONFIG_H
  35 # include "config.h"
  36 #endif
  37
  38 #ifndef SHA256_DEBUG
  39 # define SHA256_DEBUG 0
  40 #endif
  41
  42 #if SHA256_DEBUG
  43 # include <stdio.h>
  44 # define DEBUG(i) \
  45   fprintf(stderr, "%2d: %8x %8x %8x %8x %8x %8x %8x %8x\n", \
  46           i, A, B, C, D ,E, F, G, H)
  47 #else
  48 # define DEBUG(i)
  49 #endif
  50
  51 #include <assert.h>
  52 #include <stdlib.h>
  53 #include <string.h>
  54
  55 #include "sha2.h"
  56
  57 #include "macros.h"
  58
  59 /* A block, treated as a sequence of 32-bit words. */
  60 #define SHA256_DATA_LENGTH 16
  61
  62 /* The SHA256 functions. The Choice function is the same as the SHA1
  63    function f1, and the majority function is the same as the SHA1 f3
  64    function. They can be optimized to save one boolean operation each
  65    - thanks to Rich Schroeppel, rcs@cs.arizona.edu for discovering
  66    this */
  67
  68 /* #define Choice(x,y,z) ( ( (x) & (y) ) | ( ~(x) & (z) ) ) */
  69 #define Choice(x,y,z)   ( (z) ^ ( (x) & ( (y) ^ (z) ) ) )
  70 /* #define Majority(x,y,z) ( ((x) & (y)) ^ ((x) & (z)) ^ ((y) & (z)) ) */
  71 #define Majority(x,y,z) ( ((x) & (y)) ^ ((z) & ((x) ^ (y))) )
  72
  73 #define S0(x) (ROTL32(30,(x)) ^ ROTL32(19,(x)) ^ ROTL32(10,(x)))
  74 #define S1(x) (ROTL32(26,(x)) ^ ROTL32(21,(x)) ^ ROTL32(7,(x)))
  75
  76 #define s0(x) (ROTL32(25,(x)) ^ ROTL32(14,(x)) ^ ((x) >> 3))
  77 #define s1(x) (ROTL32(15,(x)) ^ ROTL32(13,(x)) ^ ((x) >> 10))
  78
  79 /* The initial expanding function.  The hash function is defined over an
  80    64-word expanded input array W, where the first 16 are copies of the input
  81    data, and the remaining 64 are defined by
  82
  83         W[ t ] = s1(W[t-2]) + W[t-7] + s0(W[i-15]) + W[i-16]
  84
  85    This implementation generates these values on the fly in a circular
  86    buffer - thanks to Colin Plumb, colin@nyx10.cs.du.edu for this
  87    optimization.
  88 */
  89
  90 #define EXPAND(W,i) \
  91 ( W[(i) & 15 ] += (s1(W[((i)-2) & 15]) + W[((i)-7) & 15] + s0(W[((i)-15) & 15])) )
  92
  93 /* The prototype SHA sub-round.  The fundamental sub-round is:
  94
  95         T1 = h + S1(e) + Choice(e,f,g) + K[t] + W[t]
  96         T2 = S0(a) + Majority(a,b,c)
  97         a' = T1+T2
  98         b' = a
  99         c' = b
 100         d' = c
 101         e' = d + T1
 102         f' = e
 103         g' = f
 104         h' = g
 105
 106    but this is implemented by unrolling the loop 8 times and renaming
 107    the variables
 108    ( h, a, b, c, d, e, f, g ) = ( a, b, c, d, e, f, g, h ) each
 109    iteration. */
 110
 111 /* It's crucial that DATA is only used once, as that argument will
 112  * have side effects. */
 113 #define ROUND(a,b,c,d,e,f,g,h,k,data) do {      \
 114     h += S1(e) + Choice(e,f,g) + k + data;      \
 115     d += h;                                     \
 116     h += S0(a) + Majority(a,b,c);               \
 117   } while (0)
 118
 119 /* For fat builds */
 120 #if HAVE_NATIVE_sha256_compress
 121 void
 122 _nettle_sha256_compress_c(uint32_t *state, const uint8_t *input, const uint32_t *k);
 123 #define _nettle_sha256_compress _nettle_sha256_compress_c
 124 #endif
 125
 126 void
 127 _nettle_sha256_compress(uint32_t *state, const uint8_t *input, const uint32_t *k)
 128 {
 129   uint32_t data[SHA256_DATA_LENGTH];
 130   uint32_t A, B, C, D, E, F, G, H;     /* Local vars */
 131   unsigned i;
 132   uint32_t *d;
 133
 134   for (i = 0; i < SHA256_DATA_LENGTH; i++, input+= 4)
 135     {
 136       data[i] = READ_UINT32(input);
 137     }
 138
 139   /* Set up first buffer and local data buffer */
 140   A = state[0];
 141   B = state[1];
 142   C = state[2];
 143   D = state[3];
 144   E = state[4];
 145   F = state[5];
 146   G = state[6];
 147   H = state[7];
 148
 149   /* Heavy mangling */
 150   /* First 16 subrounds that act on the original data */
 151
 152   DEBUG(-1);
 153   for (i = 0, d = data; i<16; i+=8, k += 8, d+= 8)
 154     {
 155       ROUND(A, B, C, D, E, F, G, H, k[0], d[0]); DEBUG(i);
 156       ROUND(H, A, B, C, D, E, F, G, k[1], d[1]); DEBUG(i+1);
 157       ROUND(G, H, A, B, C, D, E, F, k[2], d[2]);
 158       ROUND(F, G, H, A, B, C, D, E, k[3], d[3]);
 159       ROUND(E, F, G, H, A, B, C, D, k[4], d[4]);
 160       ROUND(D, E, F, G, H, A, B, C, k[5], d[5]);
 161       ROUND(C, D, E, F, G, H, A, B, k[6], d[6]); DEBUG(i+6);
 162       ROUND(B, C, D, E, F, G, H, A, k[7], d[7]); DEBUG(i+7);
 163     }
 164
 165   for (; i<64; i += 16, k+= 16)
 166     {
 167       ROUND(A, B, C, D, E, F, G, H, k[ 0], EXPAND(data,  0)); DEBUG(i);
 168       ROUND(H, A, B, C, D, E, F, G, k[ 1], EXPAND(data,  1)); DEBUG(i+1);
 169       ROUND(G, H, A, B, C, D, E, F, k[ 2], EXPAND(data,  2)); DEBUG(i+2);
 170       ROUND(F, G, H, A, B, C, D, E, k[ 3], EXPAND(data,  3)); DEBUG(i+3);
 171       ROUND(E, F, G, H, A, B, C, D, k[ 4], EXPAND(data,  4)); DEBUG(i+4);
 172       ROUND(D, E, F, G, H, A, B, C, k[ 5], EXPAND(data,  5)); DEBUG(i+5);
 173       ROUND(C, D, E, F, G, H, A, B, k[ 6], EXPAND(data,  6)); DEBUG(i+6);
 174       ROUND(B, C, D, E, F, G, H, A, k[ 7], EXPAND(data,  7)); DEBUG(i+7);
 175       ROUND(A, B, C, D, E, F, G, H, k[ 8], EXPAND(data,  8)); DEBUG(i+8);
 176       ROUND(H, A, B, C, D, E, F, G, k[ 9], EXPAND(data,  9)); DEBUG(i+9);
 177       ROUND(G, H, A, B, C, D, E, F, k[10], EXPAND(data, 10)); DEBUG(i+10);
 178       ROUND(F, G, H, A, B, C, D, E, k[11], EXPAND(data, 11)); DEBUG(i+11);
 179       ROUND(E, F, G, H, A, B, C, D, k[12], EXPAND(data, 12)); DEBUG(i+12);
 180       ROUND(D, E, F, G, H, A, B, C, k[13], EXPAND(data, 13)); DEBUG(i+13);
 181       ROUND(C, D, E, F, G, H, A, B, k[14], EXPAND(data, 14)); DEBUG(i+14);
 182       ROUND(B, C, D, E, F, G, H, A, k[15], EXPAND(data, 15)); DEBUG(i+15);
 183     }
 184
 185   /* Update state */
 186   state[0] += A;
 187   state[1] += B;
 188   state[2] += C;
 189   state[3] += D;
 190   state[4] += E;
 191   state[5] += F;
 192   state[6] += G;
 193   state[7] += H;
 194 #if SHA256_DEBUG
 195   fprintf(stderr, "99: %8x %8x %8x %8x %8x %8x %8x %8x\n",
 196           state[0], state[1], state[2], state[3],
 197           state[4], state[5], state[6], state[7]);
 198 #endif
 199 }