src/libstrongswan/plugins/newhope/newhope_reconciliation.c

   1 /*
   2  * Copyright (C) 2016 Andreas Steffen
   3  *
   4  * Based on public domain code by Erdem Alkim, Léo Ducas, Thomas Pöppelmann,
   5  * and Peter Schwabe.
   6  *
   7  * Copyright (C) secunet Security Networks AG
   8  *
   9  * This program is free software; you can redistribute it and/or modify it
  10  * under the terms of the GNU General Public License as published by the
  11  * Free Software Foundation; either version 2 of the License, or (at your
  12  * option) any later version.  See <http://www.fsf.org/copyleft/gpl.txt>.
  13  *
  14  * This program is distributed in the hope that it will be useful, but
  15  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  16  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  17  * for more details.
  18  *
  19  */
  20
  21 #include "newhope_reconciliation.h"
  22
  23 typedef struct private_newhope_reconciliation_t private_newhope_reconciliation_t;
  24
  25 /**
  26  * Private data of an newhope_reconciliation_t object.
  27  */
  28 struct private_newhope_reconciliation_t {
  29
  30         /**
  31          * Public newhope_reconciliation_t interface.
  32          */
  33         newhope_reconciliation_t public;
  34
  35         /**
  36          * Array sizes
  37          */
  38         int n, n4;
  39
  40         /**
  41          * Multiples of modulus q
  42          */
  43         int32_t q, q2, q4, q8, q16;
  44 };
  45
  46
  47 static inline int32_t rec_abs(int32_t v)
  48 {
  49   int32_t mask = v >> 31;
  50
  51   return (v ^ mask) - mask;
  52 }
  53
  54 /**
  55  * Auxiliary function used by help_reconcile() method
  56  */
  57 static int32_t rec_f(private_newhope_reconciliation_t *this,
  58                                          int32_t v, uint8_t r, int32_t *v0, int32_t *v1)
  59 {
  60         int32_t x, xit, t, b;
  61
  62         x = 8 * v + 2 * r;
  63
  64         /* compute t = x/q */
  65         b = x * 2730;
  66         t = b >> 25;
  67         b = x - t * this->q;
  68         b = this->q - 1 - b;
  69         b >>= 31;
  70         t -= b;
  71
  72         r = t & 0x01;
  73         xit = (t >> 1);
  74         *v0 = xit + r ; /* v0 = round(x/(2q)) */
  75
  76         t -= 1;
  77         r = t & 0x01;
  78         *v1 = ( t>> 1) + r;
  79
  80         return rec_abs(x - (*v0) * this->q2);
  81 }
  82
  83 /**
  84  * Auxiliary function used by reconcile() method
  85  */
  86 static int32_t rec_g(private_newhope_reconciliation_t *this, int32_t x)
  87 {
  88         int32_t t, r, b;
  89
  90         /*  t = x/(4*q) */
  91         b = x * 2730;
  92         t = b >> 27;
  93         b = x - t * this->q4;
  94         b = this->q4 - 1 - b;
  95         b >>= 31;
  96         t -= b;
  97
  98         r = t & 0x01;
  99         t = (t >> 1) + r; /* t = round(x/(8q)) */
 100         t *= this->q8;
 101
 102   return abs(t - x);
 103 }
 104
 105 METHOD(newhope_reconciliation_t, help_reconcile, uint8_t*,
 106         private_newhope_reconciliation_t *this, uint32_t *v, uint8_t *rbits)
 107 {
 108         int32_t v0[4], v1[4], v_tmp[4], k;
 109         int i, i0, i1, i2, i3, j;
 110         uint8_t *r, rbit;
 111
 112         /* allocate output vector */
 113         r = (uint8_t*)malloc(this->n);
 114
 115         for (i = 0; i < this->n4/8; i++)
 116         {
 117                 for (j = 0; j < 8; j++)
 118                 {
 119                         i0 = 8*i  + j;
 120                         i1 = i0 + this->n4;
 121                         i2 = i1 + this->n4;
 122                         i3 = i2 + this->n4;
 123
 124                         /* iterate through all 256 random bits */
 125                         rbit = (rbits[i] >> j) & 0x01;
 126
 127                         k  = rec_f(this, v[i0], rbit, &v0[0], &v1[0]);
 128                         k += rec_f(this, v[i1], rbit, &v0[1], &v1[1]);
 129                         k += rec_f(this, v[i2], rbit, &v0[2], &v1[2]);
 130                         k += rec_f(this, v[i3], rbit, &v0[3], &v1[3]);
 131
 132                         k = (this->q2 - 1 - k) >> 31;
 133
 134                         v_tmp[0] = ((~k) & v0[0]) ^ (k & v1[0]);
 135                         v_tmp[1] = ((~k) & v0[1]) ^ (k & v1[1]);
 136                         v_tmp[2] = ((~k) & v0[2]) ^ (k & v1[2]);
 137                         v_tmp[3] = ((~k) & v0[3]) ^ (k & v1[3]);
 138
 139                         r[i0] = (v_tmp[0] -     v_tmp[3]) & 0x03;
 140                         r[i1] = (v_tmp[1] -     v_tmp[3]) & 0x03;
 141                         r[i2] = (v_tmp[2] -     v_tmp[3]) & 0x03;
 142                         r[i3] = (v_tmp[3] - k + v_tmp[3]) & 0x03;
 143                 }
 144         }
 145
 146         return r;
 147 }
 148
 149 METHOD(newhope_reconciliation_t, reconcile, chunk_t,
 150         private_newhope_reconciliation_t *this, uint32_t *v, uint8_t *r)
 151 {
 152         size_t key_len;
 153         uint8_t *key;
 154         int32_t tmp[4], t;
 155         int i, i0, i1, i2, i3, j;
 156
 157         key_len = this->n4 / 8;
 158         key = (uint8_t*)malloc(key_len);
 159         memset(key, 0x00, key_len);
 160
 161         for (i = 0; i < key_len; i++)
 162         {
 163                 for (j = 0; j < 8; j++)
 164                 {
 165                         i0 = 8*i + j;
 166                         i1 = i0 + this->n4;
 167                         i2 = i1 + this->n4;
 168                         i3 = i2 + this->n4;
 169
 170                         tmp[0] = this->q16 + 8 * (int32_t)v[i0] -
 171                                          this->q  * (2*r[i0] + r[i3]);
 172                         tmp[1] = this->q16 + 8 * (int32_t)v[i1] -
 173                                          this->q  * (2*r[i1] + r[i3]);
 174                         tmp[2] = this->q16 + 8 * (int32_t)v[i2] -
 175                                          this->q  * (2*r[i2] + r[i3]);
 176                         tmp[3] = this->q16 + 8 * (int32_t)v[i3] -
 177                                          this->q *  (          r[i3]);
 178
 179                         t = rec_g(this, tmp[0]) + rec_g(this, tmp[1]) +
 180                                 rec_g(this, tmp[2]) + rec_g(this, tmp[3]) - this->q8;
 181
 182                         key[i] |= ((t >> 31) & 0x01) << j;
 183                 }
 184         }
 185
 186         return chunk_create(key, key_len);
 187 }
 188
 189 METHOD(newhope_reconciliation_t, destroy, void,
 190         private_newhope_reconciliation_t *this)
 191 {
 192         free(this);
 193 }
 194
 195 /*
 196  * Described in header.
 197  */
 198 newhope_reconciliation_t *newhope_reconciliation_create(int n, int32_t q)
 199 {
 200         private_newhope_reconciliation_t *this;
 201
 202         INIT(this,
 203                 .public = {
 204                         .help_reconcile = _help_reconcile,
 205                         .reconcile = _reconcile,
 206                         .destroy = _destroy,
 207                 },
 208                 .n   =  n,
 209                 .n4  =  n / 4,
 210                 .q   =      q,
 211                 .q2  =  2 * q,
 212                 .q4  =  4 * q,
 213                 .q8  =  8 * q,
 214                 .q16 = 16 * q,
 215         );
 216
 217         return &this->public;
 218 }