From: Dmitry Eremin-Solenikov dbaryshkov@gmail.com
Signed-off-by: Dmitry Eremin-Solenikov dbaryshkov@gmail.com --- Makefile.in | 2 +- gostdsa-vko.c | 77 ++++++++++++++++++++++++++++++ gostdsa.h | 7 +++ testsuite/.gitignore | 1 + testsuite/.test-rules.make | 3 ++ testsuite/Makefile.in | 2 +- testsuite/gostdsa-vko-test.c | 92 ++++++++++++++++++++++++++++++++++++ 7 files changed, 182 insertions(+), 2 deletions(-) create mode 100644 gostdsa-vko.c create mode 100644 testsuite/gostdsa-vko-test.c
diff --git a/Makefile.in b/Makefile.in index d4fcb81302a2..8f031d7a580d 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..f78159a736b3 --- /dev/null +++ b/gostdsa-vko.c @@ -0,0 +1,77 @@ +/* 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" + +int +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) +{ + const struct ecc_curve *ecc = key->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; + + if (pub->ecc != ecc) + return 0; + + if (out_length < 2 * bsize) { + return 0; + } + + scratch = gmp_alloc_limbs (itch); + + mpn_set_base256_le (scratch, size, ukm, ukm_length); + if (mpn_zero_p (scratch, size)) + mpn_add_1 (scratch, scratch, size, 1); + ecc_mod_mul (&ecc->q, scratch + 3*size, key->p, scratch); + ecc->mul (ecc, scratch, scratch + 3*size, pub->p, scratch + 4*size); + ecc->h_to_a (ecc, 0, scratch + 3*size, scratch, scratch + 5*size); + mpn_get_base256_le (out, bsize, scratch + 3*size, size); + mpn_get_base256_le (out+bsize, bsize, scratch + 4*size, size); + gmp_free_limbs (scratch, itch); + + return 2 * bsize; +} diff --git a/gostdsa.h b/gostdsa.h index c92dfd1e1dd6..6667d0f1d3a8 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);
+int +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 922a2c7f1350..b340e3c1b7b9 100644 --- a/testsuite/.test-rules.make +++ b/testsuite/.test-rules.make @@ -301,6 +301,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 813467a548bd..9f87c86b1c2f 100644 --- a/testsuite/Makefile.in +++ b/testsuite/Makefile.in @@ -55,7 +55,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..9c86774198ed --- /dev/null +++ b/testsuite/gostdsa-vko-test.c @@ -0,0 +1,92 @@ +#include "testutils.h" +#include "gostdsa.h" +#include "streebog.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; + int ret; + uint8_t out[128]; + + 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); + + ret = gostdsa_vko (&ecc_key, &ecc_pub, + ukm->length, ukm->data, + sizeof(out), out); + ASSERT (ret != 0); + + ecc_scalar_clear (&ecc_key); + ecc_point_clear (&ecc_pub); + + hash->init (hash_ctx); + hash->update (hash_ctx, ret, out); + hash->digest (hash_ctx, hash->digest_size, out); + + ASSERT (hash->digest_size == res->length); + ASSERT (MEMEQ (res->length, out, res->data)); +} + +void +test_main (void) +{ + struct streebog256_ctx ctx_256; + struct streebog256_ctx ctx_512; + + test_vko(nettle_get_gost_gc512a(), + "67b63ca4ac8d2bb32618d89296c7476dbeb9f9048496f202b1902cf2ce41dbc2f847712d960483458d4b380867f426c7ca0ff5782702dbc44ee8fc72d9ec90c9", + "51a6d54ee932d176e87591121cce5f395cb2f2f147114d95f463c8a7ed74a9fc5ecd2325a35fb6387831ea66bc3d2aa42ede35872cc75372073a71b983e12f19", + "793bde5bf72840ad22b02a363ae4772d4a52fc08ba1a20f7458a222a13bf98b53be002d1973f1e398ce46c17da6d00d9b6d0076f8284dcc42e599b4c413b8804", + SHEX("1d 80 60 3c 85 44 c7 27"), + &nettle_streebog256, + &ctx_256, + SHEX("c9 a9 a7 73 20 e2 cc 55 9e d7 2d ce 6f 47 e2 19 2c ce a9 5f a6 48 67 05 82 c0 54 c0 ef 36 c2 21")); + + test_vko(nettle_get_gost_gc512a(), + "dbd09213a592da5bbfd8ed068cccccbbfbeda4feac96b9b4908591440b0714803b9eb763ef932266d4c0181a9b73eacf9013efc65ec07c888515f1b6f759c848", + "a7c0adb12743c10c3c1beb97c8f631242f7937a1deb6bce5e664e49261baccd3f5dc56ec53b2abb90ca1eb703078ba546655a8b99f79188d2021ffaba4edb0aa", + "5adb1c63a4e4465e0bbefd897fb9016475934cfa0f8c95f992ea402d47921f46382d00481b720314b19d8c878e75d81b9763358dd304b2ed3a364e07a3134691", + SHEX("1d 80 60 3c 85 44 c7 27"), + &nettle_streebog256, + &ctx_256, + SHEX("c9 a9 a7 73 20 e2 cc 55 9e d7 2d ce 6f 47 e2 19 2c ce a9 5f a6 48 67 05 82 c0 54 c0 ef 36 c2 21")); + + test_vko(nettle_get_gost_gc512a(), + "67b63ca4ac8d2bb32618d89296c7476dbeb9f9048496f202b1902cf2ce41dbc2f847712d960483458d4b380867f426c7ca0ff5782702dbc44ee8fc72d9ec90c9", + "51a6d54ee932d176e87591121cce5f395cb2f2f147114d95f463c8a7ed74a9fc5ecd2325a35fb6387831ea66bc3d2aa42ede35872cc75372073a71b983e12f19", + "793bde5bf72840ad22b02a363ae4772d4a52fc08ba1a20f7458a222a13bf98b53be002d1973f1e398ce46c17da6d00d9b6d0076f8284dcc42e599b4c413b8804", + SHEX("1d 80 60 3c 85 44 c7 27"), + &nettle_streebog512, + &ctx_512, + SHEX("79 f0 02 a9 69 40 ce 7b de 32 59 a5 2e 01 52 97 ad aa d8 45 97 a0 d2 05 b5 0e 3e 17 19 f9 7b fa" + "7e e1 d2 66 1f a9 97 9a 5a a2 35 b5 58 a7 e6 d9 f8 8f 98 2d d6 3f c3 5a 8e c0 dd 5e 24 2d 3b df")); + + test_vko(nettle_get_gost_gc512a(), + "dbd09213a592da5bbfd8ed068cccccbbfbeda4feac96b9b4908591440b0714803b9eb763ef932266d4c0181a9b73eacf9013efc65ec07c888515f1b6f759c848", + "a7c0adb12743c10c3c1beb97c8f631242f7937a1deb6bce5e664e49261baccd3f5dc56ec53b2abb90ca1eb703078ba546655a8b99f79188d2021ffaba4edb0aa", + "5adb1c63a4e4465e0bbefd897fb9016475934cfa0f8c95f992ea402d47921f46382d00481b720314b19d8c878e75d81b9763358dd304b2ed3a364e07a3134691", + SHEX("1d 80 60 3c 85 44 c7 27"), + &nettle_streebog512, + &ctx_512, + SHEX("79 f0 02 a9 69 40 ce 7b de 32 59 a5 2e 01 52 97 ad aa d8 45 97 a0 d2 05 b5 0e 3e 17 19 f9 7b fa" + "7e e1 d2 66 1f a9 97 9a 5a a2 35 b5 58 a7 e6 d9 f8 8f 98 2d d6 3f c3 5a 8e c0 dd 5e 24 2d 3b df")); +}
Hi, at last I've had a closer look at this patch you posted mid February.
dbaryshkov@gmail.com writes:
+int +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)
It would be good with some docs, and a link to the spec, either in the manual, or at least comments in the header file. And what's the relation between pub and key? The usual, pub = key * generator, or somethign different?
For the interface, return value is a size, and should probably have the size_t type. It fails (and returns zero) of out_length is too small, but there's no good way for the caller to know what's the needed size.
I think it would make sense with either some other function get let the application query for the appropriate size (and then one could delete the return value), or use the awkward but common interface that calling with a NULL out argument returns the needed output size.
+{
- const struct ecc_curve *ecc = key->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;- if (pub->ecc != ecc)
return 0;
I think other functions taking both a ecc_scalar and an ecc_point assert that the correspond to the same curve.
- if (out_length < 2 * bsize) {
return 0;- }
- scratch = gmp_alloc_limbs (itch);
- mpn_set_base256_le (scratch, size, ukm, ukm_length);
If ukm_length is large, the ukm input is silently truncated (if I read mpn_set_base256_le correctly). Is that good?
- if (mpn_zero_p (scratch, size))
- mpn_add_1 (scratch, scratch, size, 1);
This is a bit odd, I guess it's required by the spec? mpn_add_1 is overkill, scratch[0] = 1 should do the same thing, right (or skip the below ecc_mod_mul, which becomes a nop)? It's not side-channel silent, does it need to be (i.e., is the ukm input considered secret?)
- ecc_mod_mul (&ecc->q, scratch + 3*size, key->p, scratch);
- ecc->mul (ecc, scratch, scratch + 3*size, pub->p, scratch + 4*size);
- ecc->h_to_a (ecc, 0, scratch + 3*size, scratch, scratch + 5*size);
This is also looks a bit strange to me, but I don't have the background. If key represents a scalar k, and pub represents a point P = k G, where G is the generator (that's the usual relation between private and public key in ecc context), then we compute another point Q = u k P = u k^2 G, where u is the number represented by the ukm input. That square (k^2) looks a bit weird, maybe I'm misunderstanding. And if I have the math right, then it's probably more efficient to compute k^2 using ecc_mod_sqr and use ecc->mul_g (and then the pub input argument becomes unused).
I also wonder if this really has to be a new primitive, or if it could be implemented in terms of ecc_point_mul, or if we should provide an ecc_scalar_mul wrapping ecc_mod_mul (&ecc->q, ...) ?
+void +test_main (void) +{
- struct streebog256_ctx ctx_256;
- struct streebog256_ctx ctx_512;
- test_vko(nettle_get_gost_gc512a(),
"67b63ca4ac8d2bb32618d89296c7476dbeb9f9048496f202b1902cf2ce41dbc2f847712d960483458d4b380867f426c7ca0ff5782702dbc44ee8fc72d9ec90c9","51a6d54ee932d176e87591121cce5f395cb2f2f147114d95f463c8a7ed74a9fc5ecd2325a35fb6387831ea66bc3d2aa42ede35872cc75372073a71b983e12f19","793bde5bf72840ad22b02a363ae4772d4a52fc08ba1a20f7458a222a13bf98b53be002d1973f1e398ce46c17da6d00d9b6d0076f8284dcc42e599b4c413b8804",SHEX("1d 80 60 3c 85 44 c7 27"),&nettle_streebog256,&ctx_256,SHEX("c9 a9 a7 73 20 e2 cc 55 9e d7 2d ce 6f 47 e2 19 2c ce a9 5f a6 48 67 05 82 c0 54 c0 ef 36 c2 21"));
What's the source of these test vectors?
Regards, /Niels
вт, 14 апр. 2020 г. в 21:45, Niels Möller nisse@lysator.liu.se:
Hi, at last I've had a closer look at this patch you posted mid February.
dbaryshkov@gmail.com writes:
+int +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)It would be good with some docs, and a link to the spec, either in the manual, or at least comments in the header file. And what's the relation between pub and key? The usual, pub = key * generator, or somethign different?
I will rename key to priv to remove this confusion. VKO is a variant of DH:
VKO = cofactor * ukm * priv * pub; For supported curves cofactor is always 1.
For the interface, return value is a size, and should probably have the size_t type. It fails (and returns zero) of out_length is too small, but there's no good way for the caller to know what's the needed size.
I think it would make sense with either some other function get let the application query for the appropriate size (and then one could delete the return value), or use the awkward but common interface that calling with a NULL out argument returns the needed output size.
The result size is always 2 * curve size. Changing return value to be boolean 0/1.
+{
- const struct ecc_curve *ecc = key->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;- if (pub->ecc != ecc)
return 0;I think other functions taking both a ecc_scalar and an ecc_point assert that the correspond to the same curve.
- if (out_length < 2 * bsize) {
return 0;- }
- scratch = gmp_alloc_limbs (itch);
- mpn_set_base256_le (scratch, size, ukm, ukm_length);
If ukm_length is large, the ukm input is silently truncated (if I read mpn_set_base256_le correctly). Is that good?
- if (mpn_zero_p (scratch, size))
- mpn_add_1 (scratch, scratch, size, 1);
This is a bit odd, I guess it's required by the spec? mpn_add_1 is overkill, scratch[0] = 1 should do the same thing, right (or skip the below ecc_mod_mul, which becomes a nop)? It's not side-channel silent, does it need to be (i.e., is the ukm input considered secret?)
- ecc_mod_mul (&ecc->q, scratch + 3*size, key->p, scratch);
- ecc->mul (ecc, scratch, scratch + 3*size, pub->p, scratch + 4*size);
- ecc->h_to_a (ecc, 0, scratch + 3*size, scratch, scratch + 5*size);
This is also looks a bit strange to me, but I don't have the background. If key represents a scalar k, and pub represents a point P = k G, where G is the generator (that's the usual relation between private and public key in ecc context), then we compute another point Q = u k P = u k^2 G, where u is the number represented by the ukm input. That square (k^2) looks a bit weird, maybe I'm misunderstanding. And if I have the math right, then it's probably more efficient to compute k^2 using ecc_mod_sqr and use ecc->mul_g (and then the pub input argument becomes unused).
I also wonder if this really has to be a new primitive, or if it could be implemented in terms of ecc_point_mul, or if we should provide an ecc_scalar_mul wrapping ecc_mod_mul (&ecc->q, ...) ?
It can be implemented using ecc_scalar_mul and ecc_point_mul (like GnuTLS does for ecc_shared_secret). But then cofactor will come to play, so it is much easier to hide this behind API function.
+void +test_main (void) +{
- struct streebog256_ctx ctx_256;
- struct streebog256_ctx ctx_512;
- test_vko(nettle_get_gost_gc512a(),
"67b63ca4ac8d2bb32618d89296c7476dbeb9f9048496f202b1902cf2ce41dbc2f847712d960483458d4b380867f426c7ca0ff5782702dbc44ee8fc72d9ec90c9","51a6d54ee932d176e87591121cce5f395cb2f2f147114d95f463c8a7ed74a9fc5ecd2325a35fb6387831ea66bc3d2aa42ede35872cc75372073a71b983e12f19","793bde5bf72840ad22b02a363ae4772d4a52fc08ba1a20f7458a222a13bf98b53be002d1973f1e398ce46c17da6d00d9b6d0076f8284dcc42e599b4c413b8804",SHEX("1d 80 60 3c 85 44 c7 27"),&nettle_streebog256,&ctx_256,SHEX("c9 a9 a7 73 20 e2 cc 55 9e d7 2d ce 6f 47 e2 19 2c ce a9 5f a6 48 67 05 82 c0 54 c0 ef 36 c2 21"));What's the source of these test vectors?
RFC 7836, adding reference.
Hello,
вт, 14 апр. 2020 г. в 21:45, Niels Möller nisse@lysator.liu.se:
Hi, at last I've had a closer look at this patch you posted mid February.
On the second consideration this patch depends on https://git.lysator.liu.se/nettle/nettle/-/merge_requests/6, which also was never reviewed. So let's drop it for now. You probably won't like so many changes for the release.
nettle-bugs@lists.lysator.liu.se
-
dbaryshkov＠gmail.com -
Dmitry Baryshkov
-
nisse＠lysator.liu.se