/*
 *  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