« back to all changes in this revision
Viewing changes to ssss.c
- browse files at revision 1
- compare with another revision
- download diff
- download tarball
- view history from revision 1
- Committer: Bazaar Package Importer
- Author(s): David Moreno Garza
- Date: 2005-10-23 16:22:30 UTC
- Revision ID: james.westby@ubuntu.com-20051023162230-0ubn2u4pnobbat6n
Tags: upstream-0.4
Import upstream version 0.4
- files added:
added
removed
ssss.c
1
/*
2
* ssss version 0.4 - Copyright 2005 B. Poettering
3
*
4
* This program is free software; you can redistribute it and/or
5
* modify it under the terms of the GNU General Public License as
6
* published by the Free Software Foundation; either version 2 of the
7
* License, or (at your option) any later version.
8
*
9
* This program is distributed in the hope that it will be useful,
10
* but WITHOUT ANY WARRANTY; without even the implied warranty of
11
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12
* General Public License for more details.
13
*
14
* You should have received a copy of the GNU General Public License
15
* along with this program; if not, write to the Free Software
16
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
17
* 02111-1307 USA
18
*/
19
20
/*
21
* http://point-at-infinity.org/ssss/
22
*
23
* This is an implementation of Shamir's Secret Sharing Scheme. See
24
* the project's homepage http://point-at-infinity.org/ssss/ for more
25
* information on this topic.
26
*
27
* This code links against the GNU multiprecision library "libgmp".
28
* I compiled the code successfully with gmp 4.1.4.
29
* You will need a system that has a /dev/random entropy source.
30
*
31
* Compile with
32
* "gcc -O2 -lgmp -o ssss-split ssss.c && ln ssss-split ssss-combine"
33
*
34
* Report bugs to: ssss AT point-at-infinity.org
35
*
36
*/
37
38
#include <stdlib.h>
39
#include <string.h>
40
#include <fcntl.h>
41
#include <unistd.h>
42
#include <stdio.h>
43
#include <stdint.h>
44
#include <assert.h>
45
46
#include <gmp.h>
47
48
#define VERSION "0.4"
49
#define RANDOM_SOURCE "/dev/random"
50
#define MAXDEGREE 1024
51
#define MAXTOKENLEN 128
52
#define MAXLINELEN (MAXTOKENLEN + 1 + 10 + 1 + MAXDEGREE / 4 + 10)
53
54
/* coefficients of some irreducible polynomials over GF(2) */
55
static const unsigned char irred_coeff[] = {
56
4,3,1,5,3,1,4,3,1,7,3,2,5,4,3,5,3,2,7,4,2,4,3,1,10,9,3,9,4,2,7,6,2,10,9,
57
6,4,3,1,5,4,3,4,3,1,7,2,1,5,3,2,7,4,2,6,3,2,5,3,2,15,3,2,11,3,2,9,8,7,7,
58
2,1,5,3,2,9,3,1,7,3,1,9,8,3,9,4,2,8,5,3,15,14,10,10,5,2,9,6,2,9,3,2,9,5,
59
2,11,10,1,7,3,2,11,2,1,9,7,4,4,3,1,8,3,1,7,4,1,7,2,1,13,11,6,5,3,2,7,3,2,
60
8,7,5,12,3,2,13,10,6,5,3,2,5,3,2,9,5,2,9,7,2,13,4,3,4,3,1,11,6,4,18,9,6,
61
19,18,13,11,3,2,15,9,6,4,3,1,16,5,2,15,14,6,8,5,2,15,11,2,11,6,2,7,5,3,8,
62
3,1,19,16,9,11,9,6,15,7,6,13,4,3,14,13,3,13,6,3,9,5,2,19,13,6,19,10,3,11,
63
6,5,9,2,1,14,3,2,13,3,1,7,5,4,11,9,8,11,6,5,23,16,9,19,14,6,23,10,2,8,3,
64
2,5,4,3,9,6,4,4,3,2,13,8,6,13,11,1,13,10,3,11,6,5,19,17,4,15,14,7,13,9,6,
65
9,7,3,9,7,1,14,3,2,11,8,2,11,6,4,13,5,2,11,5,1,11,4,1,19,10,3,21,10,6,13,
66
3,1,15,7,5,19,18,10,7,5,3,12,7,2,7,5,1,14,9,6,10,3,2,15,13,12,12,11,9,16,
67
9,7,12,9,3,9,5,2,17,10,6,24,9,3,17,15,13,5,4,3,19,17,8,15,6,3,19,6,1 };
68
69
int opt_showversion = 0;
70
int opt_help = 0;
71
int opt_quiet = 0;
72
int opt_QUIET = 0;
73
int opt_hex = 0;
74
int opt_diffusion = 1;
75
int opt_security = 0;
76
int opt_threshold = -1;
77
int opt_number = -1;
78
char *opt_token = NULL;
79
80
int ttyoutput;
81
82
unsigned int degree;
83
mpz_t poly;
84
int cprng;
85
86
#define mpz_lshift(A, B, l) mpz_mul_2exp(A, B, l)
87
#define mpz_sizeinbits(A) (mpz_cmp_ui(A, 0) ? mpz_sizeinbase(A, 2) : 0)
88
89
void fatal(char *msg)
90
{
91
fprintf(stderr, "%sFATAL: %s.\n", ttyoutput ? "\a" : "", msg);
92
exit(1);
93
}
94
95
void warning(char *msg)
96
{
97
if (! opt_QUIET)
98
fprintf(stderr, "%sWARNING: %s.\n", ttyoutput ? "\a" : "", msg);
99
}
100
101
/* field arithmetic routines */
102
103
int field_size_valid(int deg)
104
{
105
return (deg >= 8) && (deg <= MAXDEGREE) && (deg % 8 == 0);
106
}
107
108
/* initialize 'poly' to a bitfield representing the coefficients of an
109
irreducible polynomial of degree 'deg' */
110
111
void field_init(int deg)
112
{
113
mpz_init_set_ui(poly, 0);
114
mpz_setbit(poly, deg);
115
mpz_setbit(poly, irred_coeff[3 * (deg / 8 - 1) + 0]);
116
mpz_setbit(poly, irred_coeff[3 * (deg / 8 - 1) + 1]);
117
mpz_setbit(poly, irred_coeff[3 * (deg / 8 - 1) + 2]);
118
mpz_setbit(poly, 0);
119
degree = deg;
120
}
121
122
void field_deinit(void)
123
{
124
mpz_clear(poly);
125
}
126
127
/* I/O routines for GF(2^deg) field elements */
128
129
void field_import(mpz_t x, const char *s, int hexmode)
130
{
131
if (hexmode) {
132
if (strlen(s) > degree / 4)
133
fatal("input string too long");
134
if (strlen(s) < degree / 4)
135
warning("input string too short, adding null padding on the left");
136
if (mpz_set_str(x, s, 16) || (mpz_cmp_ui(x, 0) < 0))
137
fatal("invalid syntax");
138
}
139
else {
140
int i;
141
int warn = 0;
142
if (strlen(s) > degree / 8)
143
fatal("input string too long");
144
for(i = strlen(s) - 1; i >= 0; i--)
145
warn = warn || (s[i] < 32) || (s[i] >= 127);
146
if (warn)
147
warning("binary data detected, use -x mode instead");
148
mpz_import(x, strlen(s), 1, 1, 0, 0, s);
149
}
150
}
151
152
void field_print(FILE* stream, const mpz_t x, int hexmode)
153
{
154
int i;
155
if (hexmode) {
156
for(i = degree / 4 - mpz_sizeinbase(x, 16); i; i--)
157
fprintf(stream, "0");
158
mpz_out_str(stream, 16, x);
159
fprintf(stream, "\n");
160
}
161
else {
162
char buf[MAXDEGREE / 8 + 1];
163
size_t t;
164
unsigned int i;
165
int printable, warn = 0;
166
memset(buf, degree / 8 + 1, 0);
167
mpz_export(buf, &t, 1, 1, 0, 0, x);
168
for(i = 0; i < t; i++) {
169
printable = (buf[i] >= 32) && (buf[i] < 127);
170
warn = warn || ! printable;
171
fprintf(stream, "%c", printable ? buf[i] : '.');
172
}
173
fprintf(stream, "\n");
174
if (warn)
175
warning("binary data detected, use -x mode instead");
176
}
177
}
178
179
/* basic field arithmetic in GF(2^deg) */
180
181
void field_add(mpz_t z, const mpz_t x, const mpz_t y)
182
{
183
mpz_xor(z, x, y);
184
}
185
186
void field_mult(mpz_t z, const mpz_t x, const mpz_t y)
187
{
188
mpz_t b;
189
unsigned int i;
190
assert(z != y);
191
mpz_init_set(b, x);
192
if (mpz_tstbit(y, 0))
193
mpz_set(z, b);
194
else
195
mpz_set_ui(z, 0);
196
for(i = 1; i < degree; i++) {
197
mpz_lshift(b, b, 1);
198
if (mpz_tstbit(b, degree))
199
mpz_xor(b, b, poly);
200
if (mpz_tstbit(y, i))
201
mpz_xor(z, z, b);
202
}
203
mpz_clear(b);
204
}
205
206
void field_invert(mpz_t z, const mpz_t x)
207
{
208
mpz_t u, v, g, h;
209
int i;
210
assert(mpz_cmp_ui(x, 0));
211
mpz_init_set(u, x);
212
mpz_init_set(v, poly);
213
mpz_init_set_ui(g, 0);
214
mpz_set_ui(z, 1);
215
mpz_init(h);
216
while (mpz_cmp_ui(u, 1)) {
217
i = mpz_sizeinbits(u) - mpz_sizeinbits(v);
218
if (i < 0) {
219
mpz_swap(u, v);
220
mpz_swap(z, g);
221
i = -i;
222
}
223
mpz_lshift(h, v, i);
224
mpz_xor(u, u, h);
225
mpz_lshift(h, g, i);
226
mpz_xor(z, z, h);
227
}
228
mpz_clear(u); mpz_clear(v); mpz_clear(g); mpz_clear(h);
229
}
230
231
/* routines for the random number generator */
232
233
void cprng_init(void)
234
{
235
if ((cprng = open(RANDOM_SOURCE, O_RDONLY)) < 0)
236
fatal("couldn't open " RANDOM_SOURCE);
237
}
238
239
void cprng_deinit(void)
240
{
241
if (close(cprng) < 0)
242
fatal("couldn't close " RANDOM_SOURCE);
243
}
244
245
void cprng_read(mpz_t x)
246
{
247
char buf[MAXDEGREE / 8];
248
unsigned int count;
249
int i;
250
for(count = 0; count < degree / 8; count += i)
251
if ((i = read(cprng, buf + count, degree / 8 - count)) < 0) {
252
close(cprng);
253
fatal("couldn't read from " RANDOM_SOURCE);
254
}
255
mpz_import(x, degree / 8, 1, 1, 0, 0, buf);
256
}
257
258
/* a 64 bit pseudo random permutation (based on the XTEA cipher) */
259
260
void encipher_block(uint32_t *v)
261
{
262
uint32_t sum = 0, delta = 0x9E3779B9;
263
int i;
264
for(i = 0; i < 32; i++) {
265
v[0] += (((v[1] << 4) ^ (v[1] >> 5)) + v[1]) ^ sum;
266
sum += delta;
267
v[1] += (((v[0] << 4) ^ (v[0] >> 5)) + v[0]) ^ sum;
268
}
269
}
270
271
void decipher_block(uint32_t *v)
272
{
273
uint32_t sum = 0xC6EF3720, delta = 0x9E3779B9;
274
int i;
275
for(i = 0; i < 32; i++) {
276
v[1] -= ((v[0] << 4 ^ v[0] >> 5) + v[0]) ^ sum;
277
sum -= delta;
278
v[0] -= ((v[1] << 4 ^ v[1] >> 5) + v[1]) ^ sum;
279
}
280
}
281
282
void encode_slice(uint8_t *data, int idx, int len,
283
void (*process_block)(uint32_t*))
284
{
285
uint32_t v[2];
286
int i;
287
for(i = 0; i < 2; i++)
288
v[i] = data[(idx + 4 * i) % len] << 24 |
289
data[(idx + 4 * i + 1) % len] << 16 |
290
data[(idx + 4 * i + 2) % len] << 8 | data[(idx + 4 * i + 3) % len];
291
process_block(v);
292
for(i = 0; i < 2; i++) {
293
data[(idx + 4 * i + 0) % len] = v[i] >> 24;
294
data[(idx + 4 * i + 1) % len] = (v[i] >> 16) & 0xff;
295
data[(idx + 4 * i + 2) % len] = (v[i] >> 8) & 0xff;
296
data[(idx + 4 * i + 3) % len] = v[i] & 0xff;
297
}
298
}
299
300
enum encdec {ENCODE, DECODE};
301
302
void encode_mpz(mpz_t x, enum encdec encdecmode)
303
{
304
uint8_t v[(MAXDEGREE + 8) / 16 * 2];
305
size_t t;
306
int i;
307
memset(v, 0, (degree + 8) / 16 * 2);
308
mpz_export(v, &t, -1, 2, 1, 0, x);
309
if (degree % 16 == 8)
310
v[degree / 8 - 1] = v[degree / 8];
311
if (encdecmode == ENCODE) /* 40 rounds are more than enough!*/
312
for(i = 0; i < 40 * ((int)degree / 8); i += 2)
313
encode_slice(v, i, degree / 8, encipher_block);
314
else
315
for(i = 40 * (degree / 8) - 2; i >= 0; i -= 2)
316
encode_slice(v, i, degree / 8, decipher_block);
317
if (degree % 16 == 8) {
318
v[degree / 8] = v[degree / 8 - 1];
319
v[degree / 8 - 1] = 0;
320
}
321
mpz_import(x, (degree + 8) / 16, -1, 2, 1, 0, v);
322
assert(mpz_sizeinbits(x) <= degree);
323
}
324
325
/* evaluate polynomials efficiently */
326
327
void horner(int n, mpz_t y, const mpz_t x, const mpz_t coeff[])
328
{
329
int i;
330
mpz_set(y, x);
331
for(i = n - 1; i; i--) {
332
field_add(y, y, coeff[i]);
333
field_mult(y, y, x);
334
}
335
field_add(y, y, coeff[0]);
336
}
337
338
/* calculate the secret from a set of shares solving a linear equation system */
339
340
#define MPZ_SWAP(A, B) \
341
do { mpz_set(h, A); mpz_set(A, B); mpz_set(B, h); } while(0)
342
343
int restore_secret(int n, mpz_t (*A)[n], mpz_t b[])
344
{
345
mpz_t (*AA)[n] = (mpz_t (*)[n])A;
346
int i, j, k, found;
347
mpz_t h;
348
mpz_init(h);
349
for(i = 0; i < n; i++) {
350
if (! mpz_cmp_ui(AA[i][i], 0)) {
351
for(found = 0, j = i + 1; j < n; j++)
352
if (mpz_cmp_ui(AA[i][j], 0)) {
353
found = 1;
354
break;
355
}
356
if (! found)
357
return -1;
358
for(k = i; k < n; k++)
359
MPZ_SWAP(AA[k][i], AA[k][j]);
360
MPZ_SWAP(b[i], b[j]);
361
}
362
for(j = i + 1; j < n; j++) {
363
if (mpz_cmp_ui(AA[i][j], 0)) {
364
for(k = i + 1; k < n; k++) {
365
field_mult(h, AA[k][i], AA[i][j]);
366
field_mult(AA[k][j], AA[k][j], AA[i][i]);
367
field_add(AA[k][j], AA[k][j], h);
368
}
369
field_mult(h, b[i], AA[i][j]);
370
field_mult(b[j], b[j], AA[i][i]);
371
field_add(b[j], b[j], h);
372
}
373
}
374
}
375
field_invert(h, AA[n - 1][n - 1]);
376
field_mult(b[n - 1], b[n - 1], h);
377
mpz_clear(h);
378
return 0;
379
}
380
381
/* Prompt for a secret, generate shares for it */
382
383
void split(void)
384
{
385
unsigned int fmt_len;
386
mpz_t x, y, coeff[opt_threshold];
387
char buf[MAXLINELEN];
388
int i;
389
for(fmt_len = 1, i = opt_number; i >= 10; i /= 10, fmt_len++);
390
if (! opt_quiet) {
391
printf("Generating shares using a (%d,%d) scheme with ",
392
opt_threshold, opt_number);
393
if (opt_security)
394
printf("a %d bit", opt_security);
395
else
396
printf("dynamic");
397
printf(" security level.\n");
398
399
int deg = opt_security ? opt_security : MAXDEGREE;
400
fprintf(stderr, "Enter the secret, ");
401
if (opt_hex)
402
fprintf(stderr, "as most %d hex digits: ", deg / 4);
403
else
404
fprintf(stderr, "at most %d ASCII characters: ", deg / 8);
405
}
406
if (! fgets(buf, sizeof(buf), stdin))
407
fatal("I/O error while reading secret");
408
buf[strcspn(buf, "\r\n")] = '\0';
409
410
if (! opt_security) {
411
opt_security = opt_hex ? 4 * ((strlen(buf) + 1) & ~1): 8 * strlen(buf);
412
413
if (! opt_quiet)
414
fprintf(stderr, "Using a %d bit security level.\n", opt_security);
415
}
416
field_init(opt_security);
417
418
mpz_init(coeff[0]);
419
field_import(coeff[0], buf, opt_hex);
420
421
if (opt_diffusion) {
422
if (degree >= 64)
423
encode_mpz(coeff[0], ENCODE);
424
else
425
warning("security level too small for the diffusion layer");
426
}
427
428
cprng_init();
429
for(i = 1; i < opt_threshold; i++) {
430
mpz_init(coeff[i]);
431
cprng_read(coeff[i]);
432
}
433
cprng_deinit();
434
435
mpz_init(x);
436
mpz_init(y);
437
for(i = 0; i < opt_number; i++) {
438
mpz_set_ui(x, i + 1);
439
horner(opt_threshold, y, x, (const mpz_t*)coeff);
440
if (opt_token)
441
printf("%s-", opt_token);
442
printf("%0*d-", fmt_len, i + 1);
443
field_print(stdout, y, 1);
444
}
445
mpz_clear(x);
446
mpz_clear(y);
447
448
for(i = 0; i < opt_threshold; i++)
449
mpz_clear(coeff[i]);
450
field_deinit();
451
}
452
453
/* Prompt for shares, calculate the secret */
454
455
void combine(void)
456
{
457
mpz_t A[opt_threshold][opt_threshold], y[opt_threshold], x;
458
char buf[MAXLINELEN];
459
char *a, *b;
460
int i, j;
461
unsigned s = 0;
462
463
mpz_init(x);
464
if (! opt_quiet)
465
printf("Enter %d shares separated by newlines:\n", opt_threshold);
466
for (i = 0; i < opt_threshold; i++) {
467
if (! opt_quiet)
468
printf("Share [%d/%d]: ", i + 1, opt_threshold);
469
470
if (! fgets(buf, sizeof(buf), stdin))
471
fatal("I/O error while reading shares");
472
buf[strcspn(buf, "\r\n")] = '\0';
473
if (! (a = strchr(buf, '-')))
474
fatal("invalid syntax");
475
*a++ = 0;
476
if ((b = strchr(a, '-')))
477
*b++ = 0;
478
else
479
b = a, a = buf;
480
481
if (! s) {
482
s = 4 * strlen(b);
483
if (! field_size_valid(s))
484
fatal("share has illegal length");
485
field_init(s);
486
}
487
else
488
if (s != 4 * strlen(b))
489
fatal("shares have different security levels");
490
491
if (! (j = atoi(a)))
492
fatal("invalid share");
493
mpz_set_ui(x, j);
494
mpz_init_set_ui(A[opt_threshold - 1][i], 1);
495
for(j = opt_threshold - 2; j >= 0; j--) {
496
mpz_init(A[j][i]);
497
field_mult(A[j][i], A[j + 1][i], x);
498
}
499
mpz_init(y[i]);
500
field_import(y[i], b, 1);
501
field_mult(x, x, A[0][i]);
502
field_add(y[i], y[i], x);
503
}
504
mpz_clear(x);
505
if (restore_secret(opt_threshold, A, y))
506
fatal("shares inconsistent. Perhaps a single share was used twice");
507
508
if (opt_diffusion) {
509
if (degree >= 64)
510
encode_mpz(y[opt_threshold - 1], DECODE);
511
else
512
warning("security level too small for the diffusion layer");
513
}
514
515
if (! opt_quiet)
516
fprintf(stderr, "Resulting secret: ");
517
field_print(stderr, y[opt_threshold - 1], opt_hex);
518
519
for (i = 0; i < opt_threshold; i++) {
520
for (j = 0; j < opt_threshold; j++)
521
mpz_clear(A[i][j]);
522
mpz_clear(y[i]);
523
}
524
field_deinit();
525
}
526
527
int main(int argc, char *argv[])
528
{
529
char *name;
530
int i;
531
if ((i = fileno(stderr)) < 0)
532
fatal("couldn't determine fileno of stderr");
533
ttyoutput = isatty(i);
534
535
opt_help = argc == 1;
536
while((i = getopt(argc, argv, "vDhqQxs:t:n:w:")) != -1)
537
switch(i) {
538
case 'v': opt_showversion = 1; break;
539
case 'h': opt_help = 1; break;
540
case 'q': opt_quiet = 1; break;
541
case 'Q': opt_QUIET = opt_quiet = 1; break;
542
case 'x': opt_hex = 1; break;
543
case 's': opt_security = atoi(optarg); break;
544
case 't': opt_threshold = atoi(optarg); break;
545
case 'n': opt_number = atoi(optarg); break;
546
case 'w': opt_token = optarg; break;
547
case 'D': opt_diffusion = 0; break;
548
default:
549
exit(1);
550
}
551
if (! opt_help && (argc != optind))
552
fatal("invalid argument");
553
554
if ((name = strrchr(argv[0], '/')) == NULL)
555
name = argv[0];
556
557
if (strstr(name, "split")) {
558
if (opt_help || opt_showversion) {
559
puts("Split secrets using Shamir's Secret Sharing Scheme.\n"
560
"\n"
561
"ssss-split -t threshold -n shares [-w token] [-s level]"
562
" [-x] [-q] [-Q] [-D] [-v]"
563
);
564
if (opt_showversion)
565
puts("\nVersion: " VERSION);
566
exit(0);
567
}
568
569
if (opt_threshold < 2)
570
fatal("invalid parameters: invalid threshold value");
571
572
if (opt_number < opt_threshold)
573
fatal("invalid parameters: number of shares smaller than threshold");
574
575
if (opt_security && ! field_size_valid(opt_security))
576
fatal("invalid parameters: invalid security level");
577
578
if (opt_token && (strlen(opt_token) > MAXTOKENLEN))
579
fatal("invalid parameters: token too long");
580
581
split();
582
}
583
else {
584
if (opt_help || opt_showversion) {
585
puts("Combine shares using Shamir's Secret Sharing Scheme.\n"
586
"\n"
587
"ssss-combine -t threshold [-x] [-q] [-Q] [-D] [-v]");
588
if (opt_showversion)
589
puts("\nVersion: " VERSION);
590
exit(0);
591
}
592
593
if (opt_threshold < 2)
594
fatal("invalid parameters: invalid threshold value");
595
596
combine();
597
}
598
return 0;
599
}
Loggerhead is a web-based interface for Breezy
Version: 2.0.1