/*
* Copyright (C) 2021 - This file is part of libecc project
*
* Authors:
* Ryad BENADJILA <ryadbenadjila@gmail.com>
* Arnaud EBALARD <arnaud.ebalard@ssi.gouv.fr>
*
* This software is licensed under a dual BSD and GPL v2 license.
* See LICENSE file at the root folder of the project.
*/
#include "sss_private.h"
#include "sss.h"
/*
* The purpose of this example is to implement the SSS
* (Shamir's Secret Sharing) scheme based on libecc arithmetic
* primitives. The scheme is implemented over a ~256 bit prime
* field.
*
* Secret sharing allows to combine some shares (at least k among n >= k)
* to regenerate a secret. The current code also ensures the integrity
* of the shares using HMAC. A maximum of (2**16 - 1) shares can be
* generated, and beware that the time complexity of generation heavily
* increases with k and n, and the time complexity of shares combination
* increases with k.
*
* Shares regeneration from exisiting ones is also offered although it
* is expensive in CPU cycles (as the Lagrange interpolation polynomials
* have to be evaluated for each existing share before computing new ones).
*
* !! DISCLAIMER !!
* ================
* Some efforts have been put on providing a clean code and constant time
* as well as some SCA (side-channel attacks) resistance (e.g. blinding some
* operations manipulating secrets). However, no absolute guarantee can be claimed:
* use this code knowingly and at your own risks!
*
* Also, as for all other libecc primitives, beware of randomness sources. By default,
* the library uses the OS random sources (e.g. "/dev/urandom"), but the user
* is encouraged to adapt the ../external_deps/rand.c source file to combine
* multiple sources and add entropy there depending on the context where this
* code is integrated. The security level of all the cryptographic primitives
* heavily relies on random sources quality.
*
*/
#ifndef GET_UINT16_BE
#define GET_UINT16_BE(n, b, i) \
do { \
(n) = (u16)( ((u16) (b)[(i) ]) << 8 ) \
| (u16)( ((u16) (b)[(i) + 1]) ); \
} while( 0 )
#endif
#ifndef PUT_UINT16_BE
#define PUT_UINT16_BE(n, b, i) \
do { \
(b)[(i) ] = (u8) ( (n) >> 8 ); \
(b)[(i) + 1] = (u8) ( (n) ); \
} while( 0 )
#endif
/* The prime number we use: it is close to (2**256-1) but still stricly less
* than this value, hence a theoretical security of more than 255 bits but less than
* 256 bits. This prime p is used in the prime field of secp256k1, the "bitcoin"
* curve.
*
* This can be modified with another prime, beware however of the size
* of the prime to be in line with the shared secrets sizes, and also
* that all our shares and secret lie in Fp, and hence are < p,
*
* Although bigger primes could be used, beware that SSS shares recombination
* complexity is quadratic in the number of shares, yielding impractical
* computation time when the prime is too big. Also, some elements related to
* the share generation (_sss_derive_seed) must be adapated to keep proper entropy
* if the prime (size) is modified.
*/
static const u8 prime[] = {
0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
0xff, 0xff, 0xff, 0xfe, 0xff, 0xff, 0xfc, 0x2f,
};
ATTRIBUTE_WARN_UNUSED_RET static int _sss_derive_seed(fp_t out, const u8 seed[SSS_SECRET_SIZE], u16 idx)
{
int ret;
u8 hmac_val[SHA512_DIGEST_SIZE];
u8 C[2];
u8 len;
nn nn_val;
/* Sanity check on sizes to avoid entropy loss through reduction biases */
MUST_HAVE((SHA512_DIGEST_SIZE >= (2 * SSS_SECRET_SIZE)), ret, err);
/* out must be initialized with a context */
ret = fp_check_initialized(out); EG(ret, err);
ret = local_memset(hmac_val, 0, sizeof(hmac_val)); EG(ret, err);
ret = local_memset(C, 0, sizeof(C)); EG(ret, err);
/* Export our idx in big endian representation on two bytes */
PUT_UINT16_BE(idx, C, 0);
len = sizeof(hmac_val);
ret = hmac(seed, SSS_SECRET_SIZE, SHA512, C, sizeof(C), hmac_val, &len); EG(ret, err);
ret = nn_init_from_buf(&nn_val, hmac_val, len); EG(ret, err);
/* Since we will put this in Fp, take the modulo */
ret = nn_mod(&nn_val, &nn_val, &(out->ctx->p)); EG(ret, err);
/* Now import our reduced value in Fp as the result of the derivation */
ret = fp_set_nn(out, &nn_val);
err:
/* Cleanup secret data */
IGNORE_RET_VAL(local_memset(hmac_val, 0, sizeof(hmac_val)));
IGNORE_RET_VAL(local_memset(C, 0, sizeof(C)));
nn_uninit(&nn_val);
return ret;
}
/***** Raw versions ***********************/
/* SSS shares and secret generation */
ATTRIBUTE_WARN_UNUSED_RET static int _sss_raw_generate(sss_share *shares, u16 k, u16 n, sss_secret *secret, boolean input_secret)
{
fp_ctx ctx;
nn p;
fp a0, a, s;
fp exp, base, tmp;
fp blind, blind_inv;
u8 secret_seed[SSS_SECRET_SIZE];
u16 idx_shift, num_shares;
int ret;
unsigned int i, j;
p.magic = WORD(0);
exp.magic = base.magic = tmp.magic = s.magic = a.magic = a0.magic = WORD(0);
blind.magic = blind_inv.magic = WORD(0);
ret = local_memset(secret_seed, 0, sizeof(secret_seed)); EG(ret, err);
MUST_HAVE((shares != NULL) && (secret != NULL), ret, err);
/* Sanity checks */
MUST_HAVE((n <= (u16)(0xffff - 1)), ret, err);
MUST_HAVE((k <= n), ret, err);
MUST_HAVE((k >= 1), ret, err);
MUST_HAVE((SSS_SECRET_SIZE == sizeof(prime)), ret, err);
/* Import our prime number and create the Fp context */
ret = nn_init_from_buf(&p, prime, sizeof(prime)); EG(ret, err);
ret = fp_ctx_init_from_p(&ctx, &p); EG(ret, err);
/* Generate a secret seed of the size of the secret that will be our base to
* generate the plolynomial coefficients.
*/
ret = get_random(secret_seed, sizeof(secret_seed)); EG(ret, err);
/* NOTE: although we could generate all our a[i] coefficients using our randomness
* source, we prefer to derive them from a single secret seed in order to optimize
* the storage space as our share generation algorithm needs to parse these a[i] multiple
* times. This time / memory tradeoff saves a lot of memory space for embedded contexts and
* avoids "malloc" usage (preserving the "no dynamic allocation" philosophy of libecc).
*
* Our secret seed is SSS_SECRET_SIZE long, so on the security side there should be no
* loss of strength/entropy. For each index i, a[i] is computed as follows:
*
* a[i] = HMAC(secret_seed, i)
* where the HMAC is interpreted as a value in Fp (i.e. modulo p), and i is represented
* as a string of 2 elements. The HMAC uses a hash function of at least twice the
* size of the secret to avoid biases in modular reduction.
*/
/* a0 is either derived from the secret seed or taken from input if
* provided.
*/
ret = fp_init(&a0, &ctx); EG(ret, err);
if(input_secret == SSS_TRUE){
/* Import the secret the user provides
* XXX: NOTE: the user shared secret MUST be in Fp! Since our prime is < (2**256 - 1),
* some 256 bit strings can be rejected here (namely those >= p and <= (2**256 - 1)).
*/
ret = fp_import_from_buf(&a0, secret->secret, SSS_SECRET_SIZE); EG(ret, err);
}
else{
/* Generate the secret from our seed */
ret = _sss_derive_seed(&a0, secret_seed, 0); EG(ret, err);
}
/* Compute the shares P(x) for x in [idx_shift + 0, ..., idx_shift + n] (or
* [idx_shift + 0, ..., idx_shift + n + 1] to avoid the 0 index),
* with idx_shift a non-zero random index shift to avoid leaking the number of shares.
*/
ret = fp_init(&base, &ctx); EG(ret, err);
ret = fp_init(&exp, &ctx); EG(ret, err);
ret = fp_init(&tmp, &ctx); EG(ret, err);
ret = fp_init(&s, &ctx); EG(ret, err);
ret = fp_init(&a, &ctx); EG(ret, err);
/* Get a random blind mask and invert it */
ret = fp_get_random(&blind, &ctx); EG(ret, err);
ret = fp_init(&blind_inv, &ctx); EG(ret, err);
ret = fp_inv(&blind_inv, &blind); EG(ret, err);
/* Generate a non-zero random index base for x to avoid leaking
* the number of shares. We could use a static sequence from x = 1 to n
* but this would leak some information to the participants about the number
* of shares (e.g. if a participant gets the share with x = 4, she surely knows
* that n >= 4). To avoid the leak we randomize the base value of the index where
* we begin our x.
*/
idx_shift = 0;
while(idx_shift == 0){
ret = get_random((u8*)&idx_shift, sizeof(idx_shift)); EG(ret, err);
}
num_shares = 0;
i = 0;
while(num_shares < n){
_sss_raw_share *cur_share_i = &(shares[num_shares].raw_share);
u16 curr_idx = (u16)(idx_shift + i);
if(curr_idx == 0){
/* Skip the index 0 specific case */
i++;
continue;
}
/* Set s[i] to the a[0] as blinded initial value */
ret = fp_mul(&s, &blind, &a0); EG(ret, err);
/* Get a random base x as u16 for share index */
ret = fp_set_word_value(&base, (word_t)curr_idx); EG(ret, err);
/* Set the exp to 1 */
ret = fp_one(&exp); EG(ret, err);
for(j = 1; j < k; j++){
/* Compute x**j by iterative multiplications */
ret = fp_mul_monty(&exp, &exp, &base); EG(ret, err);
/* Compute our a[j] coefficient */
ret = _sss_derive_seed(&a, secret_seed, (u16)j); EG(ret, err);
/* Blind a[j] */
ret = fp_mul_monty(&a, &a, &blind); EG(ret, err);
/* NOTE1: actually, the real a[j] coefficients are _sss_derive_seed(secret_seed, j)
* multiplied by some power of r^-1 (the Montgomery constant), but this is OK as
* we need any random values (computable from the secret seed) here. We use this "trick"
* to be able to use our more performant redcified versions of Fp multiplication.
*
* NOTE2: this trick makes also this generation not deterministic with the same seed
* on binaries with different WORD sizes (16, 32, 64 bits) as the r Montgomery constant will
* differ depending on this size. However, this is not really an issue per se for our SSS
* as we are in our generation primitive and the a[j] coefficients are expected to be
* random (the only drawback is that deterministic test vectors will not be consistent
* across WORD sizes).
*/
/* Accumulate */
ret = fp_mul_monty(&tmp, &exp, &a); EG(ret, err);
ret = fp_add(&s, &s, &tmp); EG(ret, err);
}
/* Export the computed share */
PUT_UINT16_BE(curr_idx, (u8*)&(cur_share_i->index), 0);
/* Unblind */
ret = fp_mul(&s, &s, &blind_inv); EG(ret, err);
ret = fp_export_to_buf(cur_share_i->share, SSS_SECRET_SIZE, &s); EG(ret, err);
num_shares++;
i++;
}
/* The secret is a[0] */
ret = fp_export_to_buf(secret->secret, SSS_SECRET_SIZE, &a0);
err:
/* We can throw away our secret seed now that the shares have
* been generated.
*/
IGNORE_RET_VAL(local_memset(secret_seed, 0, sizeof(secret_seed)));
IGNORE_RET_VAL(local_memset(&ctx, 0, sizeof(ctx)));
nn_uninit(&p);
fp_uninit(&a0);
fp_uninit(&a);
fp_uninit(&s);
fp_uninit(&base);
fp_uninit(&exp);
fp_uninit(&tmp);
fp_uninit(&blind);
fp_uninit(&blind_inv);
return ret;
}
/* SSS helper to compute Lagrange interpolation on an input value.
* - k is the number of shares pointed by the shares pointer
* - secret is the computed secret
* - val is the 'index' on which the Lagrange interpolation must be computed, i.e.
* the idea is to have using Lagrage formulas the value f(val) where f is our polynomial. Of course
* the proper value can only be computed if enough shares k are provided (the interpolation
* does not hold in other cases and the result will be an incorrect value)
*/
ATTRIBUTE_WARN_UNUSED_RET static int _sss_raw_lagrange(const sss_share *shares, u16 k, sss_secret *secret, u16 val)
{
fp_ctx ctx;
nn p;
fp s, x, y;
fp x_i, x_j, tmp, tmp2;
fp blind, blind_inv, r_inv;
int ret;
unsigned int i, j;
p.magic = WORD(0);
x_i.magic = x_j.magic = tmp.magic = tmp2.magic = s.magic = y.magic = x.magic = WORD(0);
blind.magic = blind_inv.magic = r_inv.magic = WORD(0);
MUST_HAVE((shares != NULL) && (secret != NULL), ret, err);
/* Sanity checks */
MUST_HAVE((k >= 1), ret, err);
MUST_HAVE((SSS_SECRET_SIZE == sizeof(prime)), ret, err);
/* Import our prime number and create the Fp context */
ret = nn_init_from_buf(&p, prime, sizeof(prime)); EG(ret, err);
ret = fp_ctx_init_from_p(&ctx, &p); EG(ret, err);
/* Recombine our shared secrets */
ret = fp_init(&s, &ctx); EG(ret, err);
ret = fp_init(&y, &ctx); EG(ret, err);
ret = fp_init(&x_i, &ctx); EG(ret, err);
ret = fp_init(&x_j, &ctx); EG(ret, err);
ret = fp_init(&tmp, &ctx); EG(ret, err);
ret = fp_init(&tmp2, &ctx); EG(ret, err);
if(val != 0){
/* NOTE: we treat the case 'val = 0' in a specific case for
* optimization. This optimization is of interest since computing
* f(0) (where f(.) is our polynomial) is the formula for getting the
* SSS secret (which happens to be the constant of degree 0 of the
* polynomial).
*/
ret = fp_init(&x, &ctx); EG(ret, err);
ret = fp_set_word_value(&x, (word_t)val); EG(ret, err);
}
/* Get a random blind mask and invert it */
ret = fp_get_random(&blind, &ctx); EG(ret, err);
ret = fp_init(&blind_inv, &ctx); EG(ret, err);
ret = fp_inv(&blind_inv, &blind); EG(ret, err);
/* Perform the computation of r^-1 to optimize our multiplications using Montgomery
* multiplication in the main loop.
*/
ret = fp_init(&r_inv, &ctx); EG(ret, err);
ret = fp_set_nn(&r_inv, &(ctx.r)); EG(ret, err);
ret = fp_inv(&r_inv, &r_inv); EG(ret, err);
/* Proceed with the interpolation */
for(i = 0; i < k; i++){
u16 curr_idx;
const _sss_raw_share *cur_share_i = &(shares[i].raw_share);
/* Import s[i] */
ret = fp_import_from_buf(&s, cur_share_i->share, SSS_SECRET_SIZE); EG(ret, err);
/* Blind s[i] */
ret = fp_mul_monty(&s, &s, &blind); EG(ret, err);
/* Get the index */
GET_UINT16_BE(curr_idx, (const u8*)&(cur_share_i->index), 0);
ret = fp_set_word_value(&x_i, (word_t)(curr_idx)); EG(ret, err);
/* Initialize multiplication with "one" (actually Montgomery r^-1 for multiplication optimization) */
ret = fp_copy(&tmp2, &r_inv); EG(ret, err);
/* Compute the product for all k other than i
* NOTE: we use fp_mul in its redcified version as the multiplication by r^-1 is
* cancelled by the fraction of (x_j - x) * r^-1 / (x_j - x_i) * r^-1 = (x_j - x) / (x_j - x_i)
*/
for(j = 0; j < k; j++){
const _sss_raw_share *cur_share_j = &(shares[j].raw_share);
GET_UINT16_BE(curr_idx, (const u8*)&(cur_share_j->index), 0);
ret = fp_set_word_value(&x_j, (word_t)(curr_idx)); EG(ret, err);
if(j != i){
if(val != 0){
ret = fp_sub(&tmp, &x_j, &x); EG(ret, err);
ret = fp_mul_monty(&s, &s, &tmp); EG(ret, err);
}
else{
/* NOTE: we treat the case 'val = 0' in a specific case for
* optimization. This optimization is of interest since computing
* f(0) (where f(.) is our polynomial) is the formula for getting the
* SSS secret (which happens to be the constant of degree 0 of the
* polynomial).
*/
ret = fp_mul_monty(&s, &s, &x_j); EG(ret, err);
}
ret = fp_sub(&tmp, &x_j, &x_i); EG(ret, err);
ret = fp_mul_monty(&tmp2, &tmp2, &tmp); EG(ret, err);
}
}
/* Invert all the (x_j - x_i) poducts */
ret = fp_inv(&tmp, &tmp2); EG(ret, err);
ret = fp_mul_monty(&s, &s, &tmp); EG(ret, err);
/* Accumulate in secret */
ret = fp_add(&y, &y, &s); EG(ret, err);
}
/* Unblind y */
ret = fp_redcify(&y, &y); EG(ret, err);
ret = fp_mul(&y, &y, &blind_inv); EG(ret, err);
/* We should have our secret in y */
ret = fp_export_to_buf(secret->secret, SSS_SECRET_SIZE, &y);
err:
IGNORE_RET_VAL(local_memset(&ctx, 0, sizeof(ctx)));
nn_uninit(&p);
fp_uninit(&s);
fp_uninit(&y);
fp_uninit(&x_i);
fp_uninit(&x_j);
fp_uninit(&tmp);
fp_uninit(&tmp2);
fp_uninit(&blind);
fp_uninit(&blind_inv);
fp_uninit(&r_inv);
if(val != 0){
fp_uninit(&x);
}
return ret;
}
/* SSS shares and secret combination */
ATTRIBUTE_WARN_UNUSED_RET static int _sss_raw_combine(const sss_share *shares, u16 k, sss_secret *secret)
{
return _sss_raw_lagrange(shares, k, secret, 0);
}
/***** Secure versions (public APIs) ***********************/
/* SSS shares and secret generation:
* Inputs:
* - n: is the number of shares to generate
* - k: the quorum of shares to regenerate the secret (of course k <= n)
* - secret: the secret value when input_secret is set to 'true'
* Output:
* - shares: a pointer to the generated n shares
* - secret: the secret value when input_secret is set to 'false', this
* value being randomly generated
*/
int sss_generate(sss_share *shares, unsigned short k, unsigned short n, sss_secret *secret, boolean input_secret)
{
int ret;
unsigned int i;
u8 len;
u8 session_id[SSS_SESSION_ID_SIZE];
ret = local_memset(session_id, 0, sizeof(session_id)); EG(ret, err);
/* Generate raw shares */
ret = _sss_raw_generate(shares, k, n, secret, input_secret); EG(ret, err);
/* Sanity check */
MUST_HAVE((SSS_HMAC_SIZE == sizeof(shares[0].raw_share_hmac)), ret, err);
MUST_HAVE((SHA256_DIGEST_SIZE >= sizeof(shares[0].raw_share_hmac)), ret, err);
/* Generate a random session ID */
ret = get_random(session_id, sizeof(session_id)); EG(ret, err);
/* Compute the authenticity seal for each share with HMAC */
for(i = 0; i < n; i++){
_sss_raw_share *cur_share = &(shares[i].raw_share);
u8 *cur_id = (u8*)&(shares[i].session_id);
u8 *cur_share_hmac = (u8*)&(shares[i].raw_share_hmac);
/* NOTE: we 'abuse' casts here for shares[i].raw_share to u8*, but this should be OK since
* our structures are packed.
*/
const u8 *inputs[3] = { (const u8*)cur_share, cur_id, NULL };
const u32 ilens[3] = { sizeof(*cur_share), SSS_SESSION_ID_SIZE, 0 };
/* Copy the session ID */
ret = local_memcpy(cur_id, session_id, SSS_SESSION_ID_SIZE); EG(ret, err);
len = SSS_HMAC_SIZE;
ret = hmac_scattered((const u8*)secret, SSS_SECRET_SIZE, SHA256, inputs, ilens, cur_share_hmac, &len); EG(ret, err);
}
err:
IGNORE_RET_VAL(local_memset(session_id, 0, sizeof(session_id)));
return ret;
}
/* SSS shares and secret combination
* Inputs:
* - k: the quorum of shares to regenerate the secret
* - shares: a pointer to the k shares
* Output:
* - secret: the secret value computed from the k shares
*/
int sss_combine(const sss_share *shares, unsigned short k, sss_secret *secret)
{
int ret, cmp;
unsigned int i;
u8 hmac_val[SSS_HMAC_SIZE];
u8 len;
ret = local_memset(hmac_val, 0, sizeof(hmac_val)); EG(ret, err);
/* Recombine raw shares */
ret = _sss_raw_combine(shares, k, secret); EG(ret, err);
/* Compute and check the authenticity seal for each HMAC */
for(i = 0; i < k; i++){
const _sss_raw_share *cur_share = &(shares[i].raw_share);
const u8 *cur_id = (const u8*)&(shares[i].session_id);
const u8 *cur_id0 = (const u8*)&(shares[0].session_id);
const u8 *cur_share_hmac = (const u8*)&(shares[i].raw_share_hmac);
/* NOTE: we 'abuse' casts here for shares[i].raw_share to u8*, but this should be OK since
* our structures are packed.
*/
const u8 *inputs[3] = { (const u8*)cur_share, cur_id, NULL };
const u32 ilens[3] = { sizeof(*cur_share), SSS_SESSION_ID_SIZE, 0 };
/* Check that all our shares have the same session ID, return an error otherwise */
ret = are_equal(cur_id, cur_id0, SSS_SESSION_ID_SIZE, &cmp); EG(ret, err);
if(!cmp){
#ifdef VERBOSE
ext_printf("[-] sss_combine error for share %d / %d: session ID is not OK!\n", i, k);
#endif
ret = -1;
goto err;
}
len = sizeof(hmac_val);
ret = hmac_scattered((const u8*)secret, SSS_SECRET_SIZE, SHA256, inputs, ilens, hmac_val, &len); EG(ret, err);
/* Check the HMAC */
ret = are_equal(hmac_val, cur_share_hmac, len, &cmp); EG(ret, err);
if(!cmp){
#ifdef VERBOSE
ext_printf("[-] sss_combine error for share %d / %d: HMAC is not OK!\n", i, k);
#endif
ret = -1;
goto err;
}
}
err:
IGNORE_RET_VAL(local_memset(hmac_val, 0, sizeof(hmac_val)));
return ret;
}
/* SSS shares regeneration from existing shares
* Inputs:
* - shares: a pointer to the input k shares allowing the regeneration
* - n: is the number of shares to regenerate
* - k: the input shares (of course k <= n)
* Output:
* - shares: a pointer to the generated n shares (among which the k first are
* the ones provided as inputs)
* - secret: the recomputed secret value
*/
int sss_regenerate(sss_share *shares, unsigned short k, unsigned short n, sss_secret *secret)
{
int ret, cmp;
unsigned int i;
u16 max_idx, num_shares;
u8 hmac_val[SSS_HMAC_SIZE];
u8 len;
/* Sanity check */
MUST_HAVE((n <= (u16)(0xffff - 1)), ret, err);
MUST_HAVE((n >= k), ret, err);
ret = local_memset(hmac_val, 0, sizeof(hmac_val)); EG(ret, err);
/* Compute the secret */
ret = _sss_raw_lagrange(shares, k, secret, 0); EG(ret, err);
/* Check the authenticity of our shares */
for(i = 0; i < k; i++){
_sss_raw_share *cur_share = &(shares[i].raw_share);
u8 *cur_id = (u8*)&(shares[i].session_id);
u8 *cur_id0 = (u8*)&(shares[0].session_id);
u8 *cur_share_hmac = (u8*)&(shares[i].raw_share_hmac);
/* NOTE: we 'abuse' casts here for shares[i].raw_share to u8*, but this should be OK since
* our structures are packed.
*/
const u8 *inputs[3] = { (const u8*)cur_share, cur_id, NULL };
const u32 ilens[3] = { sizeof(*cur_share), SSS_SESSION_ID_SIZE, 0 };
/* Check that all our shares have the same session ID, return an error otherwise */
ret = are_equal(cur_id, cur_id0, SSS_SESSION_ID_SIZE, &cmp); EG(ret, err);
if(!cmp){
#ifdef VERBOSE
ext_printf("[-] sss_regenerate error for share %d / %d: session ID is not OK!\n", i, k);
#endif
ret = -1;
goto err;
}
len = sizeof(hmac_val);
/* NOTE: we 'abuse' cast here for secret to (const u8*), but this should be OK since our
* structures are packed.
*/
ret = hmac_scattered((const u8*)secret, SSS_SECRET_SIZE, SHA256, inputs, ilens, hmac_val, &len); EG(ret, err);
ret = are_equal(hmac_val, cur_share_hmac, len, &cmp); EG(ret, err);
if(!cmp){
#ifdef VERBOSE
ext_printf("[-] sss_regenerate error for share %d / %d: HMAC is not OK!\n", i, k);
#endif
ret = -1;
goto err;
}
}
/* Our secret regeneration consists of determining the maximum index, and
* proceed with Lagrange interpolation on new values.
*/
max_idx = 0;
for(i = 0; i < k; i++){
u16 curr_idx;
GET_UINT16_BE(curr_idx, (u8*)&(shares[i].raw_share.index), 0);
if(curr_idx > max_idx){
max_idx = curr_idx;
}
}
/* Now regenerate as many shares as we need */
num_shares = 0;
i = k;
while(num_shares < (n - k)){
_sss_raw_share *cur_share = &(shares[k + num_shares].raw_share);
u8 *cur_id = (u8*)&(shares[k + num_shares].session_id);
u8 *cur_id0 = (u8*)&(shares[0].session_id);
u8 *cur_share_hmac = (u8*)&(shares[k + num_shares].raw_share_hmac);
u16 curr_idx;
/* NOTE: we 'abuse' casts here for shares[i].raw_share.share to sss_secret*, but this should be OK since
* our shares[i].raw_share.share is a SSS_SECRET_SIZE as the sss_secret.secret type encapsulates and our
* structures are packed.
*/
const u8 *inputs[3] = { (const u8*)cur_share, cur_id, NULL };
const u32 ilens[3] = { sizeof(*cur_share), SSS_SESSION_ID_SIZE, 0 };
/* Skip the index = 0 case */
curr_idx = (u16)(max_idx + (u16)(i - k + 1));
if(curr_idx == 0){
i++;
continue;
}
/* Copy our session ID */
ret = local_memcpy(cur_id, cur_id0, SSS_SESSION_ID_SIZE); EG(ret, err);
ret = _sss_raw_lagrange(shares, k, (sss_secret*)(cur_share->share), curr_idx); EG(ret, err);
PUT_UINT16_BE(curr_idx, (u8*)&(cur_share->index), 0);
/* Compute the HMAC */
len = SSS_HMAC_SIZE;
ret = hmac_scattered((const u8*)secret, SSS_SECRET_SIZE, SHA256, inputs, ilens, cur_share_hmac, &len); EG(ret, err);
num_shares++;
i++;
}
err:
IGNORE_RET_VAL(local_memset(hmac_val, 0, sizeof(hmac_val)));
return ret;
}
/********* main test program for SSS *************/
#ifdef SSS
#include <libecc/utils/print_buf.h>
#define K 50
#define N 150
#define MAX_N 200
int main(int argc, char *argv[])
{
int ret = 0;
unsigned int i;
sss_share shares[MAX_N];
sss_share shares_[MAX_N];
sss_secret secret;
FORCE_USED_VAR(argc);
FORCE_USED_VAR(argv);
/* Generate N shares for SSS with at least K shares OK among N */
ext_printf("[+] Generating the secrets %d / %d, call should be OK\n", K, N);
ret = local_memset(&secret, 0x00, sizeof(secret)); EG(ret, err);
/* NOTE: 'false' here means that we let the library generate the secret randomly */
ret = sss_generate(shares, K, N, &secret, SSS_FALSE);
if(ret){
ext_printf(" [X] Error: sss_generate error\n");
goto err;
}
else{
buf_print(" secret", (u8*)&secret, SSS_SECRET_SIZE); EG(ret, err);
}
/* Shuffle shares */
for(i = 0; i < N; i++){
shares_[i] = shares[N - 1 - i];
}
/* Combine (k-1) shares: this call should trigger an ERROR */
ext_printf("[+] Combining the secrets with less shares: call should trigger an error\n");
ret = local_memset(&secret, 0x00, sizeof(secret)); EG(ret, err);
ret = sss_combine(shares_, K - 1, &secret);
if (ret) {
ext_printf(" [X] Error: sss_combine error\n");
} else{
buf_print(" secret", (u8*)&secret, SSS_SECRET_SIZE);
}
/* Combine k shares: this call should be OK and recombine the initial
* secret
*/
ext_printf("[+] Combining the secrets with minimum shares: call should be OK\n");
ret = local_memset(&secret, 0x00, sizeof(secret)); EG(ret, err);
ret = sss_combine(shares_, K, &secret);
if (ret) {
ext_printf(" [X] Error: sss_combine error\n");
goto err;
} else {
buf_print(" secret", (u8*)&secret, SSS_SECRET_SIZE);
}
/* Combine k shares: this call should be OK and recombine the initial
* secret
*/
ext_printf("[+] Combining the secrets with more shares: call should be OK\n");
ret = local_memset(&secret, 0x00, sizeof(secret)); EG(ret, err);
ret = sss_combine(shares_, K + 1, &secret);
if (ret) {
ext_printf(" [X] Error: sss_combine error\n");
goto err;
} else {
buf_print(" secret", (u8*)&secret, SSS_SECRET_SIZE);
}
/* Combine with a corrupted share: call should trigger an error */
ext_printf("[+] Combining the secrets with more shares but one corrupted: call should trigger an error\n");
ret = local_memset(&secret, 0x00, sizeof(secret)); EG(ret, err);
shares_[K].raw_share.share[0] = 0x00;
ret = sss_combine(shares_, K + 1, &secret);
if (ret) {
ext_printf(" [X] Error: sss_combine error\n");
} else {
buf_print(" secret", (u8*)&secret, SSS_SECRET_SIZE);
}
/* Regenerate more shares! call should be OK */
ext_printf("[+] Regenerating more shares: call should be OK\n");
ret = local_memset(&secret, 0x00, sizeof(secret)); EG(ret, err);
ret = sss_regenerate(shares, K, MAX_N, &secret); EG(ret, err);
if (ret) {
ext_printf(" [X] Error: sss_regenerate error\n");
goto err;
} else {
buf_print(" secret", (u8*)&secret, SSS_SECRET_SIZE);
}
/* Shuffle shares */
for(i = 0; i < MAX_N; i++){
shares_[i] = shares[MAX_N - 1 - i];
}
/* Combine newly generated shares: call should be OK */
ext_printf("[+] Combining the secrets with newly generated shares: call should be OK\n");
ret = local_memset(&secret, 0x00, sizeof(secret)); EG(ret, err);
ret = sss_combine(shares_, K, &secret);
if (ret) {
ext_printf(" [X] Error: sss_combine error\n");
goto err;
} else {
buf_print(" secret", (u8*)&secret, SSS_SECRET_SIZE);
}
/* Modify the session ID of one of the shares: call should trigger an error */
ext_printf("[+] Combining the secrets with newly generated shares and a bad session ID: call should trigger an error\n");
ret = local_memset(&secret, 0x00, sizeof(secret)); EG(ret, err);
shares_[1].session_id[0] = 0x00;
ret = sss_combine(shares_, K, &secret);
if (ret) {
ext_printf(" [X] Error: sss_combine error\n");
} else {
buf_print(" secret", (u8*)&secret, SSS_SECRET_SIZE);
}
ret = 0;
err:
return ret;
}
#endif