commit 818813ea2049df733f5e9a9015a1b82dc8ee2dda Author: Zack Weinberg zackw@cmu.edu Date: Thu Jun 7 17:17:54 2012 -0700

Import MKEM implementation from moeller-ref and write out the crypt.h interface for it. (Significant pieces of implementation still to do.) --- Makefile.am | 1 + src/crypt.h | 144 ++++++++++++++++-- src/mkem.cc | 492 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ src/mkem.h | 117 ++++++++++++++ 4 files changed, 739 insertions(+), 15 deletions(-)

diff --git a/Makefile.am b/Makefile.am index d01d4f9..d21fdde 100644 --- a/Makefile.am +++ b/Makefile.am @@ -33,6 +33,7 @@ libstegotorus_a_SOURCES = \ src/compression.cc \ src/connections.cc \ src/crypt.cc \ + src/mkem.cc \ src/network.cc \ src/protocol.cc \ src/rng.cc \ diff --git a/src/crypt.h b/src/crypt.h index cc9309a..869107a 100644 --- a/src/crypt.h +++ b/src/crypt.h @@ -9,6 +9,7 @@ const size_t AES_BLOCK_LEN = 16; const size_t GCM_TAG_LEN = 16; const size_t SHA256_LEN = 32; const size_t EC_P224_LEN = 28; +const size_t MKE_MSG_LEN = 21;

/** * Initialize cryptography library. Must be called before anything that @@ -41,9 +42,6 @@ struct key_generator;

struct ecb_encryptor { - ecb_encryptor() {} - virtual ~ecb_encryptor(); - /** Return a new AES/ECB encryption state using 'key' (of length 'keylen') as the symmetric key. 'keylen' must be 16, 24, or 32 bytes. */ static ecb_encryptor *create(const uint8_t *key, size_t keylen); @@ -57,6 +55,9 @@ struct ecb_encryptor write the result to 'out'. */ virtual void encrypt(uint8_t *out, const uint8_t *in) = 0;

+ virtual ~ecb_encryptor(); +protected: + ecb_encryptor() {} private: ecb_encryptor(const ecb_encryptor&); ecb_encryptor& operator=(const ecb_encryptor&); @@ -64,9 +65,6 @@ private:

struct ecb_decryptor { - ecb_decryptor() {} - virtual ~ecb_decryptor(); - /** Return a new AES/ECB decryption state using 'key' (of length 'keylen') as the symmetric key. 'keylen' must be 16, 24, or 32 bytes. */ static ecb_decryptor *create(const uint8_t *key, size_t keylen); @@ -80,6 +78,9 @@ struct ecb_decryptor write the result to 'out'. */ virtual void decrypt(uint8_t *out, const uint8_t *in) = 0;

+ virtual ~ecb_decryptor(); +protected: + ecb_decryptor() {} private: ecb_decryptor(const ecb_decryptor&) DELETE_METHOD; ecb_decryptor& operator=(const ecb_decryptor&) DELETE_METHOD; @@ -88,9 +89,6 @@ private:

struct gcm_encryptor { - gcm_encryptor() {} - virtual ~gcm_encryptor(); - /** Return a new AES/GCM encryption state using 'key' (of length 'keylen') as the symmetric key. 'keylen' must be 16, 24, or 32 bytes. */ static gcm_encryptor *create(const uint8_t *key, size_t keylen); @@ -108,6 +106,9 @@ struct gcm_encryptor virtual void encrypt(uint8_t *out, const uint8_t *in, size_t inlen, const uint8_t *nonce, size_t nlen) = 0;

+ virtual ~gcm_encryptor(); +protected: + gcm_encryptor() {} private: gcm_encryptor(const gcm_encryptor&); gcm_encryptor& operator=(const gcm_encryptor&); @@ -115,9 +116,6 @@ private:

struct gcm_decryptor { - gcm_decryptor() {} - virtual ~gcm_decryptor(); - /** Return a new AES/GCM decryption state using 'key' (of length 'keylen') as the symmetric key. 'keylen' must be 16, 24, or 32 bytes. */ static gcm_decryptor *create(const uint8_t *key, size_t keylen); @@ -136,6 +134,9 @@ struct gcm_decryptor virtual int decrypt(uint8_t *out, const uint8_t *in, size_t inlen, const uint8_t *nonce, size_t nlen) = 0;

+ virtual ~gcm_decryptor(); +protected: + gcm_decryptor() {} private: gcm_decryptor(const gcm_decryptor&) DELETE_METHOD; gcm_decryptor& operator=(const gcm_decryptor&) DELETE_METHOD; @@ -145,9 +146,6 @@ private: (we use NIST P-224). */ struct ecdh_message { - ecdh_message() {} - virtual ~ecdh_message(); - /** Generate a new Diffie-Hellman message from randomness. */ static ecdh_message *generate();

@@ -170,8 +168,99 @@ struct ecdh_message directly. */ virtual int combine(const uint8_t *xcoord_other, uint8_t *secret_out) const = 0; + + virtual ~ecdh_message(); +protected: + ecdh_message() {} +private: + ecdh_message(const ecdh_message&) DELETE_METHOD; + ecdh_message& operator=(const ecdh_message&) DELETE_METHOD; +}; + +/** Moeller key encapsulation generator: takes a public key and a source + of weak entropy, produces temporary key material and key encapsulation + messages. */ +struct mke_generator +{ + /** Return a new encapsulation generator based on the public key + 'key', which should be a C string of the form produced by + 'mke_decoder::pubkey()', and a key_generator. The object + retains references to both arguments, so make sure their + lifetimes exceed that of this object. You are encouraged + to use key_generator::from_rng() for this. */ + static mke_generator *create(const char *pubkey, key_generator *gen); + + /** Retrieve the public key. This will be the same pointer as was + passed to create(). */ + virtual const char *pubkey() const; + + /** Retrieve the length of the public key (you could call strlen(), + but this may be more efficient). */ + virtual size_t pklen() const; + + /** Generate temporary key material and an encapsulated key message. + This does NOT carry out key derivation; you probably want to use + key_generator::from_mke() instead. The 'message' argument must + point to at least MKE_MSG_LEN bytes of storage, and the 'secret' + argument must point to at least twice that much storage. */ + virtual int generate(uint8_t *secret, uint8_t *message) const; + + /** Extract the padding from a previously-generated encapsulated key + message. Cannot fail. Do not attempt to interpret the byte + returned; just pack it somewhere in the data encrypted with the + derived key material, so that the receiver can verify it. */ + virtual uint8_t extract_padding(uint8_t *message) const; + + virtual ~mke_generator(); +protected: + mke_generator() {} +private: + mke_generator(const mke_generator&) DELETE_METHOD; + mke_generator& operator=(const mke_generator&) DELETE_METHOD; };

+/** Moeller key encapsulation decoder: creates a keypair when + instantiated, can be asked to emit the public key, can decode the + counterpart's key encapsulation messages into temporary key material. */ +struct mke_decoder +{ + /** Return a new encapsulation decoder. Generates a new keypair + from a source of strong entropy. */ + static mke_decoder *create(); + + /** Emit the public key. The return value is a C-string. + The storage for this string belongs to the mke_decoder object. + Its contents are unspecified, but it uses only the characters + ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/=, + */ + virtual const char *pubkey() const; + + /** Retrieve the length of the public key (you could call strlen(), + but this may be more efficient). */ + virtual size_t pklen() const; + + /** Decode an encapsulated key message. This does NOT carry out key + derivation; you probably want to use key_generator::from_mke() + instead. The 'message' argument must point to at least + MKE_MSG_LEN bytes of data, and the 'secret' argument must point + to at least twice that much storage. */ + virtual int decode(uint8_t *secret, uint8_t *message) const; + + /** Extract the padding from an encapsulated key message. + Cannot fail. Do not attempt to interpret the byte returned; + just verify it by comparing it with a byte somewhere in the + data encrypted with the derived key material. */ + virtual uint8_t extract_padding(uint8_t *message) const; + + virtual ~mke_decoder(); +protected: + mke_decoder() {} +private: + mke_decoder(const mke_decoder&) DELETE_METHOD; + mke_decoder& operator=(const mke_decoder&) DELETE_METHOD; +}; + + /** Generate keying material from an initial key of some kind, a salt value, and a context value, all of which are formally bitstrings. See http://tools.ietf.org/html/rfc5869 for the requirements on the @@ -206,6 +295,31 @@ struct key_generator const uint8_t *salt, size_t slen, const uint8_t *ctxt, size_t clen);

+ /** Construct a key generator from a Moeller key generator, and as a + side effect, emit the key encapsulation message. Will use the + public key for the salt. The 'message_out' argument must point + to at least MKE_MSG_LEN bytes of storage. */ + static key_generator *from_mke(const mke_generator *gen, + uint8_t *message_out, + const uint8_t *ctxt, size_t clen); + + /** Construct a key generator from a Moeller key decoder and a + received key encapsulation message. Will use the public key for + the salt. The 'message' argument must point to at least + MKE_MSG_LEN bytes of data. */ + static key_generator *from_mke(const mke_decoder *gen, + uint8_t *message, + const uint8_t *ctxt, size_t clen); + + /** Construct a key generator from the global random number + generator. This should be used in contexts where a great deal + of key material may be required but its strength is not terribly + important; it reduces the demand on the entropy source. Key + generators created by this factory will automatically reseed + themselves when they hit the HKDF upper limit. */ + static key_generator *from_rng(const uint8_t *salt, size_t slen, + const uint8_t *ctxt, size_t clen); + /** Write LEN bytes of key material to BUF. May be called repeatedly. Note that HKDF has a hard upper limit on the total amount of key material it can generate. The return value is diff --git a/src/mkem.cc b/src/mkem.cc new file mode 100644 index 0000000..a17558d --- /dev/null +++ b/src/mkem.cc @@ -0,0 +1,492 @@ +/* Copyright 2012 SRI International + * Based on the public-domain reference implementation of Moeller 2004 + * to be found at http://github.com/zackw/moeller-ref/ + * See LICENSE for other credits and copying information + */ + +#include "util.h" +#include "crypt.h" +#include "mkem.h" + +#include <openssl/rand.h> + +/* Encapsulation of a set of elliptic curve parameters. */ + +struct mk_curve_params +{ + /* generating polynomial, aka reducing polynomial, aka modulus: bignum */ + const uint8_t *m; + size_t L_m; + + /* elliptic curve coefficient 'b': bignum */ + const uint8_t *b; + size_t L_b; + + /* curve group large primes: bignum */ + const uint8_t *p0; + size_t L_p0; + const uint8_t *p1; + size_t L_p1; + + /* curve group sizes: bignum */ + const uint8_t *n0; + size_t L_n0; + const uint8_t *n1; + size_t L_n1; + + /* curve group generators: points (SEC1 compressed format) */ + const uint8_t *g0; + size_t L_g0; + const uint8_t *g1; + size_t L_g1; +}; + +/* MK_CURVE_nbits_index constants correspond to particular curves + for which this algorithm is defined. Currently there is only one. */ + +enum MKEMCurve { + MK_CURVE_163_0 /* original 163-bit curve from Moeller 2004 */ +}; + + +/* All the known curves that can be used with this algorithm are + defined by mk_curve_params objects in this array. */ + +/* work around lack of compound literals in C89 */ +#define S_(c) #c +#define S(c) S_(\x##c) + +/* 21-byte hexadecimal bignum */ +#define N21(a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u) \ + (const uint8_t *)(S(a) S(b) S(c) S(d) S(e) S(f) S(g) \ + S(h) S(i) S(j) S(k) S(l) S(m) S(n) \ + S(o) S(p) S(q) S(r) S(s) S(t) S(u)), 21 + +/* 21+1-byte compressed hexadecimal curve point */ +#define P21(a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u) \ + (const uint8_t *)(S(02) \ + S(a) S(b) S(c) S(d) S(e) S(f) S(g) \ + S(h) S(i) S(j) S(k) S(l) S(m) S(n) \ + S(o) S(p) S(q) S(r) S(s) S(t) S(u)), 22 + +const mk_curve_params mk_curves[] = { +/* MK_CURVE_163_0: + p0 = 2923003274661805836407371179614143033958162426611, n0 = p0*4 + p1 = 5846006549323611672814736302501978089331135490587, n1 = p1*2 */ +{ + N21(08,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,c9), /* m */ + N21(05,84,6d,0f,da,25,53,61,60,67,11,bf,7a,99,b0,72,2e,2e,c8,f7,6b), /* b */ + + N21(02,00,00,00,00,00,00,00,00,00,01,40,a3,f2,a0,c6,ce,d9,ce,ea,f3), /* p0 */ + N21(03,ff,ff,ff,ff,ff,ff,ff,ff,ff,fd,7e,b8,1a,be,72,62,4c,62,2a,1b), /* p1 */ + + N21(08,00,00,00,00,00,00,00,00,00,05,02,8f,ca,83,1b,3b,67,3b,ab,cc), /* n0 */ + N21(07,ff,ff,ff,ff,ff,ff,ff,ff,ff,fa,fd,70,35,7c,e4,c4,98,c4,54,36), /* n1 */ + + P21(00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,01), /* g0 */ + P21(00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,02) /* g1 */ +}, + +}; + +#undef S_ +#undef S +#undef N21 +#undef P21 + +#define FAILZ(expr) if ((expr) == 0) goto fail; + +MKEMParams::MKEMParams(BN_CTX *ctx) + : ctx(ctx), + m(0), b(0), a0(0), a1(0), p0(0), p1(0), n0(0), n1(0), maxu(0), + c0(0), c1(0), g0(0), g1(0), + msgsize(0), pad_bits(0), pad_mask(0), curve_bit(0) +{ + const mk_curve_params *p = &mk_curves[MK_CURVE_163_0]; + size_t bitsize, bytesize, bitcap, k; + + FAILZ(m = BN_bin2bn(p->m, p->L_m, 0)); + FAILZ(b = BN_bin2bn(p->b, p->L_b, 0)); + FAILZ(a0 = BN_new()); FAILZ(BN_zero((BIGNUM *)a0)); + FAILZ(a1 = BN_value_one()); + FAILZ(p0 = BN_bin2bn(p->p0, p->L_p0, 0)); + FAILZ(p1 = BN_bin2bn(p->p1, p->L_p1, 0)); + FAILZ(n0 = BN_bin2bn(p->n0, p->L_n0, 0)); + FAILZ(n1 = BN_bin2bn(p->n1, p->L_n1, 0)); + + FAILZ(c0 = EC_GROUP_new_curve_GF2m(m, a0, b, ctx)); + FAILZ(c1 = EC_GROUP_new_curve_GF2m(m, a1, b, ctx)); + + FAILZ(g0 = EC_POINT_new(c0)); + FAILZ(EC_POINT_oct2point(c0, (EC_POINT *)g0, p->g0, p->L_g0, ctx)); + FAILZ(g1 = EC_POINT_new(c1)); + FAILZ(EC_POINT_oct2point(c1, (EC_POINT *)g1, p->g1, p->L_g1, ctx)); + + /* Calculate the upper limit for the random integer U input to + MKEM_generate_message_u. + + The paper calls for us to choose between curve 0 and curve 1 with + probability proportional to the number of points on that curve, and + then choose a random integer in the range 0 < u < n{curve}. The + easiest way to do this accurately is to choose a random integer in the + range [1, n0 + n1 - 2]. If it is less than n0, MKEM_generate_message_u + will use it unmodified with curve 0. If it is greater than or equal + to n0, MKEM_generate_message_u will subtract n0-1, leaving a number in + the range [1, n1-1], and use that with curve 1. */ + + BIGNUM *mu; + FAILZ(mu = BN_dup(n0)); + FAILZ(BN_add(mu, mu, n1)); + FAILZ(BN_sub(mu, mu, BN_value_one())); + FAILZ(BN_sub(mu, mu, BN_value_one())); + maxu = mu; + + /* Calculate the maximum size of a message and the padding mask applied + to the high byte of each message. See MKEM_generate_message_u for + further exposition. */ + bitsize = EC_GROUP_get_degree(c0); + if ((size_t)EC_GROUP_get_degree(c1) != bitsize) + goto fail; + + bytesize = (bitsize + 7) / 8; + bitcap = bytesize * 8; + k = bitcap - bitsize; + if (k == 0) + goto fail; + + msgsize = bytesize; + pad_bits = k - 1; + pad_mask = ~((1 << (8 - pad_bits)) - 1); + curve_bit = 1 << (8 - k); + return; + + fail: + log_crypto_abort("MKEMParams constructor"); +} + +MKEMParams::~MKEMParams() +{ + /* None of the values in an MKEMParams are secret, so don't bother + clearing them. */ + + /* We do not own 'ctx'. */ + + if (m) BN_free((BIGNUM *)m); + if (b) BN_free((BIGNUM *)b); + if (a0) BN_free((BIGNUM *)a0); + /* a1 is the static BN_value_one() constant and should not be freed. */ + if (p0) BN_free((BIGNUM *)p0); + if (p1) BN_free((BIGNUM *)p1); + if (n0) BN_free((BIGNUM *)n0); + if (n1) BN_free((BIGNUM *)n1); + if (maxu) BN_free((BIGNUM *)maxu); + + if (c0) EC_GROUP_free((EC_GROUP *)c1); + if (c1) EC_GROUP_free((EC_GROUP *)c1); + + if (g0) EC_POINT_free((EC_POINT *)g0); + if (g1) EC_POINT_free((EC_POINT *)g1); + + memset(this, 0, sizeof(*this)); +} + + +MKEM::~MKEM() +{ + /* s0 and s1 are secret. p0 and p1 are not secret, but clear them + anyway. */ + if (s0) BN_clear_free((BIGNUM *)s0); + if (s1) BN_clear_free((BIGNUM *)s1); + + if (p0) EC_POINT_clear_free((EC_POINT *)p0); + if (p1) EC_POINT_clear_free((EC_POINT *)p1); + + memset(this, 0, sizeof(*this)); +} + +/* The secret integers s0 and s1 must be in the range 0 < s < n for + some n, and must be relatively prime to that n. We know a priori + that n is of the form 2**k * p for some small integer k and prime + p. Therefore, it suffices to choose a random integer in the range + [0, n/2), multiply by two and add one (enforcing oddness), and then + reject values which are divisible by p. */ +static BIGNUM * +random_s(const BIGNUM *n, const BIGNUM *p, BN_CTX *c) +{ + BIGNUM h, m, *r; + + BN_init(&h); + BN_init(&m); + FAILZ(r = BN_new()); + FAILZ(BN_copy(&h, n)); + FAILZ(BN_rshift1(&h, &h)); + + do { + FAILZ(BN_rand_range(r, &h)); + FAILZ(BN_lshift1(r, r)); + FAILZ(BN_add(r, r, BN_value_one())); + FAILZ(BN_nnmod(&m, r, p, c)); + } while (BN_is_zero(&m)); + + BN_clear(&h); + BN_clear(&m); + return r; + + fail: + BN_clear(&h); + BN_clear(&m); + if (r) BN_clear_free(r); + return 0; +} + +void +MKEM::load_secret_key() +{ + FAILZ(params); FAILZ(s0); FAILZ(s1); + + FAILZ(p0 = EC_POINT_new(params->c0)); + FAILZ(p1 = EC_POINT_new(params->c1)); + FAILZ(EC_POINT_mul(params->c0, (EC_POINT *)p0, 0, params->g0, s0, + params->ctx)); + FAILZ(EC_POINT_mul(params->c1, (EC_POINT *)p1, 0, params->g1, s1, + params->ctx)); + return; + + fail: + log_crypto_abort("MKEM::MKEM(secret)"); +} + +MKEM::MKEM(const MKEMParams *params, + const uint8_t *s0v, size_t s0l, + const uint8_t *s1v, size_t s1l, + const struct MKEMPrivateKeyLoad&) + : params(params), + s0(BN_bin2bn(s0v, s0l, 0)), + s1(BN_bin2bn(s1v, s1l, 0)), + p0(0), p1(0) +{ + load_secret_key(); +} + +MKEM::MKEM(const MKEMParams *params) + : params(params), + s0(random_s(params->n0, params->p0, params->ctx)), + s1(random_s(params->n1, params->p1, params->ctx)), + p0(0), p1(0) +{ + load_secret_key(); +} + +MKEM::MKEM(const MKEMParams *params, + const uint8_t *p0v, size_t p0l, + const uint8_t *p1v, size_t p1l) + : params(params), s0(0), s1(0), p0(0), p1(0) +{ + EC_POINT *pp0 = EC_POINT_new(params->c0); + EC_POINT *pp1 = EC_POINT_new(params->c1); + + FAILZ(pp0); FAILZ(pp1); + FAILZ(EC_POINT_oct2point(params->c0, pp0, p0v, p0l, params->ctx)); + FAILZ(EC_POINT_oct2point(params->c1, pp1, p1v, p1l, params->ctx)); + + p0 = pp0; + p1 = pp1; + return; + + fail: + log_crypto_abort("MKEM::MKEM(public)"); +} + +int +MKEM::export_public_key(uint8_t *p0o, uint8_t *p1o) const +{ + size_t vsize = params->msgsize + 1; + + if (EC_POINT_point2oct(params->c0, p0, POINT_CONVERSION_COMPRESSED, + p0o, vsize, params->ctx) != vsize || + EC_POINT_point2oct(params->c1, p1, POINT_CONVERSION_COMPRESSED, + p1o, vsize, params->ctx) != vsize) + return -1; + return 0; +} + +/* Write the BIGNUM 'b' to 'to', padded at the high end so that the + result occupies _exactly_ 'sz' bytes. If 'b' requires more than + 'sz' bytes it is an error. */ +static size_t +bn2bin_padhi(const BIGNUM *b, uint8_t *to, size_t sz) +{ + size_t n = BN_num_bytes(b); + if (n > sz) + return 0; + if (n < sz) { + memset(to, 0, sz - n); + to += sz - n; + } + return BN_bn2bin(b, to) + (sz - n); +} + +int +MKEM::export_secret_key(uint8_t *s0o, uint8_t *s1o) const +{ + if (!s0 || !s1) return -1; + + if (bn2bin_padhi(s0, s0o, params->msgsize) != params->msgsize || + bn2bin_padhi(s1, s1o, params->msgsize) != params->msgsize) + return -1; + return 0; +} + +int +MKEM::generate(uint8_t *secret, uint8_t *message) const +{ + BIGNUM u; + uint8_t pad; + int rv = -1; + BN_init(&u); + if (BN_rand_range(&u, params->maxu) && + BN_add(&u, &u, BN_value_one()) && + RAND_bytes(&pad, 1) && + !generate(&u, pad, secret, message)) + rv = 0; + + BN_clear(&u); + return rv; +} + +int +MKEM::generate(const BIGNUM *uraw, uint8_t pad, + uint8_t *secret, uint8_t *message) const +{ + BIGNUM u, x, y; + int use_curve0 = (BN_cmp(uraw, params->n0) < 0); + const EC_GROUP *ca; + const EC_POINT *ga; + const EC_POINT *pa; + EC_POINT *q = 0, *r = 0; + size_t mlen = params->msgsize; + int rv; + + BN_init(&u); + BN_init(&x); + BN_init(&y); + + if (use_curve0) { + ca = params->c0; + ga = params->g0; + pa = p0; + FAILZ(BN_copy(&u, uraw)); + } else { + ca = params->c1; + ga = params->g1; + pa = p1; + FAILZ(BN_sub(&u, uraw, params->n0)); + FAILZ(BN_add(&u, &u, BN_value_one())); + } + + FAILZ(q = EC_POINT_new(ca)); + FAILZ(r = EC_POINT_new(ca)); + FAILZ(EC_POINT_mul(ca, q, 0, ga, &u, params->ctx)); + FAILZ(EC_POINT_mul(ca, r, 0, pa, &u, params->ctx)); + + FAILZ(EC_POINT_get_affine_coordinates_GF2m(ca, q, &x, &y, params->ctx)); + if (bn2bin_padhi(&x, message, mlen) != mlen) + goto fail; + if (message[0] & (params->pad_mask|params->curve_bit)) /* see below */ + goto fail; + memcpy(secret, message, mlen); + + FAILZ(EC_POINT_get_affine_coordinates_GF2m(ca, r, &x, &y, params->ctx)); + if (bn2bin_padhi(&x, secret + mlen, mlen) != mlen) + goto fail; + + /* K high bits of the message will be zero. Fill in the high K-1 + of them with random bits from the pad, and use the lowest bit + to identify the curve in use. That bit will have a bias on the + order of 2^{-d/2} where d is the bit-degree of the curve; 2^{-81} + for the only curve presently implemented. This is acceptably + small since an elliptic curve of d bits gives only about d/2 bits + of security anyway, and is much better than allowing a timing + attack via the recipient having to attempt point decompression + twice for curve 1 but only once for curve 0 (or, alternatively, + doubling the time required for all decryptions). */ + + pad &= params->pad_mask; + pad |= (use_curve0 ? 0 : params->curve_bit); + message[0] |= pad; + + rv = 0; + done: + BN_clear(&u); + BN_clear(&x); + BN_clear(&y); + if (q) EC_POINT_clear_free(q); + if (r) EC_POINT_clear_free(r); + return rv; + + fail: + log_crypto_warn("MKEM::generate"); + memset(message, 0, mlen); + memset(secret, 0, mlen * 2); + rv = -1; + goto done; +} + +int +MKEM::decode(uint8_t *secret, const uint8_t *message) const +{ + int use_curve0 = !(message[0] & params->curve_bit); + const EC_GROUP *ca = use_curve0 ? params->c0 : params->c1; + const BIGNUM *sa = use_curve0 ? s0 : s1; + EC_POINT *q = 0, *r = 0; + uint8_t *unpadded = 0; + BIGNUM x, y; + size_t mlen = params->msgsize; + int rv; + + if (!s0 || !s1) /* secret key not available */ + return -1; + + BN_init(&x); + BN_init(&y); + FAILZ(q = EC_POINT_new(ca)); + FAILZ(r = EC_POINT_new(ca)); + FAILZ(unpadded = (uint8_t *)xmalloc(mlen + 1)); + + /* Copy the message, erase the padding bits, and put an 0x02 byte on + the front so we can use EC_POINT_oct2point to recover the + y-coordinate. */ + unpadded[0] = 0x02; + unpadded[1] = (message[0] & ~(params->pad_mask|params->curve_bit)); + memcpy(&unpadded[2], &message[1], mlen - 1); + + FAILZ(EC_POINT_oct2point(ca, q, unpadded, mlen + 1, + params->ctx)); + FAILZ(EC_POINT_mul(ca, r, 0, q, sa, params->ctx)); + + FAILZ(EC_POINT_get_affine_coordinates_GF2m(ca, q, &x, &y, params->ctx)); + if (bn2bin_padhi(&x, secret, mlen) != mlen) + goto fail; + + FAILZ(EC_POINT_get_affine_coordinates_GF2m(ca, r, &x, &y, params->ctx)); + if (bn2bin_padhi(&x, secret + mlen, mlen) != mlen) + goto fail; + + rv = 0; + done: + if (unpadded) { + memset(unpadded, 0, mlen + 1); + free(unpadded); + } + if (q) EC_POINT_clear_free(q); + if (r) EC_POINT_clear_free(r); + BN_clear(&x); + BN_clear(&y); + return rv; + + fail: + log_crypto_warn("MKEM::decode"); + rv = -1; + memset(secret, 0, mlen * 2); + goto done; +} diff --git a/src/mkem.h b/src/mkem.h new file mode 100644 index 0000000..8e9d6a6 --- /dev/null +++ b/src/mkem.h @@ -0,0 +1,117 @@ +/* Copyright 2012 SRI International + * Based on the public-domain reference implementation of Moeller 2004 + * to be found at http://github.com/zackw/moeller-ref/ + * See LICENSE for other credits and copying information + */ + +#ifndef MKEM_H +#define MKEM_H + +/* NOTE: The APIs defined in this header should not be used directly. + Use the crypt.h 'mke_generator' and 'mke_decoder' objects instead. */ + +#include <openssl/bn.h> +#include <openssl/ec.h> + +struct MKEMParams +{ + BN_CTX *ctx; + + const BIGNUM *m; + const BIGNUM *b; + const BIGNUM *a0; + const BIGNUM *a1; + const BIGNUM *p0; + const BIGNUM *p1; + const BIGNUM *n0; + const BIGNUM *n1; + const BIGNUM *maxu; + + const EC_GROUP *c0; + const EC_GROUP *c1; + + const EC_POINT *g0; + const EC_POINT *g1; + + size_t msgsize; + unsigned int pad_bits; + uint8_t pad_mask; + uint8_t curve_bit; + + MKEMParams(BN_CTX *ctx); + ~MKEMParams(); + +private: + MKEMParams(const MKEMParams&) DELETE_METHOD; + MKEMParams& operator=(const MKEMParams&) DELETE_METHOD; +}; + +// needed to distinguish two constructor overloads +struct MKEMPrivateKeyLoad {}; +const struct MKEMPrivateKeyLoad PRIVATE_KEY = {}; + +struct MKEM +{ + const MKEMParams *params; + const BIGNUM *s0; + const BIGNUM *s1; + const EC_POINT *p0; + const EC_POINT *p1; + + ~MKEM(); + + /** Generate a brand new keypair from randomness. */ + MKEM(const MKEMParams *params); + + /** Load a secret key expressed as two integers (s0, s1), and + regenerate the public key from it. */ + MKEM(const MKEMParams *params, + const uint8_t *s0, size_t s0l, + const uint8_t *s1, size_t s1l, + const struct MKEMPrivateKeyLoad&); + + /** Load a public key expressed as two elliptic curve points (p0, p1). + Since the secret key is not available, MKEM_export_secret_key and + MKEM_decode_message will fail if called on this MKEM. */ + MKEM(const MKEMParams *params, + const uint8_t *p0, size_t p0l, + const uint8_t *p1, size_t p1l); + + /** Export the public key as a pair of points. The byte buffers + must each point to at least params->msgsize+1 bytes of storage. */ + int export_public_key(uint8_t *p1, uint8_t *p2) const; + + /** Export the secret key as a pair of integers. The byte buffers + must each point to at least params->msgsize bytes of storage. */ + int export_secret_key(uint8_t *s0, uint8_t *s1) const; + + /** Generate secret material K and encrypted message kk from randomness. + This does NOT carry out key derivation; the "secret" output is what + the paper describes as $\mathfrak{k} || encode(x_R)$, not KDF of that. + The 'message' argument must point to at least params->msgsize + bytes of storage, and the 'secret' argument must point to twice + that much storage. */ + int generate(uint8_t *secret, uint8_t *message) const; + + /** Same, but work from a preselected integer 'u', which must be in + the closed interval [1, params->maxu], and an extra byte's worth + of random bits for padding. + + This is exposed only for the sake of known-answer tests. Use of + non-random 'u' or 'pad' invalidates system properties, as does + reuse of either value. */ + int generate(const BIGNUM *u, uint8_t pad, + uint8_t *secret, uint8_t *message) const; + + /* Decode an encrypted message. As with MKEM_generate_message, the + result is NOT run through a KDF. */ + int decode(uint8_t *secret, const uint8_t *message) const; + +private: + void load_secret_key(); + + MKEM(const MKEM&) DELETE_METHOD; + MKEM& operator=(const MKEM&) DELETE_METHOD; +}; + +#endif