Implement GOST VKO key derivation algorithm

Signed-off-by: Dmitry Baryshkov <dbaryshkov@gmail.com>

8 files changed, 215 insertions, 2 deletions

diff --git a/Makefile.in b/Makefile.in
index 56815d89..2453fa7e 100644
--- a/Makefile.in
+++ b/Makefile.in
@@ -194,7 +194,7 @@ hogweed_SOURCES = sexp.c sexp-format.c \
 		  ecc-ecdsa-sign.c ecdsa-sign.c \
 		  ecc-ecdsa-verify.c ecdsa-verify.c ecdsa-keygen.c \
 		  ecc-gostdsa-sign.c gostdsa-sign.c \
-		  ecc-gostdsa-verify.c gostdsa-verify.c \
+		  ecc-gostdsa-verify.c gostdsa-verify.c gostdsa-vko.c \
 		  curve25519-mul-g.c curve25519-mul.c curve25519-eh-to-x.c \
 		  curve448-mul-g.c curve448-mul.c curve448-eh-to-x.c \
 		  eddsa-compress.c eddsa-decompress.c eddsa-expand.c \
diff --git a/gostdsa-vko.c b/gostdsa-vko.c
new file mode 100644
index 00000000..7bdcdfc3
--- /dev/null
+++ b/gostdsa-vko.c
@@ -0,0 +1,96 @@
+/* gostdsa-vko.c
+
+   Copyright (C) 2016 Dmitry Eremin-Solenikov
+
+   This file is part of GNU Nettle.
+
+   GNU Nettle is free software: you can redistribute it and/or
+   modify it under the terms of either:
+
+     * the GNU Lesser General Public License as published by the Free
+       Software Foundation; either version 3 of the License, or (at your
+       option) any later version.
+
+   or
+
+     * 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.
+
+   or both in parallel, as here.
+
+   GNU Nettle 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.
+
+   You should have received copies of the GNU General Public License and
+   the GNU Lesser General Public License along with this program.  If
+   not, see http://www.gnu.org/licenses/.
+*/
+
+#if HAVE_CONFIG_H
+# include "config.h"
+#endif
+
+#include <assert.h>
+#include <stdlib.h>
+
+#include "ecc-internal.h"
+#include "gostdsa.h"
+
+/*
+ * Shared key derivation/key agreement for GOST DSA algorithm.
+ * It is defined in RFC 4357 Section 5.2 and RFC 7836 Section 4.3.1
+ *
+ * output is 2 * curve size:
+ * 64 bytes for 256 bit curves and 128 bytes for 512 bit ones
+ *
+ * Basically shared key is equal to hash(cofactor * ukm * priv * pub). This
+ * function does multiplication. Caller should do hashing on his own.
+ *
+ * UKM is not a secret value (consider it as a nonce).
+ *
+ * For supported GOST curves cofactor is equal to 1.
+ */
+void
+gostdsa_vko (const struct ecc_scalar *priv,
+		const struct ecc_point *pub,
+		size_t ukm_length, const uint8_t *ukm,
+		uint8_t *out)
+{
+  const struct ecc_curve *ecc = priv->ecc;
+  unsigned bsize = (ecc_bit_size (ecc) + 7) / 8;
+  mp_size_t size = ecc->p.size;
+  mp_size_t itch = 4*size + ecc->mul_itch;
+  mp_limb_t *scratch;
+
+  if (itch < 5*size + ecc->h_to_a_itch)
+      itch = 5*size + ecc->h_to_a_itch;
+
+  assert (pub->ecc == ecc);
+  assert (priv->ecc == ecc);
+  assert (ukm_length <= bsize);
+
+  scratch = gmp_alloc_limbs (itch);
+
+#define UKM scratch
+#define TEMP (scratch + 3*size)
+#define XYZ scratch
+#define TEMP_Y (scratch + 4*size)
+
+  mpn_set_base256_le (UKM, size, ukm, ukm_length);
+
+  /* If ukm is 0, set it to 1, otherwise the result will be allways equal to 0,
+   * no matter what private and public keys are. See RFC 4357 referencing GOST
+   * R 34.10-2001 (RFC 5832) Section 6.1 step 2. */
+  if (mpn_zero_p (UKM, size))
+    UKM[0] = 1;
+
+  ecc_mod_mul (&ecc->q, TEMP, priv->p, UKM); /* TEMP = UKM * priv */
+  ecc->mul (ecc, XYZ, TEMP, pub->p, scratch + 4*size); /* XYZ = UKM * priv * pub */
+  ecc->h_to_a (ecc, 0, TEMP, XYZ, scratch + 5*size); /* TEMP = XYZ */
+  mpn_get_base256_le (out, bsize, TEMP, size);
+  mpn_get_base256_le (out+bsize, bsize, TEMP_Y, size);
+  gmp_free_limbs (scratch, itch);
+}
diff --git a/gostdsa.h b/gostdsa.h
index c92dfd1e..d479201e 100644
--- a/gostdsa.h
+++ b/gostdsa.h
@@ -44,6 +44,7 @@ extern "C" {
 /* Name mangling */
 #define gostdsa_sign nettle_gostdsa_sign
 #define gostdsa_verify nettle_gostdsa_verify
+#define gostdsa_vko nettle_gostdsa_vko
 #define ecc_gostdsa_sign nettle_ecc_gostdsa_sign
 #define ecc_gostdsa_sign_itch nettle_ecc_gostdsa_sign_itch
 #define ecc_gostdsa_verify nettle_ecc_gostdsa_verify
@@ -68,6 +69,12 @@ gostdsa_verify (const struct ecc_point *pub,
 	        size_t length, const uint8_t *digest,
 	        const struct dsa_signature *signature);
 
+void
+gostdsa_vko (const struct ecc_scalar *key,
+	     const struct ecc_point *pub,
+	     size_t ukm_length, const uint8_t *ukm,
+	     uint8_t *out);
+
 /* Low-level GOSTDSA functions. */
 mp_size_t
 ecc_gostdsa_sign_itch (const struct ecc_curve *ecc);
diff --git a/nettle.texinfo b/nettle.texinfo
index ff64889c..995d5de8 100644
--- a/nettle.texinfo
+++ b/nettle.texinfo
@@ -1065,6 +1065,7 @@ This function also resets the context in the same way as
 @subsubsection @acronym{GOSTHASH94 and GOSTHASH94CP}
 @cindex GOST hash
 
+@anchor{GOSTHASH94CP}
 The GOST94 or GOST R 34.11-94 hash algorithm is a Soviet-era algorithm 
 used in Russian government standards (see @cite{RFC 4357}).
 It outputs message digests of 256 bits, or 32 octets. The standard itself
@@ -5157,6 +5158,20 @@ Returns curve corresponding to following identifiers:
 @end itemize
 @end deftypefun
 
+For GOST key pairs key derivation/key agreement function (VKO) is defined in
+@cite{RFC 4357} and @cite{RFC 7836}.  Basically shared key is equal to
+hash(cofactor * ukm * priv * pub). Nettle library provides a function that does
+multiplication. Caller should do hashing on his own (it will be either
+GOST R 34.11-94 (@pxref{GOSTHASH94CP}) or GOST R 34.11-2012, Streebog, which nor part of the library yet).
+
+@deftypefun void gostdsa_vko (const struct ecc_scalar *@var{priv}, const struct ecc_point *@var{pub}, size_t @var{ukm_length}, const uint8_t *@var{ukm}, uint8_t *@var{out})
+Uses private key @var{priv}, public ket @var{pub} and shared key material
+@var{ukm} to generate shared secret, written to buffer @var{out}. The buffer
+should be of the size equal to 2 private key lengths: 64 bytes for 256 bit
+curves and 128 bytes for 512 bit ones. UKM is a shared key material, usually
+transferred in cleartext. It does not have to be secret.
+@end deftypefun
+
 @node Curve 25519 and Curve 448, , ECDSA, Elliptic curves
 @comment  node-name,  next,  previous,  up
 @subsubsection Curve25519 and Curve448
diff --git a/testsuite/.gitignore b/testsuite/.gitignore
index b8b36c2a..a2b3d523 100644
--- a/testsuite/.gitignore
+++ b/testsuite/.gitignore
@@ -46,6 +46,7 @@
 /gostdsa-keygen-test
 /gostdsa-sign-test
 /gostdsa-verify-test
+/gostdsa-vko-test
 /gosthash94-test
 /hkdf-test
 /hmac-test
diff --git a/testsuite/.test-rules.make b/testsuite/.test-rules.make
index 9de8f412..fdcde6cb 100644
--- a/testsuite/.test-rules.make
+++ b/testsuite/.test-rules.make
@@ -304,6 +304,9 @@ gostdsa-verify-test$(EXEEXT): gostdsa-verify-test.$(OBJEXT)
 gostdsa-keygen-test$(EXEEXT): gostdsa-keygen-test.$(OBJEXT)
 	$(LINK) gostdsa-keygen-test.$(OBJEXT) $(TEST_OBJS) -o gostdsa-keygen-test$(EXEEXT)
 
+gostdsa-vko-test$(EXEEXT): gostdsa-vko-test.$(OBJEXT)
+	$(LINK) gostdsa-vko-test.$(OBJEXT) $(TEST_OBJS) -o gostdsa-vko-test$(EXEEXT)
+
 sha1-huge-test$(EXEEXT): sha1-huge-test.$(OBJEXT)
 	$(LINK) sha1-huge-test.$(OBJEXT) $(TEST_OBJS) -o sha1-huge-test$(EXEEXT)
 
diff --git a/testsuite/Makefile.in b/testsuite/Makefile.in
index 89b52efa..025f3ea1 100644
--- a/testsuite/Makefile.in
+++ b/testsuite/Makefile.in
@@ -56,7 +56,7 @@ TS_HOGWEED_SOURCES = sexp-test.c sexp-format-test.c \
 		     eddsa-compress-test.c eddsa-sign-test.c \
 		     eddsa-verify-test.c ed25519-test.c ed448-test.c \
 		     gostdsa-sign-test.c gostdsa-verify-test.c \
-		     gostdsa-keygen-test.c
+		     gostdsa-keygen-test.c gostdsa-vko-test.c
 
 TS_SOURCES = $(TS_NETTLE_SOURCES) $(TS_HOGWEED_SOURCES)
 CXX_SOURCES = cxx-test.cxx
diff --git a/testsuite/gostdsa-vko-test.c b/testsuite/gostdsa-vko-test.c
new file mode 100644
index 00000000..c8a762b1
--- /dev/null
+++ b/testsuite/gostdsa-vko-test.c
@@ -0,0 +1,91 @@
+#include "testutils.h"
+#include "gostdsa.h"
+
+static void
+test_vko (const struct ecc_curve *ecc,
+	  const char *priv,
+	  const char *x,
+	  const char *y,
+	  const struct tstring *ukm,
+	  const struct nettle_hash *hash,
+	  void * hash_ctx,
+	  const struct tstring *res)
+{
+    struct ecc_scalar ecc_key;
+    struct ecc_point ecc_pub;
+    mpz_t temp1, temp2;
+    uint8_t out[128];
+    size_t out_len = ((ecc_bit_size(ecc) + 7) / 8) * 2;
+
+    ASSERT(out_len <= sizeof(out));
+
+    ecc_point_init (&ecc_pub, ecc);
+    mpz_init_set_str (temp1, x, 16);
+    mpz_init_set_str (temp2, y, 16);
+    ASSERT (ecc_point_set (&ecc_pub, temp1, temp2) != 0);
+
+    ecc_scalar_init (&ecc_key, ecc);
+    mpz_set_str (temp1, priv, 16);
+    ASSERT (ecc_scalar_set (&ecc_key, temp1) != 0);
+
+    mpz_clear (temp1);
+    mpz_clear (temp2);
+
+    gostdsa_vko (&ecc_key, &ecc_pub,
+		 ukm->length, ukm->data,
+		 out);
+
+    ecc_scalar_clear (&ecc_key);
+    ecc_point_clear (&ecc_pub);
+
+    if (hash)
+      {
+	hash->init (hash_ctx);
+	hash->update (hash_ctx, out_len, out);
+	hash->digest (hash_ctx, hash->digest_size, out);
+
+	ASSERT (hash->digest_size == res->length);
+	ASSERT (MEMEQ (res->length, out, res->data));
+      }
+    else
+      {
+	ASSERT (out_len == res->length);
+	ASSERT (MEMEQ (res->length, out, res->data));
+      }
+}
+
+void
+test_main (void)
+{
+    /* RFC 7836, App B, provides test vectors, values there are little endian.
+     *
+     * However those test vectors depend on the availability of Streebog hash
+     * functions, which is not available (yet). So these test vectors capture
+     * the VKO value just before hash function. One can verify them by
+     * calculating the Streeebog function and comparing the result with RFC
+     * 7836, App B. */
+    test_vko(nettle_get_gost_gc512a(),
+	     "67b63ca4ac8d2bb32618d89296c7476dbeb9f9048496f202b1902cf2ce41dbc2f847712d960483458d4b380867f426c7ca0ff5782702dbc44ee8fc72d9ec90c9",
+	     "51a6d54ee932d176e87591121cce5f395cb2f2f147114d95f463c8a7ed74a9fc5ecd2325a35fb6387831ea66bc3d2aa42ede35872cc75372073a71b983e12f19",
+	     "793bde5bf72840ad22b02a363ae4772d4a52fc08ba1a20f7458a222a13bf98b53be002d1973f1e398ce46c17da6d00d9b6d0076f8284dcc42e599b4c413b8804",
+	     SHEX("1d 80 60 3c 85 44 c7 27"),
+	     NULL,
+	     NULL,
+	     SHEX("5fb5261b61e872f9 3efc03200f47378e f039aa89b993a274 a25dec5e5d49ed59"
+		  "84b7dfdf5970c3f7 3059a26d08f7bbc5 0830799bda18b533 499c4f00c21cff3e"
+		  "3b8e53a1ea920eb1 d7f3d08aa9e47595 4a53ac018c210b48 15451b7accc4a797"
+		  "a2b8faf3d89ee717 d07a857794b9b053 f8e0fd5456ccfcc2 2fd081c873416a3f"));
+
+    test_vko(nettle_get_gost_gc512a(),
+	     "dbd09213a592da5bbfd8ed068cccccbbfbeda4feac96b9b4908591440b0714803b9eb763ef932266d4c0181a9b73eacf9013efc65ec07c888515f1b6f759c848",
+	     "a7c0adb12743c10c3c1beb97c8f631242f7937a1deb6bce5e664e49261baccd3f5dc56ec53b2abb90ca1eb703078ba546655a8b99f79188d2021ffaba4edb0aa",
+	     "5adb1c63a4e4465e0bbefd897fb9016475934cfa0f8c95f992ea402d47921f46382d00481b720314b19d8c878e75d81b9763358dd304b2ed3a364e07a3134691",
+	     SHEX("1d 80 60 3c 85 44 c7 27"),
+	     NULL,
+	     NULL,
+	     SHEX("5fb5261b61e872f9 3efc03200f47378e f039aa89b993a274 a25dec5e5d49ed59"
+		  "84b7dfdf5970c3f7 3059a26d08f7bbc5 0830799bda18b533 499c4f00c21cff3e"
+		  "3b8e53a1ea920eb1 d7f3d08aa9e47595 4a53ac018c210b48 15451b7accc4a797"
+		  "a2b8faf3d89ee717 d07a857794b9b053 f8e0fd5456ccfcc2 2fd081c873416a3f"));
+
+}