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) {
106 // Although this function works for a==0, its not trivially obvious why,
107 // and since we never call with a==0, we just assert a != 0 (except when testing)
110 return field_pow_ret(exp[(log[a] * e) % 255], a, e);
114 static uint8_t field_mul_calc(uint8_t a, uint8_t b) {
115 // side-channel attacks here
119 for (counter = 0; counter < 8; counter++) {
125 a ^= 0x1b; // what x^8 is modulo x^8 + x^4 + x^3 + x + 1
130 static uint8_t field_pow_calc(uint8_t a, uint8_t e) {
132 for (uint8_t i = 0; i < e; i++)
133 ret = field_mul_calc(ret, a);
137 // Test inversion with the logarithm tables
138 for (uint16_t i = 1; i < P; i++)
139 assert(field_mul_calc(i, field_invert(i)) == 1);
141 // Test multiplication with the logarithm tables
142 for (uint16_t i = 0; i < P; i++) {
143 for (uint16_t j = 0; j < P; j++)
144 assert(field_mul(i, j) == field_mul_calc(i, j));
147 // Test exponentiation with the logarithm tables
148 for (uint16_t i = 0; i < P; i++) {
149 for (uint16_t j = 0; j < P; j++)
150 assert(field_pow(i, j) == field_pow_calc(i, j));
153 #endif // defined(TEST)
158 * Calculations across the polynomial q
161 static uint8_t calculateQ(uint8_t a[], uint8_t k, uint8_t x) {
162 assert(x != 0); // q(0) == secret, though so does a[0]
164 for (uint8_t i = 1; i < k; i++) {
165 ret = field_add(ret, field_mul(a[i], field_pow(x, i)));
170 uint8_t calculateSecret(uint8_t x[], uint8_t q[], uint8_t k) {
171 // Calculate the x^0 term using a derivation of the forumula at
172 // http://en.wikipedia.org/wiki/Lagrange_polynomial#Example_2
174 for (uint8_t i = 0; i < k; i++) {
176 for (uint8_t j = 0; j < k; j++) {
179 temp = field_mul(temp, field_neg(x[j]));
180 temp = field_mul(temp, field_invert(field_sub(x[i], x[j])));
182 ret = field_add(ret, temp);
189 int main(int argc, char* argv[]) {
190 assert(mlockall(MCL_CURRENT | MCL_FUTURE) == 0);
193 uint8_t n = 0, k = 0;
194 char* files[P]; uint8_t files_count = 0;
195 char *in_file = (void*)0, *out_file_param = (void*)0;
198 while((i = getopt(argc, argv, "scn:k:f:o:i:h?")) != -1)
201 if ((split & 0x2) && !(split & 0x1))
202 ERROREXIT("-s (split) and -c (combine) are mutually exclusive\n")
207 if ((split & 0x2) && (split & 0x1))
208 ERROREXIT("-s (split) and -c (combine) are mutually exclusive\n")
213 int t = atoi(optarg);
214 if (t <= 0 || t >= P)
215 ERROREXIT("n must be > 0 and < %u\n", P)
221 int t = atoi(optarg);
222 if (t <= 0 || t >= P)
223 ERROREXIT("n must be > 0 and < %u\n", P)
232 out_file_param = optarg;
235 if (files_count >= P-1)
236 ERROREXIT("May only specify up to %u files\n", P-1)
237 files[files_count++] = optarg;
241 printf("Split usage: -s -n <total shares> -k <shares required> -i <input file> -o <output file path base>\n");
242 printf("Combine usage: -c -k <shares provided == shares required> <-f <share>>*k -o <output file>\n");
246 ERROREXIT("getopt failed?\n")
249 ERROREXIT("Must specify one of -c, -s or -?\n")
253 ERROREXIT("Invalid argument\n")
257 ERROREXIT("n and k must be set.\n")
260 ERROREXIT("k must be <= n\n")
262 if (files_count != 0 || !in_file || !out_file_param)
263 ERROREXIT("Must specify -i <input file> and -o <output file path base> but not -f in split mode.\n")
265 FILE* random = fopen("/dev/random", "r");
267 FILE* secret_file = fopen(in_file, "r");
269 ERROREXIT("Could not open %s for reading.\n", in_file)
271 uint8_t secret[MAX_LENGTH];
273 size_t secret_length = fread(secret, 1, MAX_LENGTH*sizeof(uint8_t), secret_file);
274 if (secret_length == 0)
275 ERROREXIT("Error reading secret\n")
276 if (fread(secret, 1, 1, secret_file) > 0)
277 ERROREXIT("Secret may not be longer than %u\n", MAX_LENGTH)
279 printf("Using secret of length %lu\n", secret_length);
281 uint8_t a[k], D[n][secret_length];
283 for (uint32_t i = 0; i < secret_length; i++) {
286 for (uint8_t j = 1; j < k; j++)
287 assert(fread(&a[j], sizeof(uint8_t), 1, random) == 1);
288 for (uint8_t j = 0; j < n; j++)
289 D[j][i] = calculateQ(a, k, j+1);
291 if (i % 32 == 0 && i != 0)
292 printf("Finished processing %u bytes.\n", i);
295 char out_file_name_buf[strlen(out_file_param) + 4];
296 strcpy(out_file_name_buf, out_file_param);
297 for (uint8_t i = 0; i < n; i++) {
299 for (uint8_t j = 0; j < secret_length; j++)
300 printf("%02x", D[i][j]);
303 sprintf(((char*)out_file_name_buf) + strlen(out_file_param), "%u", i);
304 FILE* out_file = fopen(out_file_name_buf, "w+");
306 ERROREXIT("Could not open output file %s\n", out_file_name_buf)
309 if (fwrite(&x, sizeof(uint8_t), 1, out_file) != 1)
310 ERROREXIT("Could not write 1 byte to %s\n", out_file_name_buf)
312 if (fwrite(D[i], 1, secret_length, out_file) != secret_length)
313 ERROREXIT("Could not write %lu bytes to %s\n", secret_length, out_file_name_buf)
317 /*printf("secret = ");
318 for (uint8_t i = 0; i < secret_length; i++)
319 printf("%02x", secret[i]);
322 // Clear sensitive data (No, GCC 4.7.2 is currently not optimizing this out)
323 memset(secret, 0, sizeof(uint8_t)*secret_length);
324 memset(a, 0, sizeof(uint8_t)*k);
325 memset(in_file, 0, strlen(in_file));
330 ERROREXIT("k must be set.\n")
332 if (files_count != k || in_file || !out_file_param)
333 ERROREXIT("Must not specify -i and must specify -o and exactly k -f <input file>s in combine mode.\n")
338 for (uint8_t i = 0; i < k; i++) {
339 files_fps[i] = fopen(files[i], "r");
341 ERROREXIT("Couldn't open file %s for reading.\n", files[i])
342 if (fread(&x[i], sizeof(uint8_t), 1, files_fps[i]) != 1)
343 ERROREXIT("Couldn't read the x byte of %s\n", files[i])
346 uint8_t secret[MAX_LENGTH];
349 while (fread(&q[0], sizeof(uint8_t), 1, files_fps[0]) == 1) {
350 for (uint8_t j = 1; j < k; j++) {
351 if (fread(&q[j], sizeof(uint8_t), 1, files_fps[j]) != 1)
352 ERROREXIT("Couldn't read next byte from %s\n", files[j])
354 secret[i++] = calculateSecret(x, q, k);
356 printf("Got secret of length %u\n", i);
358 FILE* out_file = fopen(out_file_param, "w+");
359 fwrite(secret, sizeof(uint8_t), i, out_file);
362 for (uint8_t i = 0; i < k; i++)
363 fclose(files_fps[i]);
365 // Clear sensitive data (No, GCC 4.7.2 is currently not optimizing this out)
366 memset(secret, 0, sizeof(uint8_t)*i);
367 memset(q, 0, sizeof(uint8_t)*k);
368 memset(out_file_param, 0, strlen(out_file_param));
369 for (uint8_t i = 0; i < k; i++)
370 memset(files[i], 0, strlen(files[i]));
371 memset(x, 0, sizeof(uint8_t)*k);
376 #endif // !defined(TEST)