sha256-compress.c

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