_ Git - shamirs/blob - shamirssecret.c

   1 /*
   2  * Shamir's secret sharing implementation
   3  *
   4  * Copyright (C) 2013 Matt Corallo <git@bluematt.me>
   5  *
   6  * This file is part of ASSS (Audit-friendly Shamir's Secret Sharing)
   7  *
   8  * ASSS is free software: you can redistribute it and/or modify
   9  * it under the terms of the GNU Affero General Public License as
  10  * published by the Free Software Foundation, either version 3 of
  11  * the License, or (at your option) any later version.
  12  *
  13  * ASSS is distributed in the hope that it will be useful,
  14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16  * GNU Affero General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU Affero General Public
  19  * License along with ASSS.  If not, see
  20  * <http://www.gnu.org/licenses/>.
  21  */
  22
  23 #ifndef IN_KERNEL
  24 #include <assert.h>
  25 #define CHECKSTATE(x) assert(x)
  26 #else
  27 #include <linux/bug.h>
  28 #define CHECKSTATE(x) BUG_ON(!(x))
  29 #endif
  30
  31 #include "shamirssecret.h"
  32
  33 #ifndef noinline
  34 #define noinline __attribute__((noinline))
  35 #endif
  36
  37 /*
  38  * Calculations across the finite field GF(2^8)
  39  */
  40
  41 #ifndef TEST
  42 static uint8_t field_add(uint8_t a, uint8_t b) {
  43         return a ^ b;
  44 }
  45
  46 static uint8_t field_sub(uint8_t a, uint8_t b) {
  47         return a ^ b;
  48 }
  49
  50 static uint8_t field_neg(uint8_t a) {
  51         return field_sub(0, a);
  52 }
  53 #endif
  54
  55 //TODO: Using static tables will very likely create side-channel attacks when measuring cache hits
  56 //      Because these are fairly small tables, we can probably get them loaded mostly/fully into
  57 //      cache before use to break such attacks.
  58 static const uint8_t exp[P] = {
  59         0x01, 0x03, 0x05, 0x0f, 0x11, 0x33, 0x55, 0xff, 0x1a, 0x2e, 0x72, 0x96, 0xa1, 0xf8, 0x13, 0x35,
  60         0x5f, 0xe1, 0x38, 0x48, 0xd8, 0x73, 0x95, 0xa4, 0xf7, 0x02, 0x06, 0x0a, 0x1e, 0x22, 0x66, 0xaa,
  61         0xe5, 0x34, 0x5c, 0xe4, 0x37, 0x59, 0xeb, 0x26, 0x6a, 0xbe, 0xd9, 0x70, 0x90, 0xab, 0xe6, 0x31,
  62         0x53, 0xf5, 0x04, 0x0c, 0x14, 0x3c, 0x44, 0xcc, 0x4f, 0xd1, 0x68, 0xb8, 0xd3, 0x6e, 0xb2, 0xcd,
  63         0x4c, 0xd4, 0x67, 0xa9, 0xe0, 0x3b, 0x4d, 0xd7, 0x62, 0xa6, 0xf1, 0x08, 0x18, 0x28, 0x78, 0x88,
  64         0x83, 0x9e, 0xb9, 0xd0, 0x6b, 0xbd, 0xdc, 0x7f, 0x81, 0x98, 0xb3, 0xce, 0x49, 0xdb, 0x76, 0x9a,
  65         0xb5, 0xc4, 0x57, 0xf9, 0x10, 0x30, 0x50, 0xf0, 0x0b, 0x1d, 0x27, 0x69, 0xbb, 0xd6, 0x61, 0xa3,
  66         0xfe, 0x19, 0x2b, 0x7d, 0x87, 0x92, 0xad, 0xec, 0x2f, 0x71, 0x93, 0xae, 0xe9, 0x20, 0x60, 0xa0,
  67         0xfb, 0x16, 0x3a, 0x4e, 0xd2, 0x6d, 0xb7, 0xc2, 0x5d, 0xe7, 0x32, 0x56, 0xfa, 0x15, 0x3f, 0x41,
  68         0xc3, 0x5e, 0xe2, 0x3d, 0x47, 0xc9, 0x40, 0xc0, 0x5b, 0xed, 0x2c, 0x74, 0x9c, 0xbf, 0xda, 0x75,
  69         0x9f, 0xba, 0xd5, 0x64, 0xac, 0xef, 0x2a, 0x7e, 0x82, 0x9d, 0xbc, 0xdf, 0x7a, 0x8e, 0x89, 0x80,
  70         0x9b, 0xb6, 0xc1, 0x58, 0xe8, 0x23, 0x65, 0xaf, 0xea, 0x25, 0x6f, 0xb1, 0xc8, 0x43, 0xc5, 0x54,
  71         0xfc, 0x1f, 0x21, 0x63, 0xa5, 0xf4, 0x07, 0x09, 0x1b, 0x2d, 0x77, 0x99, 0xb0, 0xcb, 0x46, 0xca,
  72         0x45, 0xcf, 0x4a, 0xde, 0x79, 0x8b, 0x86, 0x91, 0xa8, 0xe3, 0x3e, 0x42, 0xc6, 0x51, 0xf3, 0x0e,
  73         0x12, 0x36, 0x5a, 0xee, 0x29, 0x7b, 0x8d, 0x8c, 0x8f, 0x8a, 0x85, 0x94, 0xa7, 0xf2, 0x0d, 0x17,
  74         0x39, 0x4b, 0xdd, 0x7c, 0x84, 0x97, 0xa2, 0xfd, 0x1c, 0x24, 0x6c, 0xb4, 0xc7, 0x52, 0xf6, 0x01};
  75 static const uint8_t log[P] = {
  76         0x00, // log(0) is not defined
  77         0xff, 0x19, 0x01, 0x32, 0x02, 0x1a, 0xc6, 0x4b, 0xc7, 0x1b, 0x68, 0x33, 0xee, 0xdf, 0x03, 0x64,
  78         0x04, 0xe0, 0x0e, 0x34, 0x8d, 0x81, 0xef, 0x4c, 0x71, 0x08, 0xc8, 0xf8, 0x69, 0x1c, 0xc1, 0x7d,
  79         0xc2, 0x1d, 0xb5, 0xf9, 0xb9, 0x27, 0x6a, 0x4d, 0xe4, 0xa6, 0x72, 0x9a, 0xc9, 0x09, 0x78, 0x65,
  80         0x2f, 0x8a, 0x05, 0x21, 0x0f, 0xe1, 0x24, 0x12, 0xf0, 0x82, 0x45, 0x35, 0x93, 0xda, 0x8e, 0x96,
  81         0x8f, 0xdb, 0xbd, 0x36, 0xd0, 0xce, 0x94, 0x13, 0x5c, 0xd2, 0xf1, 0x40, 0x46, 0x83, 0x38, 0x66,
  82         0xdd, 0xfd, 0x30, 0xbf, 0x06, 0x8b, 0x62, 0xb3, 0x25, 0xe2, 0x98, 0x22, 0x88, 0x91, 0x10, 0x7e,
  83         0x6e, 0x48, 0xc3, 0xa3, 0xb6, 0x1e, 0x42, 0x3a, 0x6b, 0x28, 0x54, 0xfa, 0x85, 0x3d, 0xba, 0x2b,
  84         0x79, 0x0a, 0x15, 0x9b, 0x9f, 0x5e, 0xca, 0x4e, 0xd4, 0xac, 0xe5, 0xf3, 0x73, 0xa7, 0x57, 0xaf,
  85         0x58, 0xa8, 0x50, 0xf4, 0xea, 0xd6, 0x74, 0x4f, 0xae, 0xe9, 0xd5, 0xe7, 0xe6, 0xad, 0xe8, 0x2c,
  86         0xd7, 0x75, 0x7a, 0xeb, 0x16, 0x0b, 0xf5, 0x59, 0xcb, 0x5f, 0xb0, 0x9c, 0xa9, 0x51, 0xa0, 0x7f,
  87         0x0c, 0xf6, 0x6f, 0x17, 0xc4, 0x49, 0xec, 0xd8, 0x43, 0x1f, 0x2d, 0xa4, 0x76, 0x7b, 0xb7, 0xcc,
  88         0xbb, 0x3e, 0x5a, 0xfb, 0x60, 0xb1, 0x86, 0x3b, 0x52, 0xa1, 0x6c, 0xaa, 0x55, 0x29, 0x9d, 0x97,
  89         0xb2, 0x87, 0x90, 0x61, 0xbe, 0xdc, 0xfc, 0xbc, 0x95, 0xcf, 0xcd, 0x37, 0x3f, 0x5b, 0xd1, 0x53,
  90         0x39, 0x84, 0x3c, 0x41, 0xa2, 0x6d, 0x47, 0x14, 0x2a, 0x9e, 0x5d, 0x56, 0xf2, 0xd3, 0xab, 0x44,
  91         0x11, 0x92, 0xd9, 0x23, 0x20, 0x2e, 0x89, 0xb4, 0x7c, 0xb8, 0x26, 0x77, 0x99, 0xe3, 0xa5, 0x67,
  92         0x4a, 0xed, 0xde, 0xc5, 0x31, 0xfe, 0x18, 0x0d, 0x63, 0x8c, 0x80, 0xc0, 0xf7, 0x70, 0x07};
  93
  94 // We disable lots of optimizations that result in non-constant runtime (+/- branch delays)
  95 static uint8_t field_mul_ret(uint8_t calc, uint8_t a, uint8_t b) __attribute__((optimize("-O0"))) noinline;
  96 static uint8_t field_mul_ret(uint8_t calc, uint8_t a, uint8_t b) {
  97         uint8_t ret, ret2;
  98         if (a == 0)
  99                 ret2 = 0;
 100         else
 101                 ret2 = calc;
 102         if (b == 0)
 103                 ret = 0;
 104         else
 105                 ret = ret2;
 106         return ret;
 107 }
 108 static uint8_t field_mul(uint8_t a, uint8_t b)  {
 109         return field_mul_ret(exp[(log[a] + log[b]) % 255], a, b);
 110 }
 111
 112 static uint8_t field_invert(uint8_t a) {
 113         CHECKSTATE(a != 0);
 114         return exp[0xff - log[a]]; // log[1] == 0xff
 115 }
 116
 117 // We disable lots of optimizations that result in non-constant runtime (+/- branch delays)
 118 static uint8_t field_pow_ret(uint8_t calc, uint8_t a, uint8_t e) __attribute__((optimize("-O0"))) noinline;
 119 static uint8_t field_pow_ret(uint8_t calc, uint8_t a, uint8_t e) {
 120         uint8_t ret, ret2;
 121         if (a == 0)
 122                 ret2 = 0;
 123         else
 124                 ret2 = calc;
 125         if (e == 0)
 126                 ret = 1;
 127         else
 128                 ret = ret2;
 129         return ret;
 130 }
 131 static uint8_t field_pow(uint8_t a, uint8_t e) {
 132 #ifndef TEST
 133         // Although this function works for a==0, its not trivially obvious why,
 134         // and since we never call with a==0, we just assert a != 0 (except when testing)
 135         CHECKSTATE(a != 0);
 136 #endif
 137         return field_pow_ret(exp[(log[a] * e) % 255], a, e);
 138 }
 139
 140 #ifdef TEST
 141 static uint8_t field_mul_calc(uint8_t a, uint8_t b) {
 142         // side-channel attacks here
 143         uint8_t ret = 0;
 144         uint8_t counter;
 145         uint8_t carry;
 146         for (counter = 0; counter < 8; counter++) {
 147                 if (b & 1)
 148                         ret ^= a;
 149                 carry = (a & 0x80);
 150                 a <<= 1;
 151                 if (carry)
 152                         a ^= 0x1b; // what x^8 is modulo x^8 + x^4 + x^3 + x + 1
 153                 b >>= 1;
 154         }
 155         return ret;
 156 }
 157 static uint8_t field_pow_calc(uint8_t a, uint8_t e) {
 158         uint8_t ret = 1;
 159         for (uint8_t i = 0; i < e; i++)
 160                 ret = field_mul_calc(ret, a);
 161         return ret;
 162 }
 163 int main() {
 164         // Test inversion with the logarithm tables
 165         for (uint16_t i = 1; i < P; i++)
 166                 CHECKSTATE(field_mul_calc(i, field_invert(i)) == 1);
 167
 168         // Test multiplication with the logarithm tables
 169         for (uint16_t i = 0; i < P; i++) {
 170                 for (uint16_t j = 0; j < P; j++)
 171                         CHECKSTATE(field_mul(i, j) == field_mul_calc(i, j));
 172         }
 173
 174         // Test exponentiation with the logarithm tables
 175         for (uint16_t i = 0; i < P; i++) {
 176                 for (uint16_t j = 0; j < P; j++)
 177                         CHECKSTATE(field_pow(i, j) == field_pow_calc(i, j));
 178         }
 179 }
 180 #endif // defined(TEST)
 181
 182
 183
 184 /*
 185  * Calculations across the polynomial q
 186  */
 187 #ifndef TEST
 188 /**
 189  * Calculates the Y coordinate that the point with the given X
 190  * coefficients[0] == secret, the rest are random values
 191  */
 192 uint8_t calculateQ(uint8_t coefficients[], uint8_t shares_required, uint8_t x) {
 193         uint8_t ret = coefficients[0], i;
 194         CHECKSTATE(x != 0); // q(0) == secret, though so does a[0]
 195         for (i = 1; i < shares_required; i++) {
 196                 ret = field_add(ret, field_mul(coefficients[i], field_pow(x, i)));
 197         }
 198         return ret;
 199 }
 200
 201 /**
 202  * Derives the secret given a set of shares_required points (x and q coordinates)
 203  */
 204 uint8_t calculateSecret(uint8_t x[], uint8_t q[], uint8_t shares_required) {
 205         // Calculate the x^0 term using a derivation of the forumula at
 206         // http://en.wikipedia.org/wiki/Lagrange_polynomial#Example_2
 207         uint8_t ret = 0, i, j;
 208         for (i = 0; i < shares_required; i++) {
 209                 uint8_t temp = q[i];
 210                 for (j = 0; j < shares_required; j++) {
 211                         if (i == j)
 212                                 continue;
 213                         temp = field_mul(temp, field_neg(x[j]));
 214                         temp = field_mul(temp, field_invert(field_sub(x[i], x[j])));
 215                 }
 216                 ret = field_add(ret, temp);
 217         }
 218         return ret;
 219 }
 220 #endif // !defined(TEST)