Add scalar blinding for ecmult

gmaxwell commented at 8:54 pm on January 20, 2015: contributor

This computes (n-b)G + bG with random value b, in place of nG.

This is intended to reduce exposure to potential power/EMI sidechannels during signing and pubkey generation by blinding the secret value with another value which is hopefully unknown to the attacker.

It may not be very helpful if the attacker is able to observe the setup or if even the scalar addition has an unacceptable leak, but it has low overhead in any case and the security should be purely additive on top of the existing defenses against sidechannels.

For comments right now, there is no interface presented for users to pass in a seed. We should probably change the API to use a context pointer created by start, and could change start to take a random uchar[32] at that time.

gmaxwell commented at 8:55 pm on January 20, 2015: contributor

This addresses issue #186.

sipa commented at 0:33 am on February 13, 2015: contributor

I’d like to see this rebased on top of #208.

sipa cross-referenced this on Mar 16, 2015 from issue [API BREAK] Introduce explicit contexts by sipa

sipa commented at 10:48 am on April 11, 2015: contributor

Please rebase (I can do so, if you want to).

gmaxwell commented at 9:42 pm on April 15, 2015: contributor

Updated. If this looks good I’ll add another commit that adds an additional re-projection with H(gnb) in ecmult_gen().

dcousens commented at 2:39 am on April 16, 2015: contributor

To clarify, the point of difference here is that: n-b is hopefully safer than nG because the point scalar-multiplication has known side channels, where scalar-subtraction does not?

And further, that the subsequent point scalar-multiplication (n-b)G is safer than nG because b is unknown?

And finally, that the point addition (n-b)G + bG is safer than nG because there is no known side channels that reveal both operands?

gmaxwell commented at 3:08 am on April 16, 2015: contributor

Multipliers are much more likely to have sidechannels in general owing to their greater complexity and internal architecture. They have have, on various real systems, even have had data dependent timing, fully visible from software (though I am not aware of this being the case case for any current common desktop hardware; I’ve experienced this on ppc440, arm7tdmi, and some other processors).

More importantly, the blinding operation is tiny and very fast, compared to a huge number of multiply operations each of which could leak. In practice it would plausibly be harder to exploit any leak from the blinding because its so fast… but ultimately if additions leak, well, they leak and the library will thus leak regardless of what we do.

b is (hopefully) unknown, so n has uniform probability if you only learn (n-b). If you can observe all behavior flawlessly then the protection may not help, but each randomization is cumulative and if you miss only one (e.g. the first one) you’re out of luck if your only leak is the multipliers.

It’s not a guarantee, but we practice defense in depth, and this change does not produce a measurable slowdown (or at least it’s below the timing noise on my laptop; the effect should be tiny). (The next commit will likely be a more measurable slowdown but still a small one).

dcousens commented at 3:11 am on April 16, 2015: contributor

Thanks for the explanation @gmaxwell.

dcousens commented at 3:14 am on April 16, 2015: contributor

b is (hopefully) unknown, so n has uniform probability if you only learn (n-b). If you can observe all behavior flawlessly then the protection may not help, but each randomization is cumulative and if you miss only one (e.g. the first one) you’re out of luck if your only leak is the multipliers.

But if you learn (n - b), then use the same side channel you are trying to eliminate with bG to discover b, couldn’t you then just add (n - b) + b to discover n?

Granted, it is one more step, but.

gmaxwell commented at 3:19 am on April 16, 2015: contributor

It doesn’t compute bG every time (that would be slow and obviously have more leaks). It computes bG at start, and forward chains any time b is changed.

dcousens commented at 3:20 am on April 16, 2015: contributor

Ah!

Thanks for clearing that up :)

gmaxwell commented at 3:23 am on April 16, 2015: contributor

@sipa API question– instead of a explicit reset, which is a pretty obscure option which I doubt wouldn’t ever be used except for testing infrastructure, what would you think of me using a null seed pointer to reset?

sipa commented at 5:50 am on April 16, 2015: contributor

Oh yes, using NULL seems fine.

gmaxwell commented at 12:20 pm on April 16, 2015: contributor

@sipa updated for the api change.

gmaxwell commented at 12:52 pm on April 16, 2015: contributor

@sipa another behavior question: ‘default seed`, zeros or the address of one of the libraries functions? (Advantage being that the state ends up somewhat unpredictable (esp on hosts with ASLR), even if the caller never call randomize; disadvantage is that behavior differs from host to host even if randomize isn’t called which could complicate debugging)

sipa commented at 12:59 pm on April 16, 2015: contributor

I don’t think that using “attempted randomness” makes sense if no guarantees can be made. It’s not something to rely on, so let’s just use zeroes.

dcousens commented at 1:24 pm on April 16, 2015: contributor

+1 to all zeros. Uninitialized memory or externally ‘sourced’ memory may lead to unexpected consequences.

sipa commented at 2:21 pm on April 16, 2015: contributor

Perhaps you can add a test to see whether the Z coordinate of the result differs after signing with seeded context?

gmaxwell commented at 6:43 pm on April 16, 2015: contributor

@dcousens My suggestion was not uninitialized memory. Use of uninitialized memory would be undefined behavior and would permit the compiler to instead substitute formatting the user’s disk. What I would have been completely safe but also of very little value (or I would have just done it, instead of asking). :) @sipa: sounds good. I think I still need to do scalar equals functions in the tests.

in src/ecmult_gen_impl.h: in d41999e0b2 outdated

0@@ -1,5 +1,5 @@
1 /**********************************************************************
2- * Copyright (c) 2013, 2014 Pieter Wuille                             *
3+ * Copyright (c) 2013, 2014, 2015 Pieter Wuille, Gregory Maxwell      *

sipa commented at 9:54 am on April 22, 2015:

About time.

in src/ecmult_gen_impl.h: in d41999e0b2 outdated

147+        secp256k1_gej_set_ge(&ctx->initial, &secp256k1_ge_const_g);
148+        secp256k1_gej_neg(&ctx->initial, &ctx->initial);
149+        secp256k1_scalar_set_int(&ctx->blind, 1);
150+    }
151+    secp256k1_scalar_get_b32(nonce32, &ctx->blind);
152+    /** Using a CSPRNG allows a simpler-failure free interface, avoids needing large amounts of random data,

sipa commented at 9:55 am on April 22, 2015:

Simpler than what alternative? I know what you mean, but it may be unclear to someone just reading the code.

in src/ecmult_gen_impl.h: in d41999e0b2 outdated

150+    }
151+    secp256k1_scalar_get_b32(nonce32, &ctx->blind);
152+    /** Using a CSPRNG allows a simpler-failure free interface, avoids needing large amounts of random data,
153+     *  and guards against weak or adversarial seeds.
154+     */
155+    secp256k1_rfc6979_hmac_sha256_initialize(&rng, seed32 ? seed32 : nonce32, 32, nonce32, 32, NULL, 0);

sipa commented at 9:58 am on April 22, 2015:

How does this cause a reset if seed32=NULL is passed? The previous ctx->blind is used as PRNG seed.

EDIT: nevermind. ctx->blind is reset to 1 first.

in src/tests.c: in d41999e0b2 outdated

900@@ -901,6 +901,27 @@ void ge_equals_ge(const secp256k1_ge_t *a, const secp256k1_ge_t *b) {
901     CHECK(secp256k1_fe_equal_var(&b->y, &b->y));
902 }
903 
904+int gej_equals_gej(const secp256k1_gej_t *a, const secp256k1_gej_t *b) {

sipa commented at 10:03 am on April 22, 2015:

Perhaps add a comment that this compares the actual representation of the gej (including the Z) coordinate, and not just its geometric meaning?

sipa commented at 10:19 am on April 22, 2015: contributor

ACK apart from nits. I see no measurable slowdown (perhaps even a slight speedup, wtf?).

gmaxwell commented at 5:19 pm on April 22, 2015: contributor

Updated.

Add scalar blinding and a secp256k1_context_randomize() call.

This computes (n-b)G + bG with random value b, in place of nG in
 ecmult_gen() for signing.

This is intended to reduce exposure to potential power/EMI sidechannels
 during signing and pubkey generation by blinding the secret value with
 another value which is hopefully unknown to the attacker.

It may not be very helpful if the attacker is able to observe the setup
 or if even the scalar addition has an unacceptable leak, but it has low
 overhead in any case and the security should be purely additive on top
 of the existing defenses against sidechannels.

d2275795ff

in src/ecmult_gen_impl.h: in 47b5caf2d4 outdated

150+        secp256k1_scalar_set_int(&ctx->blind, 1);
151+    }
152+    /* The prior blinding value (if not reset) is chained forward by including it in the hash. */
153+    secp256k1_scalar_get_b32(nonce32, &ctx->blind);
154+    /** Using a CSPRNG allows a failure free interface, avoids needing large amounts of random data,
155+     *   and guards against weak or adversarial seeds.  This is a simpler and safer interface then

sipa commented at 6:40 pm on April 22, 2015:

s/then/than/

in src/ecmult_gen_impl.h: in d2275795ff

143+    unsigned char nonce32[32];
144+    secp256k1_rfc6979_hmac_sha256_t rng;
145+    int retry;
146+    if (!seed32) {
147+        /* When seed is NULL, reset the initial point and blinding value. */
148+        secp256k1_gej_set_ge(&ctx->initial, &secp256k1_ge_const_g);

sipa commented at 7:27 pm on April 22, 2015:

This, and the next line are actually redundant. (I’m fine with keeping them for clarity, though).

sipa merged this on Apr 22, 2015

sipa closed this on Apr 22, 2015

sipa referenced this in commit 61c1b1ed46 on Apr 22, 2015

sipa commented at 7:37 pm on April 22, 2015: contributor

ACK

Add scalar blinding for ecmult_gen() #190