bliss_param_set.h bliss_param_set.c \
bliss_private_key.h bliss_private_key.c \
bliss_public_key.h bliss_public_key.c \
+ bliss_signature.h bliss_signature.c \
+ bliss_utils.h bliss_utils.c \
bliss_fft.h bliss_fft.c \
bliss_fft_params.h bliss_fft_params.c \
bliss_sampler.h bliss_sampler.c
.oid = OID_BLISS_I,
.strength = 128,
.q = 12289,
+ .q2_inv = 6145,
.n = 512,
.n_bits = 9,
.fft_params = &bliss_fft_12289_512,
.k_sigma_bits = 8,
.c = c_bliss_i,
.c_cols = 16,
- .c_rows = 21
+ .c_rows = 21,
+ .d = 10,
+ .p = 24,
+ .M = 46539,
+ .B_inf = 2100,
+ .B_l2 = 12872 * 12872
},
/* BLISS-III scheme */
.oid = OID_BLISS_III,
.strength = 160,
.q = 12289,
+ .q2_inv = 6145,
.n = 512,
.n_bits = 9,
.fft_params = &bliss_fft_12289_512,
.k_sigma_bits = 9,
.c = c_bliss_iii,
.c_cols = 16,
- .c_rows = 21
+ .c_rows = 21,
+ .d = 9,
+ .p = 48,
+ .M = 128113,
+ .B_inf = 1760,
+ .B_l2 = 10206 * 10206
},
/* BLISS-IV scheme */
.oid = OID_BLISS_IV,
.strength = 192,
.q = 12289,
+ .q2_inv = 6145,
.n = 512,
.n_bits = 9,
.fft_params = &bliss_fft_12289_512,
.k_sigma_bits = 9,
.c = c_bliss_iv,
.c_cols = 16,
- .c_rows = 22
+ .c_rows = 22,
+ .d = 8,
+ .p = 96,
+ .M = 244186,
+ .B_inf = 1613,
+ .B_l2 = 9901 * 9901
}
};
*/
uint16_t q;
+ /**
+ * Inverse of (q + 2) mod 2q
+ */
+ uint16_t q2_inv;
+
/**
* Ring dimension equal to the number of polynomial coefficients
*/
*/
size_t c_rows;
+ /**
+ * Number of bits to be dropped after rounding
+ */
+ uint16_t d;
+
+ /**
+ * Modulus p = floor(2q / 2^d) applied after bit dropping
+ */
+ uint16_t p;
+
+ /**
+ * M = sigma^2 / alpha_rejection^2
+ */
+ uint32_t M;
+
+ /**
+ * B_infinity bound
+ */
+ uint16_t B_inf;
+
+ /**
+ * B_verify bound
+ */
+ uint32_t B_l2;
};
/**
*/
#include "bliss_private_key.h"
+#include "bliss_public_key.h"
#include "bliss_param_set.h"
+#include "bliss_utils.h"
#include "bliss_sampler.h"
+#include "bliss_signature.h"
#include "bliss_fft.h"
#include <crypto/mgf1/mgf1_bitspender.h>
typedef struct private_bliss_private_key_t private_bliss_private_key_t;
-#define SECRET_KEY_TRIALS_MAX 30
-
-/**
- * Functions shared with bliss_public_key class
- */
-extern uint32_t* bliss_public_key_from_asn1(chunk_t object, int n);
-
-extern chunk_t bliss_public_key_encode(uint32_t *pubkey, int n);
-
-extern chunk_t bliss_public_key_info_encode(int oid, uint32_t *pubkey, int n);
-
-extern bool bliss_public_key_fingerprint(int oid, uint32_t *pubkey, int n,
- cred_encoding_type_t type, chunk_t *fp);
+#define SECRET_KEY_TRIALS_MAX 50
/**
* Private data of a bliss_private_key_t object.
return KEY_BLISS;
}
+/**
+ * Multiply secret vector s with binary challenge vector c
+ */
+static void multiply_by_c(int8_t *s, int n, uint16_t *c_indices,
+ uint16_t kappa, int32_t *product)
+{
+ int i, j, index;
+
+ for (i = 0; i < n; i++)
+ {
+ product[i] = 0;
+
+ for (j = 0; j < kappa; j++)
+ {
+ index = c_indices[j];
+ if (i - index < 0)
+ {
+ product[i] -= s[i - index + n];
+ }
+ else
+ {
+ product[i] += s[i - index];
+ }
+ }
+ }
+}
+
+/**
+ * Compute a BLISS signature based on a SHA-512 hash
+ */
static bool sign_bliss_with_sha512(private_bliss_private_key_t *this,
chunk_t data, chunk_t *signature)
{
rng_t *rng;
hash_algorithm_t alg;
- bliss_sampler_t *sampler;
- int i, count_max = 100000000;
- int hist_len = 20000, hist_len2 = hist_len / 2;
- int32_t x, hist[hist_len];
- double mean = 0, sigma2 = 0;
- uint8_t seed_buf[32];
+ hasher_t *hasher;
+ bliss_fft_t *fft;
+ bliss_signature_t *sig;
+ bliss_sampler_t *sampler = NULL;
+ uint8_t seed_buf[32], data_hash_buf[HASH_SIZE_SHA512];
+ uint16_t q, q2, p, p2, *c_indices, tests = 0;
+ uint32_t *A, *ay;
+ int32_t *y1, *y2, *z1, *z2, *u, *s1c, *s2c;
+ int32_t y1_min, y1i, y1_max, y2_min, y2i, y2_max, scalar, norm, ui;
+ int16_t *ud, *uz2d, *z2d, value;
+ int i, n;
size_t seed_len;
+ double mean1 = 0, mean2 = 0, sigma1 = 0, sigma2 = 0;
chunk_t seed;
+ chunk_t data_hash = { data_hash_buf, sizeof(data_hash_buf) };
+ bool accepted, positive, success = FALSE;
+
+ /* Initialize signature */
+ *signature = chunk_empty;
+
+ /* Create data hash */
+ hasher = lib->crypto->create_hasher(lib->crypto, HASH_SHA512);
+ if (!hasher )
+ {
+ return FALSE;
+ }
+ if (!hasher->get_hash(hasher, data, data_hash_buf))
+ {
+ hasher->destroy(hasher);
+ return FALSE;
+ }
/* Set MGF1 hash algorithm and seed length based on security strength */
if (this->set->strength > 160)
}
seed = chunk_create(seed_buf, seed_len);
- rng = lib->crypto->create_rng(lib->crypto, RNG_TRUE);
+ rng = lib->crypto->create_rng(lib->crypto, RNG_STRONG);
if (!rng)
{
+ hasher->destroy(hasher);
return FALSE;
}
- if (!rng->get_bytes(rng, seed_len, seed_buf))
- {
- rng->destroy(rng);
- return FALSE;
- }
- rng->destroy(rng);
- sampler = bliss_sampler_create(alg, seed, this->set);
- if (!sampler)
+ /* Initialize a couple of needed variables */
+ n = this->set->n;
+ q = this->set->q;
+ p = this->set->p;
+ q2 = 2 * q;
+ p2 = p / 2;
+ A = malloc(n * sizeof(uint32_t));
+ ay = malloc(n * sizeof(uint32_t));
+ z2 = malloc(n * sizeof(int32_t));
+ s1c = malloc(n * sizeof(int32_t));
+ s2c = malloc(n * sizeof(int32_t));
+ u = malloc(n * sizeof(int32_t));
+ uz2d = malloc(n * sizeof(int16_t));
+
+ sig = bliss_signature_create(this->set);
+ sig->get_parameters(sig, &z1, &z2d, &c_indices);
+ y1 = z1;
+ y2 = z2;
+ ud = z2d;
+
+ fft = bliss_fft_create(this->set->fft_params);
+ fft->transform(fft, this->a, A, FALSE);
+
+ while (true)
{
- return FALSE;
- }
+ tests++;
- for (i = 0; i < hist_len; i++)
- {
- hist[i] = 0;
- }
+ if (!rng->get_bytes(rng, seed_len, seed_buf))
+ {
+ goto end;
+ }
+ DESTROY_IF(sampler);
- for (i = 0; i < count_max; i++)
- {
- if (!sampler->gaussian(sampler, &x))
+ sampler = bliss_sampler_create(alg, seed, this->set);
+ if (!sampler)
{
- sampler->destroy(sampler);
- return FALSE;
+ goto end;
}
- hist[hist_len2 + x]++;
- }
- for (i = 0; i < hist_len; i++)
- {
- if (hist[i])
+
+ /* Gaussian sampling for vectors y1 and y2 */
+ for (i = 0; i < n; i++)
+ {
+ if (!sampler->gaussian(sampler, &y1i) ||
+ !sampler->gaussian(sampler, &y2i))
+ {
+ goto end;
+ }
+ y1[i] = y1i;
+ y2[i] = y2i;
+
+ /* Collect statistical data on rejection sampling */
+ if (i == 0)
+ {
+ y1_min = y1_max = y1i;
+ y2_min = y2_max = y2i;
+ }
+ else
+ {
+ if (y1i < y1_min)
+ {
+ y1_min = y1i;
+ }
+ else if (y1i > y1_max)
+ {
+ y1_max = y1i;
+ }
+ if (y2i < y2_min)
+ {
+ y2_min = y2i;
+ }
+ else if (y2i > y2_max)
+ {
+ y2_max = y2i;
+ }
+ }
+ mean1 += y1i;
+ mean2 += y2i;
+ sigma1 += y1i * y1i;
+ sigma2 += y2i * y2i;
+
+ ay[i] = y1i < 0 ? q + y1i : y1i;
+ }
+
+ /* Compute statistics on vectors y1 and y2 */
+ mean1 /= n;
+ mean2 /= n;
+ sigma1 /= n;
+ sigma2 /= n;
+ sigma2 -= mean1 * mean1;
+ sigma2 -= mean2 * mean2;
+ DBG2(DBG_LIB, "y1 = %d..%d (sigma2 = %5.0f, mean = %4.1f)",
+ y1_min, y1_max, sigma1, mean1);
+ DBG2(DBG_LIB, "y2 = %d..%d (sigma2 = %5.0f, mean = %4.1f)",
+ y2_min, y2_max, sigma2, mean2);
+
+ fft->transform(fft, ay, ay, FALSE);
+
+ for (i = 0; i < n; i++)
+ {
+ ay[i] = (A[i] * ay[i]) % q;
+ }
+ fft->transform(fft, ay, ay, TRUE);
+
+ for (i = 0; i < n; i++)
+ {
+ ui = 2 * this->set->q2_inv * (int32_t)ay[i] + y2[i];
+ u[i] = ((ui < 0) ? q2 + ui : ui) % q2;
+ }
+ bliss_utils_round_and_drop(this->set, u, ud);
+
+ /* Detailed debugging information */
+ DBG3(DBG_LIB, " i u[i] ud[i]");
+ for (i = 0; i < n; i++)
+ {
+ DBG3(DBG_LIB, "%3d %6d %4d", i, u[i], ud[i]);
+ }
+
+ if (!bliss_utils_generate_c(hasher, data_hash, ud, n, this->set->kappa,
+ c_indices))
+ {
+ goto end;
+ }
+
+ /* Compute s*c */
+ multiply_by_c(this->s1, n, c_indices, this->set->kappa, s1c);
+ multiply_by_c(this->s2, n, c_indices, this->set->kappa, s2c);
+
+ /* Reject with probability 1/(M*exp(-norm^2/2*sigma^2)) */
+ norm = bliss_utils_scalar_product(s1c, s1c, n) +
+ bliss_utils_scalar_product(s2c, s2c, n);
+
+ if (!sampler->bernoulli_exp(sampler, this->set->M - norm, &accepted))
+ {
+ goto end;
+ }
+ DBG2(DBG_LIB, "norm2(s1*c) + norm2(s2*c) = %u, %s",
+ norm, accepted ? "accepted" : "rejected");
+ if (!accepted)
+ {
+ continue;
+ }
+
+ /* Compute z */
+ if (!sampler->sign(sampler, &positive))
+ {
+ goto end;
+ }
+ for (i = 0; i < n; i++)
+ {
+ if (positive)
+ {
+ z1[i] = y1[i] + s1c[i];
+ z2[i] = y2[i] + s2c[i];
+ }
+ else
+ {
+ z1[i] = y1[i] - s1c[i];
+ z2[i] = y2[i] - s2c[i];
+ }
+ }
+ /* Reject with probability 1/cosh(scalar/sigma^2) */
+ scalar = bliss_utils_scalar_product(z1, s1c, n) +
+ bliss_utils_scalar_product(z2, s2c, n);
+
+ if (!sampler->bernoulli_cosh(sampler, scalar, &accepted))
+ {
+ goto end;
+ }
+ DBG2(DBG_LIB, "scalar(z1,s1*c) + scalar(z2,s2*c) = %d, %s",
+ scalar, accepted ? "accepted" : "rejected");
+ if (!accepted)
+ {
+ continue;
+ }
+
+ /* Compute z2 with dropped bits */
+ for (i = 0; i < n; i++)
{
- x = i - hist_len2;
- DBG2(DBG_LIB, "hist[%4d] = %7u", x, hist[i]);
- mean += (double)hist[i] * x;
- sigma2 += (double)hist[i] * x * x;
+ u[i] -= z2[i];
+ if (u[i] < 0)
+ {
+ u[i] += q2;
+ }
+ else if (u[i] >= q2)
+ {
+ u[i] -= q2;
+ }
}
+ bliss_utils_round_and_drop(this->set, u, uz2d);
+
+ for (i = 0; i < n; i++)
+ {
+ value = ud[i] - uz2d[i];
+ if (value <= -p2)
+ {
+ value += p;
+ }
+ else if (value > p2)
+ {
+ value -= p;
+ }
+ z2d[i] = value;
+ }
+
+ if (!bliss_utils_check_norms(this->set, z1, z2d))
+ {
+ continue;
+ }
+ DBG2(DBG_LIB, "signature generation needed %u round%s", tests,
+ (tests == 1) ? "" : "s");
+ break;
}
- mean /= (double)count_max;
- sigma2 /= (double)count_max;
- sigma2 -= mean * mean;
- DBG2(DBG_LIB, "mean = %6.4f, sigma2 = %7.2f ", mean, sigma2);
+ success = TRUE;
- sampler->destroy(sampler);
+ *signature = sig->get_encoding(sig);
- DBG2(DBG_LIB, "empty signature");
- *signature = chunk_empty;
+end:
+ /* cleanup */
+ sampler->destroy(sampler);
+ hasher->destroy(hasher);
+ sig->destroy(sig);
+ fft->destroy(fft);
+ rng->destroy(rng);
+ free(A);
+ free(ay);
+ free(z2);
+ free(s1c);
+ free(s2c);
+ free(u);
+ free(uz2d);
- return TRUE;
+ return success;
}
METHOD(private_key_t, sign, bool,
public_key_t *public;
chunk_t pubkey;
- pubkey = bliss_public_key_info_encode(this->set->oid, this->a,
- this->set->n);
+ pubkey = bliss_public_key_info_encode(this->set->oid, this->a, this->set->n);
public = lib->creds->create(lib->creds, CRED_PUBLIC_KEY, KEY_BLISS,
BUILD_BLOB_ASN1_DER, pubkey, BUILD_END);
free(pubkey.ptr);
#include "bliss_public_key.h"
#include "bliss_param_set.h"
+#include "bliss_signature.h"
+#include "bliss_fft.h"
+#include "bliss_utils.h"
#include <asn1/asn1.h>
#include <asn1/asn1_parser.h>
return KEY_BLISS;
}
-METHOD(public_key_t, verify, bool,
- private_bliss_public_key_t *this, signature_scheme_t scheme,
- chunk_t data, chunk_t signature)
+/**
+ * Verify a BLISS signature based on a SHA-512 hash
+ */
+static bool verify_bliss_with_sha512(private_bliss_public_key_t *this,
+ chunk_t data, chunk_t signature)
{
- switch (scheme)
+ int i, n;
+ int32_t *z1, *u;
+ int16_t *ud, *z2d;
+ uint16_t q, q2, p, *c_indices, *indices;
+ uint32_t *az;
+ uint8_t data_hash_buf[HASH_SIZE_SHA512];
+ chunk_t data_hash = { data_hash_buf, sizeof(data_hash_buf) };
+ hasher_t *hasher;
+ bliss_fft_t *fft;
+ bliss_signature_t *sig;
+ bool success = FALSE;
+
+ /* Create data hash */
+ hasher = lib->crypto->create_hasher(lib->crypto, HASH_SHA512);
+ if (!hasher )
{
- case SIGN_BLISS_WITH_SHA512:
- return FALSE;
- default:
- DBG1(DBG_LIB, "signature scheme %N not supported by BLISS",
- signature_scheme_names, scheme);
- return FALSE;
+ return FALSE;
+ }
+ if (!hasher->get_hash(hasher, data, data_hash_buf))
+ {
+ hasher->destroy(hasher);
+ return FALSE;
}
-}
-
-METHOD(public_key_t, encrypt_, bool,
- private_bliss_public_key_t *this, encryption_scheme_t scheme,
- chunk_t plain, chunk_t *crypto)
-{
- DBG1(DBG_LIB, "encryption scheme %N not supported",
- encryption_scheme_names, scheme);
- return FALSE;
-}
-METHOD(public_key_t, get_keysize, int,
- private_bliss_public_key_t *this)
-{
- return this->set->strength;
-}
+ sig = bliss_signature_create_from_data(this->set, signature);
+ if (!sig)
+ {
+ hasher->destroy(hasher);
+ return FALSE;
+ }
+ sig->get_parameters(sig, &z1, &z2d, &c_indices);
-/**
- * Parse an ASN.1 OCTET STRING into an array of public key coefficients
- */
-uint32_t* bliss_public_key_from_asn1(chunk_t object, int n)
-{
- uint32_t *pubkey;
- uint16_t coeff;
- u_char *pos;
- int i;
+ if (!bliss_utils_check_norms(this->set, z1, z2d))
+ {
+ hasher->destroy(hasher);
+ sig->destroy(sig);
+ return FALSE;
+ }
- pubkey = malloc(n * sizeof(uint32_t));
- pos = object.ptr;
+ /* Initialize a couple of needed variables */
+ n = this->set->n;
+ q = this->set->q;
+ p = this->set->p;
+ q2 = 2 * q;
+ az = malloc(n * sizeof(uint32_t));
+ u = malloc(n * sizeof(int32_t));
+ ud = malloc(n * sizeof(int16_t));
+ indices = malloc(this->set->kappa * sizeof(uint16_t));
for (i = 0; i < n; i++)
{
- coeff = untoh16(pos);
- pubkey[i] = (uint32_t)coeff;
- pos += 2;
+ az[i] = z1[i] < 0 ? q + z1[i] : z1[i];
}
+ fft = bliss_fft_create(this->set->fft_params);
+ fft->transform(fft, this->a, A, FALSE);
+ fft->transform(fft, az, az, FALSE);
- return pubkey;
-}
+ for (i = 0; i < n; i++)
+ {
+ az[i] = (A[i] * az[i]) % q;
+ }
+ fft->transform(fft, az, az, TRUE);
-/**
- * Encode a raw BLISS subjectPublicKey in ASN.1 DER format
- */
-chunk_t bliss_public_key_encode(uint32_t *pubkey, int n)
-{
- u_char *pos;
- chunk_t encoding;
- int i;
+ for (i = 0; i < n; i++)
+ {
+ u[i] = (2 * this->set->q2_inv * az[i]) % q2;
+ }
- pos = asn1_build_object(&encoding, ASN1_OCTET_STRING, 2 * n);
+ for (i = 0; i < this->set->kappa; i++)
+ {
+ u[c_indices[i]] = (u[c_indices[i]] + q * this->set->q2_inv) % q2;
+ }
+ bliss_utils_round_and_drop(this->set, u, ud);
for (i = 0; i < n; i++)
{
- htoun16(pos, (uint16_t)pubkey[i]);
- pos += 2;
+ ud[i] += z2d[i];
+ if (ud[i] < 0)
+ {
+ ud[i] += p;
+ }
+ else if (ud[i] >= p)
+ {
+ ud[i] -= p;
+ }
}
- return encoding;
-}
+ /* Detailed debugging information */
+ DBG3(DBG_LIB, " i u[i] ud[i] z2d[i]");
+ for (i = 0; i < n; i++)
+ {
+ DBG3(DBG_LIB, "%3d %6d %4d %4d", i, u[i], ud[i], z2d[i]);
+ }
-/**
- * Encode a BLISS subjectPublicKeyInfo record in ASN.1 DER format
- */
-chunk_t bliss_public_key_info_encode(int oid, uint32_t *pubkey, int n)
-{
- chunk_t encoding, pubkey_encoding;
+ if (!bliss_utils_generate_c(hasher, data_hash, ud, n, this->set->kappa,
+ indices))
+ {
+ goto end;
+ }
- pubkey_encoding = bliss_public_key_encode(pubkey, n);
+ for (i = 0; i < this->set->kappa; i++)
+ {
+ if (indices[i] != c_indices[i])
+ {
+ goto end;
+ }
+ }
+ success = TRUE;
- encoding = asn1_wrap(ASN1_SEQUENCE, "mm",
- asn1_wrap(ASN1_SEQUENCE, "mm",
- asn1_build_known_oid(OID_BLISS_PUBLICKEY),
- asn1_build_known_oid(oid)),
- asn1_bitstring("m", pubkey_encoding));
+end:
+ /* cleanup */
+ hasher->destroy(hasher);
+ sig->destroy(sig);
+ fft->destroy(fft);
+ free(az);
+ free(u);
+ free(ud);
+ free(indices);
- return encoding;
+ return success;
}
-/**
- * Generate a BLISS public key fingerprint
- */
-bool bliss_public_key_fingerprint(int oid, uint32_t *pubkey, int n,
- cred_encoding_type_t type, chunk_t *fp)
+METHOD(public_key_t, verify, bool,
+ private_bliss_public_key_t *this, signature_scheme_t scheme,
+ chunk_t data, chunk_t signature)
{
- hasher_t *hasher;
- chunk_t key;
-
- switch (type)
+ switch (scheme)
{
- case KEYID_PUBKEY_SHA1:
- key = bliss_public_key_encode(pubkey, n);
- break;
- case KEYID_PUBKEY_INFO_SHA1:
- key = bliss_public_key_info_encode(oid, pubkey, n);
- break;
+ case SIGN_BLISS_WITH_SHA512:
+ return verify_bliss_with_sha512(this, data, signature);
default:
+ DBG1(DBG_LIB, "signature scheme %N not supported by BLISS",
+ signature_scheme_names, scheme);
return FALSE;
}
+}
- hasher = lib->crypto->create_hasher(lib->crypto, HASH_SHA1);
- if (!hasher || !hasher->allocate_hash(hasher, key, fp))
- {
- DBG1(DBG_LIB, "SHA1 hash algorithm not supported, fingerprinting failed");
- DESTROY_IF(hasher);
- free(key.ptr);
-
- return FALSE;
- }
- hasher->destroy(hasher);
- free(key.ptr);
+METHOD(public_key_t, encrypt_, bool,
+ private_bliss_public_key_t *this, encryption_scheme_t scheme,
+ chunk_t plain, chunk_t *crypto)
+{
+ DBG1(DBG_LIB, "encryption scheme %N not supported",
+ encryption_scheme_names, scheme);
+ return FALSE;
+}
- return TRUE;
+METHOD(public_key_t, get_keysize, int,
+ private_bliss_public_key_t *this)
+{
+ return this->set->strength;
}
METHOD(public_key_t, get_encoding, bool,
{
bool success = TRUE;
- *encoding = bliss_public_key_info_encode(this->set->oid, this->a,
- this->set->n);
+ *encoding = bliss_public_key_info_encode(this->set->oid, this->a, this->set->n);
if (type != PUBKEY_SPKI_ASN1_DER)
{
return &this->public;
}
+
+/**
+ * See header.
+ */
+uint32_t* bliss_public_key_from_asn1(chunk_t object, int n)
+{
+ uint32_t *pubkey;
+ uint16_t coeff;
+ u_char *pos;
+ int i;
+
+ pubkey = malloc(n * sizeof(uint32_t));
+ pos = object.ptr;
+
+ for (i = 0; i < n; i++)
+ {
+ coeff = untoh16(pos);
+ pubkey[i] = (uint32_t)coeff;
+ pos += 2;
+ }
+
+ return pubkey;
+}
+
+/**
+ * See header.
+ */
+chunk_t bliss_public_key_encode(uint32_t *pubkey, int n)
+{
+ u_char *pos;
+ chunk_t encoding;
+ int i;
+
+ pos = asn1_build_object(&encoding, ASN1_OCTET_STRING, 2 * n);
+
+ for (i = 0; i < n; i++)
+ {
+ htoun16(pos, (uint16_t)pubkey[i]);
+ pos += 2;
+ }
+
+ return encoding;
+}
+
+/**
+ * See header.
+ */
+chunk_t bliss_public_key_info_encode(int oid, uint32_t *pubkey, int n)
+{
+ chunk_t encoding, pubkey_encoding;
+
+ pubkey_encoding = bliss_public_key_encode(pubkey, n);
+
+ encoding = asn1_wrap(ASN1_SEQUENCE, "mm",
+ asn1_wrap(ASN1_SEQUENCE, "mm",
+ asn1_build_known_oid(OID_BLISS_PUBLICKEY),
+ asn1_build_known_oid(oid)),
+ asn1_bitstring("m", pubkey_encoding));
+
+ return encoding;
+}
+
+/**
+ * See header.
+ */
+bool bliss_public_key_fingerprint(int oid, uint32_t *pubkey, int n,
+ cred_encoding_type_t type, chunk_t *fp)
+{
+ hasher_t *hasher;
+ chunk_t key;
+
+ switch (type)
+ {
+ case KEYID_PUBKEY_SHA1:
+ key = bliss_public_key_encode(pubkey, n);
+ break;
+ case KEYID_PUBKEY_INFO_SHA1:
+ key = bliss_public_key_info_encode(oid, pubkey, n);
+ break;
+ default:
+ return FALSE;
+ }
+
+ hasher = lib->crypto->create_hasher(lib->crypto, HASH_SHA1);
+ if (!hasher || !hasher->allocate_hash(hasher, key, fp))
+ {
+ DBG1(DBG_LIB, "SHA1 hash algorithm not supported, fingerprinting failed");
+ DESTROY_IF(hasher);
+ free(key.ptr);
+
+ return FALSE;
+ }
+ hasher->destroy(hasher);
+ free(key.ptr);
+
+ return TRUE;
+}
+
#define BLISS_PUBLIC_KEY_H_
#include <credentials/builder.h>
+#include <credentials/cred_encoding.h>
#include <credentials/keys/public_key.h>
typedef struct bliss_public_key_t bliss_public_key_t;
*/
bliss_public_key_t *bliss_public_key_load(key_type_t type, va_list args);
+/* The following functions are shared with the bliss_private_key class */
+
+/**
+ * Parse an ASN.1 OCTET STRING into an array of public key coefficients
+ *
+ * @param object ASN.1 encoded subjectPublicKey
+ * @param n number of public key coefficients
+ * @result coefficients of public key vector
+ */
+uint32_t* bliss_public_key_from_asn1(chunk_t object, int n);
+
+/**
+ * Encode a raw BLISS subjectPublicKey in ASN.1 DER format
+ *
+ * @param coefficients of public key vector
+ * @param n number of public key coefficients
+ * @result ASN.1 encoded subjectPublicKey
+ */
+chunk_t bliss_public_key_encode(uint32_t *pubkey, int n);
+
+/**
+ * Encode a BLISS subjectPublicKeyInfo record in ASN.1 DER format
+ *
+ * @param oid BLISS public key type OID
+ * @param pubkey coefficients of public key vector
+ * @param n number of public key coefficients
+ * @result ASN.1 encoded subjectPublicKeyInfo record
+ */
+chunk_t bliss_public_key_info_encode(int oid, uint32_t *pubkey, int n);
+
+/**
+ * Generate a BLISS public key fingerprint
+ *
+ * @param oid BLISS public key type OID
+ * @param pubkey coefficients of public key vector
+ * @param n number of public key coefficients
+ * @param type type of fingerprint to be generated
+ * @param fp generated fingerprint (must be freed by caller)
+ * @result TRUE if generation was successful
+ */
+bool bliss_public_key_fingerprint(int oid, uint32_t *pubkey, int n,
+ cred_encoding_type_t type, chunk_t *fp);
+
#endif /** BLISS_PUBLIC_KEY_H_ @}*/
return TRUE;
}
+METHOD(bliss_sampler_t, bernoulli_cosh, bool,
+ private_bliss_sampler_t *this, int32_t x, bool *accepted)
+{
+ uint32_t u;
+
+ x = 2 * (x < 0 ? -x : x);
+
+ while (TRUE)
+ {
+ if (!bernoulli_exp(this, x, accepted))
+ {
+ return FALSE;
+ }
+ if (*accepted)
+ {
+ return TRUE;
+ }
+ if (!this->bitspender->get_bits(this->bitspender, 1, &u))
+ {
+ return FALSE;
+ }
+ if (u)
+ {
+ continue;
+ }
+ if (!bernoulli_exp(this, x, accepted))
+ {
+ return FALSE;
+ }
+ if (!(*accepted))
+ {
+ return TRUE;
+ }
+ }
+}
+
#define MAX_SAMPLE_INDEX 16
METHOD(bliss_sampler_t, pos_binary, bool,
return TRUE;
}
+METHOD(bliss_sampler_t, sign, bool,
+ private_bliss_sampler_t *this, bool *positive)
+{
+ uint32_t u;
+
+ if (!this->bitspender->get_bits(this->bitspender, 1, &u))
+ {
+ return FALSE;
+ }
+ *positive = u;
+
+ return TRUE;
+}
+
METHOD(bliss_sampler_t, destroy, void,
private_bliss_sampler_t *this)
{
INIT(this,
.public = {
.bernoulli_exp = _bernoulli_exp,
+ .bernoulli_cosh = _bernoulli_cosh,
.pos_binary = _pos_binary,
.gaussian = _gaussian,
+ .sign = _sign,
.destroy = _destroy,
},
.set = set,
*/
bool (*bernoulli_exp)(bliss_sampler_t *this, uint32_t x, bool *accepted);
+ /**
+ * Sample according to 1/cosh(x/sigma^2)
+ *
+ * @param x Value to be sampled
+ * @param accepted TRUE if value is accepted, FALSE if rejected
+ * @result TRUE if sampling was successful
+ */
+ bool (*bernoulli_cosh)(bliss_sampler_t *this, int32_t x, bool *accepted);
+
/**
* Sample according to 2^(-x^2) for positive x
*
*/
bool (*gaussian)(bliss_sampler_t *this, int32_t *z);
+ /**
+ * Sample the sign according to the binary distribution
+ *
+ * @param positive TRUE if positive
+ * @result TRUE if sampling was successful
+ */
+ bool (*sign)(bliss_sampler_t *this, bool *positive);
+
/**
* Destroy bliss_sampler_t object
*/
--- /dev/null
+/*
+ * Copyright (C) 2014 Andreas Steffen
+ * HSR Hochschule fuer Technik Rapperswil
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation; either version 2 of the License, or (at your
+ * option) any later version. See <http://www.fsf.org/copyleft/gpl.txt>.
+ *
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+ * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ * for more details.
+ */
+
+#include "bliss_signature.h"
+
+
+typedef struct private_bliss_signature_t private_bliss_signature_t;
+
+/**
+ * Private data of a bliss_signature_t object.
+ */
+struct private_bliss_signature_t {
+ /**
+ * Public interface for this signer.
+ */
+ bliss_signature_t public;
+
+ /**
+ * BLISS signature parameter set
+ */
+ bliss_param_set_t *set;
+
+ /**
+ * BLISS signature vector z1 of size n
+ */
+ int32_t *z1;
+
+ /**
+ * BLISS signature vector z2d of size n
+ */
+ int16_t *z2d;
+
+ /**
+ * Indices of sparse BLISS challenge vector c of size kappa
+ */
+ uint16_t *c_indices;
+
+ /**
+ * Compressed encoding of BLISS signature
+ */
+ chunk_t encoding;
+
+};
+
+METHOD(bliss_signature_t, get_encoding, chunk_t,
+ private_bliss_signature_t *this)
+{
+ if (this->encoding.len == 0)
+ {
+ uint8_t *pos;
+ int i;
+
+ this->encoding = chunk_alloc(this->set->kappa * sizeof(uint16_t) +
+ this->set->n * sizeof(int16_t) +
+ this->set->n * sizeof(int8_t)),
+ pos = this->encoding.ptr;
+
+ for (i = 0; i < this->set->kappa; i++)
+ {
+ htoun16(pos, this->c_indices[i]);
+ pos += 2;
+ }
+ for (i = 0; i < this->set->n; i++)
+ {
+ htoun16(pos, (uint16_t)this->z1[i]);
+ pos += 2;
+ }
+ for (i = 0; i < this->set->n; i++)
+ {
+ *pos++ = (uint8_t)this->z2d[i];
+ }
+ DBG2(DBG_LIB, "generated BLISS signature (%u bytes)",
+ this->encoding.len);
+ }
+ return chunk_clone(this->encoding);
+}
+
+METHOD(bliss_signature_t, get_parameters, void,
+ private_bliss_signature_t *this, int32_t **z1, int16_t **z2d,
+ uint16_t **c_indices)
+{
+ *z1 = this->z1;
+ *z2d = this->z2d;
+ *c_indices = this->c_indices;
+}
+
+METHOD(bliss_signature_t, destroy, void,
+ private_bliss_signature_t *this)
+{
+ free(this->z1);
+ free(this->z2d);
+ free(this->c_indices);
+ free(this->encoding.ptr);
+ free(this);
+}
+
+/**
+ * See header.
+ */
+bliss_signature_t *bliss_signature_create(bliss_param_set_t *set)
+{
+ private_bliss_signature_t *this;
+
+ INIT(this,
+ .public = {
+ .get_encoding = _get_encoding,
+ .get_parameters = _get_parameters,
+ .destroy = _destroy,
+ },
+ .set = set,
+ .z1 = malloc(set->n * sizeof(int32_t)),
+ .z2d = malloc(set->n * sizeof(int16_t)),
+ .c_indices = malloc(set->n * sizeof(uint16_t)),
+ );
+
+ return &this->public;
+}
+
+/**
+ * See header.
+ */
+bliss_signature_t *bliss_signature_create_from_data(bliss_param_set_t *set,
+ chunk_t encoding)
+{
+ private_bliss_signature_t *this;
+ uint8_t *pos;
+ int i;
+
+ if (encoding.len != set->kappa * sizeof(uint16_t) +
+ set->n * sizeof(int16_t) + set->n * sizeof(int8_t))
+ {
+ DBG1(DBG_LIB, "incorrect BLISS signature size");
+ return NULL;
+ }
+
+ INIT(this,
+ .public = {
+ .get_encoding = _get_encoding,
+ .get_parameters = _get_parameters,
+ .destroy = _destroy,
+ },
+ .set = set,
+ .z1 = malloc(set->n * sizeof(int32_t)),
+ .z2d = malloc(set->n * sizeof(int16_t)),
+ .c_indices = malloc(set->n * sizeof(uint16_t)),
+ .encoding = chunk_clone(encoding),
+ );
+
+ pos = encoding.ptr;
+
+ for (i = 0; i < set->kappa; i++)
+ {
+ this->c_indices[i] = untoh16(pos);
+ pos += 2;
+ }
+ for (i = 0; i < set->n; i++)
+ {
+ this->z1[i] = (int16_t)untoh16(pos);
+ pos += 2;
+ }
+ for (i = 0; i < set->n; i++)
+ {
+ this->z2d[i] = (int8_t)(*pos++);
+ }
+
+ return &this->public;
+}
--- /dev/null
+/*
+ * Copyright (C) 2014 Andreas Steffen
+ * HSR Hochschule fuer Technik Rapperswil
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation; either version 2 of the License, or (at your
+ * option) any later version. See <http://www.fsf.org/copyleft/gpl.txt>.
+ *
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+ * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ * for more details.
+ */
+
+/**
+ * @defgroup bliss_signature bliss_signature
+ * @{ @ingroup bliss_p
+ */
+
+#ifndef BLISS_SIGNATURE_H_
+#define BLISS_SIGNATURE_H_
+
+typedef struct bliss_signature_t bliss_signature_t;
+
+#include "bliss_param_set.h"
+
+#include <library.h>
+
+/**
+ * Public interface of BLISS signature object
+ */
+struct bliss_signature_t {
+
+ /**
+ * Get compressed binary encoding of BLISS signature
+ *
+ * @result binary encoding of BLISS signature
+ */
+ chunk_t (*get_encoding)(bliss_signature_t *this);
+
+ /**
+ * Get signature parameters extracted from compressd binary encoding
+ *
+ * @param z1 signature vector z1 of size n
+ * @param z2d signature vector z2d of size n
+ * @param c_indices indices of sparse binary challenge vector of size kappa
+ */
+ void (*get_parameters)(bliss_signature_t *this, int32_t **z1, int16_t **z2d,
+ uint16_t **c_indices);
+
+ /**
+ * Destroy bliss_signature_t object
+ */
+ void (*destroy)(bliss_signature_t *this);
+
+};
+
+/**
+ * Create a BLISS signature object.
+ *
+ * @param set BLISS parameter set
+ */
+bliss_signature_t *bliss_signature_create(bliss_param_set_t *set);
+
+/**
+ * Create a BLISS signature object from encoding.
+ *
+ * @param set BLISS parameter set
+ * @param encoding binary signature encoding
+ */
+bliss_signature_t *bliss_signature_create_from_data(bliss_param_set_t *set,
+ chunk_t encoding);
+
+#endif /** BLISS_SIGNATURE_H_ @}*/
--- /dev/null
+/*
+ * Copyright (C) 2014 Andreas Steffen
+ * HSR Hochschule fuer Technik Rapperswil
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation; either version 2 of the License, or (at your
+ * option) any later version. See <http://www.fsf.org/copyleft/gpl.txt>.
+ *
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+ * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ * for more details.
+ */
+
+#include "bliss_utils.h"
+
+#include <asn1/asn1.h>
+#include <crypto/hashers/hasher.h>
+#include <utils/debug.h>
+
+/**
+ * See header.
+ */
+int32_t bliss_utils_scalar_product(int32_t *x, int32_t *y, int n)
+{
+ int32_t product = 0;
+ int i;
+
+ for (i = 0; i < n; i++)
+ {
+ product += x[i] * y[i];
+ }
+
+ return product;
+}
+
+/**
+ * See header.
+ */
+void bliss_utils_round_and_drop(bliss_param_set_t *set, int32_t *x, int16_t *xd)
+{
+ int32_t factor;
+ int i;
+
+ factor = 1 << set->d;
+
+ for (i = 0; i < set->n; i++)
+ {
+ xd[i] = ((x[i] + (factor >> 1)) / factor) % set->p;
+ }
+}
+
+/**
+ * See header.
+ */
+bool bliss_utils_generate_c(hasher_t *hasher, chunk_t data_hash, uint16_t *ud,
+ int n, uint16_t kappa, uint16_t *c_indices)
+{
+ int i, j;
+ uint64_t extra_bits;
+ uint16_t index, rounds = 0;
+ uint8_t hash[HASH_SIZE_SHA512], un16_buf[2];
+ chunk_t un16 = { un16_buf, 2 };
+ bool index_taken[n];
+
+ while (TRUE)
+ {
+ if (!hasher->get_hash(hasher, data_hash, NULL))
+ {
+ return FALSE;
+ }
+
+ for (i = 0; i < n; i++)
+ {
+ htoun16(un16_buf, ud[i]);
+ if (!hasher->get_hash(hasher, un16, NULL))
+ {
+ return FALSE;
+ }
+ index_taken[i] = FALSE;
+ }
+
+ htoun16(un16_buf, rounds++);
+ if (!hasher->get_hash(hasher, un16, hash))
+ {
+ return FALSE;
+ }
+
+ extra_bits = untoh64(hash + sizeof(hash) - sizeof(uint64_t));
+
+ for (i = 0, j = 0; j < sizeof(hash); j++)
+ {
+ index = 2 * (uint16_t)hash[i] + (extra_bits & 1);
+ if (!index_taken[index])
+ {
+ c_indices[i++] = index;
+ index_taken[index] = TRUE;
+ }
+ if (i == kappa)
+ {
+ return TRUE;
+ }
+ }
+ }
+}
+
+/**
+ * See header.
+ */
+bool bliss_utils_check_norms(bliss_param_set_t *set, int32_t *z1, int16_t *z2d)
+{
+ int32_t z2ds[set->n];
+ int32_t z1_min, z1_max, norm;
+ int16_t z2d_min, z2d_max;
+ int i;
+
+ /* some statistics on the values of z1 and z2d */
+ z1_min = z1_max = z1[0];
+ z2d_min = z2d_max = z2d[0];
+
+ for (i = 1; i < set->n; i++)
+ {
+ if (z1[i] < z1_min)
+ {
+ z1_min = z1[i];
+ }
+ else if (z1[i] > z1_max)
+ {
+ z1_max = z1[i];
+ }
+ if (z2d[i] < z2d_min)
+ {
+ z2d_min = z2d[i];
+ }
+ else if (z2d[i] > z2d_max)
+ {
+ z2d_max = z2d[i];
+ }
+ }
+ DBG2(DBG_LIB, "z1 = %d..%d, z2d = %d..%d", z1_min, z1_max, z2d_min, z2d_max);
+
+ /* Restriction on infinite norm */
+ for (i = 0; i < set->n; i++)
+ {
+ z2ds[i] = (1 << set->d) * z2d[i];
+
+ if (z1[i] >= set->B_inf || z2ds[i] >= set->B_inf ||
+ z1[i] <= -set->B_inf || z2ds[i] <= -set->B_inf)
+ {
+ DBG2(DBG_LIB, "signature rejected due to excessive infinite norm");
+ return FALSE;
+ }
+ }
+
+ /* Restriction on l2-norm */
+ norm = bliss_utils_scalar_product(z1, z1, set->n) +
+ bliss_utils_scalar_product(z2ds, z2ds, set->n);
+
+ if (norm >= set->B_l2)
+ {
+ DBG2(DBG_LIB, "signature rejected due to excessive l2-norm");
+ return FALSE;
+ }
+
+ return TRUE;
+}
--- /dev/null
+/*
+ * Copyright (C) 2014 Andreas Steffen
+ * HSR Hochschule fuer Technik Rapperswil
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation; either version 2 of the License, or (at your
+ * option) any later version. See <http://www.fsf.org/copyleft/gpl.txt>.
+ *
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+ * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ * for more details.
+ */
+
+/**
+ * @defgroup bliss_utils bliss_utils
+ * @{ @ingroup bliss_p
+ */
+
+#ifndef BLISS_UTILS_H_
+#define BLISS_UTILS_H_
+
+#include "bliss_param_set.h"
+
+#include <library.h>
+
+/**
+ * Compute the scalar product of two vectors of size n
+ *
+ * @param x input vector of size n
+ * @param y input vector of size n
+ * @param n size of input vectors x and y
+ * @result scalar product of x and y
+ */
+int32_t bliss_utils_scalar_product(int32_t *x, int32_t *y, int n);
+
+/**
+ * Drop d bits but round first
+ *
+ * @param set BLISS parameter set
+ * @param x input vector x of size n
+ * @param xd rounded vector x with d bits dropped
+ */
+void bliss_utils_round_and_drop(bliss_param_set_t *set, int32_t *x, int16_t *xd);
+
+/**
+ * Generate the binary challenge vector c as an array of kappa indices
+ *
+ * @param hasher hasher used as an oracle
+ * @param data_hash hash of the data to be signed
+ * @param ud input vector ud of size n
+ * @param n size of input vector ud
+ * @param kappa parameter kappa
+ * @param c_indices indexes of non-zero challenge coefficients
+ */
+bool bliss_utils_generate_c(hasher_t *hasher, chunk_t data_hash, uint16_t *ud,
+ int n, uint16_t kappa, uint16_t *c_indices);
+
+/**
+ * Check the infinity and l2 norms of the vectors z1 and z2d << d
+ *
+ * @param set BLISS parameter set
+ * @param z1 input vector
+ * @param z2d input vector
+ * @result TRUE if infinite and l2 norms do not exceed boundaries
+ */
+bool bliss_utils_check_norms(bliss_param_set_t *set, int32_t *z1, int16_t *z2d);
+
+#endif /** BLISS_UTILS_H_ @}*/