satsolver 0.16.3
|
00001 /* 00002 SHA-1 in C 00003 By Steve Reid <sreid@sea-to-sky.net> 00004 100% Public Domain 00005 00006 ----------------- 00007 Modified 7/98 00008 By James H. Brown <jbrown@burgoyne.com> 00009 Still 100% Public Domain 00010 00011 Corrected a problem which generated improper hash values on 16 bit machines 00012 Routine SHA1Update changed from 00013 void SHA1Update(SHA1_CTX* context, unsigned char* data, unsigned int 00014 len) 00015 to 00016 void SHA1Update(SHA1_CTX* context, unsigned char* data, unsigned 00017 long len) 00018 00019 The 'len' parameter was declared an int which works fine on 32 bit machines. 00020 However, on 16 bit machines an int is too small for the shifts being done 00021 against 00022 it. This caused the hash function to generate incorrect values if len was 00023 greater than 8191 (8K - 1) due to the 'len << 3' on line 3 of SHA1Update(). 00024 00025 Since the file IO in main() reads 16K at a time, any file 8K or larger would 00026 be guaranteed to generate the wrong hash (e.g. Test Vector #3, a million 00027 "a"s). 00028 00029 I also changed the declaration of variables i & j in SHA1Update to 00030 unsigned long from unsigned int for the same reason. 00031 00032 These changes should make no difference to any 32 bit implementations since 00033 an 00034 int and a long are the same size in those environments. 00035 00036 -- 00037 I also corrected a few compiler warnings generated by Borland C. 00038 1. Added #include <process.h> for exit() prototype 00039 2. Removed unused variable 'j' in SHA1Final 00040 3. Changed exit(0) to return(0) at end of main. 00041 00042 ALL changes I made can be located by searching for comments containing 'JHB' 00043 ----------------- 00044 Modified 8/98 00045 By Steve Reid <sreid@sea-to-sky.net> 00046 Still 100% public domain 00047 00048 1- Removed #include <process.h> and used return() instead of exit() 00049 2- Fixed overwriting of finalcount in SHA1Final() (discovered by Chris Hall) 00050 3- Changed email address from steve@edmweb.com to sreid@sea-to-sky.net 00051 00052 ----------------- 00053 Modified 4/01 00054 By Saul Kravitz <Saul.Kravitz@celera.com> 00055 Still 100% PD 00056 Modified to run on Compaq Alpha hardware. 00057 00058 ----------------- 00059 Modified 07/2002 00060 By Ralph Giles <giles@ghostscript.com> 00061 Still 100% public domain 00062 modified for use with stdint types, autoconf 00063 code cleanup, removed attribution comments 00064 switched SHA1Final() argument order for consistency 00065 use SHA1_ prefix for public api 00066 move public api to sha1.h 00067 */ 00068 00069 /* 00070 Test Vectors (from FIPS PUB 180-1) 00071 "abc" 00072 A9993E36 4706816A BA3E2571 7850C26C 9CD0D89D 00073 "abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq" 00074 84983E44 1C3BD26E BAAE4AA1 F95129E5 E54670F1 00075 A million repetitions of "a" 00076 34AA973C D4C4DAA4 F61EEB2B DBAD2731 6534016F 00077 */ 00078 00079 #include <stdio.h> 00080 #include <string.h> 00081 #include <endian.h> 00082 #include "sha1.h" 00083 00084 00085 static void SHA1_Transform(uint32_t state[5], const uint8_t buffer[64]); 00086 00087 #define rol(value, bits) (((value) << (bits)) | ((value) >> (32 - (bits)))) 00088 00089 /* blk0() and blk() perform the initial expand. */ 00090 /* I got the idea of expanding during the round function from SSLeay */ 00091 /* FIXME: can we do this in an endian-proof way? */ 00092 #if __BYTE_ORDER == __BIG_ENDIAN 00093 #define blk0(i) block.l[i] 00094 #else 00095 #define blk0(i) (block.l[i] = (rol(block.l[i],24)&0xFF00FF00) \ 00096 |(rol(block.l[i],8)&0x00FF00FF)) 00097 #endif 00098 #define blk(i) (block.l[i&15] = rol(block.l[(i+13)&15]^block.l[(i+8)&15] \ 00099 ^block.l[(i+2)&15]^block.l[i&15],1)) 00100 00101 /* (R0+R1), R2, R3, R4 are the different operations used in SHA1 */ 00102 #define R0(v,w,x,y,z,i) z+=((w&(x^y))^y)+blk0(i)+0x5A827999+rol(v,5);w=rol(w,30); 00103 #define R1(v,w,x,y,z,i) z+=((w&(x^y))^y)+blk(i)+0x5A827999+rol(v,5);w=rol(w,30); 00104 #define R2(v,w,x,y,z,i) z+=(w^x^y)+blk(i)+0x6ED9EBA1+rol(v,5);w=rol(w,30); 00105 #define R3(v,w,x,y,z,i) z+=(((w|x)&y)|(w&x))+blk(i)+0x8F1BBCDC+rol(v,5);w=rol(w,30); 00106 #define R4(v,w,x,y,z,i) z+=(w^x^y)+blk(i)+0xCA62C1D6+rol(v,5);w=rol(w,30); 00107 00108 00109 /* Hash a single 512-bit block. This is the core of the algorithm. */ 00110 static void SHA1_Transform(uint32_t state[5], const uint8_t buffer[64]) 00111 { 00112 uint32_t a, b, c, d, e; 00113 typedef union { 00114 uint8_t c[64]; 00115 uint32_t l[16]; 00116 } CHAR64LONG16; 00117 CHAR64LONG16 block; 00118 00119 memcpy(&block, buffer, 64); 00120 00121 /* Copy context->state[] to working vars */ 00122 a = state[0]; 00123 b = state[1]; 00124 c = state[2]; 00125 d = state[3]; 00126 e = state[4]; 00127 00128 /* 4 rounds of 20 operations each. Loop unrolled. */ 00129 R0(a,b,c,d,e, 0); R0(e,a,b,c,d, 1); R0(d,e,a,b,c, 2); R0(c,d,e,a,b, 3); 00130 R0(b,c,d,e,a, 4); R0(a,b,c,d,e, 5); R0(e,a,b,c,d, 6); R0(d,e,a,b,c, 7); 00131 R0(c,d,e,a,b, 8); R0(b,c,d,e,a, 9); R0(a,b,c,d,e,10); R0(e,a,b,c,d,11); 00132 R0(d,e,a,b,c,12); R0(c,d,e,a,b,13); R0(b,c,d,e,a,14); R0(a,b,c,d,e,15); 00133 R1(e,a,b,c,d,16); R1(d,e,a,b,c,17); R1(c,d,e,a,b,18); R1(b,c,d,e,a,19); 00134 R2(a,b,c,d,e,20); R2(e,a,b,c,d,21); R2(d,e,a,b,c,22); R2(c,d,e,a,b,23); 00135 R2(b,c,d,e,a,24); R2(a,b,c,d,e,25); R2(e,a,b,c,d,26); R2(d,e,a,b,c,27); 00136 R2(c,d,e,a,b,28); R2(b,c,d,e,a,29); R2(a,b,c,d,e,30); R2(e,a,b,c,d,31); 00137 R2(d,e,a,b,c,32); R2(c,d,e,a,b,33); R2(b,c,d,e,a,34); R2(a,b,c,d,e,35); 00138 R2(e,a,b,c,d,36); R2(d,e,a,b,c,37); R2(c,d,e,a,b,38); R2(b,c,d,e,a,39); 00139 R3(a,b,c,d,e,40); R3(e,a,b,c,d,41); R3(d,e,a,b,c,42); R3(c,d,e,a,b,43); 00140 R3(b,c,d,e,a,44); R3(a,b,c,d,e,45); R3(e,a,b,c,d,46); R3(d,e,a,b,c,47); 00141 R3(c,d,e,a,b,48); R3(b,c,d,e,a,49); R3(a,b,c,d,e,50); R3(e,a,b,c,d,51); 00142 R3(d,e,a,b,c,52); R3(c,d,e,a,b,53); R3(b,c,d,e,a,54); R3(a,b,c,d,e,55); 00143 R3(e,a,b,c,d,56); R3(d,e,a,b,c,57); R3(c,d,e,a,b,58); R3(b,c,d,e,a,59); 00144 R4(a,b,c,d,e,60); R4(e,a,b,c,d,61); R4(d,e,a,b,c,62); R4(c,d,e,a,b,63); 00145 R4(b,c,d,e,a,64); R4(a,b,c,d,e,65); R4(e,a,b,c,d,66); R4(d,e,a,b,c,67); 00146 R4(c,d,e,a,b,68); R4(b,c,d,e,a,69); R4(a,b,c,d,e,70); R4(e,a,b,c,d,71); 00147 R4(d,e,a,b,c,72); R4(c,d,e,a,b,73); R4(b,c,d,e,a,74); R4(a,b,c,d,e,75); 00148 R4(e,a,b,c,d,76); R4(d,e,a,b,c,77); R4(c,d,e,a,b,78); R4(b,c,d,e,a,79); 00149 00150 /* Add the working vars back into context.state[] */ 00151 state[0] += a; 00152 state[1] += b; 00153 state[2] += c; 00154 state[3] += d; 00155 state[4] += e; 00156 00157 /* Wipe variables */ 00158 a = b = c = d = e = 0; 00159 } 00160 00161 00162 /* SHA1Init - Initialize new context */ 00163 void sat_SHA1_Init(SHA1_CTX* context) 00164 { 00165 /* SHA1 initialization constants */ 00166 context->state[0] = 0x67452301; 00167 context->state[1] = 0xEFCDAB89; 00168 context->state[2] = 0x98BADCFE; 00169 context->state[3] = 0x10325476; 00170 context->state[4] = 0xC3D2E1F0; 00171 context->count[0] = context->count[1] = 0; 00172 } 00173 00174 00175 /* Run your data through this. */ 00176 void sat_SHA1_Update(SHA1_CTX* context, const uint8_t* data, const size_t len) 00177 { 00178 size_t i, j; 00179 00180 #ifdef VERBOSE 00181 SHAPrintContext(context, "before"); 00182 #endif 00183 00184 j = (context->count[0] >> 3) & 63; 00185 if ((context->count[0] += len << 3) < (len << 3)) context->count[1]++; 00186 context->count[1] += (len >> 29); 00187 if ((j + len) > 63) { 00188 memcpy(&context->buffer[j], data, (i = 64-j)); 00189 SHA1_Transform(context->state, context->buffer); 00190 for ( ; i + 63 < len; i += 64) { 00191 SHA1_Transform(context->state, data + i); 00192 } 00193 j = 0; 00194 } 00195 else i = 0; 00196 memcpy(&context->buffer[j], &data[i], len - i); 00197 00198 #ifdef VERBOSE 00199 SHAPrintContext(context, "after "); 00200 #endif 00201 } 00202 00203 00204 /* Add padding and return the message digest. */ 00205 void sat_SHA1_Final(SHA1_CTX* context, uint8_t digest[SHA1_DIGEST_SIZE]) 00206 { 00207 uint32_t i; 00208 uint8_t finalcount[8]; 00209 00210 for (i = 0; i < 8; i++) { 00211 finalcount[i] = (unsigned char)((context->count[(i >= 4 ? 0 : 1)] 00212 >> ((3-(i & 3)) * 8) ) & 255); /* Endian independent */ 00213 } 00214 sat_SHA1_Update(context, (uint8_t *)"\200", 1); 00215 while ((context->count[0] & 504) != 448) { 00216 sat_SHA1_Update(context, (uint8_t *)"\0", 1); 00217 } 00218 sat_SHA1_Update(context, finalcount, 8); /* Should cause a SHA1_Transform() */ 00219 for (i = 0; i < SHA1_DIGEST_SIZE; i++) { 00220 digest[i] = (uint8_t) 00221 ((context->state[i>>2] >> ((3-(i & 3)) * 8) ) & 255); 00222 } 00223 00224 /* Wipe variables */ 00225 i = 0; 00226 memset(context->buffer, 0, 64); 00227 memset(context->state, 0, 20); 00228 memset(context->count, 0, 8); 00229 memset(finalcount, 0, 8); /* SWR */ 00230 }