chiark - git - mdw - secnet/blob - x25519.c

   1 /*
   2  * x25519.c: Bernstein's X25519 key-exchange function
   3  */
   4 /*
   5  * This file is Free Software.  It has been modified to as part of its
   6  * incorporation into secnet.
   7  *
   8  * Copyright 2017 Mark Wooding
   9  *
  10  * You may redistribute this file and/or modify it under the terms of
  11  * the permissive licence shown below.
  12  *
  13  * You may redistribute secnet as a whole and/or modify it under the
  14  * terms of the GNU General Public License as published by the Free
  15  * Software Foundation; either version 3, or (at your option) any
  16  * later version.
  17  *
  18  * This program is distributed in the hope that it will be useful,
  19  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  20  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  21  * GNU General Public License for more details.
  22  *
  23  * You should have received a copy of the GNU General Public License
  24  * along with this program; if not, see
  25  * https://www.gnu.org/licenses/gpl.html.
  26  */
  27 /*
  28  * Imported from Catacomb, and modified for Secnet (2017-04-30):
  29  *
  30  *   * Use `fake-mLib-bits.h' in place of the real <mLib/bits.h>.
  31  *
  32  *   * Remove the test rig code: a replacement is in a separate source file.
  33  *
  34  *   * Ignore the top bit of the input public key: in Secnet, conformance
  35  *     with RFC7748 is more valuable than flexibility.
  36  *
  37  *   * Strip out the key-management definitions.
  38  *
  39  * The file's original comment headers are preserved below.
  40  */
  41 /* -*-c-*-
  42  *
  43  * The X25519 key-agreement algorithm
  44  *
  45  * (c) 2017 Straylight/Edgeware
  46  */
  47
  48 /*----- Licensing notice --------------------------------------------------*
  49  *
  50  * This file is part of Catacomb.
  51  *
  52  * Catacomb is free software; you can redistribute it and/or modify
  53  * it under the terms of the GNU Library General Public License as
  54  * published by the Free Software Foundation; either version 2 of the
  55  * License, or (at your option) any later version.
  56  *
  57  * Catacomb is distributed in the hope that it will be useful,
  58  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  59  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  60  * GNU Library General Public License for more details.
  61  *
  62  * You should have received a copy of the GNU Library General Public
  63  * License along with Catacomb; if not, write to the Free
  64  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  65  * MA 02111-1307, USA.
  66  */
  67
  68 /*----- Header files ------------------------------------------------------*/
  69
  70 #include "fake-mLib-bits.h"
  71
  72 #include "montladder.h"
  73 #include "f25519.h"
  74 #include "x25519.h"
  75
  76 /*----- Important constants -----------------------------------------------*/
  77
  78 const octet x25519_base[32] = { 9, 0, /* ... */ };
  79
  80 #define A0 121665
  81
  82 /*----- Main code ---------------------------------------------------------*/
  83
  84 /* --- @x25519@ --- *
  85  *
  86  * Arguments:   @octet zz[X25519_OUTSZ]@ = where to put the result
  87  *              @const octet k[X25519_KEYSZ]@ = pointer to private key
  88  *              @const octet qx[X25519_PUBSZ]@ = pointer to public value
  89  *
  90  * Returns:     ---
  91  *
  92  * Use:         Calculates X25519 of @k@ and @qx@.
  93  *
  94  *              Note that there is disagreement over whether the most
  95  *              significant bit of @qx@ (i.e., the value @qx[31]&0x80@)
  96  *              should be ignored or counted towards the represented value.
  97  *              Historically implementations respected the bit; later
  98  *              convention seems to be to ignore it.  This implementation
  99  *              honours the bit: a caller who wants to ignore the bit can
 100  *              easily clear it, while caller who wants to respect it has a
 101  *              difficult job if this function ignores it.
 102  */
 103
 104 void x25519(octet zz[X25519_OUTSZ],
 105             const octet k[X25519_KEYSZ],
 106             const octet qx[X25519_PUBSZ])
 107 {
 108   uint32 kw[8];
 109   uint8_t b[X25519_PUBSZ];
 110   f25519 x1;
 111
 112   /* Load and clamp the key.  The low bits are cleared to kill the small
 113    * subgroups on the curve and its twist, and a high bit is set to guard
 114    * against careless implementations, though this isn't one of those.
 115    */
 116   kw[0] = LOAD32_L(k +  0); kw[1] = LOAD32_L(k +  4);
 117   kw[2] = LOAD32_L(k +  8); kw[3] = LOAD32_L(k + 12);
 118   kw[4] = LOAD32_L(k + 16); kw[5] = LOAD32_L(k + 20);
 119   kw[6] = LOAD32_L(k + 24); kw[7] = LOAD32_L(k + 28);
 120   kw[0] &= 0xfffffff8; kw[7] = (kw[7]&0x3fffffff) | 0x40000000;
 121
 122   /* Copy the input point and clamp the top bit. */
 123   memcpy(b, qx, sizeof(b)); b[31] &= 0x7f;
 124   f25519_load(&x1, b);
 125
 126   /* And run the ladder. */
 127 #define MULA0(z, x) do { f25519_mulconst((z), (x), A0); } while (0)
 128   MONT_LADDER(f25519, MULA0, kw, 8, 32, &x1, &x1);
 129 #undef MULA0
 130   f25519_store(zz, &x1);
 131 }
 132
 133 /*----- Test rig ----------------------------------------------------------*/
 134
 135 #ifdef TEST_RIG
 136
 137 #include <stdio.h>
 138 #include <string.h>
 139
 140 #include <mLib/report.h>
 141 #include <mLib/testrig.h>
 142
 143 static int vrf_x25519(dstr dv[])
 144 {
 145   dstr dz = DSTR_INIT;
 146   int ok = 1;
 147
 148   if (dv[0].len != 32) die(1, "bad key length");
 149   if (dv[1].len != 32) die(1, "bad public length");
 150   if (dv[2].len != 32) die(1, "bad result length");
 151
 152   dstr_ensure(&dz, 32); dz.len = 32;
 153   x25519((octet *)dz.buf,
 154          (const octet *)dv[0].buf,
 155          (const octet *)dv[1].buf);
 156   if (memcmp(dz.buf, dv[2].buf, 32) != 0) {
 157     ok = 0;
 158     fprintf(stderr, "failed!");
 159     fprintf(stderr, "\n\t   k = "); type_hex.dump(&dv[0], stderr);
 160     fprintf(stderr, "\n\t   p = "); type_hex.dump(&dv[1], stderr);
 161     fprintf(stderr, "\n\twant = "); type_hex.dump(&dv[2], stderr);
 162     fprintf(stderr, "\n\tcalc = "); type_hex.dump(&dz, stderr);
 163     fprintf(stderr, "\n");
 164   }
 165
 166   dstr_destroy(&dz);
 167   return (ok);
 168 }
 169
 170 static int vrf_mct(dstr dv[])
 171 {
 172   octet b0[32], b1[32], *k = b0, *x = b1, *t;
 173   unsigned long i, niter;
 174   dstr d = DSTR_INIT;
 175   int ok = 1;
 176
 177   if (dv[0].len != sizeof(b0)) { fprintf(stderr, "k len\n"); exit(2); }
 178   if (dv[1].len != sizeof(b1)) { fprintf(stderr, "x len\n"); exit(2); }
 179   if (dv[3].len != sizeof(b0)) { fprintf(stderr, "result len\n"); exit(2); }
 180   memcpy(b0, dv[0].buf, sizeof(b0));
 181   memcpy(b1, dv[1].buf, sizeof(b1));
 182   niter = *(unsigned long *)dv[2].buf;
 183   dstr_ensure(&d, 32); d.len = 32; t = (octet *)d.buf;
 184
 185   for (i = 0; i < niter; i++) {
 186     x[31] &= 0x7f;
 187     x25519(x, k, x);
 188     t = x; x = k; k = t;
 189   }
 190   memcpy(d.buf, k, d.len);
 191
 192   if (memcmp(d.buf, dv[3].buf, d.len) != 0) {
 193     ok = 0;
 194     fprintf(stderr, "failed...");
 195     fprintf(stderr, "\n\tinitial k = "); type_hex.dump(&dv[0], stderr);
 196     fprintf(stderr, "\n\tinitial x = "); type_hex.dump(&dv[1], stderr);
 197     fprintf(stderr, "\n\titerations = %lu", niter);
 198     fprintf(stderr, "\n\texpected = "); type_hex.dump(&dv[3], stderr);
 199     fprintf(stderr, "\n\tcalculated = "); type_hex.dump(&d, stderr);
 200     fputc('\n', stderr);
 201   }
 202
 203   dstr_destroy(&d);
 204   return (ok);
 205 }
 206
 207 static test_chunk tests[] = {
 208   { "x25519", vrf_x25519, { &type_hex, &type_hex, &type_hex } },
 209   { "x25519-mct", vrf_mct,
 210     { &type_hex, &type_hex, &type_ulong, &type_hex } },
 211   { 0, 0, { 0 } }
 212 };
 213
 214 int main(int argc, char *argv[])
 215 {
 216   test_run(argc, argv, tests, SRCDIR "/t/x25519");
 217   return (0);
 218 }
 219
 220 #endif
 221
 222 /*----- That's all, folks -------------------------------------------------*/