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