cipher/sha1.c

   1 /* sha1.c - SHA1 hash function
   2  *      Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
   3  *
   4  * Please see below for more legal information!
   5  *
   6  * This file is part of GnuPG.
   7  *
   8  * GnuPG is free software; you can redistribute it and/or modify
   9  * it under the terms of the GNU General Public License as published by
  10  * the Free Software Foundation; either version 2 of the License, or
  11  * (at your option) any later version.
  12  *
  13  * GnuPG is distributed in the hope that it will be useful,
  14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16  * GNU General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU General Public License
  19  * along with this program; if not, write to the Free Software
  20  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
  21  */
  22
  23
  24 /*  Test vectors:
  25  *
  26  *  "abc"
  27  *  A999 3E36 4706 816A BA3E  2571 7850 C26C 9CD0 D89D
  28  *
  29  *  "abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq"
  30  *  8498 3E44 1C3B D26E BAAE  4AA1 F951 29E5 E546 70F1
  31  */
  32
  33
  34 #include <config.h>
  35 #include <stdio.h>
  36 #include <stdlib.h>
  37 #include <string.h>
  38 #include <assert.h>
  39 #include "util.h"
  40 #include "memory.h"
  41 #include "algorithms.h"
  42 #include "bithelp.h"
  43
  44
  45 typedef struct {
  46     u32  h0,h1,h2,h3,h4;
  47     u32  nblocks;
  48     byte buf[64];
  49     int  count;
  50 } SHA1_CONTEXT;
  51
  52 static void
  53 burn_stack (int bytes)
  54 {
  55     char buf[128];
  56
  57     memset (buf, 0, sizeof buf);
  58     bytes -= sizeof buf;
  59     if (bytes > 0)
  60         burn_stack (bytes);
  61 }
  62
  63
  64 void
  65 sha1_init( SHA1_CONTEXT *hd )
  66 {
  67     hd->h0 = 0x67452301;
  68     hd->h1 = 0xefcdab89;
  69     hd->h2 = 0x98badcfe;
  70     hd->h3 = 0x10325476;
  71     hd->h4 = 0xc3d2e1f0;
  72     hd->nblocks = 0;
  73     hd->count = 0;
  74 }
  75
  76
  77 /****************
  78  * Transform the message X which consists of 16 32-bit-words
  79  */
  80 static void
  81 transform( SHA1_CONTEXT *hd, byte *data )
  82 {
  83     u32 a,b,c,d,e,tm;
  84     u32 x[16];
  85
  86     /* get values from the chaining vars */
  87     a = hd->h0;
  88     b = hd->h1;
  89     c = hd->h2;
  90     d = hd->h3;
  91     e = hd->h4;
  92
  93   #ifdef BIG_ENDIAN_HOST
  94     memcpy( x, data, 64 );
  95   #else
  96     { int i;
  97       byte *p2;
  98       for(i=0, p2=(byte*)x; i < 16; i++, p2 += 4 ) {
  99         p2[3] = *data++;
 100         p2[2] = *data++;
 101         p2[1] = *data++;
 102         p2[0] = *data++;
 103       }
 104     }
 105   #endif
 106
 107
 108 #define K1  0x5A827999L
 109 #define K2  0x6ED9EBA1L
 110 #define K3  0x8F1BBCDCL
 111 #define K4  0xCA62C1D6L
 112 #define F1(x,y,z)   ( z ^ ( x & ( y ^ z ) ) )
 113 #define F2(x,y,z)   ( x ^ y ^ z )
 114 #define F3(x,y,z)   ( ( x & y ) | ( z & ( x | y ) ) )
 115 #define F4(x,y,z)   ( x ^ y ^ z )
 116
 117
 118 #define M(i) ( tm =   x[i&0x0f] ^ x[(i-14)&0x0f] \
 119                     ^ x[(i-8)&0x0f] ^ x[(i-3)&0x0f] \
 120                , (x[i&0x0f] = rol(tm,1)) )
 121
 122 #define R(a,b,c,d,e,f,k,m)  do { e += rol( a, 5 )     \
 123                                       + f( b, c, d )  \
 124                                       + k             \
 125                                       + m;            \
 126                                  b = rol( b, 30 );    \
 127                                } while(0)
 128     R( a, b, c, d, e, F1, K1, x[ 0] );
 129     R( e, a, b, c, d, F1, K1, x[ 1] );
 130     R( d, e, a, b, c, F1, K1, x[ 2] );
 131     R( c, d, e, a, b, F1, K1, x[ 3] );
 132     R( b, c, d, e, a, F1, K1, x[ 4] );
 133     R( a, b, c, d, e, F1, K1, x[ 5] );
 134     R( e, a, b, c, d, F1, K1, x[ 6] );
 135     R( d, e, a, b, c, F1, K1, x[ 7] );
 136     R( c, d, e, a, b, F1, K1, x[ 8] );
 137     R( b, c, d, e, a, F1, K1, x[ 9] );
 138     R( a, b, c, d, e, F1, K1, x[10] );
 139     R( e, a, b, c, d, F1, K1, x[11] );
 140     R( d, e, a, b, c, F1, K1, x[12] );
 141     R( c, d, e, a, b, F1, K1, x[13] );
 142     R( b, c, d, e, a, F1, K1, x[14] );
 143     R( a, b, c, d, e, F1, K1, x[15] );
 144     R( e, a, b, c, d, F1, K1, M(16) );
 145     R( d, e, a, b, c, F1, K1, M(17) );
 146     R( c, d, e, a, b, F1, K1, M(18) );
 147     R( b, c, d, e, a, F1, K1, M(19) );
 148     R( a, b, c, d, e, F2, K2, M(20) );
 149     R( e, a, b, c, d, F2, K2, M(21) );
 150     R( d, e, a, b, c, F2, K2, M(22) );
 151     R( c, d, e, a, b, F2, K2, M(23) );
 152     R( b, c, d, e, a, F2, K2, M(24) );
 153     R( a, b, c, d, e, F2, K2, M(25) );
 154     R( e, a, b, c, d, F2, K2, M(26) );
 155     R( d, e, a, b, c, F2, K2, M(27) );
 156     R( c, d, e, a, b, F2, K2, M(28) );
 157     R( b, c, d, e, a, F2, K2, M(29) );
 158     R( a, b, c, d, e, F2, K2, M(30) );
 159     R( e, a, b, c, d, F2, K2, M(31) );
 160     R( d, e, a, b, c, F2, K2, M(32) );
 161     R( c, d, e, a, b, F2, K2, M(33) );
 162     R( b, c, d, e, a, F2, K2, M(34) );
 163     R( a, b, c, d, e, F2, K2, M(35) );
 164     R( e, a, b, c, d, F2, K2, M(36) );
 165     R( d, e, a, b, c, F2, K2, M(37) );
 166     R( c, d, e, a, b, F2, K2, M(38) );
 167     R( b, c, d, e, a, F2, K2, M(39) );
 168     R( a, b, c, d, e, F3, K3, M(40) );
 169     R( e, a, b, c, d, F3, K3, M(41) );
 170     R( d, e, a, b, c, F3, K3, M(42) );
 171     R( c, d, e, a, b, F3, K3, M(43) );
 172     R( b, c, d, e, a, F3, K3, M(44) );
 173     R( a, b, c, d, e, F3, K3, M(45) );
 174     R( e, a, b, c, d, F3, K3, M(46) );
 175     R( d, e, a, b, c, F3, K3, M(47) );
 176     R( c, d, e, a, b, F3, K3, M(48) );
 177     R( b, c, d, e, a, F3, K3, M(49) );
 178     R( a, b, c, d, e, F3, K3, M(50) );
 179     R( e, a, b, c, d, F3, K3, M(51) );
 180     R( d, e, a, b, c, F3, K3, M(52) );
 181     R( c, d, e, a, b, F3, K3, M(53) );
 182     R( b, c, d, e, a, F3, K3, M(54) );
 183     R( a, b, c, d, e, F3, K3, M(55) );
 184     R( e, a, b, c, d, F3, K3, M(56) );
 185     R( d, e, a, b, c, F3, K3, M(57) );
 186     R( c, d, e, a, b, F3, K3, M(58) );
 187     R( b, c, d, e, a, F3, K3, M(59) );
 188     R( a, b, c, d, e, F4, K4, M(60) );
 189     R( e, a, b, c, d, F4, K4, M(61) );
 190     R( d, e, a, b, c, F4, K4, M(62) );
 191     R( c, d, e, a, b, F4, K4, M(63) );
 192     R( b, c, d, e, a, F4, K4, M(64) );
 193     R( a, b, c, d, e, F4, K4, M(65) );
 194     R( e, a, b, c, d, F4, K4, M(66) );
 195     R( d, e, a, b, c, F4, K4, M(67) );
 196     R( c, d, e, a, b, F4, K4, M(68) );
 197     R( b, c, d, e, a, F4, K4, M(69) );
 198     R( a, b, c, d, e, F4, K4, M(70) );
 199     R( e, a, b, c, d, F4, K4, M(71) );
 200     R( d, e, a, b, c, F4, K4, M(72) );
 201     R( c, d, e, a, b, F4, K4, M(73) );
 202     R( b, c, d, e, a, F4, K4, M(74) );
 203     R( a, b, c, d, e, F4, K4, M(75) );
 204     R( e, a, b, c, d, F4, K4, M(76) );
 205     R( d, e, a, b, c, F4, K4, M(77) );
 206     R( c, d, e, a, b, F4, K4, M(78) );
 207     R( b, c, d, e, a, F4, K4, M(79) );
 208
 209     /* update chainig vars */
 210     hd->h0 += a;
 211     hd->h1 += b;
 212     hd->h2 += c;
 213     hd->h3 += d;
 214     hd->h4 += e;
 215 }
 216
 217
 218 /* Update the message digest with the contents
 219  * of INBUF with length INLEN.
 220  */
 221 static void
 222 sha1_write( SHA1_CONTEXT *hd, byte *inbuf, size_t inlen)
 223 {
 224     if( hd->count == 64 ) { /* flush the buffer */
 225         transform( hd, hd->buf );
 226         burn_stack (88+4*sizeof(void*));
 227         hd->count = 0;
 228         hd->nblocks++;
 229     }
 230     if( !inbuf )
 231         return;
 232     if( hd->count ) {
 233         for( ; inlen && hd->count < 64; inlen-- )
 234             hd->buf[hd->count++] = *inbuf++;
 235         sha1_write( hd, NULL, 0 );
 236         if( !inlen )
 237             return;
 238     }
 239
 240     while( inlen >= 64 ) {
 241         transform( hd, inbuf );
 242         hd->count = 0;
 243         hd->nblocks++;
 244         inlen -= 64;
 245         inbuf += 64;
 246     }
 247     burn_stack (88+4*sizeof(void*));
 248     for( ; inlen && hd->count < 64; inlen-- )
 249         hd->buf[hd->count++] = *inbuf++;
 250 }
 251
 252
 253 /* The routine final terminates the computation and
 254  * returns the digest.
 255  * The handle is prepared for a new cycle, but adding bytes to the
 256  * handle will the destroy the returned buffer.
 257  * Returns: 20 bytes representing the digest.
 258  */
 259
 260 static void
 261 sha1_final(SHA1_CONTEXT *hd)
 262 {
 263     u32 t, msb, lsb;
 264     byte *p;
 265
 266     sha1_write(hd, NULL, 0); /* flush */;
 267
 268     t = hd->nblocks;
 269     /* multiply by 64 to make a byte count */
 270     lsb = t << 6;
 271     msb = t >> 26;
 272     /* add the count */
 273     t = lsb;
 274     if( (lsb += hd->count) < t )
 275         msb++;
 276     /* multiply by 8 to make a bit count */
 277     t = lsb;
 278     lsb <<= 3;
 279     msb <<= 3;
 280     msb |= t >> 29;
 281
 282     if( hd->count < 56 ) { /* enough room */
 283         hd->buf[hd->count++] = 0x80; /* pad */
 284         while( hd->count < 56 )
 285             hd->buf[hd->count++] = 0;  /* pad */
 286     }
 287     else { /* need one extra block */
 288         hd->buf[hd->count++] = 0x80; /* pad character */
 289         while( hd->count < 64 )
 290             hd->buf[hd->count++] = 0;
 291         sha1_write(hd, NULL, 0);  /* flush */;
 292         memset(hd->buf, 0, 56 ); /* fill next block with zeroes */
 293     }
 294     /* append the 64 bit count */
 295     hd->buf[56] = msb >> 24;
 296     hd->buf[57] = msb >> 16;
 297     hd->buf[58] = msb >>  8;
 298     hd->buf[59] = msb      ;
 299     hd->buf[60] = lsb >> 24;
 300     hd->buf[61] = lsb >> 16;
 301     hd->buf[62] = lsb >>  8;
 302     hd->buf[63] = lsb      ;
 303     transform( hd, hd->buf );
 304     burn_stack (88+4*sizeof(void*));
 305
 306     p = hd->buf;
 307   #ifdef BIG_ENDIAN_HOST
 308     #define X(a) do { *(u32*)p = hd->h##a ; p += 4; } while(0)
 309   #else /* little endian */
 310     #define X(a) do { *p++ = hd->h##a >> 24; *p++ = hd->h##a >> 16;      \
 311                       *p++ = hd->h##a >> 8; *p++ = hd->h##a; } while(0)
 312   #endif
 313     X(0);
 314     X(1);
 315     X(2);
 316     X(3);
 317     X(4);
 318   #undef X
 319
 320 }
 321
 322 static byte *
 323 sha1_read( SHA1_CONTEXT *hd )
 324 {
 325     return hd->buf;
 326 }
 327
 328 /****************
 329  * Return some information about the algorithm.  We need algo here to
 330  * distinguish different flavors of the algorithm.
 331  * Returns: A pointer to string describing the algorithm or NULL if
 332  *          the ALGO is invalid.
 333  */
 334 const char *
 335 sha1_get_info( int algo, size_t *contextsize,
 336                byte **r_asnoid, int *r_asnlen, int *r_mdlen,
 337                void (**r_init)( void *c ),
 338                void (**r_write)( void *c, byte *buf, size_t nbytes ),
 339                void (**r_final)( void *c ),
 340                byte *(**r_read)( void *c )
 341              )
 342 {
 343     static byte asn[15] = /* Object ID is 1.3.14.3.2.26 */
 344                     { 0x30, 0x21, 0x30, 0x09, 0x06, 0x05, 0x2b, 0x0e, 0x03,
 345                       0x02, 0x1a, 0x05, 0x00, 0x04, 0x14 };
 346     if( algo != 2 )
 347         return NULL;
 348
 349     *contextsize = sizeof(SHA1_CONTEXT);
 350     *r_asnoid = asn;
 351     *r_asnlen = DIM(asn);
 352     *r_mdlen = 20;
 353     *(void  (**)(SHA1_CONTEXT *))r_init                 = sha1_init;
 354     *(void  (**)(SHA1_CONTEXT *, byte*, size_t))r_write = sha1_write;
 355     *(void  (**)(SHA1_CONTEXT *))r_final                = sha1_final;
 356     *(byte *(**)(SHA1_CONTEXT *))r_read                 = sha1_read;
 357
 358     return "SHA1";
 359 }