Re: [PATCH v4 3/4] Add GOST DSA according to GOST R 34.10-2001/-2012

Hello,

чт, 16 янв. 2020 г. в 21:36, Niels Möller nisse@lysator.liu.se:

...

From: Dmitry Eremin-Solenikov dbaryshkov@gmail.com

Add GOST Digital Signature Algorithms support according to GOST R 34.10-2001/-2012. English translations of these standards are provided as RFC 5832 and RFC 7091.

I've merged the first two patches to a branch ecc-gost. A few comments on the signature implementation.

Thank you!

...

+void +ecc_gostdsa_sign (const struct ecc_curve *ecc,

•         const mp_limb_t *zp,
  

•         const mp_limb_t *kp,
  

•         size_t length, const uint8_t *digest,
  

•         mp_limb_t *rp, mp_limb_t *sp,
  

•         mp_limb_t *scratch)
  

+{ +#define P scratch +#define hp (scratch + 4*ecc->p.size) +#define tp (scratch + 2*ecc->p.size) +#define t2p scratch

• /* Procedure, according to GOST 34.10. q denotes the group

• order.
  

• 1. k <-- uniformly random, 0 < k < q
  

• 2. C <-- (c_x, c_y) = k g
  

• 3. r <-- c_x mod q
  

• 4. s <-- (r*z + k*h) mod q.
  

• */

So no modular inversion in the signature operation? That's an improvement over NIST's DSA and ECDSA.

exactly.

...

diff --git a/ecc-gostdsa-verify.c b/ecc-gostdsa-verify.c new file mode 100644 index 000000000000..4358132b2bf6 --- /dev/null +++ b/ecc-gostdsa-verify.c +/* FIXME: Use faster primitives, not requiring side-channel silence. */ +int +ecc_gostdsa_verify (const struct ecc_curve *ecc,

•           const mp_limb_t *pp, /* Public key */
  

•           size_t length, const uint8_t *digest,
  

•           const mp_limb_t *rp, const mp_limb_t *sp,
  

•           mp_limb_t *scratch)
  

+{

• /* Procedure, according to GOST R 34.10. q denotes the group

• order.
  

• 1. Check 0 < r, s < q.
  

• 2. v <-- h^{-1}  (mod q)
  

• 3. z1  <-- s * v (mod q)
  

• 4. z2  <-- -r * v (mod q)
  

• 5. R = u1 G + u2 Y
  

• 6. Signature is valid if R_x = r (mod q).
  

• */

+#define hp (scratch) +#define vp (scratch + ecc->p.size) +#define z1 (scratch + 3*ecc->p.size) +#define z2 (scratch + 4*ecc->p.size)

+#define P1 (scratch + 4*ecc->p.size) +#define P2 (scratch)

• if (! (ecdsa_in_range (ecc, rp)

•  && ecdsa_in_range (ecc, sp)))
  

• return 0;
• gost_hash (&ecc->q, hp, length, digest);
• if (mpn_zero_p (hp, ecc->p.size))
• mpn_add_1 (hp, hp, ecc->p.size, 1);
• /* Compute v */
• ecc->q.invert (&ecc->q, vp, hp, vp + 2*ecc->p.size);

Comment about faster primitives applies particularly to this modular inversion. Using mpn_gcdext, which isn't side-channel silent, is likely significantly faster (but a bit different interface). Would be interesting to add to hogweed-benchmark, to compare to other ecc signatures.

I'll take a look at this later.

...

diff --git a/ecc-hash.c b/ecc-hash.c index 4e830a514ac4..07877110263f 100644 --- a/ecc-hash.c +++ b/ecc-hash.c @@ -62,3 +62,14 @@ ecc_hash (const struct ecc_modulo *m, /* We got a few extra bits, at the low end. Discard them. */ mpn_rshift (hp, hp, m->size + 1, 8*length - m->bit_size); }

+void +gost_hash (const struct ecc_modulo *m,

•    mp_limb_t *hp,
  

•    size_t length, const uint8_t *digest)
  

+{

• if (length > ((size_t) m->bit_size + 7) / 8)
• length = (m->bit_size + 7) / 8;
• mpn_set_base256_le (hp, m->size + 1, digest, length);

+}

It looks a bit strange to truncate the digest in this function, but I see that's the same as ecc_hash just above. Do you need to also handle the case of left-over bits, 8*length > m->bit_size?

Technically there should be no need to truncate, as the standard enforces using specific hash functions. I've copied this from ecc_hash just to be on a safe side.

Are the details very specific to gost, or could the helper be renamed ecc_hash_le ?

Just there is no point in doing hash_le for the generic ecc case.

What are typical values of length, compared to the prime size?

256-bit curve, 256-bit prime, 256-bit hash function 512-bit curve, 512-bit prime, 512-bit hash function

...

--- /dev/null +++ b/gostdsa.h @@ -0,0 +1,102 @@

[...]

...

+/* Development of Nettle's ECC support was funded by the .SE Internet Fund. */

Left-over note?

Oops, dropped in v5.

...

diff --git a/testsuite/testutils.h b/testsuite/testutils.h index f4ea38da9deb..cef7f4011a7c 100644 --- a/testsuite/testutils.h +++ b/testsuite/testutils.h @@ -22,6 +22,7 @@ # include "ecc.h" # include "ecc-internal.h" # include "ecdsa.h" +# include "gostdsa.h" # include "gmp-glue.h" # if NETTLE_USE_MINI_GMP # include "knuth-lfib.h"

Drop include, if nothing in testutils.h or testutils.c need gostdsa types.

Done.