ecmult_gen_impl.h (6738B)
1 /*********************************************************************** 2 * Copyright (c) 2013, 2014, 2015 Pieter Wuille, Gregory Maxwell * 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_ECMULT_GEN_IMPL_H 8 #define SECP256K1_ECMULT_GEN_IMPL_H 9 10 #include "util.h" 11 #include "scalar.h" 12 #include "group.h" 13 #include "ecmult_gen.h" 14 #include "hash_impl.h" 15 #include "precomputed_ecmult_gen.h" 16 17 static void haskellsecp256k1_v0_1_0_ecmult_gen_context_build(haskellsecp256k1_v0_1_0_ecmult_gen_context *ctx) { 18 haskellsecp256k1_v0_1_0_ecmult_gen_blind(ctx, NULL); 19 ctx->built = 1; 20 } 21 22 static int haskellsecp256k1_v0_1_0_ecmult_gen_context_is_built(const haskellsecp256k1_v0_1_0_ecmult_gen_context* ctx) { 23 return ctx->built; 24 } 25 26 static void haskellsecp256k1_v0_1_0_ecmult_gen_context_clear(haskellsecp256k1_v0_1_0_ecmult_gen_context *ctx) { 27 ctx->built = 0; 28 haskellsecp256k1_v0_1_0_scalar_clear(&ctx->blind); 29 haskellsecp256k1_v0_1_0_gej_clear(&ctx->initial); 30 } 31 32 /* For accelerating the computation of a*G: 33 * To harden against timing attacks, use the following mechanism: 34 * * Break up the multiplicand into groups of PREC_BITS bits, called n_0, n_1, n_2, ..., n_(PREC_N-1). 35 * * Compute sum(n_i * (PREC_G)^i * G + U_i, i=0 ... PREC_N-1), where: 36 * * U_i = U * 2^i, for i=0 ... PREC_N-2 37 * * U_i = U * (1-2^(PREC_N-1)), for i=PREC_N-1 38 * where U is a point with no known corresponding scalar. Note that sum(U_i, i=0 ... PREC_N-1) = 0. 39 * For each i, and each of the PREC_G possible values of n_i, (n_i * (PREC_G)^i * G + U_i) is 40 * precomputed (call it prec(i, n_i)). The formula now becomes sum(prec(i, n_i), i=0 ... PREC_N-1). 41 * None of the resulting prec group elements have a known scalar, and neither do any of 42 * the intermediate sums while computing a*G. 43 * The prec values are stored in haskellsecp256k1_v0_1_0_ecmult_gen_prec_table[i][n_i] = n_i * (PREC_G)^i * G + U_i. 44 */ 45 static void haskellsecp256k1_v0_1_0_ecmult_gen(const haskellsecp256k1_v0_1_0_ecmult_gen_context *ctx, haskellsecp256k1_v0_1_0_gej *r, const haskellsecp256k1_v0_1_0_scalar *gn) { 46 int bits = ECMULT_GEN_PREC_BITS; 47 int g = ECMULT_GEN_PREC_G(bits); 48 int n = ECMULT_GEN_PREC_N(bits); 49 50 haskellsecp256k1_v0_1_0_ge add; 51 haskellsecp256k1_v0_1_0_ge_storage adds; 52 haskellsecp256k1_v0_1_0_scalar gnb; 53 int i, j, n_i; 54 55 memset(&adds, 0, sizeof(adds)); 56 *r = ctx->initial; 57 /* Blind scalar/point multiplication by computing (n-b)G + bG instead of nG. */ 58 haskellsecp256k1_v0_1_0_scalar_add(&gnb, gn, &ctx->blind); 59 add.infinity = 0; 60 for (i = 0; i < n; i++) { 61 n_i = haskellsecp256k1_v0_1_0_scalar_get_bits(&gnb, i * bits, bits); 62 for (j = 0; j < g; j++) { 63 /** This uses a conditional move to avoid any secret data in array indexes. 64 * _Any_ use of secret indexes has been demonstrated to result in timing 65 * sidechannels, even when the cache-line access patterns are uniform. 66 * See also: 67 * "A word of warning", CHES 2013 Rump Session, by Daniel J. Bernstein and Peter Schwabe 68 * (https://cryptojedi.org/peter/data/chesrump-20130822.pdf) and 69 * "Cache Attacks and Countermeasures: the Case of AES", RSA 2006, 70 * by Dag Arne Osvik, Adi Shamir, and Eran Tromer 71 * (https://www.tau.ac.il/~tromer/papers/cache.pdf) 72 */ 73 haskellsecp256k1_v0_1_0_ge_storage_cmov(&adds, &haskellsecp256k1_v0_1_0_ecmult_gen_prec_table[i][j], j == n_i); 74 } 75 haskellsecp256k1_v0_1_0_ge_from_storage(&add, &adds); 76 haskellsecp256k1_v0_1_0_gej_add_ge(r, r, &add); 77 } 78 n_i = 0; 79 haskellsecp256k1_v0_1_0_ge_clear(&add); 80 haskellsecp256k1_v0_1_0_scalar_clear(&gnb); 81 } 82 83 /* Setup blinding values for haskellsecp256k1_v0_1_0_ecmult_gen. */ 84 static void haskellsecp256k1_v0_1_0_ecmult_gen_blind(haskellsecp256k1_v0_1_0_ecmult_gen_context *ctx, const unsigned char *seed32) { 85 haskellsecp256k1_v0_1_0_scalar b; 86 haskellsecp256k1_v0_1_0_gej gb; 87 haskellsecp256k1_v0_1_0_fe s; 88 unsigned char nonce32[32]; 89 haskellsecp256k1_v0_1_0_rfc6979_hmac_sha256 rng; 90 unsigned char keydata[64]; 91 if (seed32 == NULL) { 92 /* When seed is NULL, reset the initial point and blinding value. */ 93 haskellsecp256k1_v0_1_0_gej_set_ge(&ctx->initial, &haskellsecp256k1_v0_1_0_ge_const_g); 94 haskellsecp256k1_v0_1_0_gej_neg(&ctx->initial, &ctx->initial); 95 haskellsecp256k1_v0_1_0_scalar_set_int(&ctx->blind, 1); 96 return; 97 } 98 /* The prior blinding value (if not reset) is chained forward by including it in the hash. */ 99 haskellsecp256k1_v0_1_0_scalar_get_b32(keydata, &ctx->blind); 100 /** Using a CSPRNG allows a failure free interface, avoids needing large amounts of random data, 101 * and guards against weak or adversarial seeds. This is a simpler and safer interface than 102 * asking the caller for blinding values directly and expecting them to retry on failure. 103 */ 104 VERIFY_CHECK(seed32 != NULL); 105 memcpy(keydata + 32, seed32, 32); 106 haskellsecp256k1_v0_1_0_rfc6979_hmac_sha256_initialize(&rng, keydata, 64); 107 memset(keydata, 0, sizeof(keydata)); 108 haskellsecp256k1_v0_1_0_rfc6979_hmac_sha256_generate(&rng, nonce32, 32); 109 haskellsecp256k1_v0_1_0_fe_set_b32_mod(&s, nonce32); 110 haskellsecp256k1_v0_1_0_fe_cmov(&s, &haskellsecp256k1_v0_1_0_fe_one, haskellsecp256k1_v0_1_0_fe_normalizes_to_zero(&s)); 111 /* Randomize the projection to defend against multiplier sidechannels. 112 Do this before our own call to haskellsecp256k1_v0_1_0_ecmult_gen below. */ 113 haskellsecp256k1_v0_1_0_gej_rescale(&ctx->initial, &s); 114 haskellsecp256k1_v0_1_0_fe_clear(&s); 115 haskellsecp256k1_v0_1_0_rfc6979_hmac_sha256_generate(&rng, nonce32, 32); 116 haskellsecp256k1_v0_1_0_scalar_set_b32(&b, nonce32, NULL); 117 /* A blinding value of 0 works, but would undermine the projection hardening. */ 118 haskellsecp256k1_v0_1_0_scalar_cmov(&b, &haskellsecp256k1_v0_1_0_scalar_one, haskellsecp256k1_v0_1_0_scalar_is_zero(&b)); 119 haskellsecp256k1_v0_1_0_rfc6979_hmac_sha256_finalize(&rng); 120 memset(nonce32, 0, 32); 121 /* The random projection in ctx->initial ensures that gb will have a random projection. */ 122 haskellsecp256k1_v0_1_0_ecmult_gen(ctx, &gb, &b); 123 haskellsecp256k1_v0_1_0_scalar_negate(&b, &b); 124 ctx->blind = b; 125 ctx->initial = gb; 126 haskellsecp256k1_v0_1_0_scalar_clear(&b); 127 haskellsecp256k1_v0_1_0_gej_clear(&gb); 128 } 129 130 #endif /* SECP256K1_ECMULT_GEN_IMPL_H */