_ Git - shamirs/blob - shamirssecret.c

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