X-Git-Url: http://git.bitcoin.ninja/index.cgi?p=shamirs;a=blobdiff_plain;f=shamirssecret.c;h=92c2c9cf8bdf1fac83be393a7175ee1f923fbc2a;hp=66442953709a93ffa6a01db4e00863d860fc596d;hb=39318502b0e2fedca71d901ba007fea2a0d26208;hpb=7f4c90df0dd4a86afa72b7894030875cd5d2f6e1 diff --git a/shamirssecret.c b/shamirssecret.c index 6644295..92c2c9c 100644 --- a/shamirssecret.c +++ b/shamirssecret.c @@ -7,6 +7,7 @@ #include #include #include +#include #define MAX_LENGTH 1024 #define ERROREXIT(str...) {fprintf(stderr, str); exit(1);} @@ -16,6 +17,7 @@ */ #define P 256 +#ifndef TEST static uint8_t field_add(uint8_t a, uint8_t b) { return a ^ b; } @@ -27,6 +29,7 @@ static uint8_t field_sub(uint8_t a, uint8_t b) { static uint8_t field_neg(uint8_t a) { return field_sub(0, a); } +#endif static const uint8_t exp[P] = { 0x01, 0x03, 0x05, 0x0f, 0x11, 0x33, 0x55, 0xff, 0x1a, 0x2e, 0x72, 0x96, 0xa1, 0xf8, 0x13, 0x35, @@ -102,6 +105,11 @@ static uint8_t field_pow_ret(uint8_t calc, uint8_t a, uint8_t e) { return ret; } static uint8_t field_pow(uint8_t a, uint8_t e) { +#ifndef TEST + // Although this function works for a==0, its not trivially obvious why, + // and since we never call with a==0, we just assert a != 0 (except when testing) + assert(a != 0); +#endif return field_pow_ret(exp[(log[a] * e) % 255], a, e); } @@ -125,7 +133,7 @@ static uint8_t field_mul_calc(uint8_t a, uint8_t b) { static uint8_t field_pow_calc(uint8_t a, uint8_t e) { uint8_t ret = 1; for (uint8_t i = 0; i < e; i++) - ret = field_mul(ret, a); + ret = field_mul_calc(ret, a); return ret; } int main() { @@ -134,7 +142,7 @@ int main() { assert(field_mul_calc(i, field_invert(i)) == 1); // Test multiplication with the logarithm tables - for (uint16_t i = 0; i < 2; i++) { + for (uint16_t i = 0; i < P; i++) { for (uint16_t j = 0; j < P; j++) assert(field_mul(i, j) == field_mul_calc(i, j)); } @@ -180,12 +188,77 @@ uint8_t calculateSecret(uint8_t x[], uint8_t q[], uint8_t k) { } +void derive_missing_part(uint8_t total_shares, uint8_t shares_required, bool parts_have[], uint8_t* split_version, uint8_t split_index, uint8_t split_size) { + uint8_t (*D)[split_size] = (uint8_t (*)[split_size])split_version; + uint8_t x[shares_required], q[shares_required]; + + // Fill in x/q with the selected shares + uint16_t x_pos = 0; + for (uint8_t i = 0; i < P-1; i++) { + if (parts_have[i]) { + x[x_pos] = i+1; + q[x_pos++] = D[i][split_index]; + } + } + assert(x_pos == shares_required - 1); + + // Now loop through ALL x we didn't already set (despite not having that many + // shares, because more shares could be added arbitrarily, any x should not be + // able to rule out any possible secrets) and try each possible q, making sure + // that each q gives us a new possibility for the secret. + bool impossible_secrets[P]; + memset(impossible_secrets, 0, sizeof(impossible_secrets)); + for (uint16_t final_x = 1; final_x < P; final_x++) { + bool x_already_used = false; + for (uint8_t j = 0; j < shares_required; j++) { + if (x[j] == final_x) + x_already_used = true; + } + if (x_already_used) + continue; + + x[shares_required-1] = final_x; + bool possible_secrets[P]; + memset(possible_secrets, 0, sizeof(possible_secrets)); + for (uint16_t new_q = 0; new_q < P; new_q++) { + q[shares_required-1] = new_q; + possible_secrets[calculateSecret(x, q, shares_required)] = 1; + } + + for (uint16_t i = 0; i < P; i++) + assert(possible_secrets[i]); + } + + //TODO: Check that gcc isn't optimizing this one away + memset(q, 0, sizeof(q)); +} + +void check_possible_missing_part_derivations_intern(uint8_t total_shares, uint8_t shares_required, bool parts_have[], uint8_t parts_included, uint16_t progress, uint8_t* split_version, uint8_t split_index, uint8_t split_size) { + if (parts_included == shares_required-1) + return derive_missing_part(total_shares, shares_required, parts_have, split_version, split_index, split_size); + + if (total_shares - progress < shares_required) + return; + + check_possible_missing_part_derivations_intern(total_shares, shares_required, parts_have, parts_included, progress+1, split_version, split_index, split_size); + parts_have[progress] = 1; + check_possible_missing_part_derivations_intern(total_shares, shares_required, parts_have, parts_included+1, progress+1, split_version, split_index, split_size); + parts_have[progress] = 0; +} + +void check_possible_missing_part_derivations(uint8_t total_shares, uint8_t shares_required, uint8_t* split_version, uint8_t split_index, uint8_t split_size) { + bool parts_have[P]; + memset(parts_have, 0, sizeof(parts_have)); + check_possible_missing_part_derivations_intern(total_shares, shares_required, parts_have, 0, 0, split_version, split_index, split_size); +} + + int main(int argc, char* argv[]) { assert(mlockall(MCL_CURRENT | MCL_FUTURE) == 0); char split = 0; - uint8_t n = 0, k = 0; + uint8_t total_shares = 0, shares_required = 0; char* files[P]; uint8_t files_count = 0; char *in_file = (void*)0, *out_file_param = (void*)0; @@ -209,7 +282,7 @@ int main(int argc, char* argv[]) { if (t <= 0 || t >= P) ERROREXIT("n must be > 0 and < %u\n", P) else - n = t; + total_shares = t; break; } case 'k': { @@ -217,7 +290,7 @@ int main(int argc, char* argv[]) { if (t <= 0 || t >= P) ERROREXIT("n must be > 0 and < %u\n", P) else - k = t; + shares_required = t; break; } case 'i': @@ -241,17 +314,17 @@ int main(int argc, char* argv[]) { ERROREXIT("getopt failed?\n") } if (!(split & 0x2)) - ERROREXIT("Must specify either -c or -s\n") + ERROREXIT("Must specify one of -c, -s or -?\n") split &= 0x1; if (argc != optind) ERROREXIT("Invalid argument\n") if (split) { - if (!n || !k) + if (!total_shares || !shares_required) ERROREXIT("n and k must be set.\n") - if (k > n) + if (shares_required > total_shares) ERROREXIT("k must be <= n\n") if (files_count != 0 || !in_file || !out_file_param) @@ -273,20 +346,26 @@ int main(int argc, char* argv[]) { fclose(secret_file); printf("Using secret of length %lu\n", secret_length); - uint8_t a[k], D[n][secret_length]; + uint8_t a[shares_required], D[total_shares][secret_length]; - for (uint8_t i = 0; i < secret_length; i++) { + for (uint32_t i = 0; i < secret_length; i++) { a[0] = secret[i]; - for (uint8_t j = 1; j < k; j++) + for (uint8_t j = 1; j < shares_required; j++) assert(fread(&a[j], sizeof(uint8_t), 1, random) == 1); - for (uint8_t j = 0; j < n; j++) - D[j][i] = calculateQ(a, k, j+1); + for (uint8_t j = 0; j < total_shares; j++) + D[j][i] = calculateQ(a, shares_required, j+1); + + // Now, for sanity's sake, we ensure that no matter which piece we are missing, we can derive no information about the secret + check_possible_missing_part_derivations(total_shares, shares_required, &(D[0][0]), i, secret_length); + + if (i % 32 == 0 && i != 0) + printf("Finished processing %u bytes.\n", i); } char out_file_name_buf[strlen(out_file_param) + 4]; strcpy(out_file_name_buf, out_file_param); - for (uint8_t i = 0; i < n; i++) { + for (uint8_t i = 0; i < total_shares; i++) { /*printf("%u-", i); for (uint8_t j = 0; j < secret_length; j++) printf("%02x", D[i][j]); @@ -313,21 +392,21 @@ int main(int argc, char* argv[]) { // Clear sensitive data (No, GCC 4.7.2 is currently not optimizing this out) memset(secret, 0, sizeof(uint8_t)*secret_length); - memset(a, 0, sizeof(uint8_t)*k); + memset(a, 0, sizeof(uint8_t)*shares_required); memset(in_file, 0, strlen(in_file)); fclose(random); } else { - if (!k) + if (!shares_required) ERROREXIT("k must be set.\n") - if (files_count != k || in_file || !out_file_param) + if (files_count != shares_required || in_file || !out_file_param) ERROREXIT("Must not specify -i and must specify -o and exactly k -f s in combine mode.\n") - uint8_t x[k], q[k]; - FILE* files_fps[k]; + uint8_t x[shares_required], q[shares_required]; + FILE* files_fps[shares_required]; - for (uint8_t i = 0; i < k; i++) { + for (uint8_t i = 0; i < shares_required; i++) { files_fps[i] = fopen(files[i], "r"); if (!files_fps[i]) ERROREXIT("Couldn't open file %s for reading.\n", files[i]) @@ -337,13 +416,13 @@ int main(int argc, char* argv[]) { uint8_t secret[MAX_LENGTH]; - uint8_t i = 0; + uint32_t i = 0; while (fread(&q[0], sizeof(uint8_t), 1, files_fps[0]) == 1) { - for (uint8_t j = 1; j < k; j++) { + for (uint8_t j = 1; j < shares_required; j++) { if (fread(&q[j], sizeof(uint8_t), 1, files_fps[j]) != 1) ERROREXIT("Couldn't read next byte from %s\n", files[j]) } - secret[i++] = calculateSecret(x, q, k); + secret[i++] = calculateSecret(x, q, shares_required); } printf("Got secret of length %u\n", i); @@ -351,16 +430,16 @@ int main(int argc, char* argv[]) { fwrite(secret, sizeof(uint8_t), i, out_file); fclose(out_file); - for (uint8_t i = 0; i < k; i++) + for (uint8_t i = 0; i < shares_required; i++) fclose(files_fps[i]); // Clear sensitive data (No, GCC 4.7.2 is currently not optimizing this out) memset(secret, 0, sizeof(uint8_t)*i); - memset(q, 0, sizeof(uint8_t)*k); + memset(q, 0, sizeof(uint8_t)*shares_required); memset(out_file_param, 0, strlen(out_file_param)); - for (uint8_t i = 0; i < k; i++) + for (uint8_t i = 0; i < shares_required; i++) memset(files[i], 0, strlen(files[i])); - memset(x, 0, sizeof(uint8_t)*k); + memset(x, 0, sizeof(uint8_t)*shares_required); } return 0;