Subject: Re: [Cfrg] Elliptic Curves - poll on security levels (ends on February 17th)

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Tue, 10 Feb 2015 17:20:59 +0300

Q1: No.
Q2: Yes.

For Q2: for Russia it is of primary importance that the curve is strictly
512-bit, not 521-bit.

Best regards,
Stanislav Smyshlyaev

Alexey Melnikov:

> CFRG chairs are starting a poll, containing 2 initial questions:
>
> Q1: Should CFRG recommend a curve at the 192-bit security level?
>
> Q2: Should CFRG recommend a curve at the 256-bit security level?
>
> Answering Yes/No to each of these would suffice.
>
> Once this first set of issues is resolved, we will move to choices of prime
> at the selected security level(s), if any. After that we will be
> discussing implementation specifics and coordinate systems for
> Diffie-Hellman. We will then make decisions on signature schemes.
> Please don't discuss any of these future topics at this time.
>
>
>

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Tue, 10 Feb 2015 12:46:21 -0500

> For Q2: for Russia it is of primary importance that the curve is strictly

Can you elaborate on why this is of primary importance?  If a 521-bit
curve is as performant, what would cause you to reject it? 

        --dkg

---

From: Станислав Смышляев <[email-masked]>
Date: Tue, 10 Feb 2015 23:15:09 +0400

Dear Daniel,

the Russian digital signature standard strictly requires that the order of the prime subgroup of a curve either lies between 2^(254) and 2^(256) or lies between 2^(508) and 2^(512) - and one won't generate a curve with a cofactor of 512 (=2^(521-512)). 

Best regards,
Stanislav Smyshlyaev

> 10 февр. 2015 г., в 21:46, Daniel Kahn Gillmor <[email-masked]> написал(а):
>

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Tue, 10 Feb 2015 17:49:44 -0500

On Tue 2015-02-10 14:15:09 -0500, Станислав Смышляев wrote:

> the Russian digital signature standard strictly requires that the
> order of the prime subgroup of a curve either lies between 2^(254) and
> 2^(256) or lies between 2^(508) and 2^(512) - and one won't generate a
> curve with a cofactor of 512 (=2^(521-512)).

This feels a bit like begging the question to me: without more
explanation, saying the "Russian digital signature standard strictly
requires" still seems arbitrary.  Does the Russian digital signature
standard provide an explicit rationale for the upper bound?

Maybe more detail would be useful:

Will there be systems unable to adopt new recommended curves at that
security level because of a larger group?  how many?  what sorts of
systems?  Which Russian digital signature standard exactly?  Can you
provide a pointer so that people unfamiliar with it can see what the
constraints are themselves?

How much will the Russian Digital Signature standard need to be updated
to allow the use of any new curves?  If it needs to be updated anyway,
could it be also updated to allow 521-bit curves if we manage to get a
rough consensus from other participants?

By comparison, the NIST folks (from the US gov't) seem open to
considering new curves in the near future.  Is that flexibility
something that the agency governing the standards in question can also
provide?

I think we can take your concerns into better consideration (and we can
make better decisions as a group) the more details we know about these
constraints.

        --dkg

---

From: David Leon Gil <[email-masked]>
Date: Wed, 11 Feb 2015 00:52:52 +0000

With respect to both questions: No.

The CFRG has already had ample opportunity to display its utility.

In addition, it seems very likely that additional academic research will be
done as a result of various other standards bodies' interest in this topic.

It would therefore be premature for CFRG to take any action on a
high-security-strength curve, even if it were at all plausible it was
capable of taking any.

David Leon Gil
Yahoo

(Sending from my Google account because the CFRG listserv forges From:
headers. Pace DMARC deniers.)
On Tue, Feb 10, 2015 at 2:50 PM Daniel Kahn Gillmor <[email-masked]>
wrote:

> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg
>

---

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Wed, 11 Feb 2015 10:02:26 +0300

Dear Daniel,

there is a draft of the new Russian digital signature standard GOST R
34.10-2012 in English:
https://tools.ietf.org/html/draft-dolmatov-gost34102012-00. Also the
previous standard (there are only two major differences between standards:
distinct hash functions and available key sizes) is included in ISO/IEC
14888-3:2006/Amd.1:2010(en) Information technology — Security techniques —
Digital signatures with appendix — Part 3: Discrete logarithm based
mechanisms AMENDMENT 1: Elliptic Curve Russian Digital Signature Algorithm,
Schnorr Digital Signature Algorithm, Elliptic Curve Schnorr Digital
Signature Algorithm, and Elliptic Curve Full Schnorr Digital Signature
Algorithm.

If there is a need of any comments to these two documents, I will be glad
to provide them.

Best regards,

Stanislav V. Smyshlyaev, Ph.D.,

Head of Information Security Department,

CryptoPro LLC

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Wed, 11 Feb 2015 10:24:03 -0500

On Wed 2015-02-11 02:02:26 -0500, Stanislav V. Smyshlyaev wrote:

> https://tools.ietf.org/html/draft-dolmatov-gost34102012-00.

It looks to me like this is now RFC 7091.

> Also the previous standard (there are only two major differences
> between standards: distinct hash functions and available key sizes

the previous standard was translated in english as RFC 5832, i think.
here are the sections about parameters restrictions:

https://tools.ietf.org/html/rfc7091#section-5.2

https://tools.ietf.org/html/rfc5832#section-5.2

As i read them, the constraints are in two places:

 a) the fixed-bit-length "Binary vectors" key representations (section
    5.3) of either exactly 512 bits or 1024 bits, which appear to be
    concatenations of big-endian values of X and Y coordinates.

 b) equation (9):

   | m = nq, n belongs to Z, n >= 1
   |                                                                 (9)
   | 2^254 < q < 2^256 or 2^508 < q < 2^512

Constraint (a) does seem to rule out 521-bit values which would cause
interoperability issues with systems that have adopted this standard,
but only constraint (b) rules out in-between choices like Goldilocks.

The main change from 2001 to 2012 is the addition of the 512-bit level
to this standard; how many systems support the 512-bit level with
arbitrary curves today?  what sort of work needs to be done to enable
those systems to use a novel curve?  Do implementations actually verify
equation (9) dynamically when confronted with a new curve, or could
points from an intermediate curve left-padded with zeros satisfy the
binary vector representation requirement and move forward with these
implementations?

Could the Federal Agency on Technical Regulating and Metrology consider
issuing another revision add a new level (either intermediate or above
512) if there was a broader consensus about it?

     --dkg

---

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Wed, 11 Feb 2015 18:40:48 +0300

Dear Daniel,

thank you for the link: indeed, the draft GOST R 34.10-2012 has been
already finalized and now is RFC 7091.

In Russia 512-bit curves are not still widely used for everyday document
processing, but a lot of cryptography software and hardware already support
512-bit level – I would say that it is possible to add a novel curve, but
it doesn't seem realistic to change standard (with its constraints) or all
implementations (most of them can't support curves with p>2^{512} or
q>2^{512}).

And at least for these reasons I don't think that our Federal Agency on
Technical Regulating and Metrology could expand possible set for q.

Thank you very much for your attention.

Regards,

Stanislav Smyshlyaev