sha1.c (16255B)
1 /* 2 This file is part of libmicrohttpd 3 Copyright (C) 2019-2022 Karlson2k (Evgeny Grin) 4 5 libmicrohttpd is free software; you can redistribute it and/or 6 modify it under the terms of the GNU Lesser General Public 7 License as published by the Free Software Foundation; either 8 version 2.1 of the License, or (at your option) any later version. 9 10 This library is distributed in the hope that it will be useful, 11 but WITHOUT ANY WARRANTY; without even the implied warranty of 12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 13 Lesser General Public License for more details. 14 15 You should have received a copy of the GNU Lesser General Public 16 License along with this library. 17 If not, see <http://www.gnu.org/licenses/>. 18 */ 19 20 /** 21 * @file microhttpd/sha1.c 22 * @brief Calculation of SHA-1 digest as defined in FIPS PUB 180-4 (2015) 23 * @author Karlson2k (Evgeny Grin) 24 */ 25 26 #include "sha1.h" 27 28 #include <string.h> 29 #ifdef HAVE_MEMORY_H 30 #include <memory.h> 31 #endif /* HAVE_MEMORY_H */ 32 #include "mhd_bithelpers.h" 33 #include "mhd_assert.h" 34 35 /** 36 * Initialise structure for SHA-1 calculation. 37 * 38 * @param ctx_ must be a `struct sha1_ctx *` 39 */ 40 void 41 MHD_SHA1_init (void *ctx_) 42 { 43 struct sha1_ctx *const ctx = ctx_; 44 /* Initial hash values, see FIPS PUB 180-4 paragraph 5.3.1 */ 45 /* Just some "magic" numbers defined by standard */ 46 ctx->H[0] = UINT32_C (0x67452301); 47 ctx->H[1] = UINT32_C (0xefcdab89); 48 ctx->H[2] = UINT32_C (0x98badcfe); 49 ctx->H[3] = UINT32_C (0x10325476); 50 ctx->H[4] = UINT32_C (0xc3d2e1f0); 51 52 /* Initialise number of bytes. */ 53 ctx->count = 0; 54 } 55 56 57 /** 58 * Base of SHA-1 transformation. 59 * Gets full 512 bits / 64 bytes block of data and updates hash values; 60 * @param H hash values 61 * @param data data, must be exactly 64 bytes long 62 */ 63 static void 64 sha1_transform (uint32_t H[_SHA1_DIGEST_LENGTH], 65 const uint8_t data[SHA1_BLOCK_SIZE]) 66 { 67 /* Working variables, 68 see FIPS PUB 180-4 paragraph 6.1.3 */ 69 uint32_t a = H[0]; 70 uint32_t b = H[1]; 71 uint32_t c = H[2]; 72 uint32_t d = H[3]; 73 uint32_t e = H[4]; 74 75 /* Data buffer, used as cyclic buffer. 76 See FIPS PUB 180-4 paragraphs 5.2.1, 6.1.3 */ 77 uint32_t W[16]; 78 79 /* 'Ch' and 'Maj' macro functions are defined with 80 widely-used optimization. 81 See FIPS PUB 180-4 formulae 4.1. */ 82 #define Ch(x,y,z) ( (z) ^ ((x) & ((y) ^ (z))) ) 83 #define Maj(x,y,z) ( ((x) & (y)) ^ ((z) & ((x) ^ (y))) ) 84 /* Unoptimized (original) versions: */ 85 /* #define Ch(x,y,z) ( ( (x) & (y) ) ^ ( ~(x) & (z) ) ) */ 86 /* #define Maj(x,y,z) ( ((x) & (y)) ^ ((x) & (z)) ^ ((y) & (z)) ) */ 87 #define Par(x,y,z) ( (x) ^ (y) ^ (z) ) 88 89 /* Single step of SHA-1 computation, 90 see FIPS PUB 180-4 paragraph 6.1.3 step 3. 91 * Note: instead of reassigning all working variables on each step, 92 variables are rotated for each step: 93 SHA1STEP32 (a, b, c, d, e, func, K00, W[0]); 94 SHA1STEP32 (e, a, b, c, d, func, K00, W[1]); 95 so current 'vC' will be used as 'vD' on the next step, 96 current 'vE' will be used as 'vA' on the next step. 97 * Note: 'wt' must be used exactly one time in this macro as it change other data as well 98 every time when used. */ 99 100 #define SHA1STEP32(vA,vB,vC,vD,vE,ft,kt,wt) do { \ 101 (vE) += _MHD_ROTL32 ((vA), 5) + ft ((vB), (vC), (vD)) + (kt) + (wt); \ 102 (vB) = _MHD_ROTL32 ((vB), 30); } while (0) 103 104 /* Get value of W(t) from input data buffer, 105 See FIPS PUB 180-4 paragraph 6.1.3. 106 Input data must be read in big-endian bytes order, 107 see FIPS PUB 180-4 paragraph 3.1.2. */ 108 /* Use cast to (void*) to mute compiler alignment warning, 109 * data was already aligned in previous step */ 110 #define GET_W_FROM_DATA(buf,t) \ 111 _MHD_GET_32BIT_BE ((const void *)(((const uint8_t*) (buf)) + \ 112 (t) * SHA1_BYTES_IN_WORD)) 113 114 #ifndef _MHD_GET_32BIT_BE_UNALIGNED 115 if (0 != (((uintptr_t) data) % _MHD_UINT32_ALIGN)) 116 { 117 /* Copy the unaligned input data to the aligned buffer */ 118 memcpy (W, data, SHA1_BLOCK_SIZE); 119 /* The W[] buffer itself will be used as the source of the data, 120 * but data will be reloaded in correct bytes order during 121 * the next steps */ 122 data = (uint8_t *) W; 123 } 124 #endif /* _MHD_GET_32BIT_BE_UNALIGNED */ 125 126 /* SHA-1 values of Kt for t=0..19, see FIPS PUB 180-4 paragraph 4.2.1. */ 127 #define K00 UINT32_C(0x5a827999) 128 /* SHA-1 values of Kt for t=20..39, see FIPS PUB 180-4 paragraph 4.2.1.*/ 129 #define K20 UINT32_C(0x6ed9eba1) 130 /* SHA-1 values of Kt for t=40..59, see FIPS PUB 180-4 paragraph 4.2.1.*/ 131 #define K40 UINT32_C(0x8f1bbcdc) 132 /* SHA-1 values of Kt for t=60..79, see FIPS PUB 180-4 paragraph 4.2.1.*/ 133 #define K60 UINT32_C(0xca62c1d6) 134 135 /* During first 16 steps, before making any calculations on each step, 136 the W element is read from input data buffer as big-endian value and 137 stored in array of W elements. */ 138 /* Note: instead of using K constants as array, all K values are specified 139 individually for each step. */ 140 SHA1STEP32 (a, b, c, d, e, Ch, K00, W[0] = GET_W_FROM_DATA (data, 0)); 141 SHA1STEP32 (e, a, b, c, d, Ch, K00, W[1] = GET_W_FROM_DATA (data, 1)); 142 SHA1STEP32 (d, e, a, b, c, Ch, K00, W[2] = GET_W_FROM_DATA (data, 2)); 143 SHA1STEP32 (c, d, e, a, b, Ch, K00, W[3] = GET_W_FROM_DATA (data, 3)); 144 SHA1STEP32 (b, c, d, e, a, Ch, K00, W[4] = GET_W_FROM_DATA (data, 4)); 145 SHA1STEP32 (a, b, c, d, e, Ch, K00, W[5] = GET_W_FROM_DATA (data, 5)); 146 SHA1STEP32 (e, a, b, c, d, Ch, K00, W[6] = GET_W_FROM_DATA (data, 6)); 147 SHA1STEP32 (d, e, a, b, c, Ch, K00, W[7] = GET_W_FROM_DATA (data, 7)); 148 SHA1STEP32 (c, d, e, a, b, Ch, K00, W[8] = GET_W_FROM_DATA (data, 8)); 149 SHA1STEP32 (b, c, d, e, a, Ch, K00, W[9] = GET_W_FROM_DATA (data, 9)); 150 SHA1STEP32 (a, b, c, d, e, Ch, K00, W[10] = GET_W_FROM_DATA (data, 10)); 151 SHA1STEP32 (e, a, b, c, d, Ch, K00, W[11] = GET_W_FROM_DATA (data, 11)); 152 SHA1STEP32 (d, e, a, b, c, Ch, K00, W[12] = GET_W_FROM_DATA (data, 12)); 153 SHA1STEP32 (c, d, e, a, b, Ch, K00, W[13] = GET_W_FROM_DATA (data, 13)); 154 SHA1STEP32 (b, c, d, e, a, Ch, K00, W[14] = GET_W_FROM_DATA (data, 14)); 155 SHA1STEP32 (a, b, c, d, e, Ch, K00, W[15] = GET_W_FROM_DATA (data, 15)); 156 157 /* 'W' generation and assignment for 16 <= t <= 79. 158 See FIPS PUB 180-4 paragraph 6.1.3. 159 As only last 16 'W' are used in calculations, it is possible to 160 use 16 elements array of W as cyclic buffer. */ 161 #define Wgen(w,t) _MHD_ROTL32((w)[(t + 13) & 0xf] ^ (w)[(t + 8) & 0xf] \ 162 ^ (w)[(t + 2) & 0xf] ^ (w)[t & 0xf], 1) 163 164 /* During last 60 steps, before making any calculations on each step, 165 W element is generated from W elements of cyclic buffer and generated value 166 stored back in cyclic buffer. */ 167 /* Note: instead of using K constants as array, all K values are specified 168 individually for each step, see FIPS PUB 180-4 paragraph 4.2.1. */ 169 SHA1STEP32 (e, a, b, c, d, Ch, K00, W[16 & 0xf] = Wgen (W, 16)); 170 SHA1STEP32 (d, e, a, b, c, Ch, K00, W[17 & 0xf] = Wgen (W, 17)); 171 SHA1STEP32 (c, d, e, a, b, Ch, K00, W[18 & 0xf] = Wgen (W, 18)); 172 SHA1STEP32 (b, c, d, e, a, Ch, K00, W[19 & 0xf] = Wgen (W, 19)); 173 SHA1STEP32 (a, b, c, d, e, Par, K20, W[20 & 0xf] = Wgen (W, 20)); 174 SHA1STEP32 (e, a, b, c, d, Par, K20, W[21 & 0xf] = Wgen (W, 21)); 175 SHA1STEP32 (d, e, a, b, c, Par, K20, W[22 & 0xf] = Wgen (W, 22)); 176 SHA1STEP32 (c, d, e, a, b, Par, K20, W[23 & 0xf] = Wgen (W, 23)); 177 SHA1STEP32 (b, c, d, e, a, Par, K20, W[24 & 0xf] = Wgen (W, 24)); 178 SHA1STEP32 (a, b, c, d, e, Par, K20, W[25 & 0xf] = Wgen (W, 25)); 179 SHA1STEP32 (e, a, b, c, d, Par, K20, W[26 & 0xf] = Wgen (W, 26)); 180 SHA1STEP32 (d, e, a, b, c, Par, K20, W[27 & 0xf] = Wgen (W, 27)); 181 SHA1STEP32 (c, d, e, a, b, Par, K20, W[28 & 0xf] = Wgen (W, 28)); 182 SHA1STEP32 (b, c, d, e, a, Par, K20, W[29 & 0xf] = Wgen (W, 29)); 183 SHA1STEP32 (a, b, c, d, e, Par, K20, W[30 & 0xf] = Wgen (W, 30)); 184 SHA1STEP32 (e, a, b, c, d, Par, K20, W[31 & 0xf] = Wgen (W, 31)); 185 SHA1STEP32 (d, e, a, b, c, Par, K20, W[32 & 0xf] = Wgen (W, 32)); 186 SHA1STEP32 (c, d, e, a, b, Par, K20, W[33 & 0xf] = Wgen (W, 33)); 187 SHA1STEP32 (b, c, d, e, a, Par, K20, W[34 & 0xf] = Wgen (W, 34)); 188 SHA1STEP32 (a, b, c, d, e, Par, K20, W[35 & 0xf] = Wgen (W, 35)); 189 SHA1STEP32 (e, a, b, c, d, Par, K20, W[36 & 0xf] = Wgen (W, 36)); 190 SHA1STEP32 (d, e, a, b, c, Par, K20, W[37 & 0xf] = Wgen (W, 37)); 191 SHA1STEP32 (c, d, e, a, b, Par, K20, W[38 & 0xf] = Wgen (W, 38)); 192 SHA1STEP32 (b, c, d, e, a, Par, K20, W[39 & 0xf] = Wgen (W, 39)); 193 SHA1STEP32 (a, b, c, d, e, Maj, K40, W[40 & 0xf] = Wgen (W, 40)); 194 SHA1STEP32 (e, a, b, c, d, Maj, K40, W[41 & 0xf] = Wgen (W, 41)); 195 SHA1STEP32 (d, e, a, b, c, Maj, K40, W[42 & 0xf] = Wgen (W, 42)); 196 SHA1STEP32 (c, d, e, a, b, Maj, K40, W[43 & 0xf] = Wgen (W, 43)); 197 SHA1STEP32 (b, c, d, e, a, Maj, K40, W[44 & 0xf] = Wgen (W, 44)); 198 SHA1STEP32 (a, b, c, d, e, Maj, K40, W[45 & 0xf] = Wgen (W, 45)); 199 SHA1STEP32 (e, a, b, c, d, Maj, K40, W[46 & 0xf] = Wgen (W, 46)); 200 SHA1STEP32 (d, e, a, b, c, Maj, K40, W[47 & 0xf] = Wgen (W, 47)); 201 SHA1STEP32 (c, d, e, a, b, Maj, K40, W[48 & 0xf] = Wgen (W, 48)); 202 SHA1STEP32 (b, c, d, e, a, Maj, K40, W[49 & 0xf] = Wgen (W, 49)); 203 SHA1STEP32 (a, b, c, d, e, Maj, K40, W[50 & 0xf] = Wgen (W, 50)); 204 SHA1STEP32 (e, a, b, c, d, Maj, K40, W[51 & 0xf] = Wgen (W, 51)); 205 SHA1STEP32 (d, e, a, b, c, Maj, K40, W[52 & 0xf] = Wgen (W, 52)); 206 SHA1STEP32 (c, d, e, a, b, Maj, K40, W[53 & 0xf] = Wgen (W, 53)); 207 SHA1STEP32 (b, c, d, e, a, Maj, K40, W[54 & 0xf] = Wgen (W, 54)); 208 SHA1STEP32 (a, b, c, d, e, Maj, K40, W[55 & 0xf] = Wgen (W, 55)); 209 SHA1STEP32 (e, a, b, c, d, Maj, K40, W[56 & 0xf] = Wgen (W, 56)); 210 SHA1STEP32 (d, e, a, b, c, Maj, K40, W[57 & 0xf] = Wgen (W, 57)); 211 SHA1STEP32 (c, d, e, a, b, Maj, K40, W[58 & 0xf] = Wgen (W, 58)); 212 SHA1STEP32 (b, c, d, e, a, Maj, K40, W[59 & 0xf] = Wgen (W, 59)); 213 SHA1STEP32 (a, b, c, d, e, Par, K60, W[60 & 0xf] = Wgen (W, 60)); 214 SHA1STEP32 (e, a, b, c, d, Par, K60, W[61 & 0xf] = Wgen (W, 61)); 215 SHA1STEP32 (d, e, a, b, c, Par, K60, W[62 & 0xf] = Wgen (W, 62)); 216 SHA1STEP32 (c, d, e, a, b, Par, K60, W[63 & 0xf] = Wgen (W, 63)); 217 SHA1STEP32 (b, c, d, e, a, Par, K60, W[64 & 0xf] = Wgen (W, 64)); 218 SHA1STEP32 (a, b, c, d, e, Par, K60, W[65 & 0xf] = Wgen (W, 65)); 219 SHA1STEP32 (e, a, b, c, d, Par, K60, W[66 & 0xf] = Wgen (W, 66)); 220 SHA1STEP32 (d, e, a, b, c, Par, K60, W[67 & 0xf] = Wgen (W, 67)); 221 SHA1STEP32 (c, d, e, a, b, Par, K60, W[68 & 0xf] = Wgen (W, 68)); 222 SHA1STEP32 (b, c, d, e, a, Par, K60, W[69 & 0xf] = Wgen (W, 69)); 223 SHA1STEP32 (a, b, c, d, e, Par, K60, W[70 & 0xf] = Wgen (W, 70)); 224 SHA1STEP32 (e, a, b, c, d, Par, K60, W[71 & 0xf] = Wgen (W, 71)); 225 SHA1STEP32 (d, e, a, b, c, Par, K60, W[72 & 0xf] = Wgen (W, 72)); 226 SHA1STEP32 (c, d, e, a, b, Par, K60, W[73 & 0xf] = Wgen (W, 73)); 227 SHA1STEP32 (b, c, d, e, a, Par, K60, W[74 & 0xf] = Wgen (W, 74)); 228 SHA1STEP32 (a, b, c, d, e, Par, K60, W[75 & 0xf] = Wgen (W, 75)); 229 SHA1STEP32 (e, a, b, c, d, Par, K60, W[76 & 0xf] = Wgen (W, 76)); 230 SHA1STEP32 (d, e, a, b, c, Par, K60, W[77 & 0xf] = Wgen (W, 77)); 231 SHA1STEP32 (c, d, e, a, b, Par, K60, W[78 & 0xf] = Wgen (W, 78)); 232 SHA1STEP32 (b, c, d, e, a, Par, K60, W[79 & 0xf] = Wgen (W, 79)); 233 234 /* Compute intermediate hash. 235 See FIPS PUB 180-4 paragraph 6.1.3 step 4. */ 236 H[0] += a; 237 H[1] += b; 238 H[2] += c; 239 H[3] += d; 240 H[4] += e; 241 } 242 243 244 /** 245 * Process portion of bytes. 246 * 247 * @param ctx_ must be a `struct sha1_ctx *` 248 * @param data bytes to add to hash 249 * @param length number of bytes in @a data 250 */ 251 void 252 MHD_SHA1_update (void *ctx_, 253 const uint8_t *data, 254 size_t length) 255 { 256 struct sha1_ctx *const ctx = ctx_; 257 unsigned bytes_have; /**< Number of bytes in buffer */ 258 259 mhd_assert ((data != NULL) || (length == 0)); 260 261 if (0 == length) 262 return; /* Do nothing */ 263 264 /* Note: (count & (SHA1_BLOCK_SIZE-1)) 265 equal (count % SHA1_BLOCK_SIZE) for this block size. */ 266 bytes_have = (unsigned) (ctx->count & (SHA1_BLOCK_SIZE - 1)); 267 ctx->count += length; 268 269 if (0 != bytes_have) 270 { 271 unsigned bytes_left = SHA1_BLOCK_SIZE - bytes_have; 272 if (length >= bytes_left) 273 { /* Combine new data with the data in the buffer and 274 process the full block. */ 275 memcpy (ctx->buffer + bytes_have, 276 data, 277 bytes_left); 278 data += bytes_left; 279 length -= bytes_left; 280 sha1_transform (ctx->H, ctx->buffer); 281 bytes_have = 0; 282 } 283 } 284 285 while (SHA1_BLOCK_SIZE <= length) 286 { /* Process any full blocks of new data directly, 287 without copying to the buffer. */ 288 sha1_transform (ctx->H, data); 289 data += SHA1_BLOCK_SIZE; 290 length -= SHA1_BLOCK_SIZE; 291 } 292 293 if (0 != length) 294 { /* Copy incomplete block of new data (if any) 295 to the buffer. */ 296 memcpy (ctx->buffer + bytes_have, data, length); 297 } 298 } 299 300 301 /** 302 * Size of "length" padding addition in bytes. 303 * See FIPS PUB 180-4 paragraph 5.1.1. 304 */ 305 #define SHA1_SIZE_OF_LEN_ADD (64 / 8) 306 307 /** 308 * Finalise SHA-1 calculation, return digest. 309 * 310 * @param ctx_ must be a `struct sha1_ctx *` 311 * @param[out] digest set to the hash, must be #SHA1_DIGEST_SIZE bytes 312 */ 313 void 314 MHD_SHA1_finish (void *ctx_, 315 uint8_t digest[SHA1_DIGEST_SIZE]) 316 { 317 struct sha1_ctx *const ctx = ctx_; 318 uint64_t num_bits; /**< Number of processed bits */ 319 unsigned bytes_have; /**< Number of bytes in buffer */ 320 321 num_bits = ctx->count << 3; 322 /* Note: (count & (SHA1_BLOCK_SIZE-1)) 323 equals (count % SHA1_BLOCK_SIZE) for this block size. */ 324 bytes_have = (unsigned) (ctx->count & (SHA1_BLOCK_SIZE - 1)); 325 326 /* Input data must be padded with bit "1" and with length of data in bits. 327 See FIPS PUB 180-4 paragraph 5.1.1. */ 328 /* Data is always processed in form of bytes (not by individual bits), 329 therefore position of first padding bit in byte is always predefined (0x80). */ 330 /* Buffer always have space at least for one byte (as full buffers are 331 processed immediately). */ 332 ctx->buffer[bytes_have++] = 0x80; 333 334 if (SHA1_BLOCK_SIZE - bytes_have < SHA1_SIZE_OF_LEN_ADD) 335 { /* No space in current block to put total length of message. 336 Pad current block with zeros and process it. */ 337 if (SHA1_BLOCK_SIZE > bytes_have) 338 memset (ctx->buffer + bytes_have, 0, SHA1_BLOCK_SIZE - bytes_have); 339 /* Process full block. */ 340 sha1_transform (ctx->H, ctx->buffer); 341 /* Start new block. */ 342 bytes_have = 0; 343 } 344 345 /* Pad the rest of the buffer with zeros. */ 346 memset (ctx->buffer + bytes_have, 0, 347 SHA1_BLOCK_SIZE - SHA1_SIZE_OF_LEN_ADD - bytes_have); 348 /* Put the number of bits in the processed message as a big-endian value. */ 349 _MHD_PUT_64BIT_BE_SAFE (ctx->buffer + SHA1_BLOCK_SIZE - SHA1_SIZE_OF_LEN_ADD, 350 num_bits); 351 /* Process the full final block. */ 352 sha1_transform (ctx->H, ctx->buffer); 353 354 /* Put final hash/digest in BE mode */ 355 #ifndef _MHD_PUT_32BIT_BE_UNALIGNED 356 if (0 != ((uintptr_t) digest) % _MHD_UINT32_ALIGN) 357 { 358 uint32_t alig_dgst[_SHA1_DIGEST_LENGTH]; 359 _MHD_PUT_32BIT_BE (alig_dgst + 0, ctx->H[0]); 360 _MHD_PUT_32BIT_BE (alig_dgst + 1, ctx->H[1]); 361 _MHD_PUT_32BIT_BE (alig_dgst + 2, ctx->H[2]); 362 _MHD_PUT_32BIT_BE (alig_dgst + 3, ctx->H[3]); 363 _MHD_PUT_32BIT_BE (alig_dgst + 4, ctx->H[4]); 364 /* Copy result to unaligned destination address */ 365 memcpy (digest, alig_dgst, SHA1_DIGEST_SIZE); 366 } 367 else 368 #else /* _MHD_PUT_32BIT_BE_UNALIGNED */ 369 if (1) 370 #endif /* _MHD_PUT_32BIT_BE_UNALIGNED */ 371 { 372 /* Use cast to (void*) here to mute compiler alignment warnings. 373 * Compilers are not smart enough to see that alignment has been checked. */ 374 _MHD_PUT_32BIT_BE ((void *) (digest + 0 * SHA1_BYTES_IN_WORD), ctx->H[0]); 375 _MHD_PUT_32BIT_BE ((void *) (digest + 1 * SHA1_BYTES_IN_WORD), ctx->H[1]); 376 _MHD_PUT_32BIT_BE ((void *) (digest + 2 * SHA1_BYTES_IN_WORD), ctx->H[2]); 377 _MHD_PUT_32BIT_BE ((void *) (digest + 3 * SHA1_BYTES_IN_WORD), ctx->H[3]); 378 _MHD_PUT_32BIT_BE ((void *) (digest + 4 * SHA1_BYTES_IN_WORD), ctx->H[4]); 379 } 380 381 /* Erase potentially sensitive data. */ 382 memset (ctx, 0, sizeof(struct sha1_ctx)); 383 }