Created newhope plugin implementing the New Hope key exchange algorithm
authorAndreas Steffen <andreas.steffen@strongswan.org>
Tue, 26 Jul 2016 09:32:22 +0000 (11:32 +0200)
committerAndreas Steffen <andreas.steffen@strongswan.org>
Wed, 10 Aug 2016 12:22:00 +0000 (14:22 +0200)
15 files changed:
configure.ac
src/libcharon/config/proposal.c
src/libstrongswan/Makefile.am
src/libstrongswan/crypto/diffie_hellman.c
src/libstrongswan/crypto/diffie_hellman.h
src/libstrongswan/crypto/proposal/proposal_keywords_static.txt
src/libstrongswan/plugins/newhope/Makefile.am [new file with mode: 0644]
src/libstrongswan/plugins/newhope/newhope_ke.c [new file with mode: 0644]
src/libstrongswan/plugins/newhope/newhope_ke.h [new file with mode: 0644]
src/libstrongswan/plugins/newhope/newhope_noise.c [new file with mode: 0644]
src/libstrongswan/plugins/newhope/newhope_noise.h [new file with mode: 0644]
src/libstrongswan/plugins/newhope/newhope_plugin.c [new file with mode: 0644]
src/libstrongswan/plugins/newhope/newhope_plugin.h [new file with mode: 0644]
src/libstrongswan/plugins/newhope/newhope_reconciliation.c [new file with mode: 0644]
src/libstrongswan/plugins/newhope/newhope_reconciliation.h [new file with mode: 0644]

index 07f0d5f..9e22648 100644 (file)
@@ -136,6 +136,7 @@ ARG_DISBL_SET([gmp],            [disable GNU MP (libgmp) based crypto implementa
 ARG_DISBL_SET([hmac],           [disable HMAC crypto implementation plugin.])
 ARG_ENABL_SET([md4],            [enable MD4 software implementation plugin.])
 ARG_DISBL_SET([md5],            [disable MD5 software implementation plugin.])
+ARG_ENABL_SET([newhope],        [enable New Hope crypto plugin.])
 ARG_DISBL_SET([nonce],          [disable nonce generation plugin.])
 ARG_ENABL_SET([ntru],           [enables the NTRU crypto plugin.])
 ARG_ENABL_SET([openssl],        [enables the OpenSSL crypto plugin.])
@@ -1358,6 +1359,7 @@ ADD_PLUGIN([ctr],                  [s charon scripts nm cmd])
 ADD_PLUGIN([ccm],                  [s charon scripts nm cmd])
 ADD_PLUGIN([gcm],                  [s charon scripts nm cmd])
 ADD_PLUGIN([ntru],                 [s charon scripts nm cmd])
+ADD_PLUGIN([newhope],              [s charon scripts nm cmd])
 ADD_PLUGIN([bliss],                [s charon pki scripts nm cmd])
 ADD_PLUGIN([curl],                 [s charon scepclient pki scripts nm cmd])
 ADD_PLUGIN([files],                [s charon scepclient pki scripts nm cmd])
@@ -1515,6 +1517,7 @@ AM_CONDITIONAL(USE_CCM, test x$ccm = xtrue)
 AM_CONDITIONAL(USE_GCM, test x$gcm = xtrue)
 AM_CONDITIONAL(USE_AF_ALG, test x$af_alg = xtrue)
 AM_CONDITIONAL(USE_NTRU, test x$ntru = xtrue)
+AM_CONDITIONAL(USE_NEWHOPE, test x$newhope = xtrue)
 AM_CONDITIONAL(USE_BLISS, test x$bliss = xtrue)
 
 #  charon plugins
@@ -1630,7 +1633,7 @@ AM_CONDITIONAL(USE_CONFTEST, test x$conftest = xtrue)
 AM_CONDITIONAL(USE_LIBSTRONGSWAN, test x$charon = xtrue -o x$pki = xtrue -o x$scepclient = xtrue -o x$conftest = xtrue -o x$fast = xtrue -o x$imcv = xtrue -o x$nm = xtrue -o x$tkm = xtrue -o x$cmd = xtrue -o x$tls = xtrue -o x$tnc_tnccs = xtrue -o x$aikgen = xtrue -o x$aikpub2 = xtrue -o x$svc = xtrue -o x$systemd = xtrue)
 AM_CONDITIONAL(USE_LIBCHARON, test x$charon = xtrue -o x$conftest = xtrue -o x$nm = xtrue -o x$tkm = xtrue -o x$cmd = xtrue -o x$svc = xtrue -o x$systemd = xtrue)
 AM_CONDITIONAL(USE_LIBIPSEC, test x$libipsec = xtrue)
-AM_CONDITIONAL(USE_LIBNTTFFT, test x$bliss = xtrue)
+AM_CONDITIONAL(USE_LIBNTTFFT, test x$bliss = xtrue -o x$newhope = xtrue)
 AM_CONDITIONAL(USE_LIBTNCIF, test x$tnc_tnccs = xtrue -o x$imcv = xtrue)
 AM_CONDITIONAL(USE_LIBTNCCS, test x$tnc_tnccs = xtrue)
 AM_CONDITIONAL(USE_LIBPTTLS, test x$tnc_tnccs = xtrue)
@@ -1778,6 +1781,7 @@ AC_CONFIG_FILES([
        src/libstrongswan/plugins/ntru/Makefile
        src/libstrongswan/plugins/bliss/Makefile
        src/libstrongswan/plugins/bliss/tests/Makefile
+       src/libstrongswan/plugins/newhope/Makefile
        src/libstrongswan/plugins/test_vectors/Makefile
        src/libstrongswan/tests/Makefile
        src/libipsec/Makefile
index a83acec..ddbc155 100644 (file)
@@ -842,6 +842,7 @@ static bool proposal_add_supported_ike(private_proposal_t *this, bool aead)
                        case NTRU_128_BIT:
                        case NTRU_192_BIT:
                        case NTRU_256_BIT:
+                       case NH_128_BIT:
                                add_algorithm(this, DIFFIE_HELLMAN_GROUP, group, 0);
                                break;
                        default:
index 4546878..eee4408 100644 (file)
@@ -601,6 +601,13 @@ if MONOLITHIC
 endif
 endif
 
+if USE_NEWHOPE
+  SUBDIRS += plugins/newhope
+if MONOLITHIC
+  libstrongswan_la_LIBADD += plugins/newhope/libstrongswan-newhope.la
+endif
+endif
+
 if USE_TEST_VECTORS
   SUBDIRS += plugins/test_vectors
 if MONOLITHIC
index 0d4cd91..6dcb6cb 100644 (file)
@@ -49,7 +49,9 @@ ENUM_NEXT(diffie_hellman_group_names, NTRU_112_BIT, NTRU_256_BIT, MODP_NULL,
        "NTRU_128",
        "NTRU_192",
        "NTRU_256");
-ENUM_NEXT(diffie_hellman_group_names, MODP_CUSTOM, MODP_CUSTOM, NTRU_256_BIT,
+ENUM_NEXT(diffie_hellman_group_names, NH_128_BIT, NH_128_BIT, NTRU_256_BIT,
+       "NEWHOPE_128");
+ENUM_NEXT(diffie_hellman_group_names, MODP_CUSTOM, MODP_CUSTOM, NH_128_BIT,
        "MODP_CUSTOM");
 ENUM_END(diffie_hellman_group_names, MODP_CUSTOM);
 
@@ -554,6 +556,7 @@ bool diffie_hellman_verify_value(diffie_hellman_group_t group, chunk_t value)
                case NTRU_128_BIT:
                case NTRU_192_BIT:
                case NTRU_256_BIT:
+               case NH_128_BIT:
                        /* verification currently not supported, do in plugin */
                        valid = FALSE;
                        break;
index abebd66..f457153 100644 (file)
@@ -68,6 +68,7 @@ enum diffie_hellman_group_t {
        NTRU_128_BIT = 1031,
        NTRU_192_BIT = 1032,
        NTRU_256_BIT = 1033,
+       NH_128_BIT   = 1040,
        /** internally used DH group with additional parameters g and p, outside
         * of PRIVATE USE (i.e. IKEv2 DH group range) so it can't be negotiated */
        MODP_CUSTOM = 65536,
index 8760243..3ac7729 100644 (file)
@@ -167,5 +167,6 @@ ntru112,          DIFFIE_HELLMAN_GROUP, NTRU_112_BIT,              0
 ntru128,          DIFFIE_HELLMAN_GROUP, NTRU_128_BIT,              0
 ntru192,          DIFFIE_HELLMAN_GROUP, NTRU_192_BIT,              0
 ntru256,          DIFFIE_HELLMAN_GROUP, NTRU_256_BIT,              0
+newhope128,       DIFFIE_HELLMAN_GROUP, NH_128_BIT,                0
 noesn,            EXTENDED_SEQUENCE_NUMBERS, NO_EXT_SEQ_NUMBERS,   0
 esn,              EXTENDED_SEQUENCE_NUMBERS, EXT_SEQ_NUMBERS,      0
diff --git a/src/libstrongswan/plugins/newhope/Makefile.am b/src/libstrongswan/plugins/newhope/Makefile.am
new file mode 100644 (file)
index 0000000..fc72410
--- /dev/null
@@ -0,0 +1,25 @@
+AM_CPPFLAGS = \
+       -I$(top_srcdir)/src/libstrongswan \
+       -I$(top_srcdir)/src/libstrongswan/math/libnttfft
+
+AM_CFLAGS = \
+       $(PLUGIN_CFLAGS) \
+       @COVERAGE_CFLAGS@
+
+if MONOLITHIC
+noinst_LTLIBRARIES = libstrongswan-newhope.la
+else
+plugin_LTLIBRARIES = libstrongswan-newhope.la
+endif
+
+libstrongswan_newhope_la_SOURCES = \
+       newhope_plugin.h newhope_plugin.c \
+       newhope_ke.h newhope_ke.c \
+       newhope_noise.h newhope_noise.c \
+       newhope_reconciliation.h newhope_reconciliation.c
+
+libstrongswan_newhope_la_LDFLAGS = -module -avoid-version
+
+libstrongswan_newhope_la_LIBADD = \
+       $(top_builddir)/src/libstrongswan/math/libnttfft/libnttfft.la
+
diff --git a/src/libstrongswan/plugins/newhope/newhope_ke.c b/src/libstrongswan/plugins/newhope/newhope_ke.c
new file mode 100644 (file)
index 0000000..d4ce8c6
--- /dev/null
@@ -0,0 +1,622 @@
+/*
+ * Copyright (C) 2016 Andreas Steffen
+ * HSR Hochschule fuer Technik Rapperswil
+ *
+ * Based on public domain code by Erdem Alkim, Léo Ducas, Thomas Pöppelmann,
+ * and Peter Schwabe.
+ *
+ * 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 "newhope_ke.h"
+#include "newhope_noise.h"
+#include "newhope_reconciliation.h"
+
+#include <ntt_fft.h>
+#include <ntt_fft_reduce.h>
+#include <crypto/diffie_hellman.h>
+#include <utils/debug.h>
+
+static const int seed_len =   32;  /* 256 bits */
+static const int poly_len = 1792;  /* size of 1024 packed 14-bit coefficients */
+static const int rec_len =   256;  /* size of 1024 packed  2-bit coefficients */
+
+typedef struct private_newhope_ke_t private_newhope_ke_t;
+
+/**
+ * Private data of an newhope_ke_t object.
+ */
+struct private_newhope_ke_t {
+
+       /**
+        * Public newhope_ke_t interface.
+        */
+       newhope_ke_t public;
+
+       /**
+        * FFT parameter set
+        */
+       const ntt_fft_params_t *params;
+
+       /**
+        * Secret noise polynomial s
+        */
+       uint32_t *s;
+
+       /**
+        * Output polynomial u = a * NTT(s') + NTT(e')
+        */
+       uint32_t *u;
+
+       /**
+        * Error reconciliation help bits
+        */
+       uint8_t *r;
+
+       /**
+        * Shared secret
+        */
+       chunk_t shared_secret;
+
+};
+
+/**
+ * Derive 14-bit coefficients of polynomial a from 256 bit random seed
+ * using the SHAKE128 extended output function
+ */
+static uint32_t* derive_a_poly(private_newhope_ke_t *this, chunk_t seed)
+{
+       uint32_t *a;
+       uint8_t x[2];
+       int i = 0;
+       xof_t *xof;
+
+       xof = lib->crypto->create_xof(lib->crypto, XOF_SHAKE_128);
+       if (!xof)
+       {
+               DBG1(DBG_LIB, "could not instantiate SHAKE128 XOF");
+               return NULL;
+       }
+
+       if (!xof->set_seed(xof, seed))
+       {
+               DBG1(DBG_LIB, "could not set seed of SHAKE128 XOF");
+               xof->destroy(xof);
+               return NULL;
+       }
+
+       /* allocate dynamic memory for polynomial a */
+       a = (uint32_t*)malloc(this->params->n * sizeof(uint32_t));
+
+       while (i < this->params->n)
+       {
+               if (!xof->get_bytes(xof, sizeof(x), x))
+               {
+                       DBG1(DBG_LIB, "could not get bytes from SHAKE128 XOF");
+                       xof->destroy(xof);
+                       free(a);
+                       return NULL;
+               }
+
+               /*
+                * Treat x as a 16 bit unsigned little endian integer
+                * and truncate to 14 bits
+                */
+               a[i] = uletoh16(x) & 0x3fff;
+
+               if (a[i] < this->params->q)
+               {
+                       i++;
+               }
+       }
+       xof->destroy(xof);
+
+       return a;
+}
+
+/**
+ * Pack four 14-bit coefficients into seven consecutive bytes
+ *
+ *                       1                   2                   3
+ *   0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+ *  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+ *  |L 0 0 0 0 0 0 0|L 1 H 0 0 0 0 0|M 1 1 1 1 1 1 1|L 2 2 2 H 1 1 1|
+ *  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+ *  |M 2 2 2 2 2 2 2|L 3 3 3 3 3 H 2|H 3 3 3 3 3 3 3|L 0 0 0 0 0 0 0|
+ *  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+ */
+static void pack_poly(private_newhope_ke_t *this, uint8_t *x, uint32_t *p)
+{
+       int i;
+
+       for (i = 0; i < this->params->n; i += 4)
+       {
+               *x++ = (p[i] & 0xff );
+               *x++ = (p[i]   >>  8) | (p[i+1] << 6);
+               *x++ = (p[i+1] >>  2);
+               *x++ = (p[i+1] >> 10) | (p[i+2] << 4);
+               *x++ = (p[i+2] >>  4);
+               *x++ = (p[i+2] >> 12) | (p[i+3] << 2);
+               *x++ = (p[i+3] >>  6);
+       }
+}
+
+/**
+ * Unpack seven consecutive bytes into four 14-bit coefficients
+ */
+static uint32_t* unpack_poly(private_newhope_ke_t * this, uint8_t *x)
+{
+       uint32_t *p;
+       int i;
+
+       p = (uint32_t*)malloc(this->params->n * sizeof(uint32_t));
+
+       for (i = 0; i < this->params->n; i += 4)
+       {
+               p[i]   =  x[0]       | (((uint32_t)x[1] & 0x3f) <<  8);
+               p[i+1] = (x[1] >> 6) | (((uint32_t)x[2]) <<  2)
+                                                        | (((uint32_t)x[3] & 0x0f) << 10);
+               p[i+2] = (x[3] >> 4) | (((uint32_t)x[4]) <<  4)
+                                                        | (((uint32_t)x[5] & 0x03) << 12);
+               p[i+3] = (x[5] >> 2) | (((uint32_t)x[6]) <<  6);
+               x += 7;
+       }
+       for (i = 0; i < this->params->n; i++)
+       {
+               if (p[i] >= this->params->q)
+               {
+                       DBG1(DBG_LIB, "polynomial coefficient must be smaller than %u",
+                                                  this->params->q);
+                       free(p);
+                       return NULL;
+               }
+       }
+       return p;
+}
+
+/**
+ * Multiply and add polynomials in the frequency domain
+ */
+static uint32_t* multiply_add_poly(private_newhope_ke_t *this,
+                                                                  uint32_t *a, uint32_t *e)
+{
+       ntt_fft_t *fft;
+       uint32_t *b, t;
+       int i;
+
+       /* transform s and h to frequency domain */
+       fft = ntt_fft_create(this->params);
+       fft->transform(fft, this->s, this->s, FALSE);
+       fft->transform(fft, e, e, FALSE);
+       fft->destroy(fft);
+       
+       b = (uint32_t*)malloc(this->params->n * sizeof(uint32_t));
+
+       /* compute  b = a * s + e in the frequency domain */
+       for (i = 0; i < this->params->n; i++)
+       {
+               /* convert a[i] to Montgomery domain */
+               t = ntt_fft_mreduce(a[i] * this->params->r2, this->params);
+
+               /* compute b[i] = a[i] * s[i] + e[i] in Montgomery domain */
+               t = ntt_fft_mreduce(t * this->s[i], this->params) + e[i];
+
+               /* exit Montgomery domain before transmitting polynomial b */
+               b[i] = ntt_fft_mreduce(t, this->params);
+       }
+       memwipe(e, this->params->n * sizeof(uint32_t));
+
+       return b;
+}
+
+/**
+ * Multiply polynomials in the frequency domain and return to time domain
+ */
+static uint32_t* multiply_ntt_inv_poly(private_newhope_ke_t *this, uint32_t *b)
+{
+       ntt_fft_t *fft;
+       uint32_t *v, t;
+       int i;
+
+       v = (uint32_t*)malloc(this->params->n * sizeof(uint32_t));
+
+       for (i = 0; i < this->params->n; i++)
+       {
+               /* convert b[i] to Montgomery domain */
+               t = ntt_fft_mreduce(b[i] * this->params->r2, this->params);
+
+               /* compute v[i] = b[i] * s[i] in Montgomery domain */
+               v[i] = ntt_fft_mreduce(t * this->s[i], this->params);
+       }
+
+       /* transform v back to time domain */
+       fft = ntt_fft_create(this->params);
+       fft->transform(fft, v, v, TRUE);
+       fft->destroy(fft);
+
+       return v;
+}
+
+/**
+ * Pack four 2-bit coefficents into one byte
+ */
+static void pack_rec(private_newhope_ke_t *this, uint8_t *x, uint8_t *r)
+{
+       int i;
+
+       for (i = 0; i < this->params->n; i += 4)
+       {
+               *x++ = r[i] | r[i+1] << 2 | r[i+2] << 4 | r[i+3] << 6;
+       }
+}
+
+static uint8_t* unpack_rec(private_newhope_ke_t *this, uint8_t *x)
+{
+       uint8_t *r;
+       int i;
+
+       r = (uint8_t*)malloc(this->params->n);
+
+       for (i = 0; i < this->params->n; i += 4)
+       {
+               r[i]   = (*x)      & 0x03;
+               r[i+1] = (*x >> 2) & 0x03;
+               r[i+2] = (*x >> 4) & 0x03;
+               r[i+3] = (*x >> 6) & 0x03;
+               x++;
+       }
+
+       return r;
+}
+
+METHOD(diffie_hellman_t, get_my_public_value, bool,
+       private_newhope_ke_t *this, chunk_t *value)
+{
+       uint16_t n, q;
+       int i;
+
+       /* Define some often-used constants */
+       n = this->params->n;
+       q = this->params->q;
+
+       /* are we the initiator? */
+       if (this->u == NULL)
+       {
+               rng_t *rng;
+               uint32_t *a = NULL, *b = NULL, *e = NULL;
+               uint8_t noise_seed_buf[seed_len];
+               chunk_t noise_seed = { noise_seed_buf, seed_len};
+               chunk_t a_seed;
+               newhope_noise_t *noise = NULL;
+               bool success = FALSE;
+
+               /* allocate space for public output value */
+               *value = chunk_alloc(poly_len + seed_len);
+               a_seed = chunk_create(value->ptr + poly_len, seed_len);
+       
+               /* create polynomial a from 256 bit random seed */
+               rng = lib->crypto->create_rng(lib->crypto, RNG_STRONG);
+               if (!rng)
+               {
+                       DBG1(DBG_LIB, "could not instatiate random source");
+                       return FALSE;
+               }
+               if (!rng->get_bytes(rng, seed_len, a_seed.ptr))
+               {
+                       DBG1(DBG_LIB, "could not generate seed for polynomial a");
+                       goto end;
+               }
+       
+               a = derive_a_poly(this, a_seed);
+               if (a == NULL)
+               {
+                       goto end;
+               }
+       
+               /* generate random seed for the derivation of noise polynomials */
+               if (!rng->get_bytes(rng, seed_len, noise_seed.ptr))
+               {
+                       DBG1(DBG_LIB, "could not generate seed for noise polynomials");
+                       goto end;
+               }
+       
+               /* create noise polynomial generator */
+               noise = newhope_noise_create(noise_seed);
+               if (!noise)
+               {
+                       goto end;
+               }
+
+               /* create noise polynomial s from seed with nonce = 0x00 */
+               this->s = noise->get_binomial_words(noise, 0x00, n, q);
+               if (this->s == NULL)
+               {
+                       goto end;
+               }
+
+               /* create noise polynomial e from seed with nonce = 0x01 */
+               e = noise->get_binomial_words(noise, 0x01, n, q);
+               if (e == NULL)
+               {
+                       goto end;
+               }
+
+               /* compute b = a * NTT(s) + NTT(e) */
+               b = multiply_add_poly(this, a, e);
+
+               DBG3(DBG_LIB, "   i  a[i]  b[i]");
+               for (i = 0; i < n; i++)
+               {
+                       DBG3(DBG_LIB, "%4d %5u %5u", i, a[i], b[i]);
+               }
+
+               /* pack coefficients of polynomial b */
+               pack_poly(this, value->ptr, b);
+               success = TRUE;
+
+       end:
+               rng->destroy(rng);
+               DESTROY_IF(noise);
+               free(a);
+               free(b);
+               free(e);
+
+               if (!success)
+               {
+               chunk_free(value);
+               }
+               return success;
+       }
+       else
+       {
+               DBG3(DBG_LIB, "   i  u[i]  r[i]");
+               for (i = 0; i < n; i++)
+               {
+                       DBG3(DBG_LIB, "%4d %5u %5u", i, this->u[i], this->r[i]);
+               }
+
+               /* allocate space for public output value */
+               *value = chunk_alloc(poly_len + rec_len);
+
+               /* pack coefficients of polynomial u */
+               pack_poly(this, value->ptr, this->u);
+
+               /* pack coefficients of polynomial r */
+               pack_rec(this, value->ptr + poly_len, this->r);
+
+               return TRUE;
+       }
+}
+
+METHOD(diffie_hellman_t, get_shared_secret, bool,
+       private_newhope_ke_t *this, chunk_t *secret)
+{
+       if (this->shared_secret.len == 0)
+       {
+               *secret = chunk_empty;
+               return FALSE;
+       }
+       *secret = chunk_clone(this->shared_secret);
+
+       return TRUE;
+}
+
+METHOD(diffie_hellman_t, set_other_public_value, bool,
+       private_newhope_ke_t *this, chunk_t value)
+{
+       newhope_reconciliation_t * rec;
+       uint16_t n, q;
+       int i;
+
+       /* Define some often-used constants */
+       n = this->params->n;
+       q = this->params->q;
+
+       /* are we the responder? */
+       if (this->s == NULL)
+       {
+               uint32_t *a = NULL, *b = NULL, *e1 = NULL, *e2 = NULL, *v = NULL, t;
+               uint8_t *rbits = NULL;
+               uint8_t noise_seed_buf[seed_len];
+               chunk_t noise_seed = { noise_seed_buf, seed_len };
+               chunk_t a_seed;
+               newhope_noise_t *noise = NULL;
+               rng_t *rng = NULL;
+               bool success = FALSE;
+
+               if (value.len != poly_len + seed_len)
+               {
+                       DBG1(DBG_LIB, "received %N KE payload of incorrect size",
+                                                  diffie_hellman_group_names, NH_128_BIT);
+                       return FALSE;
+               }
+               a_seed = chunk_create(value.ptr + poly_len, seed_len);
+
+               a = derive_a_poly(this, a_seed);
+               if (a == NULL)
+               {
+                       return FALSE;
+               }
+
+               b = unpack_poly(this, value.ptr);
+               if (b == NULL)
+               {
+                       goto end;
+               }
+
+               /* debug output of polynomials a and b */
+               DBG3(DBG_LIB, "   i  a[i]  b[i]");
+               for (i = 0; i < n; i++)
+               {
+                       DBG3(DBG_LIB, "%4d %5u %5u", i, a[i], b[i]);
+               }
+               
+               /* generate random seed for the derivation of noise polynomials */
+               rng = lib->crypto->create_rng(lib->crypto, RNG_STRONG);
+               if (!rng)
+               {
+                       DBG1(DBG_LIB, "could not instatiate random source");
+                       return FALSE;
+               }
+               if (!rng->get_bytes(rng, seed_len, noise_seed.ptr))
+               {
+                       DBG1(DBG_LIB, "could not generate seed for noise polynomials");
+                       goto end;
+               }
+
+               /* create noise polynomial generator */
+               noise = newhope_noise_create(noise_seed);
+               if (!noise)
+               {
+                       goto end;
+               }
+
+               /* create noise polynomial s' from seed with nonce = 0x00 */
+               this->s = noise->get_binomial_words(noise, 0x00, n, q);
+               if (this->s == NULL)
+               {
+                       goto end;
+               }
+
+               /* create noise polynomial e' from seed with nonce = 0x01 */
+               e1 = noise->get_binomial_words(noise, 0x01, n, q);
+               if (e1 == NULL)
+               {
+                       goto end;
+               }
+               
+               /* create noise polynomial e'' from seed with nonce = 0x02 */
+               e2 = noise->get_binomial_words(noise, 0x02, n, q);
+               if (e2 == NULL)
+               {
+                       goto end;
+               }
+
+               /* compute u = a * NTT(s') + NTT(e') */
+               this->u = multiply_add_poly(this, a, e1);
+
+               /* compute v = NTT_inv( b * NTT(s') ) */
+               v = multiply_ntt_inv_poly(this, b);
+
+               /* compute v = v + e'' */
+               for (i = 0; i < n; i++)
+               {
+                       t = v[i] + e2[i];
+                       v[i] = (t < q) ? t : t - q;
+               }
+               memwipe(e2, n * sizeof(uint32_t));
+
+               /* create uniform noise bytes from seed with nonce = 0x02 */
+               rbits = noise->get_uniform_bytes(noise, 0x03, n/(4*8));
+
+               rec = newhope_reconciliation_create(n, q);
+               this->r = rec->help_reconcile(rec, v, rbits);
+               free(rbits);
+               this->shared_secret = rec->reconcile(rec, v, this->r);
+               rec->destroy(rec);
+
+               DBG4(DBG_LIB, "key: %B", &this->shared_secret);
+               success = TRUE;
+
+       end:
+               DESTROY_IF(rng);
+               DESTROY_IF(noise);
+               free(a);
+               free(b);
+               free(e1);
+               free(e2);
+               free(v);
+
+               return success;
+       }
+       else
+       {
+               uint32_t *v;
+
+               if (value.len != poly_len + rec_len)
+               {
+                       DBG1(DBG_LIB, "received %N KE payload of incorrect size",
+                                                  diffie_hellman_group_names, NH_128_BIT);
+                       return FALSE;
+               }
+
+               this->u = unpack_poly(this, value.ptr);
+               if (this->u == NULL)
+               {
+                       return FALSE;
+               }
+
+               this->r = unpack_rec(this, value.ptr + poly_len);
+               if (this->r == NULL)
+               {
+                       return FALSE;
+               }
+
+               DBG3(DBG_LIB, "   i  u[i]  r[i]");
+               for (i = 0; i < n; i++)
+               {
+                       DBG3(DBG_LIB, "%4d %5u %5u", i, this->u[i], this->r[i]);
+               }
+
+               /* compute v' = NTT_inv( u * NTT(s) ) */
+               v = multiply_ntt_inv_poly(this, this->u);
+
+               rec = newhope_reconciliation_create(n, q);
+               this->shared_secret = rec->reconcile(rec, v, this->r);
+               free(v);
+               rec->destroy(rec);
+
+               DBG4(DBG_LIB, "key: %B", &this->shared_secret);
+
+               return TRUE;
+       }
+}
+
+METHOD(diffie_hellman_t, get_dh_group, diffie_hellman_group_t,
+       private_newhope_ke_t *this)
+{
+       return NH_128_BIT;
+}
+
+METHOD(diffie_hellman_t, destroy, void,
+       private_newhope_ke_t *this)
+{
+       chunk_clear(&this->shared_secret);
+       memwipe(this->s, this->params->n * sizeof(uint32_t));
+       free(this->s);
+       free(this->u);
+       free(this->r);
+       free(this);
+}
+
+/*
+ * Described in header.
+ */
+newhope_ke_t *newhope_ke_create(diffie_hellman_group_t group, chunk_t g, chunk_t p)
+{
+       private_newhope_ke_t *this;
+
+       INIT(this,
+               .public = {
+                       .dh = {
+                               .get_shared_secret = _get_shared_secret,
+                               .set_other_public_value = _set_other_public_value,
+                               .get_my_public_value = _get_my_public_value,
+                               .get_dh_group = _get_dh_group,
+                               .destroy = _destroy,
+                       },
+               },
+               .params = &ntt_fft_12289_1024,
+
+       );
+
+       return &this->public;
+}
diff --git a/src/libstrongswan/plugins/newhope/newhope_ke.h b/src/libstrongswan/plugins/newhope/newhope_ke.h
new file mode 100644 (file)
index 0000000..677d04f
--- /dev/null
@@ -0,0 +1,50 @@
+/*
+ * Copyright (C) 2016 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 newhope_ke newhope_ke
+ * @{ @ingroup newhope_p
+ */
+
+#ifndef NEWHOPE_KE_H_
+#define NEWHOPE_KE_H_
+
+typedef struct newhope_ke_t newhope_ke_t;
+
+#include <library.h>
+
+/**
+ * Implementation of a key exchange algorithm using the New Hope algorithm
+ */
+struct newhope_ke_t {
+
+       /**
+        * Implements diffie_hellman_t interface.
+        */
+       diffie_hellman_t dh;
+};
+
+/**
+ * Creates a new newhope_ke_t object.
+ *
+ * @param group                        New Hope DH group number
+ * @param g                            not used
+ * @param p                            not used
+ * @return                             newhope_ke_t object, NULL if not supported
+ */
+newhope_ke_t *newhope_ke_create(diffie_hellman_group_t group, chunk_t g, chunk_t p);
+
+#endif /** NEWHOPE_KE_H_ @}*/
+
diff --git a/src/libstrongswan/plugins/newhope/newhope_noise.c b/src/libstrongswan/plugins/newhope/newhope_noise.c
new file mode 100644 (file)
index 0000000..5ba9f94
--- /dev/null
@@ -0,0 +1,160 @@
+/*
+ * Copyright (C) 2016 Andreas Steffen
+ * HSR Hochschule fuer Technik Rapperswil
+ *
+ * Based on public domain code by Erdem Alkim, Léo Ducas, Thomas Pöppelmann,
+ * and Peter Schwabe.
+ *
+ * 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 "newhope_noise.h"
+
+typedef struct private_newhope_noise_t private_newhope_noise_t;
+
+static const int seed_len =   32;  /* 256 bits */
+static const int nonce_len =  12;  /*  96 bits */
+
+/**
+ * Private data of an newhope_noise_t object.
+ */
+struct private_newhope_noise_t {
+
+       /**
+        * Public newhope_noise_t interface.
+        */
+       newhope_noise_t public;
+
+       /**
+        * 256 bit seed and 96 bit nonce (44 bytes)
+        */
+       chunk_t seed;
+
+       /**
+        * ChaCha20 stream
+        */
+       xof_t *xof;
+
+};
+
+METHOD(newhope_noise_t, get_uniform_bytes, uint8_t*,
+       private_newhope_noise_t *this, uint8_t nonce, uint16_t n)
+{
+       uint8_t *bytes;
+
+       this->seed.ptr[seed_len] = nonce;
+       if (!this->xof->set_seed(this->xof, this->seed))
+       {
+               DBG1(DBG_LIB, "could not set seed of CHACHA20 XOF");
+               return NULL;
+       }
+
+       /* allocate dynamic memory for the noise polynomial */
+       bytes = (uint8_t*)malloc(n);
+
+       if (!this->xof->get_bytes(this->xof, n, bytes))
+       {
+               DBG1(DBG_LIB, "could not get bytes from SHAKE128 XOF");
+               free(bytes);
+               return NULL;
+       }
+
+       return bytes;
+}
+
+METHOD(newhope_noise_t, get_binomial_words, uint32_t*,
+       private_newhope_noise_t *this, uint8_t nonce, uint16_t n, uint16_t q)
+{
+       uint32_t *np, a, b, d, t;
+       uint8_t x[4];
+       int i = 0, j;
+
+       this->seed.ptr[seed_len] = nonce;
+       if (!this->xof->set_seed(this->xof, this->seed))
+       {
+               DBG1(DBG_LIB, "could not set seed of CHACHA20 XOF");
+               return NULL;
+       }
+
+       /* allocate dynamic memory for the noise polynomial */
+       np = (uint32_t*)malloc(n * sizeof(uint32_t));
+
+       for (i = 0; i < n; i++)
+       {
+               if (!this->xof->get_bytes(this->xof, sizeof(x), x))
+               {
+                       DBG1(DBG_LIB, "could not get bytes from SHAKE128 XOF");
+                       free(np);
+                       return NULL;
+               }
+
+               /* Treat x as a 32 bit unsigned little endian integer */
+               t = uletoh32(x);
+
+               /* Compute Psi_16 distribution */
+               d = 0;
+               for (j = 0; j < 8; j++)
+               {
+                       d += (t >> j) & 0x01010101;
+               }
+               a = ((d >>  8) & 0xff) + (d & 0xff);
+               b = ((d >> 16) & 0xff) + (d >> 24);
+               np[i] = (a >= b) ? a - b : a + q - b;
+       }
+
+       return np;
+}
+
+METHOD(newhope_noise_t, destroy, void,
+       private_newhope_noise_t *this)
+{
+       this->xof->destroy(this->xof);
+       chunk_free(&this->seed);
+       free(this);
+}
+
+/*
+ * Described in header.
+ */
+newhope_noise_t *newhope_noise_create(chunk_t seed)
+{
+       private_newhope_noise_t *this;
+       xof_t *xof;
+
+       if (seed.len != seed_len)
+       {
+               DBG1(DBG_LIB, "seed for ChaCha20 stream must be 256 bits");
+               return NULL;
+       }
+
+       xof = lib->crypto->create_xof(lib->crypto, XOF_CHACHA20);
+       if (!xof)
+       {
+               DBG1(DBG_LIB, "could not instantiate ChaCha20 stream");
+               return NULL;
+       }       
+
+       INIT(this,
+               .public = {
+                       .get_uniform_bytes = _get_uniform_bytes,
+                       .get_binomial_words = _get_binomial_words,
+                       .destroy = _destroy,
+               },
+               .xof = xof,
+               .seed = chunk_alloc(seed_len + nonce_len),
+       );
+
+       /* initialize seed for ChaCha 20 stream */
+       memcpy(this->seed.ptr, seed.ptr, seed_len);
+       memset(this->seed.ptr + seed_len, 0x00, nonce_len);
+
+       return &this->public;
+}
diff --git a/src/libstrongswan/plugins/newhope/newhope_noise.h b/src/libstrongswan/plugins/newhope/newhope_noise.h
new file mode 100644 (file)
index 0000000..d7819d3
--- /dev/null
@@ -0,0 +1,70 @@
+/*
+ * Copyright (C) 2016 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 newhope_noise newhope_noise
+ * @{ @ingroup newhope_p
+ */
+
+#ifndef NEWHOPE_NOISE_H_
+#define NEWHOPE_NOISE_H_
+
+typedef struct newhope_noise_t newhope_noise_t;
+
+#include <library.h>
+
+/**
+ * Generate pseudo random noise using a ChaCha20 stream
+ * initialized with a 256 bit seed and an 8 bit nonce
+ */
+struct newhope_noise_t {
+
+       /**
+        * Return n pseudo random bytes with a uniform distribution
+        *
+        * @param nonce         Nonce determining the pseudo random stream
+        * @param n                     Number of pseudo random bytes to be returned
+        * @return                      Return array with n peudo random bytes
+        */
+       uint8_t* (*get_uniform_bytes)(newhope_noise_t *this, uint8_t nonce,
+                                                                 uint16_t n);
+
+       /**
+        * Return n pseudo random 32-bit words with a Psi16 binomial distribution
+        *
+        * @param nonce         Nonce determining the pseudo random stream
+        * @param n                     Number of pseudo random Psi16 words to be returned
+        * @param q                     Prime number q determining the ring
+        * @return                      Return array with n pseudo random 32 bit words
+        */
+       uint32_t* (*get_binomial_words)(newhope_noise_t *this, uint8_t nonce,
+                                                                       uint16_t n, uint16_t q);
+
+       /**
+        * Destroy a newhope_noise_t object
+        */
+       void (*destroy)(newhope_noise_t *this);
+};
+
+/**
+ * Creates a new newhope_noise_t object.
+ *
+ * @param seed                 256 bit seed (32 byte chunk)
+ * @return                             newhope_noise_t object, NULL if not supported
+ */
+newhope_noise_t *newhope_noise_create(chunk_t seed);
+
+#endif /** NEWHOPE_NOISE_H_ @}*/
+
diff --git a/src/libstrongswan/plugins/newhope/newhope_plugin.c b/src/libstrongswan/plugins/newhope/newhope_plugin.c
new file mode 100644 (file)
index 0000000..444e61a
--- /dev/null
@@ -0,0 +1,78 @@
+/*
+ * Copyright (C) 2016 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 "newhope_plugin.h"
+#include "newhope_ke.h"
+
+#include <library.h>
+
+typedef struct private_newhope_plugin_t private_newhope_plugin_t;
+
+/**
+ * private data of newhope_plugin
+ */
+struct private_newhope_plugin_t {
+
+       /**
+        * public functions
+        */
+       newhope_plugin_t public;
+};
+
+METHOD(plugin_t, get_name, char*,
+       private_newhope_plugin_t *this)
+{
+       return "newhope";
+}
+
+METHOD(plugin_t, get_features, int,
+       private_newhope_plugin_t *this, plugin_feature_t *features[])
+{
+       static plugin_feature_t f[] = {
+               PLUGIN_REGISTER(DH, newhope_ke_create),
+                       PLUGIN_PROVIDE(DH, NH_128_BIT),
+                               PLUGIN_DEPENDS(XOF, XOF_SHAKE_128),
+                               PLUGIN_DEPENDS(XOF, XOF_CHACHA20),
+       };
+       *features = f;
+
+       return countof(f);
+}
+
+METHOD(plugin_t, destroy, void,
+       private_newhope_plugin_t *this)
+{
+       free(this);
+}
+
+/*
+ * see header file
+ */
+plugin_t *newhope_plugin_create()
+{
+       private_newhope_plugin_t *this;
+
+       INIT(this,
+               .public = {
+                       .plugin = {
+                               .get_name = _get_name,
+                               .get_features = _get_features,
+                               .destroy = _destroy,
+                       },
+               },
+       );
+
+       return &this->public.plugin;
+}
diff --git a/src/libstrongswan/plugins/newhope/newhope_plugin.h b/src/libstrongswan/plugins/newhope/newhope_plugin.h
new file mode 100644 (file)
index 0000000..96e3a19
--- /dev/null
@@ -0,0 +1,42 @@
+/*
+ * Copyright (C) 2016 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 newhope_p ntru
+ * @ingroup plugins
+ *
+ * @defgroup newhope_plugin newhope_plugin
+ * @{ @ingroup newhope_p
+ */
+
+#ifndef NEWHOPE_PLUGIN_H_
+#define NEWHOPE_PLUGIN_H_
+
+#include <plugins/plugin.h>
+
+typedef struct newhope_plugin_t newhope_plugin_t;
+
+/**
+ * Plugin implementing New Hope-based key exchange
+ */
+struct newhope_plugin_t {
+
+       /**
+        * implements plugin interface
+        */
+       plugin_t plugin;
+};
+
+#endif /** NEWHOPE_PLUGIN_H_ @}*/
diff --git a/src/libstrongswan/plugins/newhope/newhope_reconciliation.c b/src/libstrongswan/plugins/newhope/newhope_reconciliation.c
new file mode 100644 (file)
index 0000000..4aed60e
--- /dev/null
@@ -0,0 +1,217 @@
+/*
+ * Copyright (C) 2016 Andreas Steffen
+ * HSR Hochschule fuer Technik Rapperswil
+ *
+ * Based on public domain code by Erdem Alkim, Léo Ducas, Thomas Pöppelmann,
+ * and Peter Schwabe.
+ *
+ * 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 "newhope_reconciliation.h"
+
+typedef struct private_newhope_reconciliation_t private_newhope_reconciliation_t;
+
+/**
+ * Private data of an newhope_reconciliation_t object.
+ */
+struct private_newhope_reconciliation_t {
+
+       /**
+        * Public newhope_reconciliation_t interface.
+        */
+       newhope_reconciliation_t public;
+
+       /**
+        * Array sizes
+        */
+       int n, n4;
+
+       /**
+        * Multiples of modulus q
+        */
+       int32_t q, q2, q4, q8, q16;
+};
+
+
+static inline int32_t rec_abs(int32_t v)
+{
+  int32_t mask = v >> 31;
+
+  return (v ^ mask) - mask;
+}
+
+/**
+ * Auxiliary function used by help_reconcile() method
+ */
+static int32_t rec_f(private_newhope_reconciliation_t *this,
+                                        int32_t v, uint8_t r, int32_t *v0, int32_t *v1)
+{
+       int32_t x, xit, t, b;
+
+       x = 8 * v + 2 * r;
+
+       /* compute t = x/q */
+       b = x * 2730;
+       t = b >> 25;
+       b = x - t * this->q;
+       b = this->q - 1 - b;
+       b >>= 31;
+       t -= b;
+
+       r = t & 0x01;
+       xit = (t >> 1);
+       *v0 = xit + r ; /* v0 = round(x/(2q)) */
+
+       t -= 1;
+       r = t & 0x01;
+       *v1 = ( t>> 1) + r;
+
+       return rec_abs(x - (*v0) * this->q2);
+}
+
+/**
+ * Auxiliary function used by reconcile() method
+ */
+static int32_t rec_g(private_newhope_reconciliation_t *this, int32_t x)
+{
+       int32_t t, r, b;
+
+       /*  t = x/(4*q) */
+       b = x * 2730;
+       t = b >> 27;
+       b = x - t * this->q4;
+       b = this->q4 - 1 - b;
+       b >>= 31;
+       t -= b;
+
+       r = t & 0x01;
+       t = (t >> 1) + r; /* t = round(x/(8q)) */
+       t *= this->q8;
+
+  return abs(t - x);
+}
+
+METHOD(newhope_reconciliation_t, help_reconcile, uint8_t*,
+       private_newhope_reconciliation_t *this, uint32_t *v, uint8_t *rbits)
+{
+       int32_t v0[4], v1[4], v_tmp[4], k;
+       int i, i0, i1, i2, i3, j;
+       uint8_t *r, rbit;
+
+       /* allocate output vector */
+       r = (uint8_t*)malloc(this->n);
+
+       for (i = 0; i < this->n4/8; i++)
+       {
+               for (j = 0; j < 8; j++)
+               {
+                       i0 = 8*i  + j;
+                       i1 = i0 + this->n4;
+                       i2 = i1 + this->n4;
+                       i3 = i2 + this->n4;
+
+                       /* iterate through all 256 random bits */
+                       rbit = (rbits[i] >> j) & 0x01;
+
+                       k  = rec_f(this, v[i0], rbit, &v0[0], &v1[0]);
+                       k += rec_f(this, v[i1], rbit, &v0[1], &v1[1]);
+                       k += rec_f(this, v[i2], rbit, &v0[2], &v1[2]);
+                       k += rec_f(this, v[i3], rbit, &v0[3], &v1[3]);
+
+                       k = (this->q2 - 1 - k) >> 31;
+
+                       v_tmp[0] = ((~k) & v0[0]) ^ (k & v1[0]);
+                       v_tmp[1] = ((~k) & v0[1]) ^ (k & v1[1]);
+                       v_tmp[2] = ((~k) & v0[2]) ^ (k & v1[2]);
+                       v_tmp[3] = ((~k) & v0[3]) ^ (k & v1[3]);
+
+                       r[i0] = (v_tmp[0] -     v_tmp[3]) & 0x03;
+                       r[i1] = (v_tmp[1] -     v_tmp[3]) & 0x03;
+                       r[i2] = (v_tmp[2] -     v_tmp[3]) & 0x03;
+                       r[i3] = (v_tmp[3] - k + v_tmp[3]) & 0x03;
+               }
+       }
+
+       return r;
+}
+
+METHOD(newhope_reconciliation_t, reconcile, chunk_t,
+       private_newhope_reconciliation_t *this, uint32_t *v, uint8_t *r)
+{
+       size_t key_len;
+       uint8_t *key;
+       int32_t tmp[4], t;
+       int i, i0, i1, i2, i3, j;
+
+       key_len = this->n4 / 8;
+       key = (uint8_t*)malloc(key_len);
+       memset(key, 0x00, key_len);
+
+       for (i = 0; i < key_len; i++)
+       {
+               for (j = 0; j < 8; j++)
+               {
+                       i0 = 8*i + j;
+                       i1 = i0 + this->n4;
+                       i2 = i1 + this->n4;
+                       i3 = i2 + this->n4;
+
+                       tmp[0] = this->q16 + 8 * (int32_t)v[i0] - 
+                                        this->q  * (2*r[i0] + r[i3]);
+                       tmp[1] = this->q16 + 8 * (int32_t)v[i1] -
+                                        this->q  * (2*r[i1] + r[i3]);
+                       tmp[2] = this->q16 + 8 * (int32_t)v[i2] -
+                                        this->q  * (2*r[i2] + r[i3]);
+                       tmp[3] = this->q16 + 8 * (int32_t)v[i3] -
+                                        this->q *  (          r[i3]);
+
+                       t = rec_g(this, tmp[0]) + rec_g(this, tmp[1]) +
+                               rec_g(this, tmp[2]) + rec_g(this, tmp[3]) - this->q8;
+
+                       key[i] |= ((t >> 31) & 0x01) << j;
+               }
+       }
+
+       return chunk_create(key, key_len);
+}
+
+METHOD(newhope_reconciliation_t, destroy, void,
+       private_newhope_reconciliation_t *this)
+{
+       free(this);
+}
+
+/*
+ * Described in header.
+ */
+newhope_reconciliation_t *newhope_reconciliation_create(int n, int32_t q)
+{
+       private_newhope_reconciliation_t *this;
+
+       INIT(this,
+               .public = {
+                       .help_reconcile = _help_reconcile,
+                       .reconcile = _reconcile,
+                       .destroy = _destroy,
+               },
+               .n   =  n,
+               .n4  =  n / 4,
+               .q   =      q,
+               .q2  =  2 * q,
+               .q4  =  4 * q,
+               .q8  =  8 * q,
+               .q16 = 16 * q,
+       );
+
+       return &this->public;
+}
diff --git a/src/libstrongswan/plugins/newhope/newhope_reconciliation.h b/src/libstrongswan/plugins/newhope/newhope_reconciliation.h
new file mode 100644 (file)
index 0000000..7cbf0d2
--- /dev/null
@@ -0,0 +1,70 @@
+/*
+ * Copyright (C) 2016 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 newhope_reconciliation newhope_reconciliation
+ * @{ @ingroup newhope_p
+ */
+
+#ifndef NEWHOPE_RECONCILIATION_H_
+#define NEWHOPE_RECONCILIATION_H_
+
+typedef struct newhope_reconciliation_t newhope_reconciliation_t;
+
+#include <library.h>
+
+/**
+ * Class assisting the error reconciliation
+ * resulting in a key exchange error rate < 2^(-60)
+ */
+struct newhope_reconciliation_t {
+
+       /**
+        * Generate reconciliation polynomial
+        *
+        * @param v                     polynomial v
+        * @param rbits         pseudo random bit array 
+        * @return                      return array with reconciliation polynomial
+        */
+       uint8_t* (*help_reconcile)(newhope_reconciliation_t *this,
+                                                          uint32_t *v, uint8_t *rbits);
+
+       /**
+        * Use reconciliation polynomial r to derive shared secret
+        *
+        * @param v                     polynomial v or v'
+        * @param r                     reconciliation polynomial r
+        * @return                      Return shared secret
+        */
+       chunk_t (*reconcile)(newhope_reconciliation_t *this,
+                                               uint32_t *v, uint8_t *r);
+
+       /**
+        * Destroy a newhope_reconciliation_t object
+        */
+       void (*destroy)(newhope_reconciliation_t *this);
+};
+
+/**
+ * Creates a new newhope_reconciliation_t object.
+ *
+ * @param n                            array size
+ * @param q                            prime modulus
+ * @return                             newhope_reconciliation_t object
+ */
+newhope_reconciliation_t *newhope_reconciliation_create(int n, int32_t q);
+
+#endif /** NEWHOPE_RECONCILIATION_H_ @}*/
+