1/* sha1.c - SHA1 hash function 2 * Copyright (C) 1998, 2001, 2002, 2003, 2008 Free Software Foundation, Inc. 3 * 4 * This file is part of Libgcrypt. 5 * 6 * Libgcrypt is free software; you can redistribute it and/or modify 7 * it under the terms of the GNU Lesser General Public License as 8 * published by the Free Software Foundation; either version 2.1 of 9 * the License, or (at your option) any later version. 10 * 11 * Libgcrypt is distributed in the hope that it will be useful, 12 * but WITHOUT ANY WARRANTY; without even the implied warranty of 13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 * GNU Lesser General Public License for more details. 15 * 16 * You should have received a copy of the GNU Lesser General Public 17 * License along with this program; if not, see <http://www.gnu.org/licenses/>. 18 */ 19 20 21/* Test vectors: 22 * 23 * "abc" 24 * A999 3E36 4706 816A BA3E 2571 7850 C26C 9CD0 D89D 25 * 26 * "abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq" 27 * 8498 3E44 1C3B D26E BAAE 4AA1 F951 29E5 E546 70F1 28 */ 29 30 31#include <config.h> 32#include <stdio.h> 33#include <stdlib.h> 34#include <string.h> 35#ifdef HAVE_STDINT_H 36# include <stdint.h> 37#endif 38 39#include "g10lib.h" 40#include "bithelp.h" 41#include "cipher.h" 42#include "hash-common.h" 43 44 45/* A macro to test whether P is properly aligned for an u32 type. 46 Note that config.h provides a suitable replacement for uintptr_t if 47 it does not exist in stdint.h. */ 48/* #if __GNUC__ >= 2 */ 49/* # define U32_ALIGNED_P(p) (!(((uintptr_t)p) % __alignof__ (u32))) */ 50/* #else */ 51/* # define U32_ALIGNED_P(p) (!(((uintptr_t)p) % sizeof (u32))) */ 52/* #endif */ 53 54#define TRANSFORM(x,d,n) transform ((x), (d), (n)) 55 56 57typedef struct 58{ 59 u32 h0,h1,h2,h3,h4; 60 u32 nblocks; 61 unsigned char buf[64]; 62 int count; 63} SHA1_CONTEXT; 64 65 66 67static void 68sha1_init (void *context) 69{ 70 SHA1_CONTEXT *hd = context; 71 72 hd->h0 = 0x67452301; 73 hd->h1 = 0xefcdab89; 74 hd->h2 = 0x98badcfe; 75 hd->h3 = 0x10325476; 76 hd->h4 = 0xc3d2e1f0; 77 hd->nblocks = 0; 78 hd->count = 0; 79} 80 81 82/* Round function macros. */ 83#define K1 0x5A827999L 84#define K2 0x6ED9EBA1L 85#define K3 0x8F1BBCDCL 86#define K4 0xCA62C1D6L 87#define F1(x,y,z) ( z ^ ( x & ( y ^ z ) ) ) 88#define F2(x,y,z) ( x ^ y ^ z ) 89#define F3(x,y,z) ( ( x & y ) | ( z & ( x | y ) ) ) 90#define F4(x,y,z) ( x ^ y ^ z ) 91#define M(i) ( tm = x[ i &0x0f] \ 92 ^ x[(i-14)&0x0f] \ 93 ^ x[(i-8) &0x0f] \ 94 ^ x[(i-3) &0x0f], \ 95 (x[i&0x0f] = rol(tm, 1))) 96#define R(a,b,c,d,e,f,k,m) do { e += rol( a, 5 ) \ 97 + f( b, c, d ) \ 98 + k \ 99 + m; \ 100 b = rol( b, 30 ); \ 101 } while(0) 102 103 104/* 105 * Transform NBLOCKS of each 64 bytes (16 32-bit words) at DATA. 106 */ 107static void 108transform (SHA1_CONTEXT *hd, const unsigned char *data, size_t nblocks) 109{ 110 register u32 a, b, c, d, e; /* Local copies of the chaining variables. */ 111 register u32 tm; /* Helper. */ 112 u32 x[16]; /* The array we work on. */ 113 114 /* Loop over all blocks. */ 115 for ( ;nblocks; nblocks--) 116 { 117#ifdef WORDS_BIGENDIAN 118 memcpy (x, data, 64); 119 data += 64; 120#else 121 { 122 int i; 123 unsigned char *p; 124 125 for(i=0, p=(unsigned char*)x; i < 16; i++, p += 4 ) 126 { 127 p[3] = *data++; 128 p[2] = *data++; 129 p[1] = *data++; 130 p[0] = *data++; 131 } 132 } 133#endif 134 /* Get the values of the chaining variables. */ 135 a = hd->h0; 136 b = hd->h1; 137 c = hd->h2; 138 d = hd->h3; 139 e = hd->h4; 140 141 /* Transform. */ 142 R( a, b, c, d, e, F1, K1, x[ 0] ); 143 R( e, a, b, c, d, F1, K1, x[ 1] ); 144 R( d, e, a, b, c, F1, K1, x[ 2] ); 145 R( c, d, e, a, b, F1, K1, x[ 3] ); 146 R( b, c, d, e, a, F1, K1, x[ 4] ); 147 R( a, b, c, d, e, F1, K1, x[ 5] ); 148 R( e, a, b, c, d, F1, K1, x[ 6] ); 149 R( d, e, a, b, c, F1, K1, x[ 7] ); 150 R( c, d, e, a, b, F1, K1, x[ 8] ); 151 R( b, c, d, e, a, F1, K1, x[ 9] ); 152 R( a, b, c, d, e, F1, K1, x[10] ); 153 R( e, a, b, c, d, F1, K1, x[11] ); 154 R( d, e, a, b, c, F1, K1, x[12] ); 155 R( c, d, e, a, b, F1, K1, x[13] ); 156 R( b, c, d, e, a, F1, K1, x[14] ); 157 R( a, b, c, d, e, F1, K1, x[15] ); 158 R( e, a, b, c, d, F1, K1, M(16) ); 159 R( d, e, a, b, c, F1, K1, M(17) ); 160 R( c, d, e, a, b, F1, K1, M(18) ); 161 R( b, c, d, e, a, F1, K1, M(19) ); 162 R( a, b, c, d, e, F2, K2, M(20) ); 163 R( e, a, b, c, d, F2, K2, M(21) ); 164 R( d, e, a, b, c, F2, K2, M(22) ); 165 R( c, d, e, a, b, F2, K2, M(23) ); 166 R( b, c, d, e, a, F2, K2, M(24) ); 167 R( a, b, c, d, e, F2, K2, M(25) ); 168 R( e, a, b, c, d, F2, K2, M(26) ); 169 R( d, e, a, b, c, F2, K2, M(27) ); 170 R( c, d, e, a, b, F2, K2, M(28) ); 171 R( b, c, d, e, a, F2, K2, M(29) ); 172 R( a, b, c, d, e, F2, K2, M(30) ); 173 R( e, a, b, c, d, F2, K2, M(31) ); 174 R( d, e, a, b, c, F2, K2, M(32) ); 175 R( c, d, e, a, b, F2, K2, M(33) ); 176 R( b, c, d, e, a, F2, K2, M(34) ); 177 R( a, b, c, d, e, F2, K2, M(35) ); 178 R( e, a, b, c, d, F2, K2, M(36) ); 179 R( d, e, a, b, c, F2, K2, M(37) ); 180 R( c, d, e, a, b, F2, K2, M(38) ); 181 R( b, c, d, e, a, F2, K2, M(39) ); 182 R( a, b, c, d, e, F3, K3, M(40) ); 183 R( e, a, b, c, d, F3, K3, M(41) ); 184 R( d, e, a, b, c, F3, K3, M(42) ); 185 R( c, d, e, a, b, F3, K3, M(43) ); 186 R( b, c, d, e, a, F3, K3, M(44) ); 187 R( a, b, c, d, e, F3, K3, M(45) ); 188 R( e, a, b, c, d, F3, K3, M(46) ); 189 R( d, e, a, b, c, F3, K3, M(47) ); 190 R( c, d, e, a, b, F3, K3, M(48) ); 191 R( b, c, d, e, a, F3, K3, M(49) ); 192 R( a, b, c, d, e, F3, K3, M(50) ); 193 R( e, a, b, c, d, F3, K3, M(51) ); 194 R( d, e, a, b, c, F3, K3, M(52) ); 195 R( c, d, e, a, b, F3, K3, M(53) ); 196 R( b, c, d, e, a, F3, K3, M(54) ); 197 R( a, b, c, d, e, F3, K3, M(55) ); 198 R( e, a, b, c, d, F3, K3, M(56) ); 199 R( d, e, a, b, c, F3, K3, M(57) ); 200 R( c, d, e, a, b, F3, K3, M(58) ); 201 R( b, c, d, e, a, F3, K3, M(59) ); 202 R( a, b, c, d, e, F4, K4, M(60) ); 203 R( e, a, b, c, d, F4, K4, M(61) ); 204 R( d, e, a, b, c, F4, K4, M(62) ); 205 R( c, d, e, a, b, F4, K4, M(63) ); 206 R( b, c, d, e, a, F4, K4, M(64) ); 207 R( a, b, c, d, e, F4, K4, M(65) ); 208 R( e, a, b, c, d, F4, K4, M(66) ); 209 R( d, e, a, b, c, F4, K4, M(67) ); 210 R( c, d, e, a, b, F4, K4, M(68) ); 211 R( b, c, d, e, a, F4, K4, M(69) ); 212 R( a, b, c, d, e, F4, K4, M(70) ); 213 R( e, a, b, c, d, F4, K4, M(71) ); 214 R( d, e, a, b, c, F4, K4, M(72) ); 215 R( c, d, e, a, b, F4, K4, M(73) ); 216 R( b, c, d, e, a, F4, K4, M(74) ); 217 R( a, b, c, d, e, F4, K4, M(75) ); 218 R( e, a, b, c, d, F4, K4, M(76) ); 219 R( d, e, a, b, c, F4, K4, M(77) ); 220 R( c, d, e, a, b, F4, K4, M(78) ); 221 R( b, c, d, e, a, F4, K4, M(79) ); 222 223 /* Update the chaining variables. */ 224 hd->h0 += a; 225 hd->h1 += b; 226 hd->h2 += c; 227 hd->h3 += d; 228 hd->h4 += e; 229 } 230} 231 232 233/* Update the message digest with the contents 234 * of INBUF with length INLEN. 235 */ 236static void 237sha1_write( void *context, const void *inbuf_arg, size_t inlen) 238{ 239 const unsigned char *inbuf = inbuf_arg; 240 SHA1_CONTEXT *hd = context; 241 size_t nblocks; 242 243 if (hd->count == 64) /* Flush the buffer. */ 244 { 245 TRANSFORM( hd, hd->buf, 1 ); 246 _gcry_burn_stack (88+4*sizeof(void*)); 247 hd->count = 0; 248 hd->nblocks++; 249 } 250 if (!inbuf) 251 return; 252 253 if (hd->count) 254 { 255 for (; inlen && hd->count < 64; inlen--) 256 hd->buf[hd->count++] = *inbuf++; 257 sha1_write (hd, NULL, 0); 258 if (!inlen) 259 return; 260 } 261 262 nblocks = inlen / 64; 263 if (nblocks) 264 { 265 TRANSFORM (hd, inbuf, nblocks); 266 hd->count = 0; 267 hd->nblocks += nblocks; 268 inlen -= nblocks * 64; 269 inbuf += nblocks * 64; 270 } 271 _gcry_burn_stack (88+4*sizeof(void*)); 272 273 /* Save remaining bytes. */ 274 for (; inlen && hd->count < 64; inlen--) 275 hd->buf[hd->count++] = *inbuf++; 276} 277 278 279/* The routine final terminates the computation and 280 * returns the digest. 281 * The handle is prepared for a new cycle, but adding bytes to the 282 * handle will the destroy the returned buffer. 283 * Returns: 20 bytes representing the digest. 284 */ 285 286static void 287sha1_final(void *context) 288{ 289 SHA1_CONTEXT *hd = context; 290 291 u32 t, msb, lsb; 292 unsigned char *p; 293 294 sha1_write(hd, NULL, 0); /* flush */; 295 296 t = hd->nblocks; 297 /* multiply by 64 to make a byte count */ 298 lsb = t << 6; 299 msb = t >> 26; 300 /* add the count */ 301 t = lsb; 302 if( (lsb += hd->count) < t ) 303 msb++; 304 /* multiply by 8 to make a bit count */ 305 t = lsb; 306 lsb <<= 3; 307 msb <<= 3; 308 msb |= t >> 29; 309 310 if( hd->count < 56 ) /* enough room */ 311 { 312 hd->buf[hd->count++] = 0x80; /* pad */ 313 while( hd->count < 56 ) 314 hd->buf[hd->count++] = 0; /* pad */ 315 } 316 else /* need one extra block */ 317 { 318 hd->buf[hd->count++] = 0x80; /* pad character */ 319 while( hd->count < 64 ) 320 hd->buf[hd->count++] = 0; 321 sha1_write(hd, NULL, 0); /* flush */; 322 memset(hd->buf, 0, 56 ); /* fill next block with zeroes */ 323 } 324 /* append the 64 bit count */ 325 hd->buf[56] = msb >> 24; 326 hd->buf[57] = msb >> 16; 327 hd->buf[58] = msb >> 8; 328 hd->buf[59] = msb ; 329 hd->buf[60] = lsb >> 24; 330 hd->buf[61] = lsb >> 16; 331 hd->buf[62] = lsb >> 8; 332 hd->buf[63] = lsb ; 333 TRANSFORM( hd, hd->buf, 1 ); 334 _gcry_burn_stack (88+4*sizeof(void*)); 335 336 p = hd->buf; 337#ifdef WORDS_BIGENDIAN 338#define X(a) do { *(u32*)p = hd->h##a ; p += 4; } while(0) 339#else /* little endian */ 340#define X(a) do { *p++ = hd->h##a >> 24; *p++ = hd->h##a >> 16; \ 341 *p++ = hd->h##a >> 8; *p++ = hd->h##a; } while(0) 342#endif 343 X(0); 344 X(1); 345 X(2); 346 X(3); 347 X(4); 348#undef X 349 350} 351 352static unsigned char * 353sha1_read( void *context ) 354{ 355 SHA1_CONTEXT *hd = context; 356 357 return hd->buf; 358} 359 360/**************** 361 * Shortcut functions which puts the hash value of the supplied buffer 362 * into outbuf which must have a size of 20 bytes. 363 */ 364void 365_gcry_sha1_hash_buffer (void *outbuf, const void *buffer, size_t length) 366{ 367 SHA1_CONTEXT hd; 368 369 sha1_init (&hd); 370 sha1_write (&hd, buffer, length); 371 sha1_final (&hd); 372 memcpy (outbuf, hd.buf, 20); 373} 374 375 376 377/* 378 Self-test section. 379 */ 380 381 382static gpg_err_code_t 383selftests_sha1 (int extended, selftest_report_func_t report) 384{ 385 const char *what; 386 const char *errtxt; 387 388 what = "short string"; 389 errtxt = _gcry_hash_selftest_check_one 390 (GCRY_MD_SHA1, 0, 391 "abc", 3, 392 "\xA9\x99\x3E\x36\x47\x06\x81\x6A\xBA\x3E" 393 "\x25\x71\x78\x50\xC2\x6C\x9C\xD0\xD8\x9D", 20); 394 if (errtxt) 395 goto failed; 396 397 if (extended) 398 { 399 what = "long string"; 400 errtxt = _gcry_hash_selftest_check_one 401 (GCRY_MD_SHA1, 0, 402 "abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq", 56, 403 "\x84\x98\x3E\x44\x1C\x3B\xD2\x6E\xBA\xAE" 404 "\x4A\xA1\xF9\x51\x29\xE5\xE5\x46\x70\xF1", 20); 405 if (errtxt) 406 goto failed; 407 408 what = "one million \"a\""; 409 errtxt = _gcry_hash_selftest_check_one 410 (GCRY_MD_SHA1, 1, 411 NULL, 0, 412 "\x34\xAA\x97\x3C\xD4\xC4\xDA\xA4\xF6\x1E" 413 "\xEB\x2B\xDB\xAD\x27\x31\x65\x34\x01\x6F", 20); 414 if (errtxt) 415 goto failed; 416 } 417 418 return 0; /* Succeeded. */ 419 420 failed: 421 if (report) 422 report ("digest", GCRY_MD_SHA1, what, errtxt); 423 return GPG_ERR_SELFTEST_FAILED; 424} 425 426 427/* Run a full self-test for ALGO and return 0 on success. */ 428static gpg_err_code_t 429run_selftests (int algo, int extended, selftest_report_func_t report) 430{ 431 gpg_err_code_t ec; 432 433 switch (algo) 434 { 435 case GCRY_MD_SHA1: 436 ec = selftests_sha1 (extended, report); 437 break; 438 default: 439 ec = GPG_ERR_DIGEST_ALGO; 440 break; 441 442 } 443 return ec; 444} 445 446 447 448 449static unsigned char asn[15] = /* Object ID is 1.3.14.3.2.26 */ 450 { 0x30, 0x21, 0x30, 0x09, 0x06, 0x05, 0x2b, 0x0e, 0x03, 451 0x02, 0x1a, 0x05, 0x00, 0x04, 0x14 }; 452 453static gcry_md_oid_spec_t oid_spec_sha1[] = 454 { 455 /* iso.member-body.us.rsadsi.pkcs.pkcs-1.5 (sha1WithRSAEncryption) */ 456 { "1.2.840.113549.1.1.5" }, 457 /* iso.member-body.us.x9-57.x9cm.3 (dsaWithSha1)*/ 458 { "1.2.840.10040.4.3" }, 459 /* from NIST's OIW (sha1) */ 460 { "1.3.14.3.2.26" }, 461 /* from NIST OIW (sha-1WithRSAEncryption) */ 462 { "1.3.14.3.2.29" }, 463 /* iso.member-body.us.ansi-x9-62.signatures.ecdsa-with-sha1 */ 464 { "1.2.840.10045.4.1" }, 465 { NULL }, 466 }; 467 468gcry_md_spec_t _gcry_digest_spec_sha1 = 469 { 470 "SHA1", asn, DIM (asn), oid_spec_sha1, 20, 471 sha1_init, sha1_write, sha1_final, sha1_read, 472 sizeof (SHA1_CONTEXT) 473 }; 474md_extra_spec_t _gcry_digest_extraspec_sha1 = 475 { 476 run_selftests 477 }; 478