hash_impl.h
1 /*********************************************************************** 2 * Copyright (c) 2014 Pieter Wuille * 3 * Distributed under the MIT software license, see the accompanying * 4 * file COPYING or https://www.opensource.org/licenses/mit-license.php.* 5 ***********************************************************************/ 6 7 #ifndef SECP256K1_HASH_IMPL_H 8 #define SECP256K1_HASH_IMPL_H 9 10 #include "hash.h" 11 #include "util.h" 12 13 #include <stdlib.h> 14 #include <stdint.h> 15 #include <string.h> 16 17 #define Ch(x,y,z) ((z) ^ ((x) & ((y) ^ (z)))) 18 #define Maj(x,y,z) (((x) & (y)) | ((z) & ((x) | (y)))) 19 #define Sigma0(x) (((x) >> 2 | (x) << 30) ^ ((x) >> 13 | (x) << 19) ^ ((x) >> 22 | (x) << 10)) 20 #define Sigma1(x) (((x) >> 6 | (x) << 26) ^ ((x) >> 11 | (x) << 21) ^ ((x) >> 25 | (x) << 7)) 21 #define sigma0(x) (((x) >> 7 | (x) << 25) ^ ((x) >> 18 | (x) << 14) ^ ((x) >> 3)) 22 #define sigma1(x) (((x) >> 17 | (x) << 15) ^ ((x) >> 19 | (x) << 13) ^ ((x) >> 10)) 23 24 #define Round(a,b,c,d,e,f,g,h,k,w) do { \ 25 uint32_t t1 = (h) + Sigma1(e) + Ch((e), (f), (g)) + (k) + (w); \ 26 uint32_t t2 = Sigma0(a) + Maj((a), (b), (c)); \ 27 (d) += t1; \ 28 (h) = t1 + t2; \ 29 } while(0) 30 31 static void secp256k1_sha256_initialize(secp256k1_sha256 *hash) { 32 hash->s[0] = 0x6a09e667ul; 33 hash->s[1] = 0xbb67ae85ul; 34 hash->s[2] = 0x3c6ef372ul; 35 hash->s[3] = 0xa54ff53aul; 36 hash->s[4] = 0x510e527ful; 37 hash->s[5] = 0x9b05688cul; 38 hash->s[6] = 0x1f83d9abul; 39 hash->s[7] = 0x5be0cd19ul; 40 hash->bytes = 0; 41 } 42 43 static void secp256k1_sha256_initialize_midstate(secp256k1_sha256 *hash, uint64_t bytes, const uint32_t state[8]) { 44 VERIFY_CHECK((bytes & 0x3F) == 0); 45 VERIFY_CHECK(state != NULL); 46 memcpy(hash->s, state, sizeof(hash->s)); 47 hash->bytes = bytes; 48 } 49 50 /** Perform one SHA-256 transformation, processing 16 big endian 32-bit words. */ 51 static void secp256k1_sha256_transform_impl(uint32_t* s, const unsigned char* buf) { 52 uint32_t a = s[0], b = s[1], c = s[2], d = s[3], e = s[4], f = s[5], g = s[6], h = s[7]; 53 uint32_t w0, w1, w2, w3, w4, w5, w6, w7, w8, w9, w10, w11, w12, w13, w14, w15; 54 55 Round(a, b, c, d, e, f, g, h, 0x428a2f98, w0 = secp256k1_read_be32(&buf[0])); 56 Round(h, a, b, c, d, e, f, g, 0x71374491, w1 = secp256k1_read_be32(&buf[4])); 57 Round(g, h, a, b, c, d, e, f, 0xb5c0fbcf, w2 = secp256k1_read_be32(&buf[8])); 58 Round(f, g, h, a, b, c, d, e, 0xe9b5dba5, w3 = secp256k1_read_be32(&buf[12])); 59 Round(e, f, g, h, a, b, c, d, 0x3956c25b, w4 = secp256k1_read_be32(&buf[16])); 60 Round(d, e, f, g, h, a, b, c, 0x59f111f1, w5 = secp256k1_read_be32(&buf[20])); 61 Round(c, d, e, f, g, h, a, b, 0x923f82a4, w6 = secp256k1_read_be32(&buf[24])); 62 Round(b, c, d, e, f, g, h, a, 0xab1c5ed5, w7 = secp256k1_read_be32(&buf[28])); 63 Round(a, b, c, d, e, f, g, h, 0xd807aa98, w8 = secp256k1_read_be32(&buf[32])); 64 Round(h, a, b, c, d, e, f, g, 0x12835b01, w9 = secp256k1_read_be32(&buf[36])); 65 Round(g, h, a, b, c, d, e, f, 0x243185be, w10 = secp256k1_read_be32(&buf[40])); 66 Round(f, g, h, a, b, c, d, e, 0x550c7dc3, w11 = secp256k1_read_be32(&buf[44])); 67 Round(e, f, g, h, a, b, c, d, 0x72be5d74, w12 = secp256k1_read_be32(&buf[48])); 68 Round(d, e, f, g, h, a, b, c, 0x80deb1fe, w13 = secp256k1_read_be32(&buf[52])); 69 Round(c, d, e, f, g, h, a, b, 0x9bdc06a7, w14 = secp256k1_read_be32(&buf[56])); 70 Round(b, c, d, e, f, g, h, a, 0xc19bf174, w15 = secp256k1_read_be32(&buf[60])); 71 72 Round(a, b, c, d, e, f, g, h, 0xe49b69c1, w0 += sigma1(w14) + w9 + sigma0(w1)); 73 Round(h, a, b, c, d, e, f, g, 0xefbe4786, w1 += sigma1(w15) + w10 + sigma0(w2)); 74 Round(g, h, a, b, c, d, e, f, 0x0fc19dc6, w2 += sigma1(w0) + w11 + sigma0(w3)); 75 Round(f, g, h, a, b, c, d, e, 0x240ca1cc, w3 += sigma1(w1) + w12 + sigma0(w4)); 76 Round(e, f, g, h, a, b, c, d, 0x2de92c6f, w4 += sigma1(w2) + w13 + sigma0(w5)); 77 Round(d, e, f, g, h, a, b, c, 0x4a7484aa, w5 += sigma1(w3) + w14 + sigma0(w6)); 78 Round(c, d, e, f, g, h, a, b, 0x5cb0a9dc, w6 += sigma1(w4) + w15 + sigma0(w7)); 79 Round(b, c, d, e, f, g, h, a, 0x76f988da, w7 += sigma1(w5) + w0 + sigma0(w8)); 80 Round(a, b, c, d, e, f, g, h, 0x983e5152, w8 += sigma1(w6) + w1 + sigma0(w9)); 81 Round(h, a, b, c, d, e, f, g, 0xa831c66d, w9 += sigma1(w7) + w2 + sigma0(w10)); 82 Round(g, h, a, b, c, d, e, f, 0xb00327c8, w10 += sigma1(w8) + w3 + sigma0(w11)); 83 Round(f, g, h, a, b, c, d, e, 0xbf597fc7, w11 += sigma1(w9) + w4 + sigma0(w12)); 84 Round(e, f, g, h, a, b, c, d, 0xc6e00bf3, w12 += sigma1(w10) + w5 + sigma0(w13)); 85 Round(d, e, f, g, h, a, b, c, 0xd5a79147, w13 += sigma1(w11) + w6 + sigma0(w14)); 86 Round(c, d, e, f, g, h, a, b, 0x06ca6351, w14 += sigma1(w12) + w7 + sigma0(w15)); 87 Round(b, c, d, e, f, g, h, a, 0x14292967, w15 += sigma1(w13) + w8 + sigma0(w0)); 88 89 Round(a, b, c, d, e, f, g, h, 0x27b70a85, w0 += sigma1(w14) + w9 + sigma0(w1)); 90 Round(h, a, b, c, d, e, f, g, 0x2e1b2138, w1 += sigma1(w15) + w10 + sigma0(w2)); 91 Round(g, h, a, b, c, d, e, f, 0x4d2c6dfc, w2 += sigma1(w0) + w11 + sigma0(w3)); 92 Round(f, g, h, a, b, c, d, e, 0x53380d13, w3 += sigma1(w1) + w12 + sigma0(w4)); 93 Round(e, f, g, h, a, b, c, d, 0x650a7354, w4 += sigma1(w2) + w13 + sigma0(w5)); 94 Round(d, e, f, g, h, a, b, c, 0x766a0abb, w5 += sigma1(w3) + w14 + sigma0(w6)); 95 Round(c, d, e, f, g, h, a, b, 0x81c2c92e, w6 += sigma1(w4) + w15 + sigma0(w7)); 96 Round(b, c, d, e, f, g, h, a, 0x92722c85, w7 += sigma1(w5) + w0 + sigma0(w8)); 97 Round(a, b, c, d, e, f, g, h, 0xa2bfe8a1, w8 += sigma1(w6) + w1 + sigma0(w9)); 98 Round(h, a, b, c, d, e, f, g, 0xa81a664b, w9 += sigma1(w7) + w2 + sigma0(w10)); 99 Round(g, h, a, b, c, d, e, f, 0xc24b8b70, w10 += sigma1(w8) + w3 + sigma0(w11)); 100 Round(f, g, h, a, b, c, d, e, 0xc76c51a3, w11 += sigma1(w9) + w4 + sigma0(w12)); 101 Round(e, f, g, h, a, b, c, d, 0xd192e819, w12 += sigma1(w10) + w5 + sigma0(w13)); 102 Round(d, e, f, g, h, a, b, c, 0xd6990624, w13 += sigma1(w11) + w6 + sigma0(w14)); 103 Round(c, d, e, f, g, h, a, b, 0xf40e3585, w14 += sigma1(w12) + w7 + sigma0(w15)); 104 Round(b, c, d, e, f, g, h, a, 0x106aa070, w15 += sigma1(w13) + w8 + sigma0(w0)); 105 106 Round(a, b, c, d, e, f, g, h, 0x19a4c116, w0 += sigma1(w14) + w9 + sigma0(w1)); 107 Round(h, a, b, c, d, e, f, g, 0x1e376c08, w1 += sigma1(w15) + w10 + sigma0(w2)); 108 Round(g, h, a, b, c, d, e, f, 0x2748774c, w2 += sigma1(w0) + w11 + sigma0(w3)); 109 Round(f, g, h, a, b, c, d, e, 0x34b0bcb5, w3 += sigma1(w1) + w12 + sigma0(w4)); 110 Round(e, f, g, h, a, b, c, d, 0x391c0cb3, w4 += sigma1(w2) + w13 + sigma0(w5)); 111 Round(d, e, f, g, h, a, b, c, 0x4ed8aa4a, w5 += sigma1(w3) + w14 + sigma0(w6)); 112 Round(c, d, e, f, g, h, a, b, 0x5b9cca4f, w6 += sigma1(w4) + w15 + sigma0(w7)); 113 Round(b, c, d, e, f, g, h, a, 0x682e6ff3, w7 += sigma1(w5) + w0 + sigma0(w8)); 114 Round(a, b, c, d, e, f, g, h, 0x748f82ee, w8 += sigma1(w6) + w1 + sigma0(w9)); 115 Round(h, a, b, c, d, e, f, g, 0x78a5636f, w9 += sigma1(w7) + w2 + sigma0(w10)); 116 Round(g, h, a, b, c, d, e, f, 0x84c87814, w10 += sigma1(w8) + w3 + sigma0(w11)); 117 Round(f, g, h, a, b, c, d, e, 0x8cc70208, w11 += sigma1(w9) + w4 + sigma0(w12)); 118 Round(e, f, g, h, a, b, c, d, 0x90befffa, w12 += sigma1(w10) + w5 + sigma0(w13)); 119 Round(d, e, f, g, h, a, b, c, 0xa4506ceb, w13 += sigma1(w11) + w6 + sigma0(w14)); 120 Round(c, d, e, f, g, h, a, b, 0xbef9a3f7, w14 + sigma1(w12) + w7 + sigma0(w15)); 121 Round(b, c, d, e, f, g, h, a, 0xc67178f2, w15 + sigma1(w13) + w8 + sigma0(w0)); 122 123 s[0] += a; 124 s[1] += b; 125 s[2] += c; 126 s[3] += d; 127 s[4] += e; 128 s[5] += f; 129 s[6] += g; 130 s[7] += h; 131 } 132 133 static void secp256k1_sha256_transform(uint32_t *state, const unsigned char *blocks64, size_t n_blocks) { 134 while (n_blocks--) { 135 secp256k1_sha256_transform_impl(state, blocks64); 136 blocks64 += 64; 137 } 138 } 139 140 static void secp256k1_hash_ctx_init(secp256k1_hash_ctx *hash_ctx) { 141 VERIFY_CHECK(hash_ctx != NULL); 142 hash_ctx->fn_sha256_compression = secp256k1_sha256_transform; 143 } 144 145 static void secp256k1_sha256_write(const secp256k1_hash_ctx *hash_ctx, secp256k1_sha256 *hash, const unsigned char *data, size_t len) { 146 size_t chunk_len; 147 size_t bufsize = hash->bytes & 0x3F; 148 hash->bytes += len; 149 VERIFY_CHECK(hash->bytes >= len); 150 VERIFY_CHECK(hash_ctx != NULL); 151 VERIFY_CHECK(hash_ctx->fn_sha256_compression != NULL); 152 153 /* If we exceed the 64-byte block size with this input, process it and wipe the buffer */ 154 chunk_len = 64 - bufsize; 155 if (bufsize && len >= chunk_len) { 156 memcpy(hash->buf + bufsize, data, chunk_len); 157 data += chunk_len; 158 len -= chunk_len; 159 hash_ctx->fn_sha256_compression(hash->s, hash->buf, 1); 160 bufsize = 0; 161 } 162 163 /* If we still have data to process, invoke compression directly on the input */ 164 if (len >= 64) { 165 const size_t n_blocks = len / 64; 166 const size_t advance = n_blocks * 64; 167 hash_ctx->fn_sha256_compression(hash->s, data, n_blocks); 168 data += advance; 169 len -= advance; 170 } 171 172 /* Fill the buffer with what remains */ 173 if (len) { 174 memcpy(hash->buf + bufsize, data, len); 175 } 176 } 177 178 static void secp256k1_sha256_finalize(const secp256k1_hash_ctx *hash_ctx, secp256k1_sha256 *hash, unsigned char *out32) { 179 static const unsigned char pad[64] = {0x80}; 180 unsigned char sizedesc[8]; 181 int i; 182 /* The maximum message size of SHA256 is 2^64-1 bits. */ 183 VERIFY_CHECK(hash->bytes < ((uint64_t)1 << 61)); 184 secp256k1_write_be32(&sizedesc[0], hash->bytes >> 29); 185 secp256k1_write_be32(&sizedesc[4], hash->bytes << 3); 186 secp256k1_sha256_write(hash_ctx, hash, pad, 1 + ((119 - (hash->bytes % 64)) % 64)); 187 secp256k1_sha256_write(hash_ctx, hash, sizedesc, 8); 188 for (i = 0; i < 8; i++) { 189 secp256k1_write_be32(&out32[4*i], hash->s[i]); 190 hash->s[i] = 0; 191 } 192 } 193 194 /* Initializes a sha256 struct and writes the 64 byte string 195 * SHA256(tag)||SHA256(tag) into it. */ 196 static void secp256k1_sha256_initialize_tagged(const secp256k1_hash_ctx *hash_ctx, secp256k1_sha256 *hash, const unsigned char *tag, size_t taglen) { 197 unsigned char buf[32]; 198 secp256k1_sha256_initialize(hash); 199 secp256k1_sha256_write(hash_ctx, hash, tag, taglen); 200 secp256k1_sha256_finalize(hash_ctx, hash, buf); 201 202 secp256k1_sha256_initialize(hash); 203 secp256k1_sha256_write(hash_ctx, hash, buf, 32); 204 secp256k1_sha256_write(hash_ctx, hash, buf, 32); 205 } 206 207 static void secp256k1_sha256_clear(secp256k1_sha256 *hash) { 208 secp256k1_memclear_explicit(hash, sizeof(*hash)); 209 } 210 211 static void secp256k1_hmac_sha256_initialize(const secp256k1_hash_ctx *hash_ctx, secp256k1_hmac_sha256 *hash, const unsigned char *key, size_t keylen) { 212 size_t n; 213 unsigned char rkey[64]; 214 if (keylen <= sizeof(rkey)) { 215 memcpy(rkey, key, keylen); 216 memset(rkey + keylen, 0, sizeof(rkey) - keylen); 217 } else { 218 secp256k1_sha256 sha256; 219 secp256k1_sha256_initialize(&sha256); 220 secp256k1_sha256_write(hash_ctx, &sha256, key, keylen); 221 secp256k1_sha256_finalize(hash_ctx, &sha256, rkey); 222 memset(rkey + 32, 0, 32); 223 } 224 225 secp256k1_sha256_initialize(&hash->outer); 226 for (n = 0; n < sizeof(rkey); n++) { 227 rkey[n] ^= 0x5c; 228 } 229 secp256k1_sha256_write(hash_ctx, &hash->outer, rkey, sizeof(rkey)); 230 231 secp256k1_sha256_initialize(&hash->inner); 232 for (n = 0; n < sizeof(rkey); n++) { 233 rkey[n] ^= 0x5c ^ 0x36; 234 } 235 secp256k1_sha256_write(hash_ctx, &hash->inner, rkey, sizeof(rkey)); 236 secp256k1_memclear_explicit(rkey, sizeof(rkey)); 237 } 238 239 static void secp256k1_hmac_sha256_write(const secp256k1_hash_ctx *hash_ctx, secp256k1_hmac_sha256 *hash, const unsigned char *data, size_t size) { 240 secp256k1_sha256_write(hash_ctx, &hash->inner, data, size); 241 } 242 243 static void secp256k1_hmac_sha256_finalize(const secp256k1_hash_ctx *hash_ctx, secp256k1_hmac_sha256 *hash, unsigned char *out32) { 244 unsigned char temp[32]; 245 secp256k1_sha256_finalize(hash_ctx, &hash->inner, temp); 246 secp256k1_sha256_write(hash_ctx, &hash->outer, temp, 32); 247 secp256k1_memclear_explicit(temp, sizeof(temp)); 248 secp256k1_sha256_finalize(hash_ctx, &hash->outer, out32); 249 } 250 251 static void secp256k1_hmac_sha256_clear(secp256k1_hmac_sha256 *hash) { 252 secp256k1_memclear_explicit(hash, sizeof(*hash)); 253 } 254 255 static void secp256k1_rfc6979_hmac_sha256_initialize(const secp256k1_hash_ctx *hash_ctx, secp256k1_rfc6979_hmac_sha256 *rng, const unsigned char *key, size_t keylen) { 256 secp256k1_hmac_sha256 hmac; 257 static const unsigned char zero[1] = {0x00}; 258 static const unsigned char one[1] = {0x01}; 259 260 memset(rng->v, 0x01, 32); /* RFC6979 3.2.b. */ 261 memset(rng->k, 0x00, 32); /* RFC6979 3.2.c. */ 262 263 /* RFC6979 3.2.d. */ 264 secp256k1_hmac_sha256_initialize(hash_ctx, &hmac, rng->k, 32); 265 secp256k1_hmac_sha256_write(hash_ctx, &hmac, rng->v, 32); 266 secp256k1_hmac_sha256_write(hash_ctx, &hmac, zero, 1); 267 secp256k1_hmac_sha256_write(hash_ctx, &hmac, key, keylen); 268 secp256k1_hmac_sha256_finalize(hash_ctx, &hmac, rng->k); 269 secp256k1_hmac_sha256_initialize(hash_ctx, &hmac, rng->k, 32); 270 secp256k1_hmac_sha256_write(hash_ctx, &hmac, rng->v, 32); 271 secp256k1_hmac_sha256_finalize(hash_ctx, &hmac, rng->v); 272 273 /* RFC6979 3.2.f. */ 274 secp256k1_hmac_sha256_initialize(hash_ctx, &hmac, rng->k, 32); 275 secp256k1_hmac_sha256_write(hash_ctx, &hmac, rng->v, 32); 276 secp256k1_hmac_sha256_write(hash_ctx, &hmac, one, 1); 277 secp256k1_hmac_sha256_write(hash_ctx, &hmac, key, keylen); 278 secp256k1_hmac_sha256_finalize(hash_ctx, &hmac, rng->k); 279 secp256k1_hmac_sha256_initialize(hash_ctx, &hmac, rng->k, 32); 280 secp256k1_hmac_sha256_write(hash_ctx, &hmac, rng->v, 32); 281 secp256k1_hmac_sha256_finalize(hash_ctx, &hmac, rng->v); 282 rng->retry = 0; 283 } 284 285 static void secp256k1_rfc6979_hmac_sha256_generate(const secp256k1_hash_ctx *hash_ctx, secp256k1_rfc6979_hmac_sha256 *rng, unsigned char *out, size_t outlen) { 286 /* RFC6979 3.2.h. */ 287 static const unsigned char zero[1] = {0x00}; 288 if (rng->retry) { 289 secp256k1_hmac_sha256 hmac; 290 secp256k1_hmac_sha256_initialize(hash_ctx, &hmac, rng->k, 32); 291 secp256k1_hmac_sha256_write(hash_ctx, &hmac, rng->v, 32); 292 secp256k1_hmac_sha256_write(hash_ctx, &hmac, zero, 1); 293 secp256k1_hmac_sha256_finalize(hash_ctx, &hmac, rng->k); 294 secp256k1_hmac_sha256_initialize(hash_ctx, &hmac, rng->k, 32); 295 secp256k1_hmac_sha256_write(hash_ctx, &hmac, rng->v, 32); 296 secp256k1_hmac_sha256_finalize(hash_ctx, &hmac, rng->v); 297 } 298 299 while (outlen > 0) { 300 secp256k1_hmac_sha256 hmac; 301 size_t now = outlen; 302 secp256k1_hmac_sha256_initialize(hash_ctx, &hmac, rng->k, 32); 303 secp256k1_hmac_sha256_write(hash_ctx, &hmac, rng->v, 32); 304 secp256k1_hmac_sha256_finalize(hash_ctx, &hmac, rng->v); 305 if (now > 32) { 306 now = 32; 307 } 308 memcpy(out, rng->v, now); 309 out += now; 310 outlen -= now; 311 } 312 313 rng->retry = 1; 314 } 315 316 static void secp256k1_rfc6979_hmac_sha256_finalize(secp256k1_rfc6979_hmac_sha256 *rng) { 317 (void) rng; 318 } 319 320 static void secp256k1_rfc6979_hmac_sha256_clear(secp256k1_rfc6979_hmac_sha256 *rng) { 321 secp256k1_memclear_explicit(rng, sizeof(*rng)); 322 } 323 324 #undef Round 325 #undef sigma1 326 #undef sigma0 327 #undef Sigma1 328 #undef Sigma0 329 #undef Maj 330 #undef Ch 331 332 #endif /* SECP256K1_HASH_IMPL_H */