1 /*
2 * ssss version 0.5 - Copyright 2005,2006 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 * Compile with -DNOMLOCK to obtain a version without memory locking.
35 *
36 * Report bugs to: ssss AT point-at-infinity.org
37 *
38 */
39
40 #include <stdlib.h>
41 #include <string.h>
42 #include <errno.h>
43 #include <fcntl.h>
44 #include <unistd.h>
45 #include <stdio.h>
46 #include <stdint.h>
47 #include <assert.h>
48 #include <termios.h>
49 #include <sys/mman.h>
50
51 #include <gmp.h>
52
53 #define VERSION "0.5"
54 #define RANDOM_SOURCE "/dev/random"
55 #define MAXDEGREE 1024
56 #define MAXTOKENLEN 128
57 #define MAXLINELEN (MAXTOKENLEN + 1 + 10 + 1 + MAXDEGREE / 4 + 10)
58
59 /* coefficients of some irreducible polynomials over GF(2) */
60 static const unsigned char irred_coeff[] = {
61 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,
62 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,
63 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,
64 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,
65 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,
66 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,
67 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,
68 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,
69 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,
70 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,
71 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,
72 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 };
73
74 int opt_showversion = 0;
75 int opt_help = 0;
76 int opt_quiet = 0;
77 int opt_QUIET = 0;
78 int opt_hex = 0;
79 int opt_diffusion = 1;
80 int opt_security = 0;
81 int opt_threshold = -1;
82 int opt_number = -1;
83 char *opt_token = NULL;
84
85 unsigned int degree;
86 mpz_t poly;
87 int cprng;
88 struct termios echo_orig, echo_off;
89
90 #define mpz_lshift(A, B, l) mpz_mul_2exp(A, B, l)
91 #define mpz_sizeinbits(A) (mpz_cmp_ui(A, 0) ? mpz_sizeinbase(A, 2) : 0)
92
93 /* emergency abort and warning functions */
94
fatal(char * msg)95 void fatal(char *msg)
96 {
97 tcsetattr(0, TCSANOW, &echo_orig);
98 fprintf(stderr, "%sFATAL: %s.\n", isatty(2) ? "\a" : "", msg);
99 exit(1);
100 }
101
warning(char * msg)102 void warning(char *msg)
103 {
104 if (! opt_QUIET)
105 fprintf(stderr, "%sWARNING: %s.\n", isatty(2) ? "\a" : "", msg);
106 }
107
108 /* field arithmetic routines */
109
field_size_valid(int deg)110 int field_size_valid(int deg)
111 {
112 return (deg >= 8) && (deg <= MAXDEGREE) && (deg % 8 == 0);
113 }
114
115 /* initialize 'poly' to a bitfield representing the coefficients of an
116 irreducible polynomial of degree 'deg' */
117
field_init(int deg)118 void field_init(int deg)
119 {
120 assert(field_size_valid(deg));
121 mpz_init_set_ui(poly, 0);
122 mpz_setbit(poly, deg);
123 mpz_setbit(poly, irred_coeff[3 * (deg / 8 - 1) + 0]);
124 mpz_setbit(poly, irred_coeff[3 * (deg / 8 - 1) + 1]);
125 mpz_setbit(poly, irred_coeff[3 * (deg / 8 - 1) + 2]);
126 mpz_setbit(poly, 0);
127 degree = deg;
128 }
129
field_deinit(void)130 void field_deinit(void)
131 {
132 mpz_clear(poly);
133 }
134
135 /* I/O routines for GF(2^deg) field elements */
136
field_import(mpz_t x,const char * s,int hexmode)137 void field_import(mpz_t x, const char *s, int hexmode)
138 {
139 if (hexmode) {
140 if (strlen(s) > degree / 4)
141 fatal("input string too long");
142 if (strlen(s) < degree / 4)
143 warning("input string too short, adding null padding on the left");
144 if (mpz_set_str(x, s, 16) || (mpz_cmp_ui(x, 0) < 0))
145 fatal("invalid syntax");
146 }
147 else {
148 int i;
149 int warn = 0;
150 if (strlen(s) > degree / 8)
151 fatal("input string too long");
152 for(i = strlen(s) - 1; i >= 0; i--)
153 warn = warn || (s[i] < 32) || (s[i] >= 127);
154 if (warn)
155 warning("binary data detected, use -x mode instead");
156 mpz_import(x, strlen(s), 1, 1, 0, 0, s);
157 }
158 }
159
field_print(FILE * stream,const mpz_t x,int hexmode)160 void field_print(FILE* stream, const mpz_t x, int hexmode)
161 {
162 int i;
163 if (hexmode) {
164 for(i = degree / 4 - mpz_sizeinbase(x, 16); i; i--)
165 fprintf(stream, "0");
166 mpz_out_str(stream, 16, x);
167 fprintf(stream, "\n");
168 }
169 else {
170 char buf[MAXDEGREE / 8 + 1];
171 size_t t;
172 unsigned int i;
173 int printable, warn = 0;
174 memset(buf, degree / 8 + 1, 0);
175 mpz_export(buf, &t, 1, 1, 0, 0, x);
176 for(i = 0; i < t; i++) {
177 printable = (buf[i] >= 32) && (buf[i] < 127);
178 warn = warn || ! printable;
179 fprintf(stream, "%c", printable ? buf[i] : '.');
180 }
181 fprintf(stream, "\n");
182 if (warn)
183 warning("binary data detected, use -x mode instead");
184 }
185 }
186
187 /* basic field arithmetic in GF(2^deg) */
188
field_add(mpz_t z,const mpz_t x,const mpz_t y)189 void field_add(mpz_t z, const mpz_t x, const mpz_t y)
190 {
191 mpz_xor(z, x, y);
192 }
193
field_mult(mpz_t z,const mpz_t x,const mpz_t y)194 void field_mult(mpz_t z, const mpz_t x, const mpz_t y)
195 {
196 mpz_t b;
197 unsigned int i;
198 assert(z != y);
199 mpz_init_set(b, x);
200 if (mpz_tstbit(y, 0))
201 mpz_set(z, b);
202 else
203 mpz_set_ui(z, 0);
204 for(i = 1; i < degree; i++) {
205 mpz_lshift(b, b, 1);
206 if (mpz_tstbit(b, degree))
207 mpz_xor(b, b, poly);
208 if (mpz_tstbit(y, i))
209 mpz_xor(z, z, b);
210 }
211 mpz_clear(b);
212 }
213
field_invert(mpz_t z,const mpz_t x)214 void field_invert(mpz_t z, const mpz_t x)
215 {
216 mpz_t u, v, g, h;
217 int i;
218 assert(mpz_cmp_ui(x, 0));
219 mpz_init_set(u, x);
220 mpz_init_set(v, poly);
221 mpz_init_set_ui(g, 0);
222 mpz_set_ui(z, 1);
223 mpz_init(h);
224 while (mpz_cmp_ui(u, 1)) {
225 i = mpz_sizeinbits(u) - mpz_sizeinbits(v);
226 if (i < 0) {
227 mpz_swap(u, v);
228 mpz_swap(z, g);
229 i = -i;
230 }
231 mpz_lshift(h, v, i);
232 mpz_xor(u, u, h);
233 mpz_lshift(h, g, i);
234 mpz_xor(z, z, h);
235 }
236 mpz_clear(u); mpz_clear(v); mpz_clear(g); mpz_clear(h);
237 }
238
239 /* routines for the random number generator */
240
cprng_init(void)241 void cprng_init(void)
242 {
243 if ((cprng = open(RANDOM_SOURCE, O_RDONLY)) < 0)
244 fatal("couldn't open " RANDOM_SOURCE);
245 }
246
cprng_deinit(void)247 void cprng_deinit(void)
248 {
249 if (close(cprng) < 0)
250 fatal("couldn't close " RANDOM_SOURCE);
251 }
252
cprng_read(mpz_t x)253 void cprng_read(mpz_t x)
254 {
255 char buf[MAXDEGREE / 8];
256 unsigned int count;
257 int i;
258 for(count = 0; count < degree / 8; count += i)
259 if ((i = read(cprng, buf + count, degree / 8 - count)) < 0) {
260 close(cprng);
261 fatal("couldn't read from " RANDOM_SOURCE);
262 }
263 mpz_import(x, degree / 8, 1, 1, 0, 0, buf);
264 }
265
266 /* a 64 bit pseudo random permutation (based on the XTEA cipher) */
267
encipher_block(uint32_t * v)268 void encipher_block(uint32_t *v)
269 {
270 uint32_t sum = 0, delta = 0x9E3779B9;
271 int i;
272 for(i = 0; i < 32; i++) {
273 v[0] += (((v[1] << 4) ^ (v[1] >> 5)) + v[1]) ^ sum;
274 sum += delta;
275 v[1] += (((v[0] << 4) ^ (v[0] >> 5)) + v[0]) ^ sum;
276 }
277 }
278
decipher_block(uint32_t * v)279 void decipher_block(uint32_t *v)
280 {
281 uint32_t sum = 0xC6EF3720, delta = 0x9E3779B9;
282 int i;
283 for(i = 0; i < 32; i++) {
284 v[1] -= ((v[0] << 4 ^ v[0] >> 5) + v[0]) ^ sum;
285 sum -= delta;
286 v[0] -= ((v[1] << 4 ^ v[1] >> 5) + v[1]) ^ sum;
287 }
288 }
289
encode_slice(uint8_t * data,int idx,int len,void (* process_block)(uint32_t *))290 void encode_slice(uint8_t *data, int idx, int len,
291 void (*process_block)(uint32_t*))
292 {
293 uint32_t v[2];
294 int i;
295 for(i = 0; i < 2; i++)
296 v[i] = data[(idx + 4 * i) % len] << 24 |
297 data[(idx + 4 * i + 1) % len] << 16 |
298 data[(idx + 4 * i + 2) % len] << 8 | data[(idx + 4 * i + 3) % len];
299 process_block(v);
300 for(i = 0; i < 2; i++) {
301 data[(idx + 4 * i + 0) % len] = v[i] >> 24;
302 data[(idx + 4 * i + 1) % len] = (v[i] >> 16) & 0xff;
303 data[(idx + 4 * i + 2) % len] = (v[i] >> 8) & 0xff;
304 data[(idx + 4 * i + 3) % len] = v[i] & 0xff;
305 }
306 }
307
308 enum encdec {ENCODE, DECODE};
309
encode_mpz(mpz_t x,enum encdec encdecmode)310 void encode_mpz(mpz_t x, enum encdec encdecmode)
311 {
312 uint8_t v[(MAXDEGREE + 8) / 16 * 2];
313 size_t t;
314 int i;
315 memset(v, 0, (degree + 8) / 16 * 2);
316 mpz_export(v, &t, -1, 2, 1, 0, x);
317 if (degree % 16 == 8)
318 v[degree / 8 - 1] = v[degree / 8];
319 if (encdecmode == ENCODE) /* 40 rounds are more than enough!*/
320 for(i = 0; i < 40 * ((int)degree / 8); i += 2)
321 encode_slice(v, i, degree / 8, encipher_block);
322 else
323 for(i = 40 * (degree / 8) - 2; i >= 0; i -= 2)
324 encode_slice(v, i, degree / 8, decipher_block);
325 if (degree % 16 == 8) {
326 v[degree / 8] = v[degree / 8 - 1];
327 v[degree / 8 - 1] = 0;
328 }
329 mpz_import(x, (degree + 8) / 16, -1, 2, 1, 0, v);
330 assert(mpz_sizeinbits(x) <= degree);
331 }
332
333 /* evaluate polynomials efficiently */
334
horner(int n,mpz_t y,const mpz_t x,const mpz_t coeff[])335 void horner(int n, mpz_t y, const mpz_t x, const mpz_t coeff[])
336 {
337 int i;
338 mpz_set(y, x);
339 for(i = n - 1; i; i--) {
340 field_add(y, y, coeff[i]);
341 field_mult(y, y, x);
342 }
343 field_add(y, y, coeff[0]);
344 }
345
346 /* calculate the secret from a set of shares solving a linear equation system */
347
348 #define MPZ_SWAP(A, B) \
349 do { mpz_set(h, A); mpz_set(A, B); mpz_set(B, h); } while(0)
350
restore_secret(int n,void * A,mpz_t b[])351 int restore_secret(int n, void *A, mpz_t b[])
352 {
353 mpz_t (*AA)[n] = (mpz_t (*)[n])A;
354 int i, j, k, found;
355 mpz_t h;
356 mpz_init(h);
357 for(i = 0; i < n; i++) {
358 if (! mpz_cmp_ui(AA[i][i], 0)) {
359 for(found = 0, j = i + 1; j < n; j++)
360 if (mpz_cmp_ui(AA[i][j], 0)) {
361 found = 1;
362 break;
363 }
364 if (! found)
365 return -1;
366 for(k = i; k < n; k++)
367 MPZ_SWAP(AA[k][i], AA[k][j]);
368 MPZ_SWAP(b[i], b[j]);
369 }
370 for(j = i + 1; j < n; j++) {
371 if (mpz_cmp_ui(AA[i][j], 0)) {
372 for(k = i + 1; k < n; k++) {
373 field_mult(h, AA[k][i], AA[i][j]);
374 field_mult(AA[k][j], AA[k][j], AA[i][i]);
375 field_add(AA[k][j], AA[k][j], h);
376 }
377 field_mult(h, b[i], AA[i][j]);
378 field_mult(b[j], b[j], AA[i][i]);
379 field_add(b[j], b[j], h);
380 }
381 }
382 }
383 field_invert(h, AA[n - 1][n - 1]);
384 field_mult(b[n - 1], b[n - 1], h);
385 mpz_clear(h);
386 return 0;
387 }
388
389 /* Prompt for a secret, generate shares for it */
390
split(void)391 void split(void)
392 {
393 unsigned int fmt_len;
394 mpz_t x, y, coeff[opt_threshold];
395 char buf[MAXLINELEN];
396 int deg, i;
397 for(fmt_len = 1, i = opt_number; i >= 10; i /= 10, fmt_len++);
398 if (! opt_quiet) {
399 printf("Generating shares using a (%d,%d) scheme with ",
400 opt_threshold, opt_number);
401 if (opt_security)
402 printf("a %d bit", opt_security);
403 else
404 printf("dynamic");
405 printf(" security level.\n");
406
407 deg = opt_security ? opt_security : MAXDEGREE;
408 fprintf(stderr, "Enter the secret, ");
409 if (opt_hex)
410 fprintf(stderr, "as most %d hex digits: ", deg / 4);
411 else
412 fprintf(stderr, "at most %d ASCII characters: ", deg / 8);
413 }
414 tcsetattr(0, TCSANOW, &echo_off);
415 if (! fgets(buf, sizeof(buf), stdin))
416 fatal("I/O error while reading secret");
417 tcsetattr(0, TCSANOW, &echo_orig);
418 buf[strcspn(buf, "\r\n")] = '\0';
419
420 if (! opt_security) {
421 opt_security = opt_hex ? 4 * ((strlen(buf) + 1) & ~1): 8 * strlen(buf);
422 if (! field_size_valid(opt_security))
423 fatal("security level invalid (secret too long?)");
424 if (! opt_quiet)
425 fprintf(stderr, "Using a %d bit security level.\n", opt_security);
426 }
427
428 field_init(opt_security);
429
430 mpz_init(coeff[0]);
431 field_import(coeff[0], buf, opt_hex);
432
433 if (opt_diffusion) {
434 if (degree >= 64)
435 encode_mpz(coeff[0], ENCODE);
436 else
437 warning("security level too small for the diffusion layer");
438 }
439
440 cprng_init();
441 for(i = 1; i < opt_threshold; i++) {
442 mpz_init(coeff[i]);
443 cprng_read(coeff[i]);
444 }
445 cprng_deinit();
446
447 mpz_init(x);
448 mpz_init(y);
449 for(i = 0; i < opt_number; i++) {
450 mpz_set_ui(x, i + 1);
451 horner(opt_threshold, y, x, (const mpz_t*)coeff);
452 if (opt_token)
453 printf("%s-", opt_token);
454 printf("%0*d-", fmt_len, i + 1);
455 field_print(stdout, y, 1);
456 }
457 mpz_clear(x);
458 mpz_clear(y);
459
460 for(i = 0; i < opt_threshold; i++)
461 mpz_clear(coeff[i]);
462 field_deinit();
463 }
464
465 /* Prompt for shares, calculate the secret */
466
combine(void)467 void combine(void)
468 {
469 mpz_t A[opt_threshold][opt_threshold], y[opt_threshold], x;
470 char buf[MAXLINELEN];
471 char *a, *b;
472 int i, j;
473 unsigned s = 0;
474
475 mpz_init(x);
476 if (! opt_quiet)
477 printf("Enter %d shares separated by newlines:\n", opt_threshold);
478 for (i = 0; i < opt_threshold; i++) {
479 if (! opt_quiet)
480 printf("Share [%d/%d]: ", i + 1, opt_threshold);
481
482 if (! fgets(buf, sizeof(buf), stdin))
483 fatal("I/O error while reading shares");
484 buf[strcspn(buf, "\r\n")] = '\0';
485 if (! (a = strchr(buf, '-')))
486 fatal("invalid syntax");
487 *a++ = 0;
488 if ((b = strchr(a, '-')))
489 *b++ = 0;
490 else
491 b = a, a = buf;
492
493 if (! s) {
494 s = 4 * strlen(b);
495 if (! field_size_valid(s))
496 fatal("share has illegal length");
497 field_init(s);
498 }
499 else
500 if (s != 4 * strlen(b))
501 fatal("shares have different security levels");
502
503 if (! (j = atoi(a)))
504 fatal("invalid share");
505 mpz_set_ui(x, j);
506 mpz_init_set_ui(A[opt_threshold - 1][i], 1);
507 for(j = opt_threshold - 2; j >= 0; j--) {
508 mpz_init(A[j][i]);
509 field_mult(A[j][i], A[j + 1][i], x);
510 }
511 mpz_init(y[i]);
512 field_import(y[i], b, 1);
513 field_mult(x, x, A[0][i]);
514 field_add(y[i], y[i], x);
515 }
516 mpz_clear(x);
517 if (restore_secret(opt_threshold, A, y))
518 fatal("shares inconsistent. Perhaps a single share was used twice");
519
520 if (opt_diffusion) {
521 if (degree >= 64)
522 encode_mpz(y[opt_threshold - 1], DECODE);
523 else
524 warning("security level too small for the diffusion layer");
525 }
526
527 if (! opt_quiet)
528 fprintf(stderr, "Resulting secret: ");
529 field_print(stderr, y[opt_threshold - 1], opt_hex);
530
531 for (i = 0; i < opt_threshold; i++) {
532 for (j = 0; j < opt_threshold; j++)
533 mpz_clear(A[i][j]);
534 mpz_clear(y[i]);
535 }
536 field_deinit();
537 }
538
main(int argc,char * argv[])539 int main(int argc, char *argv[])
540 {
541 char *name;
542 int i;
543
544 #if ! NOMLOCK
545 if (mlockall(MCL_CURRENT | MCL_FUTURE) < 0)
546 switch(errno) {
547 case ENOMEM:
548 warning("couldn't get memory lock (ENOMEM, try to adjust RLIMIT_MEMLOCK!)");
549 break;
550 case EPERM:
551 warning("couldn't get memory lock (EPERM, try UID 0!)");
552 break;
553 case ENOSYS:
554 warning("couldn't get memory lock (ENOSYS, kernel doesn't allow page locking)");
555 break;
556 default:
557 warning("couldn't get memory lock");
558 break;
559 }
560 #endif
561
562 if (getuid() != geteuid())
563 seteuid(getuid());
564
565 tcgetattr(0, &echo_orig);
566 echo_off = echo_orig;
567 echo_off.c_lflag &= ~ECHO;
568
569 opt_help = argc == 1;
570 while((i = getopt(argc, argv, "vDhqQxs:t:n:w:")) != -1)
571 switch(i) {
572 case 'v': opt_showversion = 1; break;
573 case 'h': opt_help = 1; break;
574 case 'q': opt_quiet = 1; break;
575 case 'Q': opt_QUIET = opt_quiet = 1; break;
576 case 'x': opt_hex = 1; break;
577 case 's': opt_security = atoi(optarg); break;
578 case 't': opt_threshold = atoi(optarg); break;
579 case 'n': opt_number = atoi(optarg); break;
580 case 'w': opt_token = optarg; break;
581 case 'D': opt_diffusion = 0; break;
582 default:
583 exit(1);
584 }
585 if (! opt_help && (argc != optind))
586 fatal("invalid argument");
587
588 if ((name = strrchr(argv[0], '/')) == NULL)
589 name = argv[0];
590
591 if (strstr(name, "split")) {
592 if (opt_help || opt_showversion) {
593 puts("Split secrets using Shamir's Secret Sharing Scheme.\n"
594 "\n"
595 "ssss-split -t threshold -n shares [-w token] [-s level]"
596 " [-x] [-q] [-Q] [-D] [-v]"
597 );
598 if (opt_showversion)
599 puts("\nVersion: " VERSION);
600 exit(0);
601 }
602
603 if (opt_threshold < 2)
604 fatal("invalid parameters: invalid threshold value");
605
606 if (opt_number < opt_threshold)
607 fatal("invalid parameters: number of shares smaller than threshold");
608
609 if (opt_security && ! field_size_valid(opt_security))
610 fatal("invalid parameters: invalid security level");
611
612 if (opt_token && (strlen(opt_token) > MAXTOKENLEN))
613 fatal("invalid parameters: token too long");
614
615 split();
616 }
617 else {
618 if (opt_help || opt_showversion) {
619 puts("Combine shares using Shamir's Secret Sharing Scheme.\n"
620 "\n"
621 "ssss-combine -t threshold [-x] [-q] [-Q] [-D] [-v]");
622 if (opt_showversion)
623 puts("\nVersion: " VERSION);
624 exit(0);
625 }
626
627 if (opt_threshold < 2)
628 fatal("invalid parameters: invalid threshold value");
629
630 combine();
631 }
632 return 0;
633 }
634