sss.c
1 /* 2 * Copyright (C) 2021 - This file is part of libecc project 3 * 4 * Authors: 5 * Ryad BENADJILA <ryadbenadjila@gmail.com> 6 * Arnaud EBALARD <arnaud.ebalard@ssi.gouv.fr> 7 * 8 * This software is licensed under a dual BSD and GPL v2 license. 9 * See LICENSE file at the root folder of the project. 10 */ 11 #include "sss_private.h" 12 #include "sss.h" 13 14 /* 15 * The purpose of this example is to implement the SSS 16 * (Shamir's Secret Sharing) scheme based on libecc arithmetic 17 * primitives. The scheme is implemented over a ~256 bit prime 18 * field. 19 * 20 * Secret sharing allows to combine some shares (at least k among n >= k) 21 * to regenerate a secret. The current code also ensures the integrity 22 * of the shares using HMAC. A maximum of (2**16 - 1) shares can be 23 * generated, and beware that the time complexity of generation heavily 24 * increases with k and n, and the time complexity of shares combination 25 * increases with k. 26 * 27 * Shares regeneration from exisiting ones is also offered although it 28 * is expensive in CPU cycles (as the Lagrange interpolation polynomials 29 * have to be evaluated for each existing share before computing new ones). 30 * 31 * !! DISCLAIMER !! 32 * ================ 33 * Some efforts have been put on providing a clean code and constant time 34 * as well as some SCA (side-channel attacks) resistance (e.g. blinding some 35 * operations manipulating secrets). However, no absolute guarantee can be claimed: 36 * use this code knowingly and at your own risks! 37 * 38 * Also, as for all other libecc primitives, beware of randomness sources. By default, 39 * the library uses the OS random sources (e.g. "/dev/urandom"), but the user 40 * is encouraged to adapt the ../external_deps/rand.c source file to combine 41 * multiple sources and add entropy there depending on the context where this 42 * code is integrated. The security level of all the cryptographic primitives 43 * heavily relies on random sources quality. 44 * 45 */ 46 47 #ifndef GET_UINT16_BE 48 #define GET_UINT16_BE(n, b, i) \ 49 do { \ 50 (n) = (u16)( ((u16) (b)[(i) ]) << 8 ) \ 51 | (u16)( ((u16) (b)[(i) + 1]) ); \ 52 } while( 0 ) 53 #endif 54 55 #ifndef PUT_UINT16_BE 56 #define PUT_UINT16_BE(n, b, i) \ 57 do { \ 58 (b)[(i) ] = (u8) ( (n) >> 8 ); \ 59 (b)[(i) + 1] = (u8) ( (n) ); \ 60 } while( 0 ) 61 #endif 62 63 /* The prime number we use: it is close to (2**256-1) but still stricly less 64 * than this value, hence a theoretical security of more than 255 bits but less than 65 * 256 bits. This prime p is used in the prime field of secp256k1, the "bitcoin" 66 * curve. 67 * 68 * This can be modified with another prime, beware however of the size 69 * of the prime to be in line with the shared secrets sizes, and also 70 * that all our shares and secret lie in Fp, and hence are < p, 71 * 72 * Although bigger primes could be used, beware that SSS shares recombination 73 * complexity is quadratic in the number of shares, yielding impractical 74 * computation time when the prime is too big. Also, some elements related to 75 * the share generation (_sss_derive_seed) must be adapated to keep proper entropy 76 * if the prime (size) is modified. 77 */ 78 static const u8 prime[] = { 79 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 80 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 81 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 82 0xff, 0xff, 0xff, 0xfe, 0xff, 0xff, 0xfc, 0x2f, 83 }; 84 85 ATTRIBUTE_WARN_UNUSED_RET static int _sss_derive_seed(fp_t out, const u8 seed[SSS_SECRET_SIZE], u16 idx) 86 { 87 int ret; 88 u8 hmac_val[SHA512_DIGEST_SIZE]; 89 u8 C[2]; 90 u8 len; 91 nn nn_val; 92 93 /* Sanity check on sizes to avoid entropy loss through reduction biases */ 94 MUST_HAVE((SHA512_DIGEST_SIZE >= (2 * SSS_SECRET_SIZE)), ret, err); 95 96 /* out must be initialized with a context */ 97 ret = fp_check_initialized(out); EG(ret, err); 98 99 ret = local_memset(hmac_val, 0, sizeof(hmac_val)); EG(ret, err); 100 ret = local_memset(C, 0, sizeof(C)); EG(ret, err); 101 102 /* Export our idx in big endian representation on two bytes */ 103 PUT_UINT16_BE(idx, C, 0); 104 105 len = sizeof(hmac_val); 106 ret = hmac(seed, SSS_SECRET_SIZE, SHA512, C, sizeof(C), hmac_val, &len); EG(ret, err); 107 108 ret = nn_init_from_buf(&nn_val, hmac_val, len); EG(ret, err); 109 /* Since we will put this in Fp, take the modulo */ 110 ret = nn_mod(&nn_val, &nn_val, &(out->ctx->p)); EG(ret, err); 111 /* Now import our reduced value in Fp as the result of the derivation */ 112 ret = fp_set_nn(out, &nn_val); 113 114 err: 115 /* Cleanup secret data */ 116 IGNORE_RET_VAL(local_memset(hmac_val, 0, sizeof(hmac_val))); 117 IGNORE_RET_VAL(local_memset(C, 0, sizeof(C))); 118 nn_uninit(&nn_val); 119 120 return ret; 121 } 122 123 /***** Raw versions ***********************/ 124 /* SSS shares and secret generation */ 125 ATTRIBUTE_WARN_UNUSED_RET static int _sss_raw_generate(sss_share *shares, u16 k, u16 n, sss_secret *secret, boolean input_secret) 126 { 127 fp_ctx ctx; 128 nn p; 129 fp a0, a, s; 130 fp exp, base, tmp; 131 fp blind, blind_inv; 132 u8 secret_seed[SSS_SECRET_SIZE]; 133 u16 idx_shift, num_shares; 134 int ret; 135 unsigned int i, j; 136 p.magic = WORD(0); 137 exp.magic = base.magic = tmp.magic = s.magic = a.magic = a0.magic = WORD(0); 138 blind.magic = blind_inv.magic = WORD(0); 139 140 ret = local_memset(secret_seed, 0, sizeof(secret_seed)); EG(ret, err); 141 142 MUST_HAVE((shares != NULL) && (secret != NULL), ret, err); 143 /* Sanity checks */ 144 MUST_HAVE((n <= (u16)(0xffff - 1)), ret, err); 145 MUST_HAVE((k <= n), ret, err); 146 MUST_HAVE((k >= 1), ret, err); 147 MUST_HAVE((SSS_SECRET_SIZE == sizeof(prime)), ret, err); 148 149 /* Import our prime number and create the Fp context */ 150 ret = nn_init_from_buf(&p, prime, sizeof(prime)); EG(ret, err); 151 ret = fp_ctx_init_from_p(&ctx, &p); EG(ret, err); 152 153 /* Generate a secret seed of the size of the secret that will be our base to 154 * generate the plolynomial coefficients. 155 */ 156 ret = get_random(secret_seed, sizeof(secret_seed)); EG(ret, err); 157 /* NOTE: although we could generate all our a[i] coefficients using our randomness 158 * source, we prefer to derive them from a single secret seed in order to optimize 159 * the storage space as our share generation algorithm needs to parse these a[i] multiple 160 * times. This time / memory tradeoff saves a lot of memory space for embedded contexts and 161 * avoids "malloc" usage (preserving the "no dynamic allocation" philosophy of libecc). 162 * 163 * Our secret seed is SSS_SECRET_SIZE long, so on the security side there should be no 164 * loss of strength/entropy. For each index i, a[i] is computed as follows: 165 * 166 * a[i] = HMAC(secret_seed, i) 167 * where the HMAC is interpreted as a value in Fp (i.e. modulo p), and i is represented 168 * as a string of 2 elements. The HMAC uses a hash function of at least twice the 169 * size of the secret to avoid biases in modular reduction. 170 */ 171 172 /* a0 is either derived from the secret seed or taken from input if 173 * provided. 174 */ 175 ret = fp_init(&a0, &ctx); EG(ret, err); 176 if(input_secret == SSS_TRUE){ 177 /* Import the secret the user provides 178 * XXX: NOTE: the user shared secret MUST be in Fp! Since our prime is < (2**256 - 1), 179 * some 256 bit strings can be rejected here (namely those >= p and <= (2**256 - 1)). 180 */ 181 ret = fp_import_from_buf(&a0, secret->secret, SSS_SECRET_SIZE); EG(ret, err); 182 } 183 else{ 184 /* Generate the secret from our seed */ 185 ret = _sss_derive_seed(&a0, secret_seed, 0); EG(ret, err); 186 } 187 188 /* Compute the shares P(x) for x in [idx_shift + 0, ..., idx_shift + n] (or 189 * [idx_shift + 0, ..., idx_shift + n + 1] to avoid the 0 index), 190 * with idx_shift a non-zero random index shift to avoid leaking the number of shares. 191 */ 192 ret = fp_init(&base, &ctx); EG(ret, err); 193 ret = fp_init(&exp, &ctx); EG(ret, err); 194 ret = fp_init(&tmp, &ctx); EG(ret, err); 195 ret = fp_init(&s, &ctx); EG(ret, err); 196 ret = fp_init(&a, &ctx); EG(ret, err); 197 /* Get a random blind mask and invert it */ 198 ret = fp_get_random(&blind, &ctx); EG(ret, err); 199 ret = fp_init(&blind_inv, &ctx); EG(ret, err); 200 ret = fp_inv(&blind_inv, &blind); EG(ret, err); 201 /* Generate a non-zero random index base for x to avoid leaking 202 * the number of shares. We could use a static sequence from x = 1 to n 203 * but this would leak some information to the participants about the number 204 * of shares (e.g. if a participant gets the share with x = 4, she surely knows 205 * that n >= 4). To avoid the leak we randomize the base value of the index where 206 * we begin our x. 207 */ 208 idx_shift = 0; 209 while(idx_shift == 0){ 210 ret = get_random((u8*)&idx_shift, sizeof(idx_shift)); EG(ret, err); 211 } 212 num_shares = 0; 213 i = 0; 214 while(num_shares < n){ 215 _sss_raw_share *cur_share_i = &(shares[num_shares].raw_share); 216 u16 curr_idx = (u16)(idx_shift + i); 217 if(curr_idx == 0){ 218 /* Skip the index 0 specific case */ 219 i++; 220 continue; 221 } 222 /* Set s[i] to the a[0] as blinded initial value */ 223 ret = fp_mul(&s, &blind, &a0); EG(ret, err); 224 /* Get a random base x as u16 for share index */ 225 ret = fp_set_word_value(&base, (word_t)curr_idx); EG(ret, err); 226 /* Set the exp to 1 */ 227 ret = fp_one(&exp); EG(ret, err); 228 for(j = 1; j < k; j++){ 229 /* Compute x**j by iterative multiplications */ 230 ret = fp_mul_monty(&exp, &exp, &base); EG(ret, err); 231 /* Compute our a[j] coefficient */ 232 ret = _sss_derive_seed(&a, secret_seed, (u16)j); EG(ret, err); 233 /* Blind a[j] */ 234 ret = fp_mul_monty(&a, &a, &blind); EG(ret, err); 235 /* NOTE1: actually, the real a[j] coefficients are _sss_derive_seed(secret_seed, j) 236 * multiplied by some power of r^-1 (the Montgomery constant), but this is OK as 237 * we need any random values (computable from the secret seed) here. We use this "trick" 238 * to be able to use our more performant redcified versions of Fp multiplication. 239 * 240 * NOTE2: this trick makes also this generation not deterministic with the same seed 241 * on binaries with different WORD sizes (16, 32, 64 bits) as the r Montgomery constant will 242 * differ depending on this size. However, this is not really an issue per se for our SSS 243 * as we are in our generation primitive and the a[j] coefficients are expected to be 244 * random (the only drawback is that deterministic test vectors will not be consistent 245 * across WORD sizes). 246 */ 247 /* Accumulate */ 248 ret = fp_mul_monty(&tmp, &exp, &a); EG(ret, err); 249 ret = fp_add(&s, &s, &tmp); EG(ret, err); 250 } 251 /* Export the computed share */ 252 PUT_UINT16_BE(curr_idx, (u8*)&(cur_share_i->index), 0); 253 /* Unblind */ 254 ret = fp_mul(&s, &s, &blind_inv); EG(ret, err); 255 ret = fp_export_to_buf(cur_share_i->share, SSS_SECRET_SIZE, &s); EG(ret, err); 256 num_shares++; 257 i++; 258 } 259 /* The secret is a[0] */ 260 ret = fp_export_to_buf(secret->secret, SSS_SECRET_SIZE, &a0); 261 262 err: 263 /* We can throw away our secret seed now that the shares have 264 * been generated. 265 */ 266 IGNORE_RET_VAL(local_memset(secret_seed, 0, sizeof(secret_seed))); 267 IGNORE_RET_VAL(local_memset(&ctx, 0, sizeof(ctx))); 268 nn_uninit(&p); 269 fp_uninit(&a0); 270 fp_uninit(&a); 271 fp_uninit(&s); 272 fp_uninit(&base); 273 fp_uninit(&exp); 274 fp_uninit(&tmp); 275 fp_uninit(&blind); 276 fp_uninit(&blind_inv); 277 278 return ret; 279 } 280 281 /* SSS helper to compute Lagrange interpolation on an input value. 282 * - k is the number of shares pointed by the shares pointer 283 * - secret is the computed secret 284 * - val is the 'index' on which the Lagrange interpolation must be computed, i.e. 285 * the idea is to have using Lagrage formulas the value f(val) where f is our polynomial. Of course 286 * the proper value can only be computed if enough shares k are provided (the interpolation 287 * does not hold in other cases and the result will be an incorrect value) 288 */ 289 ATTRIBUTE_WARN_UNUSED_RET static int _sss_raw_lagrange(const sss_share *shares, u16 k, sss_secret *secret, u16 val) 290 { 291 fp_ctx ctx; 292 nn p; 293 fp s, x, y; 294 fp x_i, x_j, tmp, tmp2; 295 fp blind, blind_inv, r_inv; 296 int ret; 297 unsigned int i, j; 298 p.magic = WORD(0); 299 x_i.magic = x_j.magic = tmp.magic = tmp2.magic = s.magic = y.magic = x.magic = WORD(0); 300 blind.magic = blind_inv.magic = r_inv.magic = WORD(0); 301 302 MUST_HAVE((shares != NULL) && (secret != NULL), ret, err); 303 /* Sanity checks */ 304 MUST_HAVE((k >= 1), ret, err); 305 MUST_HAVE((SSS_SECRET_SIZE == sizeof(prime)), ret, err); 306 307 /* Import our prime number and create the Fp context */ 308 ret = nn_init_from_buf(&p, prime, sizeof(prime)); EG(ret, err); 309 ret = fp_ctx_init_from_p(&ctx, &p); EG(ret, err); 310 311 /* Recombine our shared secrets */ 312 ret = fp_init(&s, &ctx); EG(ret, err); 313 ret = fp_init(&y, &ctx); EG(ret, err); 314 ret = fp_init(&x_i, &ctx); EG(ret, err); 315 ret = fp_init(&x_j, &ctx); EG(ret, err); 316 ret = fp_init(&tmp, &ctx); EG(ret, err); 317 ret = fp_init(&tmp2, &ctx); EG(ret, err); 318 if(val != 0){ 319 /* NOTE: we treat the case 'val = 0' in a specific case for 320 * optimization. This optimization is of interest since computing 321 * f(0) (where f(.) is our polynomial) is the formula for getting the 322 * SSS secret (which happens to be the constant of degree 0 of the 323 * polynomial). 324 */ 325 ret = fp_init(&x, &ctx); EG(ret, err); 326 ret = fp_set_word_value(&x, (word_t)val); EG(ret, err); 327 } 328 /* Get a random blind mask and invert it */ 329 ret = fp_get_random(&blind, &ctx); EG(ret, err); 330 ret = fp_init(&blind_inv, &ctx); EG(ret, err); 331 ret = fp_inv(&blind_inv, &blind); EG(ret, err); 332 /* Perform the computation of r^-1 to optimize our multiplications using Montgomery 333 * multiplication in the main loop. 334 */ 335 ret = fp_init(&r_inv, &ctx); EG(ret, err); 336 ret = fp_set_nn(&r_inv, &(ctx.r)); EG(ret, err); 337 ret = fp_inv(&r_inv, &r_inv); EG(ret, err); 338 /* Proceed with the interpolation */ 339 for(i = 0; i < k; i++){ 340 u16 curr_idx; 341 const _sss_raw_share *cur_share_i = &(shares[i].raw_share); 342 /* Import s[i] */ 343 ret = fp_import_from_buf(&s, cur_share_i->share, SSS_SECRET_SIZE); EG(ret, err); 344 /* Blind s[i] */ 345 ret = fp_mul_monty(&s, &s, &blind); EG(ret, err); 346 /* Get the index */ 347 GET_UINT16_BE(curr_idx, (const u8*)&(cur_share_i->index), 0); 348 ret = fp_set_word_value(&x_i, (word_t)(curr_idx)); EG(ret, err); 349 /* Initialize multiplication with "one" (actually Montgomery r^-1 for multiplication optimization) */ 350 ret = fp_copy(&tmp2, &r_inv); EG(ret, err); 351 /* Compute the product for all k other than i 352 * NOTE: we use fp_mul in its redcified version as the multiplication by r^-1 is 353 * cancelled by the fraction of (x_j - x) * r^-1 / (x_j - x_i) * r^-1 = (x_j - x) / (x_j - x_i) 354 */ 355 for(j = 0; j < k; j++){ 356 const _sss_raw_share *cur_share_j = &(shares[j].raw_share); 357 GET_UINT16_BE(curr_idx, (const u8*)&(cur_share_j->index), 0); 358 ret = fp_set_word_value(&x_j, (word_t)(curr_idx)); EG(ret, err); 359 if(j != i){ 360 if(val != 0){ 361 ret = fp_sub(&tmp, &x_j, &x); EG(ret, err); 362 ret = fp_mul_monty(&s, &s, &tmp); EG(ret, err); 363 } 364 else{ 365 /* NOTE: we treat the case 'val = 0' in a specific case for 366 * optimization. This optimization is of interest since computing 367 * f(0) (where f(.) is our polynomial) is the formula for getting the 368 * SSS secret (which happens to be the constant of degree 0 of the 369 * polynomial). 370 */ 371 ret = fp_mul_monty(&s, &s, &x_j); EG(ret, err); 372 } 373 ret = fp_sub(&tmp, &x_j, &x_i); EG(ret, err); 374 ret = fp_mul_monty(&tmp2, &tmp2, &tmp); EG(ret, err); 375 } 376 } 377 /* Invert all the (x_j - x_i) poducts */ 378 ret = fp_inv(&tmp, &tmp2); EG(ret, err); 379 ret = fp_mul_monty(&s, &s, &tmp); EG(ret, err); 380 /* Accumulate in secret */ 381 ret = fp_add(&y, &y, &s); EG(ret, err); 382 } 383 /* Unblind y */ 384 ret = fp_redcify(&y, &y); EG(ret, err); 385 ret = fp_mul(&y, &y, &blind_inv); EG(ret, err); 386 /* We should have our secret in y */ 387 ret = fp_export_to_buf(secret->secret, SSS_SECRET_SIZE, &y); 388 389 err: 390 IGNORE_RET_VAL(local_memset(&ctx, 0, sizeof(ctx))); 391 nn_uninit(&p); 392 fp_uninit(&s); 393 fp_uninit(&y); 394 fp_uninit(&x_i); 395 fp_uninit(&x_j); 396 fp_uninit(&tmp); 397 fp_uninit(&tmp2); 398 fp_uninit(&blind); 399 fp_uninit(&blind_inv); 400 fp_uninit(&r_inv); 401 if(val != 0){ 402 fp_uninit(&x); 403 } 404 405 return ret; 406 } 407 408 409 /* SSS shares and secret combination */ 410 ATTRIBUTE_WARN_UNUSED_RET static int _sss_raw_combine(const sss_share *shares, u16 k, sss_secret *secret) 411 { 412 return _sss_raw_lagrange(shares, k, secret, 0); 413 } 414 415 /***** Secure versions (public APIs) ***********************/ 416 /* SSS shares and secret generation: 417 * Inputs: 418 * - n: is the number of shares to generate 419 * - k: the quorum of shares to regenerate the secret (of course k <= n) 420 * - secret: the secret value when input_secret is set to 'true' 421 * Output: 422 * - shares: a pointer to the generated n shares 423 * - secret: the secret value when input_secret is set to 'false', this 424 * value being randomly generated 425 */ 426 int sss_generate(sss_share *shares, unsigned short k, unsigned short n, sss_secret *secret, boolean input_secret) 427 { 428 int ret; 429 unsigned int i; 430 u8 len; 431 u8 session_id[SSS_SESSION_ID_SIZE]; 432 433 ret = local_memset(session_id, 0, sizeof(session_id)); EG(ret, err); 434 435 /* Generate raw shares */ 436 ret = _sss_raw_generate(shares, k, n, secret, input_secret); EG(ret, err); 437 438 /* Sanity check */ 439 MUST_HAVE((SSS_HMAC_SIZE == sizeof(shares[0].raw_share_hmac)), ret, err); 440 MUST_HAVE((SHA256_DIGEST_SIZE >= sizeof(shares[0].raw_share_hmac)), ret, err); 441 442 /* Generate a random session ID */ 443 ret = get_random(session_id, sizeof(session_id)); EG(ret, err); 444 445 /* Compute the authenticity seal for each share with HMAC */ 446 for(i = 0; i < n; i++){ 447 _sss_raw_share *cur_share = &(shares[i].raw_share); 448 u8 *cur_id = (u8*)&(shares[i].session_id); 449 u8 *cur_share_hmac = (u8*)&(shares[i].raw_share_hmac); 450 /* NOTE: we 'abuse' casts here for shares[i].raw_share to u8*, but this should be OK since 451 * our structures are packed. 452 */ 453 const u8 *inputs[3] = { (const u8*)cur_share, cur_id, NULL }; 454 const u32 ilens[3] = { sizeof(*cur_share), SSS_SESSION_ID_SIZE, 0 }; 455 456 /* Copy the session ID */ 457 ret = local_memcpy(cur_id, session_id, SSS_SESSION_ID_SIZE); EG(ret, err); 458 459 len = SSS_HMAC_SIZE; 460 ret = hmac_scattered((const u8*)secret, SSS_SECRET_SIZE, SHA256, inputs, ilens, cur_share_hmac, &len); EG(ret, err); 461 } 462 463 err: 464 IGNORE_RET_VAL(local_memset(session_id, 0, sizeof(session_id))); 465 466 return ret; 467 } 468 469 /* SSS shares and secret combination 470 * Inputs: 471 * - k: the quorum of shares to regenerate the secret 472 * - shares: a pointer to the k shares 473 * Output: 474 * - secret: the secret value computed from the k shares 475 */ 476 int sss_combine(const sss_share *shares, unsigned short k, sss_secret *secret) 477 { 478 int ret, cmp; 479 unsigned int i; 480 u8 hmac_val[SSS_HMAC_SIZE]; 481 u8 len; 482 483 ret = local_memset(hmac_val, 0, sizeof(hmac_val)); EG(ret, err); 484 485 /* Recombine raw shares */ 486 ret = _sss_raw_combine(shares, k, secret); EG(ret, err); 487 488 /* Compute and check the authenticity seal for each HMAC */ 489 for(i = 0; i < k; i++){ 490 const _sss_raw_share *cur_share = &(shares[i].raw_share); 491 const u8 *cur_id = (const u8*)&(shares[i].session_id); 492 const u8 *cur_id0 = (const u8*)&(shares[0].session_id); 493 const u8 *cur_share_hmac = (const u8*)&(shares[i].raw_share_hmac); 494 /* NOTE: we 'abuse' casts here for shares[i].raw_share to u8*, but this should be OK since 495 * our structures are packed. 496 */ 497 const u8 *inputs[3] = { (const u8*)cur_share, cur_id, NULL }; 498 const u32 ilens[3] = { sizeof(*cur_share), SSS_SESSION_ID_SIZE, 0 }; 499 500 /* Check that all our shares have the same session ID, return an error otherwise */ 501 ret = are_equal(cur_id, cur_id0, SSS_SESSION_ID_SIZE, &cmp); EG(ret, err); 502 if(!cmp){ 503 #ifdef VERBOSE 504 ext_printf("[-] sss_combine error for share %d / %d: session ID is not OK!\n", i, k); 505 #endif 506 ret = -1; 507 goto err; 508 } 509 510 len = sizeof(hmac_val); 511 ret = hmac_scattered((const u8*)secret, SSS_SECRET_SIZE, SHA256, inputs, ilens, hmac_val, &len); EG(ret, err); 512 513 /* Check the HMAC */ 514 ret = are_equal(hmac_val, cur_share_hmac, len, &cmp); EG(ret, err); 515 if(!cmp){ 516 #ifdef VERBOSE 517 ext_printf("[-] sss_combine error for share %d / %d: HMAC is not OK!\n", i, k); 518 #endif 519 ret = -1; 520 goto err; 521 } 522 } 523 524 err: 525 IGNORE_RET_VAL(local_memset(hmac_val, 0, sizeof(hmac_val))); 526 527 return ret; 528 } 529 530 /* SSS shares regeneration from existing shares 531 * Inputs: 532 * - shares: a pointer to the input k shares allowing the regeneration 533 * - n: is the number of shares to regenerate 534 * - k: the input shares (of course k <= n) 535 * Output: 536 * - shares: a pointer to the generated n shares (among which the k first are 537 * the ones provided as inputs) 538 * - secret: the recomputed secret value 539 */ 540 int sss_regenerate(sss_share *shares, unsigned short k, unsigned short n, sss_secret *secret) 541 { 542 int ret, cmp; 543 unsigned int i; 544 u16 max_idx, num_shares; 545 u8 hmac_val[SSS_HMAC_SIZE]; 546 u8 len; 547 548 /* Sanity check */ 549 MUST_HAVE((n <= (u16)(0xffff - 1)), ret, err); 550 MUST_HAVE((n >= k), ret, err); 551 552 ret = local_memset(hmac_val, 0, sizeof(hmac_val)); EG(ret, err); 553 554 /* Compute the secret */ 555 ret = _sss_raw_lagrange(shares, k, secret, 0); EG(ret, err); 556 /* Check the authenticity of our shares */ 557 for(i = 0; i < k; i++){ 558 _sss_raw_share *cur_share = &(shares[i].raw_share); 559 u8 *cur_id = (u8*)&(shares[i].session_id); 560 u8 *cur_id0 = (u8*)&(shares[0].session_id); 561 u8 *cur_share_hmac = (u8*)&(shares[i].raw_share_hmac); 562 /* NOTE: we 'abuse' casts here for shares[i].raw_share to u8*, but this should be OK since 563 * our structures are packed. 564 */ 565 const u8 *inputs[3] = { (const u8*)cur_share, cur_id, NULL }; 566 const u32 ilens[3] = { sizeof(*cur_share), SSS_SESSION_ID_SIZE, 0 }; 567 568 /* Check that all our shares have the same session ID, return an error otherwise */ 569 ret = are_equal(cur_id, cur_id0, SSS_SESSION_ID_SIZE, &cmp); EG(ret, err); 570 if(!cmp){ 571 #ifdef VERBOSE 572 ext_printf("[-] sss_regenerate error for share %d / %d: session ID is not OK!\n", i, k); 573 #endif 574 ret = -1; 575 goto err; 576 } 577 578 len = sizeof(hmac_val); 579 /* NOTE: we 'abuse' cast here for secret to (const u8*), but this should be OK since our 580 * structures are packed. 581 */ 582 ret = hmac_scattered((const u8*)secret, SSS_SECRET_SIZE, SHA256, inputs, ilens, hmac_val, &len); EG(ret, err); 583 ret = are_equal(hmac_val, cur_share_hmac, len, &cmp); EG(ret, err); 584 if(!cmp){ 585 #ifdef VERBOSE 586 ext_printf("[-] sss_regenerate error for share %d / %d: HMAC is not OK!\n", i, k); 587 #endif 588 ret = -1; 589 goto err; 590 } 591 } 592 593 /* Our secret regeneration consists of determining the maximum index, and 594 * proceed with Lagrange interpolation on new values. 595 */ 596 max_idx = 0; 597 for(i = 0; i < k; i++){ 598 u16 curr_idx; 599 GET_UINT16_BE(curr_idx, (u8*)&(shares[i].raw_share.index), 0); 600 if(curr_idx > max_idx){ 601 max_idx = curr_idx; 602 } 603 } 604 /* Now regenerate as many shares as we need */ 605 num_shares = 0; 606 i = k; 607 while(num_shares < (n - k)){ 608 _sss_raw_share *cur_share = &(shares[k + num_shares].raw_share); 609 u8 *cur_id = (u8*)&(shares[k + num_shares].session_id); 610 u8 *cur_id0 = (u8*)&(shares[0].session_id); 611 u8 *cur_share_hmac = (u8*)&(shares[k + num_shares].raw_share_hmac); 612 u16 curr_idx; 613 /* NOTE: we 'abuse' casts here for shares[i].raw_share.share to sss_secret*, but this should be OK since 614 * our shares[i].raw_share.share is a SSS_SECRET_SIZE as the sss_secret.secret type encapsulates and our 615 * structures are packed. 616 */ 617 const u8 *inputs[3] = { (const u8*)cur_share, cur_id, NULL }; 618 const u32 ilens[3] = { sizeof(*cur_share), SSS_SESSION_ID_SIZE, 0 }; 619 620 /* Skip the index = 0 case */ 621 curr_idx = (u16)(max_idx + (u16)(i - k + 1)); 622 if(curr_idx == 0){ 623 i++; 624 continue; 625 } 626 627 /* Copy our session ID */ 628 ret = local_memcpy(cur_id, cur_id0, SSS_SESSION_ID_SIZE); EG(ret, err); 629 630 ret = _sss_raw_lagrange(shares, k, (sss_secret*)(cur_share->share), curr_idx); EG(ret, err); 631 PUT_UINT16_BE(curr_idx, (u8*)&(cur_share->index), 0); 632 633 /* Compute the HMAC */ 634 len = SSS_HMAC_SIZE; 635 ret = hmac_scattered((const u8*)secret, SSS_SECRET_SIZE, SHA256, inputs, ilens, cur_share_hmac, &len); EG(ret, err); 636 num_shares++; 637 i++; 638 } 639 640 err: 641 IGNORE_RET_VAL(local_memset(hmac_val, 0, sizeof(hmac_val))); 642 643 return ret; 644 } 645 646 647 /********* main test program for SSS *************/ 648 #ifdef SSS 649 #include <libecc/utils/print_buf.h> 650 651 #define K 50 652 #define N 150 653 #define MAX_N 200 654 655 int main(int argc, char *argv[]) 656 { 657 int ret = 0; 658 unsigned int i; 659 sss_share shares[MAX_N]; 660 sss_share shares_[MAX_N]; 661 sss_secret secret; 662 663 FORCE_USED_VAR(argc); 664 FORCE_USED_VAR(argv); 665 666 /* Generate N shares for SSS with at least K shares OK among N */ 667 ext_printf("[+] Generating the secrets %d / %d, call should be OK\n", K, N); 668 ret = local_memset(&secret, 0x00, sizeof(secret)); EG(ret, err); 669 /* NOTE: 'false' here means that we let the library generate the secret randomly */ 670 ret = sss_generate(shares, K, N, &secret, SSS_FALSE); 671 if(ret){ 672 ext_printf(" [X] Error: sss_generate error\n"); 673 goto err; 674 } 675 else{ 676 buf_print(" secret", (u8*)&secret, SSS_SECRET_SIZE); EG(ret, err); 677 } 678 /* Shuffle shares */ 679 for(i = 0; i < N; i++){ 680 shares_[i] = shares[N - 1 - i]; 681 } 682 683 /* Combine (k-1) shares: this call should trigger an ERROR */ 684 ext_printf("[+] Combining the secrets with less shares: call should trigger an error\n"); 685 ret = local_memset(&secret, 0x00, sizeof(secret)); EG(ret, err); 686 ret = sss_combine(shares_, K - 1, &secret); 687 if (ret) { 688 ext_printf(" [X] Error: sss_combine error\n"); 689 } else{ 690 buf_print(" secret", (u8*)&secret, SSS_SECRET_SIZE); 691 } 692 693 /* Combine k shares: this call should be OK and recombine the initial 694 * secret 695 */ 696 ext_printf("[+] Combining the secrets with minimum shares: call should be OK\n"); 697 ret = local_memset(&secret, 0x00, sizeof(secret)); EG(ret, err); 698 ret = sss_combine(shares_, K, &secret); 699 if (ret) { 700 ext_printf(" [X] Error: sss_combine error\n"); 701 goto err; 702 } else { 703 buf_print(" secret", (u8*)&secret, SSS_SECRET_SIZE); 704 } 705 706 /* Combine k shares: this call should be OK and recombine the initial 707 * secret 708 */ 709 ext_printf("[+] Combining the secrets with more shares: call should be OK\n"); 710 ret = local_memset(&secret, 0x00, sizeof(secret)); EG(ret, err); 711 ret = sss_combine(shares_, K + 1, &secret); 712 if (ret) { 713 ext_printf(" [X] Error: sss_combine error\n"); 714 goto err; 715 } else { 716 buf_print(" secret", (u8*)&secret, SSS_SECRET_SIZE); 717 } 718 719 /* Combine with a corrupted share: call should trigger an error */ 720 ext_printf("[+] Combining the secrets with more shares but one corrupted: call should trigger an error\n"); 721 ret = local_memset(&secret, 0x00, sizeof(secret)); EG(ret, err); 722 shares_[K].raw_share.share[0] = 0x00; 723 ret = sss_combine(shares_, K + 1, &secret); 724 if (ret) { 725 ext_printf(" [X] Error: sss_combine error\n"); 726 } else { 727 buf_print(" secret", (u8*)&secret, SSS_SECRET_SIZE); 728 } 729 730 /* Regenerate more shares! call should be OK */ 731 ext_printf("[+] Regenerating more shares: call should be OK\n"); 732 ret = local_memset(&secret, 0x00, sizeof(secret)); EG(ret, err); 733 ret = sss_regenerate(shares, K, MAX_N, &secret); EG(ret, err); 734 if (ret) { 735 ext_printf(" [X] Error: sss_regenerate error\n"); 736 goto err; 737 } else { 738 buf_print(" secret", (u8*)&secret, SSS_SECRET_SIZE); 739 } 740 /* Shuffle shares */ 741 for(i = 0; i < MAX_N; i++){ 742 shares_[i] = shares[MAX_N - 1 - i]; 743 } 744 745 /* Combine newly generated shares: call should be OK */ 746 ext_printf("[+] Combining the secrets with newly generated shares: call should be OK\n"); 747 ret = local_memset(&secret, 0x00, sizeof(secret)); EG(ret, err); 748 ret = sss_combine(shares_, K, &secret); 749 if (ret) { 750 ext_printf(" [X] Error: sss_combine error\n"); 751 goto err; 752 } else { 753 buf_print(" secret", (u8*)&secret, SSS_SECRET_SIZE); 754 } 755 756 /* Modify the session ID of one of the shares: call should trigger an error */ 757 ext_printf("[+] Combining the secrets with newly generated shares and a bad session ID: call should trigger an error\n"); 758 ret = local_memset(&secret, 0x00, sizeof(secret)); EG(ret, err); 759 shares_[1].session_id[0] = 0x00; 760 ret = sss_combine(shares_, K, &secret); 761 if (ret) { 762 ext_printf(" [X] Error: sss_combine error\n"); 763 } else { 764 buf_print(" secret", (u8*)&secret, SSS_SECRET_SIZE); 765 } 766 767 ret = 0; 768 769 err: 770 return ret; 771 } 772 #endif