X-Git-Url: http://git.bitcoin.ninja/index.cgi?p=shamirs;a=blobdiff_plain;f=shamirssecret.c;h=f5ca5c5f135f6bd7eaad98d95e7c8905f0e2ea3f;hp=77bc0bff8bd7d2eb2dda2f05c36c9b75e0301112;hb=2a2c594f89b469431de08aa68e38ada3bb88d9a3;hpb=5958ded10d4f4496f34ae8f5aad0b34153ed3dd6 diff --git a/shamirssecret.c b/shamirssecret.c index 77bc0bf..f5ca5c5 100644 --- a/shamirssecret.c +++ b/shamirssecret.c @@ -1,8 +1,39 @@ -#include +/* + * Shamir's secret sharing implementation + * + * Copyright (C) 2013 Matt Corallo + * + * This file is part of ASSS (Audit-friendly Shamir's Secret Sharing) + * + * ASSS is free software: you can redistribute it and/or modify + * it under the terms of the GNU Affero General Public License as + * published by the Free Software Foundation, either version 3 of + * the License, or (at your option) any later version. + * + * ASSS is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU Affero General Public License for more details. + * + * You should have received a copy of the GNU Affero General Public + * License along with ASSS. If not, see + * . + */ + +#ifndef IN_KERNEL #include +#define CHECKSTATE(x) assert(x) +#else +#include +#define CHECKSTATE(x) BUG_ON(!(x)) +#endif #include "shamirssecret.h" +#ifndef noinline +#define noinline __attribute__((noinline)) +#endif + /* * Calculations across the finite field GF(2^8) */ @@ -21,6 +52,9 @@ static uint8_t field_neg(uint8_t a) { } #endif +//TODO: Using static tables will very likely create side-channel attacks when measuring cache hits +// Because these are fairly small tables, we can probably get them loaded mostly/fully into +// cache before use to break such attacks. static const uint8_t exp[P] = { 0x01, 0x03, 0x05, 0x0f, 0x11, 0x33, 0x55, 0xff, 0x1a, 0x2e, 0x72, 0x96, 0xa1, 0xf8, 0x13, 0x35, 0x5f, 0xe1, 0x38, 0x48, 0xd8, 0x73, 0x95, 0xa4, 0xf7, 0x02, 0x06, 0x0a, 0x1e, 0x22, 0x66, 0xaa, @@ -58,7 +92,7 @@ static const uint8_t log[P] = { 0x4a, 0xed, 0xde, 0xc5, 0x31, 0xfe, 0x18, 0x0d, 0x63, 0x8c, 0x80, 0xc0, 0xf7, 0x70, 0x07}; // We disable lots of optimizations that result in non-constant runtime (+/- branch delays) -static uint8_t field_mul_ret(uint8_t calc, uint8_t a, uint8_t b) __attribute__((optimize("-O0"))) __attribute__((noinline)); +static uint8_t field_mul_ret(uint8_t calc, uint8_t a, uint8_t b) __attribute__((optimize("-O0"))) noinline; static uint8_t field_mul_ret(uint8_t calc, uint8_t a, uint8_t b) { uint8_t ret, ret2; if (a == 0) @@ -76,12 +110,12 @@ static uint8_t field_mul(uint8_t a, uint8_t b) { } static uint8_t field_invert(uint8_t a) { - assert(a != 0); + CHECKSTATE(a != 0); return exp[0xff - log[a]]; // log[1] == 0xff } // We disable lots of optimizations that result in non-constant runtime (+/- branch delays) -static uint8_t field_pow_ret(uint8_t calc, uint8_t a, uint8_t e) __attribute__((optimize("-O0"))) __attribute__((noinline)); +static uint8_t field_pow_ret(uint8_t calc, uint8_t a, uint8_t e) __attribute__((optimize("-O0"))) noinline; static uint8_t field_pow_ret(uint8_t calc, uint8_t a, uint8_t e) { uint8_t ret, ret2; if (a == 0) @@ -98,7 +132,7 @@ static uint8_t field_pow(uint8_t a, uint8_t e) { #ifndef TEST // Although this function works for a==0, its not trivially obvious why, // and since we never call with a==0, we just assert a != 0 (except when testing) - assert(a != 0); + CHECKSTATE(a != 0); #endif return field_pow_ret(exp[(log[a] * e) % 255], a, e); } @@ -129,18 +163,18 @@ static uint8_t field_pow_calc(uint8_t a, uint8_t e) { int main() { // Test inversion with the logarithm tables for (uint16_t i = 1; i < P; i++) - assert(field_mul_calc(i, field_invert(i)) == 1); + CHECKSTATE(field_mul_calc(i, field_invert(i)) == 1); // Test multiplication with the logarithm tables for (uint16_t i = 0; i < P; i++) { for (uint16_t j = 0; j < P; j++) - assert(field_mul(i, j) == field_mul_calc(i, j)); + CHECKSTATE(field_mul(i, j) == field_mul_calc(i, j)); } // Test exponentiation with the logarithm tables for (uint16_t i = 0; i < P; i++) { for (uint16_t j = 0; j < P; j++) - assert(field_pow(i, j) == field_pow_calc(i, j)); + CHECKSTATE(field_pow(i, j) == field_pow_calc(i, j)); } } #endif // defined(TEST) @@ -156,9 +190,9 @@ int main() { * coefficients[0] == secret, the rest are random values */ uint8_t calculateQ(uint8_t coefficients[], uint8_t shares_required, uint8_t x) { - assert(x != 0); // q(0) == secret, though so does a[0] - uint8_t ret = coefficients[0]; - for (uint8_t i = 1; i < shares_required; i++) { + uint8_t ret = coefficients[0], i; + CHECKSTATE(x != 0); // q(0) == secret, though so does a[0] + for (i = 1; i < shares_required; i++) { ret = field_add(ret, field_mul(coefficients[i], field_pow(x, i))); } return ret; @@ -170,10 +204,10 @@ uint8_t calculateQ(uint8_t coefficients[], uint8_t shares_required, uint8_t x) { uint8_t calculateSecret(uint8_t x[], uint8_t q[], uint8_t shares_required) { // Calculate the x^0 term using a derivation of the forumula at // http://en.wikipedia.org/wiki/Lagrange_polynomial#Example_2 - uint8_t ret = 0; - for (uint8_t i = 0; i < shares_required; i++) { + uint8_t ret = 0, i, j; + for (i = 0; i < shares_required; i++) { uint8_t temp = q[i]; - for (uint8_t j = 0; j < shares_required; j++) { + for (j = 0; j < shares_required; j++) { if (i == j) continue; temp = field_mul(temp, field_neg(x[j]));