_ Git - shamirs/blob - shamirssecret.c

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