[PATCH v2] Implement GOST VKO key derivation algorithm

-- - Added internal documentation - Dropped dependency of tests on Streebog diff --git a/Makefile.in b/Makefile.in index ddc304285321..29b3cfb4aafe 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 000000000000..0c027014e5ea --- /dev/null +++ b/gostdsa-vko.c @@ -0,0 +1,94 @@ +/* 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 + * + * 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, + size_t out_length, 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 (out_length == 2 * bsize); + 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 c92dfd1e1dd6..5ccf35a767a8 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, + size_t out_length, uint8_t *out); + /* Low-level GOSTDSA functions. */ mp_size_t ecc_gostdsa_sign_itch (const struct ecc_curve *ecc); diff --git a/testsuite/.gitignore b/testsuite/.gitignore index b8b36c2accc2..a2b3d52312cd 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 9de8f4125079..fdcde6cb9748 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 89b52efad9df..025f3ea18040 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 000000000000..5d77f2efced5 --- /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_len, 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")); + +} -- 2.25.1