From 643eb1bbf91769f4f929173dd8452a94c36f1685 Mon Sep 17 00:00:00 2001 From: Mark Wooding Date: Wed, 26 Apr 2017 11:55:08 +0100 Subject: [PATCH] pub/, progs/: Add support for X448 key exchange, defined in RFC7748. --- progs/catcrypt.1 | 12 ++++ progs/cc-kem.c | 67 ++++++++++++++++++++ progs/key.1 | 8 +++ progs/key.c | 20 ++++++ progs/perftest.c | 20 ++++++ pub/Makefile.am | 6 ++ pub/t/x448 | 41 ++++++++++++ pub/x448.c | 182 +++++++++++++++++++++++++++++++++++++++++++++++++++++ pub/x448.h | 95 ++++++++++++++++++++++++++++ utils/qfarith-test | 1 + 10 files changed, 452 insertions(+) create mode 100644 pub/t/x448 create mode 100644 pub/x448.c create mode 100644 pub/x448.h diff --git a/progs/catcrypt.1 b/progs/catcrypt.1 index e6e1534b..698b2db9 100644 --- a/progs/catcrypt.1 +++ b/progs/catcrypt.1 @@ -216,6 +216,18 @@ command (see .BR key (1)) to generate the key. +.TP +.B x448 +This is Hamburg's Curve25519, a strong Diffie-Hellman using a specific +elliptic curve. +Use the +.B x448 +algorithm of the +.B key add +command +(see +.BR key (1)) +to generate the key. .PP The bulk crypto transform is chosen based on the .B bulk diff --git a/progs/cc-kem.c b/progs/cc-kem.c index 71c89e47..5b0cbf79 100644 --- a/progs/cc-kem.c +++ b/progs/cc-kem.c @@ -44,6 +44,7 @@ #include "dh.h" #include "rsa.h" #include "x25519.h" +#include "x448.h" #include "rmd160.h" #include "blowfish-cbc.h" @@ -668,6 +669,71 @@ static const kemops x25519_decops = { x25519_encinit, x25519_decdoit, x25519_deccheck, x25519_encdestroy }; +/* --- X448 --- */ + +static kem *x448_encinit(key *k, void *kd) { return (CREATE(kem)); } +static void x448_encdestroy(kem *k) { DESTROY(k); } + +static const char *x448_enccheck(kem *k) +{ + x448_pub *kd = k->kd; + + if (kd->pub.sz != X448_PUBSZ) + return ("incorrect X448 public key length"); + return (0); +} + +static int x448_encdoit(kem *k, dstr *d, ghash *h) +{ + octet t[X448_KEYSZ], z[X448_OUTSZ]; + x448_pub *kd = k->kd; + + rand_get(RAND_GLOBAL, t, sizeof(t)); + dstr_ensure(d, X448_PUBSZ); + x448((octet *)d->buf, t, x448_base); + x448(z, t, kd->pub.k); + d->len += X448_PUBSZ; + GH_HASH(h, d->buf, X448_PUBSZ); + GH_HASH(h, z, X448_OUTSZ); + return (0); +} + +static const char *x448_deccheck(kem *k) +{ + x448_priv *kd = k->kd; + + if (kd->priv.sz != X448_KEYSZ) + return ("incorrect X448 private key length"); + if (kd->pub.sz != X448_PUBSZ) + return ("incorrect X448 public key length"); + return (0); +} + +static int x448_decdoit(kem *k, dstr *d, ghash *h) +{ + octet z[X448_OUTSZ]; + x448_priv *kd = k->kd; + int rc = -1; + + if (d->len != X448_PUBSZ) goto done; + x448(z, kd->priv.k, (const octet *)d->buf); + GH_HASH(h, d->buf, X448_PUBSZ); + GH_HASH(h, z, X448_OUTSZ); + rc = 0; +done: + return (rc); +} + +static const kemops x448_encops = { + x448_pubfetch, sizeof(x448_pub), + x448_encinit, x448_encdoit, x448_enccheck, x448_encdestroy +}; + +static const kemops x448_decops = { + x448_privfetch, sizeof(x448_priv), + x448_encinit, x448_decdoit, x448_deccheck, x448_encdestroy +}; + /* --- Symmetric --- */ typedef struct symm_ctx { @@ -737,6 +803,7 @@ const struct kemtab kemtab[] = { { "bindh", &bindh_encops, &bindh_decops }, { "ec", &ec_encops, &ec_decops }, { "x25519", &x25519_encops, &x25519_decops }, + { "x448", &x448_encops, &x448_decops }, { "symm", &symm_encops, &symm_decops }, { 0, 0, 0 } }; diff --git a/progs/key.1 b/progs/key.1 index 7479b4cb..95eb0ded 100644 --- a/progs/key.1 +++ b/progs/key.1 @@ -854,6 +854,14 @@ the public key is the .IR x -coordinate of the corresponding point. .TP +.B x448 +Generate a private scalar and a corresponding public point on the +(Montgomery-form) Ed448-Goldilocks elliptic curve. +The scalar is simply a random 256-bit string; +the public key is the +.IR x -coordinate +of the corresponding point. +.TP .B ed25519 Generate a private key and a corresponding public point on the (twisted Edwards-form) Curve25519 elliptic curve. diff --git a/progs/key.c b/progs/key.c index b2b90800..26c67eec 100644 --- a/progs/key.c +++ b/progs/key.c @@ -70,6 +70,7 @@ #include "ptab.h" #include "rsa.h" #include "x25519.h" +#include "x448.h" #include "ed25519.h" #include "cc.h" @@ -956,6 +957,24 @@ static void alg_x25519(keyopts *k) key_setkeydata(k->kf, k->k, kd); } +static void alg_x448(keyopts *k) +{ + key_data *kd, *kkd; + octet priv[X448_KEYSZ], pub[X448_PUBSZ]; + + copyparam(k, 0); + k->r->ops->fill(k->r, priv, sizeof(priv)); + x448(pub, priv, x448_base); + kkd = key_newstruct(); + key_structsteal(kkd, "priv", + key_newbinary(KCAT_PRIV | KF_BURN, priv, sizeof(priv))); + kd = key_newstruct(); + key_structsteal(kd, "private", kkd); + key_structsteal(kd, "pub", key_newbinary(KCAT_PUB, pub, sizeof(pub))); + + key_setkeydata(k->kf, k->k, kd); +} + static void alg_ed25519(keyopts *k) { key_data *kd, *kkd; @@ -996,6 +1015,7 @@ static keyalg algtab[] = { { "ec-param", alg_ecparam, "Elliptic curve parameters" }, { "ec", alg_ec, "Elliptic curve crypto" }, { "x25519", alg_x25519, "X25519 key exchange" }, + { "x448", alg_x448, "X448 key exchange" }, { "ed25519", alg_ed25519, "Ed25519 digital signatures" }, { "empty", alg_empty, "Empty parametrs-only key" }, { 0, 0 } diff --git a/progs/perftest.c b/progs/perftest.c index 33774879..b2722a4e 100644 --- a/progs/perftest.c +++ b/progs/perftest.c @@ -63,6 +63,7 @@ #include "ec.h" #include "group.h" #include "x25519.h" +#include "x448.h" #include "ed25519.h" #include "cc.h" @@ -289,6 +290,24 @@ static void *x25519_jobinit(opts *o) static void x25519_jobrun(void *cc) { x25519_jobctx *c = cc; octet z[X25519_OUTSZ]; x25519(z, c->k, c->p); } +/* --- x448 --- */ + +typedef struct x448_jobctx { + octet k[X448_KEYSZ]; + octet p[X448_PUBSZ]; +} x448_jobctx; + +static void *x448_jobinit(opts *o) +{ + x448_jobctx *c = CREATE(x448_jobctx); + rand_get(RAND_GLOBAL, c->k, sizeof(c->k)); + rand_get(RAND_GLOBAL, c->p, sizeof(c->p)); + return (c); +} + +static void x448_jobrun(void *cc) + { x448_jobctx *c = cc; octet z[X448_OUTSZ]; x448(z, c->k, c->p); } + /* --- Ed25519 --- */ typedef struct ed25519_signctx { @@ -556,6 +575,7 @@ static const jobops jobtab[] = { { "rsa-priv-blind", rsaprivblind_init, rsapriv_run }, { "rsa-pub", rsapub_init, rsapub_run }, { "x25519", x25519_jobinit, x25519_jobrun }, + { "x448", x448_jobinit, x448_jobrun }, { "ed25519-sign", ed25519_signinit, ed25519_signrun }, { "ed25519-vrf", ed25519_vrfinit, ed25519_vrfrun }, { "ksched", ksched_init, ksched_run }, diff --git a/pub/Makefile.am b/pub/Makefile.am index 63e3fe05..70470665 100644 --- a/pub/Makefile.am +++ b/pub/Makefile.am @@ -120,4 +120,10 @@ t/ed25519: ed25519-tvconv t/ed25519.djb } >t/ed25519.new && \ mv t/ed25519.new t/ed25519 +## Hamburg's X448 key-agreement algorithm. +pkginclude_HEADERS += x448.h +libpub_la_SOURCES += x448.c +TESTS += x448.t$(EXEEXT) +EXTRA_DIST += t/x448 + ###----- That's all, folks -------------------------------------------------- diff --git a/pub/t/x448 b/pub/t/x448 new file mode 100644 index 00000000..3f0a4f7f --- /dev/null +++ b/pub/t/x448 @@ -0,0 +1,41 @@ +### Tests for X448. + +x448 { + ## These are taken from RFC7748. + + 3d262fddf9ec8e88495266fea19a34d28882acef045104d0d1aae121700a779c984c24f8cdd78fbff44943eba368f54b29259a4f1c600ad3 + 06fce640fa3487bfda5f6cf2d5263f8aad88334cbd07437f020f08f9814dc031ddbdc38c19c6da2583fa5429db94ada18aa7a7fb4ef8a086 + ce3e4ff95a60dc6697da1db1d85e6afbdf79b50a2412d7546d5f239fe14fbaadeb445fc66a01b0779d98223961111e21766282f73dd96b6f; + 203d494428b8399352665ddca42f9de8fef600908e0d461cb021f8c538345dd77c3e4806e25f46d3315c44e0a5b4371282dd2c8d5be3095f + 0fbcc2f993cd56d3305b0b7d9e55d4c1a8fb5dbb52f8e9a1e9b6201b165d015894e56c4d3570bee52fe205e28a78b91cdfbde71ce8d157db + 884a02576239ff7a2f2f63b2db6a9ff37047ac13568e1e30fe63c4a7ad1b3ee3a5700df34321d62077e63633c575c1c954514e99da7c179d; + + 9a8f4925d1519f5775cf46b04b5800d4ee9ee8bae8bc5565d498c28dd9c9baf574a9419744897391006382a6f127ab1d9ac2d8c0a598726b + 0500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 + 9b08f7cc31b7e3e67d22d5aea121074a273bd2b83de09c63faa73d2c22c5d9bbc836647241d953d40c5b12da88120d53177f80e532c41fa0; + 1c306a7ac2a0e2e0990b294470cba339e6453772b075811d8fad0d1d6927c120bb5ee8972b0d3e21374c9c921b09d1b0366f10b65173992d + 0500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 + 3eb7a829b0cd20f5bcfc0b599b6feccf6da4627107bdb0d4f345b43027d8b972fc3e34fb4232a13ca706dcb57aec3dae07bdc1c67bf33609; + 9a8f4925d1519f5775cf46b04b5800d4ee9ee8bae8bc5565d498c28dd9c9baf574a9419744897391006382a6f127ab1d9ac2d8c0a598726b + 3eb7a829b0cd20f5bcfc0b599b6feccf6da4627107bdb0d4f345b43027d8b972fc3e34fb4232a13ca706dcb57aec3dae07bdc1c67bf33609 + 07fff4181ac6cc95ec1c16a94a0f74d12da232ce40a77552281d282bb60c0b56fd2464c335543936521c24403085d59a449a5037514a879d; + 1c306a7ac2a0e2e0990b294470cba339e6453772b075811d8fad0d1d6927c120bb5ee8972b0d3e21374c9c921b09d1b0366f10b65173992d + 9b08f7cc31b7e3e67d22d5aea121074a273bd2b83de09c63faa73d2c22c5d9bbc836647241d953d40c5b12da88120d53177f80e532c41fa0 + 07fff4181ac6cc95ec1c16a94a0f74d12da232ce40a77552281d282bb60c0b56fd2464c335543936521c24403085d59a449a5037514a879d; +} + +x448-mct { + ## These are taken from RFC7748. + + 0500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 + 0500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 + 1 3f482c8a9f19b01e6c46ee9711d9dc14fd4bf67af30765c2ae2b846a4d23a8cd0db897086239492caf350b51f833868b9bc2b3bca9cf4113; + 0500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 + 0500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 + 1000 aa3b4749d55b9daf1e5b00288826c467274ce3ebbdd5c17b975e09d4af6c67cf10d087202db88286e2b79fceea3ec353ef54faa26e219f38; + + ## This one takes aaaaages. + ##0500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 + ## 0500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 + ## 1000000 077f453681caca3693198420bbe515cae0002472519b3e67661a7e89cab94695c8f4bcd66e61b9b9c946da8d524de3d69bd9d9d66b997e37; +} diff --git a/pub/x448.c b/pub/x448.c new file mode 100644 index 00000000..d766e5c1 --- /dev/null +++ b/pub/x448.c @@ -0,0 +1,182 @@ +/* -*-c-*- + * + * The X448 key-agreement algorithm + * + * (c) 2017 Straylight/Edgeware + */ + +/*----- Licensing notice --------------------------------------------------* + * + * This file is part of Catacomb. + * + * Catacomb is free software; you can redistribute it and/or modify + * it under the terms of the GNU Library General Public License as + * published by the Free Software Foundation; either version 2 of the + * License, or (at your option) any later version. + * + * Catacomb 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 Library General Public License for more details. + * + * You should have received a copy of the GNU Library General Public + * License along with Catacomb; if not, write to the Free + * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, + * MA 02111-1307, USA. + */ + +/*----- Header files ------------------------------------------------------*/ + +#include + +#include "montladder.h" +#include "fgoldi.h" +#include "x448.h" + +/*----- Important constants -----------------------------------------------*/ + +const octet x448_base[56] = { 5, 0, /* ... */ }; + +#define A0 39081 + +/*----- Key fetching ------------------------------------------------------*/ + +const key_fetchdef x448_pubfetch[] = { + { "pub", offsetof(x448_pub, pub), KENC_BINARY, 0 }, + { 0, 0, 0, 0 } +}; + +static const key_fetchdef priv[] = { + { "priv", offsetof(x448_priv, priv), KENC_BINARY, 0 }, + { 0, 0, 0, 0 } +}; + +const key_fetchdef x448_privfetch[] = { + { "pub", offsetof(x448_priv, pub), KENC_BINARY, 0 }, + { "private", 0, KENC_STRUCT, priv }, + { 0, 0, 0, 0 } +}; + +/*----- Main code ---------------------------------------------------------*/ + +/* --- @x448@ --- * + * + * Arguments: @octet zz[X448_OUTSZ]@ = where to put the result + * @const octet k[X448_KEYSZ]@ = pointer to private key + * @const octet qx[X448_PUBSZ]@ = pointer to public value + * + * Returns: --- + * + * Use: Calculates X448 of @k@ and @qx@. + */ + +void x448(octet zz[X448_OUTSZ], + const octet k[X448_KEYSZ], + const octet qx[X448_PUBSZ]) +{ + uint32 kw[14]; + fgoldi x1; + unsigned i; + + /* Load and clamp the key. The low bits are cleared to kill the small + * subgroups on the curve and its twist, and a high bit is set to guard + * against careless implementations, though this isn't one of those. + */ + for (i = 0; i < 14; i++) kw[i] = LOAD32_L(k + 4*i); + kw[0] &= 0xfffffffc; kw[13] |= 0x80000000; + + /* And run the ladder. */ + fgoldi_load(&x1, qx); +#define MULA0(z, x) do { fgoldi_mulconst((z), (x), A0); } while (0) + MONT_LADDER(fgoldi, MULA0, kw, 14, 32, &x1, &x1); +#undef MULA0 + fgoldi_store(zz, &x1); +} + +/*----- Test rig ----------------------------------------------------------*/ + +#ifdef TEST_RIG + +#include +#include +#include + +static int vrf_x448(dstr dv[]) +{ + dstr dz = DSTR_INIT; + int ok = 1; + + if (dv[0].len != 56) die(1, "bad key length"); + if (dv[1].len != 56) die(1, "bad public length"); + if (dv[2].len != 56) die(1, "bad result length"); + + dstr_ensure(&dz, 56); dz.len = 56; + x448((octet *)dz.buf, + (const octet *)dv[0].buf, + (const octet *)dv[1].buf); + if (memcmp(dz.buf, dv[2].buf, 56) != 0) { + ok = 0; + fprintf(stderr, "failed!"); + fprintf(stderr, "\n\t k = "); type_hex.dump(&dv[0], stderr); + fprintf(stderr, "\n\t p = "); type_hex.dump(&dv[1], stderr); + fprintf(stderr, "\n\twant = "); type_hex.dump(&dv[2], stderr); + fprintf(stderr, "\n\tcalc = "); type_hex.dump(&dz, stderr); + fprintf(stderr, "\n"); + } + + dstr_destroy(&dz); + return (ok); +} + +static int vrf_mct(dstr dv[]) +{ + octet b0[56], b1[56], *k = b0, *x = b1, *t; + unsigned long i, niter; + dstr d = DSTR_INIT; + int ok = 1; + + if (dv[0].len != sizeof(b0)) { fprintf(stderr, "k len\n"); exit(2); } + if (dv[1].len != sizeof(b1)) { fprintf(stderr, "x len\n"); exit(2); } + if (dv[3].len != sizeof(b0)) { fprintf(stderr, "result len\n"); exit(2); } + memcpy(b0, dv[0].buf, sizeof(b0)); + memcpy(b1, dv[1].buf, sizeof(b1)); + niter = *(unsigned long *)dv[2].buf; + dstr_ensure(&d, 56); d.len = 56; t = (octet *)d.buf; + + for (i = 0; i < niter; i++) { + x448(x, k, x); + t = x; x = k; k = t; + } + memcpy(d.buf, k, d.len); + + if (memcmp(d.buf, dv[3].buf, d.len) != 0) { + ok = 0; + fprintf(stderr, "failed..."); + fprintf(stderr, "\n\tinitial k = "); type_hex.dump(&dv[0], stderr); + fprintf(stderr, "\n\tinitial x = "); type_hex.dump(&dv[1], stderr); + fprintf(stderr, "\n\titerations = %lu", niter); + fprintf(stderr, "\n\texpected = "); type_hex.dump(&dv[3], stderr); + fprintf(stderr, "\n\tcalculated = "); type_hex.dump(&d, stderr); + fputc('\n', stderr); + } + + dstr_destroy(&d); + return (ok); +} + +static test_chunk tests[] = { + { "x448", vrf_x448, { &type_hex, &type_hex, &type_hex } }, + { "x448-mct", vrf_mct, + { &type_hex, &type_hex, &type_ulong, &type_hex } }, + { 0, 0, { 0 } } +}; + +int main(int argc, char *argv[]) +{ + test_run(argc, argv, tests, SRCDIR "/t/x448"); + return (0); +} + +#endif + +/*----- That's all, folks -------------------------------------------------*/ diff --git a/pub/x448.h b/pub/x448.h new file mode 100644 index 00000000..f1b0f2cc --- /dev/null +++ b/pub/x448.h @@ -0,0 +1,95 @@ +/* -*-c-*- + * + * The X448 key-agreement algorithm + * + * (c) 2017 Straylight/Edgeware + */ + +/*----- Licensing notice --------------------------------------------------* + * + * This file is part of Catacomb. + * + * Catacomb is free software; you can redistribute it and/or modify + * it under the terms of the GNU Library General Public License as + * published by the Free Software Foundation; either version 2 of the + * License, or (at your option) any later version. + * + * Catacomb 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 Library General Public License for more details. + * + * You should have received a copy of the GNU Library General Public + * License along with Catacomb; if not, write to the Free + * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, + * MA 02111-1307, USA. + */ + +#ifndef CATACOMB_X448_H +#define CATACOMB_X448_H + +#ifdef __cplusplus + extern "C" { +#endif + +/*----- Notes on the X448 key-agreement algorithm -------------------------* + * + * This is X448, as described in RFC7748, based on the elliptic curve defined + * in Mike Hamburg, `Ed448-Goldilocks, a new elliptic curve', EUROCRYPT 2016, + * https://eprint.iacr.org/2015/625/. + * + * The RFC-specified operation is simpler than the Diffie--Hellman function + * described in Hamburg's paper, since it doesn't involve the `Decaf' + * cofactor elimination procedure. Indeed, it looks very much like X25519 + * with Hamburg's curve slotted in in place of Bernstein's. + */ + +/*----- Header files ------------------------------------------------------*/ + +#include + +#ifndef CATACOMB_KEY_H +# include "key.h" +#endif + +/*----- Key fetching ------------------------------------------------------*/ + +typedef struct x448_priv { key_bin priv, pub; } x448_priv; +typedef struct x448_pub { key_bin pub; } x448_pub; + +extern const key_fetchdef x448_pubfetch[], x448_privfetch[]; +#define X448_PUBFETCHSZ 3 +#define X448_PRIVFETCHSZ 6 + +/*----- Important constants -----------------------------------------------*/ + +#define X448_KEYSZ 56 +#define X448_PUBSZ 56 +#define X448_OUTSZ 56 + +extern const octet x448_base[56]; + +/*----- Functions provided ------------------------------------------------*/ + +/* --- @x448@ --- * + * + * Arguments: @octet zz[X448_OUTSZ]@ = where to put the result + * @const octet k[X448_KEYSZ]@ = pointer to private key + * @const octet qx[X448_PUBSZ]@ = pointer to public value + * + * Returns: --- + * + * Use: Calculates X448 of @k@ and @qx@. + */ + +extern void x448(octet /*zz*/[X448_OUTSZ], + const octet /*k*/[X448_KEYSZ], + const octet /*qx*/[X448_PUBSZ]); + +/*----- That's all, folks -------------------------------------------------*/ + +#ifdef __cplusplus + } +#endif + +#endif diff --git a/utils/qfarith-test b/utils/qfarith-test index 45f233ff..ff0782cf 100755 --- a/utils/qfarith-test +++ b/utils/qfarith-test @@ -57,6 +57,7 @@ class Field (object): return FieldElt(me, n) Field.register('f25519', C.MP(0).setbit(255) - 19) +Field.register('fgoldi', C.MP(0).setbit(448) - C.MP(0).setbit(224) - 1) def binop(k, op): x = k.rand(); y = k.rand() -- 2.11.0