11 #define MAX_LENGTH 1024
12 #define ERROREXIT(str...) {fprintf(stderr, str); exit(1);}
15 * Calculations across the finite field GF(2^8)
19 static uint8_t field_add(uint8_t a, uint8_t b) {
23 static uint8_t field_sub(uint8_t a, uint8_t b) {
27 static uint8_t field_neg(uint8_t a) {
28 return field_sub(0, a);
31 static const uint8_t exp[P] = {
32 0x01, 0x03, 0x05, 0x0f, 0x11, 0x33, 0x55, 0xff, 0x1a, 0x2e, 0x72, 0x96, 0xa1, 0xf8, 0x13, 0x35,
33 0x5f, 0xe1, 0x38, 0x48, 0xd8, 0x73, 0x95, 0xa4, 0xf7, 0x02, 0x06, 0x0a, 0x1e, 0x22, 0x66, 0xaa,
34 0xe5, 0x34, 0x5c, 0xe4, 0x37, 0x59, 0xeb, 0x26, 0x6a, 0xbe, 0xd9, 0x70, 0x90, 0xab, 0xe6, 0x31,
35 0x53, 0xf5, 0x04, 0x0c, 0x14, 0x3c, 0x44, 0xcc, 0x4f, 0xd1, 0x68, 0xb8, 0xd3, 0x6e, 0xb2, 0xcd,
36 0x4c, 0xd4, 0x67, 0xa9, 0xe0, 0x3b, 0x4d, 0xd7, 0x62, 0xa6, 0xf1, 0x08, 0x18, 0x28, 0x78, 0x88,
37 0x83, 0x9e, 0xb9, 0xd0, 0x6b, 0xbd, 0xdc, 0x7f, 0x81, 0x98, 0xb3, 0xce, 0x49, 0xdb, 0x76, 0x9a,
38 0xb5, 0xc4, 0x57, 0xf9, 0x10, 0x30, 0x50, 0xf0, 0x0b, 0x1d, 0x27, 0x69, 0xbb, 0xd6, 0x61, 0xa3,
39 0xfe, 0x19, 0x2b, 0x7d, 0x87, 0x92, 0xad, 0xec, 0x2f, 0x71, 0x93, 0xae, 0xe9, 0x20, 0x60, 0xa0,
40 0xfb, 0x16, 0x3a, 0x4e, 0xd2, 0x6d, 0xb7, 0xc2, 0x5d, 0xe7, 0x32, 0x56, 0xfa, 0x15, 0x3f, 0x41,
41 0xc3, 0x5e, 0xe2, 0x3d, 0x47, 0xc9, 0x40, 0xc0, 0x5b, 0xed, 0x2c, 0x74, 0x9c, 0xbf, 0xda, 0x75,
42 0x9f, 0xba, 0xd5, 0x64, 0xac, 0xef, 0x2a, 0x7e, 0x82, 0x9d, 0xbc, 0xdf, 0x7a, 0x8e, 0x89, 0x80,
43 0x9b, 0xb6, 0xc1, 0x58, 0xe8, 0x23, 0x65, 0xaf, 0xea, 0x25, 0x6f, 0xb1, 0xc8, 0x43, 0xc5, 0x54,
44 0xfc, 0x1f, 0x21, 0x63, 0xa5, 0xf4, 0x07, 0x09, 0x1b, 0x2d, 0x77, 0x99, 0xb0, 0xcb, 0x46, 0xca,
45 0x45, 0xcf, 0x4a, 0xde, 0x79, 0x8b, 0x86, 0x91, 0xa8, 0xe3, 0x3e, 0x42, 0xc6, 0x51, 0xf3, 0x0e,
46 0x12, 0x36, 0x5a, 0xee, 0x29, 0x7b, 0x8d, 0x8c, 0x8f, 0x8a, 0x85, 0x94, 0xa7, 0xf2, 0x0d, 0x17,
47 0x39, 0x4b, 0xdd, 0x7c, 0x84, 0x97, 0xa2, 0xfd, 0x1c, 0x24, 0x6c, 0xb4, 0xc7, 0x52, 0xf6, 0x01};
48 static const uint8_t log[P] = {
49 0x00, // log(0) is not defined
50 0xff, 0x19, 0x01, 0x32, 0x02, 0x1a, 0xc6, 0x4b, 0xc7, 0x1b, 0x68, 0x33, 0xee, 0xdf, 0x03, 0x64,
51 0x04, 0xe0, 0x0e, 0x34, 0x8d, 0x81, 0xef, 0x4c, 0x71, 0x08, 0xc8, 0xf8, 0x69, 0x1c, 0xc1, 0x7d,
52 0xc2, 0x1d, 0xb5, 0xf9, 0xb9, 0x27, 0x6a, 0x4d, 0xe4, 0xa6, 0x72, 0x9a, 0xc9, 0x09, 0x78, 0x65,
53 0x2f, 0x8a, 0x05, 0x21, 0x0f, 0xe1, 0x24, 0x12, 0xf0, 0x82, 0x45, 0x35, 0x93, 0xda, 0x8e, 0x96,
54 0x8f, 0xdb, 0xbd, 0x36, 0xd0, 0xce, 0x94, 0x13, 0x5c, 0xd2, 0xf1, 0x40, 0x46, 0x83, 0x38, 0x66,
55 0xdd, 0xfd, 0x30, 0xbf, 0x06, 0x8b, 0x62, 0xb3, 0x25, 0xe2, 0x98, 0x22, 0x88, 0x91, 0x10, 0x7e,
56 0x6e, 0x48, 0xc3, 0xa3, 0xb6, 0x1e, 0x42, 0x3a, 0x6b, 0x28, 0x54, 0xfa, 0x85, 0x3d, 0xba, 0x2b,
57 0x79, 0x0a, 0x15, 0x9b, 0x9f, 0x5e, 0xca, 0x4e, 0xd4, 0xac, 0xe5, 0xf3, 0x73, 0xa7, 0x57, 0xaf,
58 0x58, 0xa8, 0x50, 0xf4, 0xea, 0xd6, 0x74, 0x4f, 0xae, 0xe9, 0xd5, 0xe7, 0xe6, 0xad, 0xe8, 0x2c,
59 0xd7, 0x75, 0x7a, 0xeb, 0x16, 0x0b, 0xf5, 0x59, 0xcb, 0x5f, 0xb0, 0x9c, 0xa9, 0x51, 0xa0, 0x7f,
60 0x0c, 0xf6, 0x6f, 0x17, 0xc4, 0x49, 0xec, 0xd8, 0x43, 0x1f, 0x2d, 0xa4, 0x76, 0x7b, 0xb7, 0xcc,
61 0xbb, 0x3e, 0x5a, 0xfb, 0x60, 0xb1, 0x86, 0x3b, 0x52, 0xa1, 0x6c, 0xaa, 0x55, 0x29, 0x9d, 0x97,
62 0xb2, 0x87, 0x90, 0x61, 0xbe, 0xdc, 0xfc, 0xbc, 0x95, 0xcf, 0xcd, 0x37, 0x3f, 0x5b, 0xd1, 0x53,
63 0x39, 0x84, 0x3c, 0x41, 0xa2, 0x6d, 0x47, 0x14, 0x2a, 0x9e, 0x5d, 0x56, 0xf2, 0xd3, 0xab, 0x44,
64 0x11, 0x92, 0xd9, 0x23, 0x20, 0x2e, 0x89, 0xb4, 0x7c, 0xb8, 0x26, 0x77, 0x99, 0xe3, 0xa5, 0x67,
65 0x4a, 0xed, 0xde, 0xc5, 0x31, 0xfe, 0x18, 0x0d, 0x63, 0x8c, 0x80, 0xc0, 0xf7, 0x70, 0x07};
67 // We disable lots of optimizations that result in non-constant runtime (+/- branch delays)
68 static uint8_t field_mul_ret(uint8_t calc, uint8_t a, uint8_t b) __attribute__((optimize("-O0"))) __attribute__((noinline));
69 static uint8_t field_mul_ret(uint8_t calc, uint8_t a, uint8_t b) {
81 static uint8_t field_mul(uint8_t a, uint8_t b) {
82 return field_mul_ret(exp[(log[a] + log[b]) % 255], a, b);
85 static uint8_t field_invert(uint8_t a) {
87 return exp[0xff - log[a]]; // log[1] == 0xff
90 // We disable lots of optimizations that result in non-constant runtime (+/- branch delays)
91 static uint8_t field_pow_ret(uint8_t calc, uint8_t a, uint8_t e) __attribute__((optimize("-O0"))) __attribute__((noinline));
92 static uint8_t field_pow_ret(uint8_t calc, uint8_t a, uint8_t e) {
104 static uint8_t field_pow(uint8_t a, uint8_t e) {
105 return field_pow_ret(exp[(log[a] * e) % 255], a, e);
109 static uint8_t field_mul_calc(uint8_t a, uint8_t b) {
110 // side-channel attacks here
114 for (counter = 0; counter < 8; counter++) {
120 a ^= 0x1b; // what x^8 is modulo x^8 + x^4 + x^3 + x + 1
125 static uint8_t field_pow_calc(uint8_t a, uint8_t e) {
127 for (uint8_t i = 0; i < e; i++)
128 ret = field_mul_calc(ret, a);
132 // Test inversion with the logarithm tables
133 for (uint16_t i = 1; i < P; i++)
134 assert(field_mul_calc(i, field_invert(i)) == 1);
136 // Test multiplication with the logarithm tables
137 for (uint16_t i = 0; i < P; i++) {
138 for (uint16_t j = 0; j < P; j++)
139 assert(field_mul(i, j) == field_mul_calc(i, j));
142 // Test exponentiation with the logarithm tables
143 for (uint16_t i = 0; i < P; i++) {
144 for (uint16_t j = 0; j < P; j++)
145 assert(field_pow(i, j) == field_pow_calc(i, j));
148 #endif // defined(TEST)
153 * Calculations across the polynomial q
156 static uint8_t calculateQ(uint8_t a[], uint8_t k, uint8_t x) {
157 assert(x != 0); // q(0) == secret, though so does a[0]
159 for (uint8_t i = 1; i < k; i++) {
160 ret = field_add(ret, field_mul(a[i], field_pow(x, i)));
165 uint8_t calculateSecret(uint8_t x[], uint8_t q[], uint8_t k) {
166 // Calculate the x^0 term using a derivation of the forumula at
167 // http://en.wikipedia.org/wiki/Lagrange_polynomial#Example_2
169 for (uint8_t i = 0; i < k; i++) {
171 for (uint8_t j = 0; j < k; j++) {
174 temp = field_mul(temp, field_neg(x[j]));
175 temp = field_mul(temp, field_invert(field_sub(x[i], x[j])));
177 ret = field_add(ret, temp);
184 int main(int argc, char* argv[]) {
185 assert(mlockall(MCL_CURRENT | MCL_FUTURE) == 0);
188 uint8_t n = 0, k = 0;
189 char* files[P]; uint8_t files_count = 0;
190 char *in_file = (void*)0, *out_file_param = (void*)0;
193 while((i = getopt(argc, argv, "scn:k:f:o:i:h?")) != -1)
196 if ((split & 0x2) && !(split & 0x1))
197 ERROREXIT("-s (split) and -c (combine) are mutually exclusive\n")
202 if ((split & 0x2) && (split & 0x1))
203 ERROREXIT("-s (split) and -c (combine) are mutually exclusive\n")
208 int t = atoi(optarg);
209 if (t <= 0 || t >= P)
210 ERROREXIT("n must be > 0 and < %u\n", P)
216 int t = atoi(optarg);
217 if (t <= 0 || t >= P)
218 ERROREXIT("n must be > 0 and < %u\n", P)
227 out_file_param = optarg;
230 if (files_count >= P-1)
231 ERROREXIT("May only specify up to %u files\n", P-1)
232 files[files_count++] = optarg;
236 printf("Split usage: -s -n <total shares> -k <shares required> -i <input file> -o <output file path base>\n");
237 printf("Combine usage: -c -k <shares provided == shares required> <-f <share>>*k -o <output file>\n");
241 ERROREXIT("getopt failed?\n")
244 ERROREXIT("Must specify one of -c, -s or -?\n")
248 ERROREXIT("Invalid argument\n")
252 ERROREXIT("n and k must be set.\n")
255 ERROREXIT("k must be <= n\n")
257 if (files_count != 0 || !in_file || !out_file_param)
258 ERROREXIT("Must specify -i <input file> and -o <output file path base> but not -f in split mode.\n")
260 FILE* random = fopen("/dev/random", "r");
262 FILE* secret_file = fopen(in_file, "r");
264 ERROREXIT("Could not open %s for reading.\n", in_file)
266 uint8_t secret[MAX_LENGTH];
268 size_t secret_length = fread(secret, 1, MAX_LENGTH*sizeof(uint8_t), secret_file);
269 if (secret_length == 0)
270 ERROREXIT("Error reading secret\n")
271 if (fread(secret, 1, 1, secret_file) > 0)
272 ERROREXIT("Secret may not be longer than %u\n", MAX_LENGTH)
274 printf("Using secret of length %lu\n", secret_length);
276 uint8_t a[k], D[n][secret_length];
278 for (uint32_t i = 0; i < secret_length; i++) {
281 for (uint8_t j = 1; j < k; j++)
282 assert(fread(&a[j], sizeof(uint8_t), 1, random) == 1);
283 for (uint8_t j = 0; j < n; j++)
284 D[j][i] = calculateQ(a, k, j+1);
286 if (i % 32 == 0 && i != 0)
287 printf("Finished processing %u bytes.\n", i);
290 char out_file_name_buf[strlen(out_file_param) + 4];
291 strcpy(out_file_name_buf, out_file_param);
292 for (uint8_t i = 0; i < n; i++) {
294 for (uint8_t j = 0; j < secret_length; j++)
295 printf("%02x", D[i][j]);
298 sprintf(((char*)out_file_name_buf) + strlen(out_file_param), "%u", i);
299 FILE* out_file = fopen(out_file_name_buf, "w+");
301 ERROREXIT("Could not open output file %s\n", out_file_name_buf)
304 if (fwrite(&x, sizeof(uint8_t), 1, out_file) != 1)
305 ERROREXIT("Could not write 1 byte to %s\n", out_file_name_buf)
307 if (fwrite(D[i], 1, secret_length, out_file) != secret_length)
308 ERROREXIT("Could not write %lu bytes to %s\n", secret_length, out_file_name_buf)
312 /*printf("secret = ");
313 for (uint8_t i = 0; i < secret_length; i++)
314 printf("%02x", secret[i]);
317 // Clear sensitive data (No, GCC 4.7.2 is currently not optimizing this out)
318 memset(secret, 0, sizeof(uint8_t)*secret_length);
319 memset(a, 0, sizeof(uint8_t)*k);
320 memset(in_file, 0, strlen(in_file));
325 ERROREXIT("k must be set.\n")
327 if (files_count != k || in_file || !out_file_param)
328 ERROREXIT("Must not specify -i and must specify -o and exactly k -f <input file>s in combine mode.\n")
333 for (uint8_t i = 0; i < k; i++) {
334 files_fps[i] = fopen(files[i], "r");
336 ERROREXIT("Couldn't open file %s for reading.\n", files[i])
337 if (fread(&x[i], sizeof(uint8_t), 1, files_fps[i]) != 1)
338 ERROREXIT("Couldn't read the x byte of %s\n", files[i])
341 uint8_t secret[MAX_LENGTH];
344 while (fread(&q[0], sizeof(uint8_t), 1, files_fps[0]) == 1) {
345 for (uint8_t j = 1; j < k; j++) {
346 if (fread(&q[j], sizeof(uint8_t), 1, files_fps[j]) != 1)
347 ERROREXIT("Couldn't read next byte from %s\n", files[j])
349 secret[i++] = calculateSecret(x, q, k);
351 printf("Got secret of length %u\n", i);
353 FILE* out_file = fopen(out_file_param, "w+");
354 fwrite(secret, sizeof(uint8_t), i, out_file);
357 for (uint8_t i = 0; i < k; i++)
358 fclose(files_fps[i]);
360 // Clear sensitive data (No, GCC 4.7.2 is currently not optimizing this out)
361 memset(secret, 0, sizeof(uint8_t)*i);
362 memset(q, 0, sizeof(uint8_t)*k);
363 memset(out_file_param, 0, strlen(out_file_param));
364 for (uint8_t i = 0; i < k; i++)
365 memset(files[i], 0, strlen(files[i]));
366 memset(x, 0, sizeof(uint8_t)*k);
371 #endif // !defined(TEST)