Subject: [Cfrg] 512-bit twisted Edwards curve and curve generation methods in Russian standardization

From: Станислав Смышляев <[email-masked]>
Date: Tue, 27 Jan 2015 18:57:40 +0300

Good afternoon, dear colleagues,

Currently the proposed draft on elliptic curves generation methods does not
explicitly consider curves with security more than 256 bits.

In Russia we have had a similar lack of 512-bit curves (both twisted
Edwards ones and curves with groups of prime order), so we at CryptoPro
(Russian cryptographic software company) proposed three of them to our
Technical Committee for Standardization «Cryptography and Security
Mechanisms» (http://tc26.ru/en/).

In 2014 after a deep discussion with colleagues these curves were
standardized for usage with Russian national digital signature standard
(GOST R 34.10-2012).

For example, the twisted Edwards 512-bit curve is defined over the field
GF(p), where p is equal to 2^512 – 569, p = 3 (mod 4).

p =
0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFDC7

d =
0x9E4F5D8C017D8D9F13A5CF3CDF5BFE4DAB402D54198E31EBDE28A0621050439CA6B39E0A515C06B304E2CE43E79E369E91A0CFC2BC2A22B4CA302DBB33EE7550

e = 0x1

m =
0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF26336E91941AAC0130CEA7FD451D40B323B6A79E9DA6849A5188F3BD1FC08FB4

q =
0x3FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFC98CDBA46506AB004C33A9FF5147502CC8EDA9E7A769A12694623CEF47F023ED

u(P) = 0x12

v(P) =
0x469AF79D1FB1F5E16B99592B77A01E2A0FDFB0D01794368D9A56117F7B38669522DD4B650CF789EEBF068C5D139732F0905622C04B2BAAE7600303EE73001A3D

a =
0xDC9203E514A721875485A529D2C722FB187BC8980EB866644DE41C68E143064546E861C0E2C9EDD92ADE71F46FCF50FF2AD97F951FDA9F2A2EB6546F39689BD3

b =
0xB4C4EE28CEBC6C2C8AC12952CF37F16AC7EFB6A9F69F4B57FFDA2E4F0DE5ADE038CBC2FFF719D2C18DE0284B8BFEF3B52B8CC7A5F5BF0A3C8D2319A5312557E1

x(P) =
0xE2E31EDFC23DE7BDEBE241CE593EF5DE2295B7A9CBAEF021D385F7074CEA043AA27272A7AE602BF2A7B9033DB9ED3610C6FB85487EAE97AAC5BC7928C1950148

y(P) =
0xF5CE40D95B5EB899ABBCCFF5911CB8577939804D6527378B8C108C3D2090FF9BE18E2D33E3021ED2EF32D85822423B6304F726AA854BAE07D0396E9A9ADDC40F

(The following notation is used for Edwards curve coefficients: eu^2 + v^2
= 1 + du^2v^2, while the corresponding Weierstrass curve has form y^2 = x^3
+ ax +b. We denote the total number of points on the curve as m and prime
subgroup order as q. We denote base point as P; x(P), y(P) and u(P), v(P)
are respectively base point coordinates in Weierstrass and twisted Edwards
form.)

p and q are prime. The curve has been examined to be secure against
MOV-attacks (thus it can be believed to be DDH-secure) and to satisfy
CM-security requirements. Twisted curve security has also been studied:
twisted curve points group order has a prime factor of:
0x40000000000000000000000000000000000000000000000000000000000000003673245b9af954ffb3cc5600aeb8afd33712561858965ed96b9dc310b80fdaf7,
while the other factor is equal to 4.

The curve can be used both for digital signatures and for Diffie-Hellman
key agreement.

The curve parameters have been generated using random nonce W in such way
that e = 1, d = hash(W), where hash() is Russian national standard GOST R
34.11-2012 hash function (also known as “Streebog”,
https://www.streebog.net/en/). The seed value W is equal to:

W = 1F BB 79 69 B9 1B 3E A0 81 17 FB 10 74 BF BF 55 49 DD 66 07 63 F6 A5 AF
09 57 77 5B 66 4C B1 13 CF CB 91 C4 A7 7D 27 98 06 BC F2 4A 56 77 F2 5E AF
FE C6 67 76 70 2E E2 C7 AA 84 16 07 50 DA 1D D1 50 AE D2 8C 30 26 AC 7E D6
D1 9B 97 AC 2C B5 82 7C 00 03 18 47 13 53 5B FA 65 24 B3 E4 60 83,

GOST R 34.11-2012 (Streebog) implementation can be found at
https://github.com/okazymyrov/stribog, for example.

The base point has been selected as a point with the smallest u-coordinate,
satisfying curve equation and having order equal to q.

Also we have an agreed (with Russian cryptographic community, including
experts from other Russian companies, scientific community and governmental
authorities) version of curve generation methods; if you consider it
interesting, we could prepare an English translation in a couple of days.

Best regards,

Stanislav V. Smyshlyaev, Ph.D.,

Head of Information Security Department,

CryptoPro LLC

---

From: "Paterson, Kenny" <[email-masked]>
Date: Wed, 28 Jan 2015 10:32:29 +0000

Dear Stanislav,

Many thanks for sharing this detailed information.

In the current draft https://tools.ietf.org/html/draft-agl-cfrgcurve-00
(which CFRG has just adopted), we have a specific curve generation method
that is different from the one you outline below. It has taken the group
quite a bit of discussion to get to the point of having a rough consensus
that that method is one we want to use, and if we decide to produce a
higher security level curve (which I personally hope we will), then it
seems pretty likely that this method will be the one we select.

Perhaps I could encourage you to look at the current draft and engage with
the editors on it where you see fit? Note that the draft should be
evolving fairly rapidly in response to others' inputs and as we further
develop it to include signatures, higher security level curves, etc.

Regards,

Kenny (for the chairs)

On 27/01/2015 15:57, "Станислав Смышляев" <[email-masked]> wrote:

>Currently the proposed draft on elliptic curves generation methods does
>not explicitly consider curves with security more than 256 bits.
>
> 
>Technical
> Committee for Standardization «Cryptography and Security Mechanisms»
>(http://tc26.ru/en/).
> 
>0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
>FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFDC7
>d = 
>0x9E4F5D8C017D8D9F13A5CF3CDF5BFE4DAB402D54198E31EBDE28A0621050439CA6B39E0A
>515C06B304E2CE43E79E369E91A0CFC2BC2A22B4CA302DBB33EE7550
>e = 0x1
>m = 
>0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF26336E91
>941AAC0130CEA7FD451D40B323B6A79E9DA6849A5188F3BD1FC08FB4
>q = 
>0x3FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFC98CDBA4
>6506AB004C33A9FF5147502CC8EDA9E7A769A12694623CEF47F023ED
>u(P) = 0x12
>v(P) = 
>0x469AF79D1FB1F5E16B99592B77A01E2A0FDFB0D01794368D9A56117F7B38669522DD4B65
>0CF789EEBF068C5D139732F0905622C04B2BAAE7600303EE73001A3D
>a = 
>0xDC9203E514A721875485A529D2C722FB187BC8980EB866644DE41C68E143064546E861C0
>E2C9EDD92ADE71F46FCF50FF2AD97F951FDA9F2A2EB6546F39689BD3
>b = 
>0xB4C4EE28CEBC6C2C8AC12952CF37F16AC7EFB6A9F69F4B57FFDA2E4F0DE5ADE038CBC2FF
>F719D2C18DE0284B8BFEF3B52B8CC7A5F5BF0A3C8D2319A5312557E1
>x(P) = 
>0xE2E31EDFC23DE7BDEBE241CE593EF5DE2295B7A9CBAEF021D385F7074CEA043AA27272A7
>AE602BF2A7B9033DB9ED3610C6FB85487EAE97AAC5BC7928C1950148
>
>y(P) = 
>0xF5CE40D95B5EB899ABBCCFF5911CB8577939804D6527378B8C108C3D2090FF9BE18E2D33
>E3021ED2EF32D85822423B6304F726AA854BAE07D0396E9A9ADDC40F
>(The following notation is used for Edwards curve coefficients: eu^2 +
>v^2 = 1 + du^2v^2, while the corresponding Weierstrass curve has form y^2
>= x^3 + ax +b. We denote the total number of points on the curve as m and
> prime subgroup order as q. We denote base point as P; x(P), y(P) and
>u(P), v(P) are respectively base point coordinates in Weierstrass and
>twisted Edwards form.)
> 
>twisted
> curve points group order has a prime factor of:
>0x40000000000000000000000000000000000000000000000000000000000000003673245b
>9af954ffb3cc5600aeb8afd33712561858965ed96b9dc310b80fdaf7, while the other
>factor is equal to 4.
> 
>W = 1F BB 79 69 B9 1B 3E A0 81 17 FB 10 74 BF BF 55 49 DD 66 07 63 F6 A5
>AF 09 57 77 5B 66 4C B1 13 CF CB 91 C4 A7 7D 27 98 06 BC F2 4A 56 77 F2
>5E AF FE C6 67 76 70 2E E2 C7 AA 84 16 07 50 DA 1D D1 50 AE D2 8C 30 26
> AC 7E D6 D1 9B 97 AC 2C B5 82 7C 00 03 18 47 13 53 5B FA 65 24 B3 E4 60
>83,
> 
>The base point has been selected as a point with the smallest
>u-coordinate, satisfying curve equation and having order equal to q.
> 
>experts from other Russian companies, scientific community and
>governmental authorities) version of curve generation methods; if you
>consider it

---

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Wed, 28 Jan 2015 15:13:28 +0400

Dear Kenny,

Thank you very much for your letter. We'll prepare and send our comments
for the current draft as soon as possible.

Best regards,

CryptoPro LLC

---

From: Alyssa Rowan <[email-masked]>
Date: Wed, 28 Jan 2015 13:28:05 +0000

On 27 January 2015 15:57:40 GMT+00:00, "Станислав Смышляев" <[email-masked]> wrote:

>The curve parameters have been generated using random nonce W in such way that e = 1, d = hash(W), where hash() is Russian national standard GOST R 34.11-2012 hash function (also known as “Streebog”, https://www.streebog.net/en/). The seed value W is equal to:
>W = 1F BB 79 69 B9 1B 3E A0 81 17 FB 10 74 BF BF 55 49 DD 66 07 63 F6 A5 AF 09 57 77 5B 66 4C B1 13 CF CB 91 C4 A7 7D 27 98 06 BC F2 4A 56 77 F2 5E AF FE C6 67 76 70 2E E2 C7 AA 84 16 07 50 DA 1D D1 50 AE D2 8C 30 26 AC 7E D6 D1 9B 97 AC 2C B5 82 7C 00 03 18 47 13 53 5B FA 65 24 B3 E4 60 83,

...and the million-rouble question, if I may be the first to ask:

How was that seed W generated, and under what criteria?

There is now a strong preference for open curve generation processes whose criteria are all explicitly shown, chosen for clearly-defined "rigid" reasons, and whose generation can be replicated and verified.

I can't see the procedure you show here has that property, due to the unexplained seed; a property it shares with the US standard NIST curves we've been asked to replace, so I'm not too sure as to the merits of your curve?

- --
/akr

---

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Wed, 28 Jan 2015 18:14:43 +0400

Dear Alyssa,

As we believe (and as it has been mentioned earlier during discussion at
CFRG), the initital seed value doesn't have to be chosen explicitly in case
of trust in basic hash function properties – to gain some "backdoor-type"
properties of the curve with d = hash(W), one has either to combine such
algebraic properties of a curve with properties of a hash function (for a
trivial example, to have an ability to obtain a hash preimage) or to choose
a very probable "backdoor-type" property of a curve (such that it is
possible to obtain by random choice of a curve).

We believe that there really cannot be a higher level of "proven
randomness" than using d with a known hash preimage (regarding to
properties of hash function, of course).

The only one option to get a "backdoored" curve with our method that I
understand is the existence of some large publicly unknown class of "bad"
("backdoored", subverted) curves. But if such a class exists, who can
guarantee that any of your generated curves doesn't belong to this class?..

P.S.:
Nevertheless, for that exact twisted Edwards curve we have also a preimage
value of first 512 bits of W (we did this only to organize process of
candidate curve generation in parallel, without too much need also though),
but I had to mention this (pretty useless) fact.

Best regards,
Stanislav V. Smyshlyaev, Ph.D.,
Head of Information Security Department, CryptoPro LLC

2015-01-28 16:28 GMT+03:00 Alyssa Rowan <[email-masked]>:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA512
>
> AF 09 57 77 5B 66 4C B1 13 CF CB 91 C4 A7 7D 27 98 06 BC F2 4A 56 77 F2 5E
> AF FE C6 67 76 70 2E E2 C7 AA 84 16 07 50 DA 1D D1 50 AE D2 8C 30 26 AC 7E
> D6 D1 9B 97 AC 2C B5 82 7C 00 03 18 47 13 53 5B FA 65 24 B3 E4 60 83,
>
> There is now a strong preference for open curve generation processes whose
> criteria are all explicitly shown, chosen for clearly-defined "rigid"
> reasons, and whose generation can be replicated and verified.
>
> I can't see the procedure you show here has that property, due to the
> unexplained seed; a property it shares with the US standard NIST curves
> we've been asked to replace, so I'm not too sure as to the merits of your
> curve?
>
> - --
> /akr
> -----BEGIN PGP SIGNATURE-----
> Version: APG v1.1.1
>
> iQI3BAEBCgAhBQJUyOPlGhxBbHlzc2EgUm93YW4gPGFrckBha3IuaW8+AAoJEOyE
> jtkWi2t6rbAP/0/Cz+7r1IIf8spVLUVeAxtrgdsuKvtRt6Dpz5vkNiiS/pwRXpVF
> /70MbeBQA4M2ak7enzYGnRI/I2hGAv6nV6ybTwwnPDjq33iBS6F16sV7KsBaLRcy
> 7KmUTYKIT7oTncTWTDO0zlgo2k+/Hy1G/ChmnOLBFH6peKSwgt8OJgEPe0rZbg8E
> pTukrmr8lDw18MiGPhoqnj7Ug46ydJhqqZkP0aT3xtSF8Y+lVEpn7O36QV03QnAU
> d/0oQCQHkHJBfcI9w2W6tiyI6iHFH40U3c78kdASLdWjHyOfYZ/P00BasQudWcvD
> kgqYVGrZMXkrIQvn1JnMt5PD5Wl+XN6/6csAkeUOBr9oTwwWnX9xmvT+Ly14TFw2
> fw5/WaMKYht9K//qPh0hQLHCZuG0NEx/0pcoTTgYSGyXOIlAx19gDSbybmd/+ssj
> 9/ttSN+t9eENghr1IcXRMCrPcxbwnQRS2dQYGzCmqohf0ZS3DIzYAI2ChMT5eLNl
> lD9iSluaf7ss2/qlzwu+4kw25qDR/JwgKL8gmC0jhDE1ID4e8P4/ovpj3EwlW47S
> 2tRBD1XhRR0L1ZLiA5za+LLHPg9kUgFVnZ9kMhpm0ATE/bZzAujwFG1rlHmhLxiC
> RsU3euvrcb8QPcdLkNLunoCv71QSiCyABeUIG0jFKdU+oA4VoTkP+LWV
> =BuQY
> -----END PGP SIGNATURE-----
>
>

---

From: Tony Arcieri <[email-masked]>
Date: Wed, 28 Jan 2015 09:22:16 -0800

> possible to obtain by random choice of a curve).

Hi Stanislav,

Dan Bernstein and Tanja Lange have already demonstrated that such
"verifiably random" generation procedures can be used to surreptitiously
tweak specific curve parameters:

http://safecurves.cr.yp.to/bada55.html

I for one would not feel particularly inclined to trust a curve generated
with this method, and would personally prefer the sort of rigid curve
generation approach that this committee and others have been working on to
any curve with large unexplained mystery constants.

-- 
Tony Arcieri

---

From: Paul Hoffman <[email-masked]>
Date: Wed, 28 Jan 2015 09:33:22 -0800

On Jan 28, 2015, at 9:22 AM, Tony Arcieri <[email-masked]> wrote:
> Dan Bernstein and Tanja Lange have already demonstrated that such "verifiably random" generation procedures can be used to surreptitiously tweak specific curve parameters:
> 

That is a huge overstatement of what they showed. They showed that if a group of people with a common interest pick the form for the verifiably random value, they can tweak parameters. There are obvious procedures that prevent the number being chosen by such a group, and instead have the number chosen by a group where even if a single person is trusted, the randomness is trusted.

> I for one would not feel particularly inclined to trust a curve generated with this method, and would personally prefer the sort of rigid curve generation approach that this committee and others have been working on to any curve with large unexplained mystery constants.

If there were no downside to using a trustable random number, we could use one, but it seems that there are performance penalties and difficulty to make such calculations constant-time (if I understand earlier arguments correctly).

--Paul Hoffman

---

From: Watson Ladd <[email-masked]>
Date: Wed, 28 Jan 2015 09:36:14 -0800

This prime is not as fast on many platforms as p=2^521-1. Why was it
selected?

> (The following notation is used for Edwards curve coefficients: eu^2 +
v^2 = 1 + du^2v^2, while the corresponding Weierstrass curve has form y^2 =
x^3 + ax +b. We denote the total number of points on the curve as m and
prime subgroup order as q. We denote base point as P; x(P), y(P) and u(P),
v(P) are respectively base point coordinates in Weierstrass and twisted
Edwards form.)
key agreement.
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg
>

---

From: Tony Arcieri <[email-masked]>
Date: Wed, 28 Jan 2015 09:36:57 -0800

On Wed, Jan 28, 2015 at 9:33 AM, Paul Hoffman <[email-masked]> wrote:

> That is a huge overstatement of what they showed.

No it isn't. Unless these numbers are justified they can be poisoned.

> They showed that if a group of people with a common interest pick the form
> for the verifiably random value, they can tweak parameters. There are
> obvious procedures that prevent the number being chosen by such a group,
> and instead have the number chosen by a group where even if a single person
> is trusted, the randomness is trusted.
>

I guess you're probably talking about Brainpool? I guess the Brainpool
numbers are probably ok? But why use this sort of process at all? It just
provides an avenue for suspicion.

-- 
Tony Arcieri

---

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Wed, 28 Jan 2015 21:45:58 +0400

For a very simple reason – our Russian GOST signature standard has a
requirement for q: q must be either 2^254<q<2^256 or 2^508<q<2^512, where q
is the order of a cyclic subgroup.

Best regards,

Stanislav

2015-01-28 20:36 GMT+03:00 Watson Ladd <[email-masked]>:

> > The curve parameters have been generated using random nonce W in such
> way that e = 1, d = hash(W), where hash() is Russian national standard GOST
> R 34.11-2012 hash function (also known as “Streebog”,

---

From: Paul Hoffman <[email-masked]>
Date: Wed, 28 Jan 2015 09:58:51 -0800

> No it isn't. Unless these numbers are justified they can be poisoned.

Please define "justified".

>  
> They showed that if a group of people with a common interest pick the form for the verifiably random value, they can tweak parameters. There are obvious procedures that prevent the number being chosen by such a group, and instead have the number chosen by a group where even if a single person is trusted, the randomness is trusted.
> 
> I guess you're probably talking about Brainpool?

No.

> I guess the Brainpool numbers are probably ok?

I don't.

> But why use this sort of process at all? It just provides an avenue for suspicion.

Right, so don't say that I'm using that sort of process. As I said, there are many ways to hold a process that comes out with a trustable random number. Brainpool isn't that.

--Paul Hoffman

---

From: Alyssa Rowan <[email-masked]>
Date: Wed, 28 Jan 2015 18:04:28 +0000

On 28/01/2015 14:14, Stanislav V. Smyshlyaev wrote:

> …one has either to combine such algebraic properties of a curve
> with properties of a hash function (for a trivial example, to have
> an ability to obtain a hash preimage) or to choose a very probable 
> "backdoor-type" property of a curve (such that it is possible to 
> obtain by random choice of a curve).

Even a _partial_ second-preimage presents a significant problem here,
which is the big problem with the SEC1/NIST approach - and unless I'm
misunderstanding of course, the one you've taken?

A simple brute force partial second-preimage search lets you cook a
seed which yields a hash (even with a theoretical perfect hash
function) with as many bits as you can brute-force (64, no problem;
70-80, maybe for some?), and thus covertly select curves with
properties one desires (and perhaps, which we don't desire!) even down
to, say, p=1/(2^63).

Now I wouldn't characterise those properties as "very probable" to
occur by random chance at all, or indeed a large class - but it's
definitely a totally feasible condition to force for anyone who gets
to freely choose the seed.

That's why our draft rigid generation process doesn't use seeds - and
why anyone who does use seeds needs to be incredibly careful to the
extent to which anyone _can_ choose them (BADA55 being a demonstration
that a 'verifiably pseudo-random' process needs to be careful too, as
the mere choice of primitives and constants in the process may allow
enough of a degree of freedom to affect the outcome to force a
one-in-a-million choice).

So… who did choose W? Or, if W is a hash output itself, who chose the
seed for that? (The attack still works on iterated hash functions.)

- -- 
/akr

---

From: Tony Arcieri <[email-masked]>
Date: Wed, 28 Jan 2015 10:04:13 -0800

> Please define "justified".

I can give a couple examples of the opposite:

- The NIST curves
- This thread

> Right, so don't say that I'm using that sort of process. As I said, there
> are many ways to hold a process that comes out with a trustable random
> number. Brainpool isn't that.

Yeah, wasn't trying to suggest Brainpool did something that makes it
significantly better than the above.

-- 
Tony Arcieri

---

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Thu, 29 Jan 2015 12:08:29 +0400

I totally understand that a property that occurs with 2^{-18} (as Bernstein
did with BADA55 curves) can be forced to exist in the selected curve. The
example that I posted earlier is the specific curve that is standardized in
Russia, by a group of experts where the condition mentioned by Paul ("a
group where even if a single person is trusted") is satisfied ("trusted"
for us, not for the international community and CFRG, I suppose).

When we generated our curves and fixed base points, the main problem that
we addressed was to ensure that for all protocols that make use of elliptic
curves and require "provably unknown" logarithms of some points (for
example, password protected key establishment, PAKE, EKE, PACE, etc.) can
obtain such a property: x-coordinates of base points and constant points
for prototocols are chosen by hashing some random seeds – we don't want
only a blind belief of randomness of such points (the most painful example
here is Dual EC DRBG, of course). We look at curve generation problem in a
similar way: we cannot be secure against the unknown bad properties of
curves that occur with probability of 2^{-18} – even if the procedure is
totally "rigid". But at least we can be sure that if some bad property of
our curves is found, we would know that this couldn't be a "backdoor" that
can be exploited only by developers of the curve, who know some logarithms,
preimages etc. (again, as with DUAL EC DRBG).

If to talk about new curves for CFRG document, the usage of deterministic
("rigid") procedure is quite reasonable, we agree here. We've posted our
curve because we think that it can be interesting for CFRG to look at one
of the curves that have been standardized for all Russian cryptographic
community. We'll post some specific comments to the current draft later
today.

​Best regards,

---

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Thu, 29 Jan 2015 14:06:06 +0400

Hello, Tony,

> I totally understand that a property that occurs with 2^{-18} (as
Bernstein did with BADA55 curves) can be forced to exist in the selected
curve. The example that I posted earlier is the specific curve that is
standardized in Russia, by a group of experts where the condition mentioned
by Paul ("a group where even if a single person is trusted") is satisfied
("trusted" for us, not for the international community and CFRG, I suppose).

("rigid") procedure is quite reasonable, we agree here. We've posted our
curve because we think that it can be interesting for CFRG to look at one
of the urves that have been standardized for all Russian cryptographic
community. We'll post some specific comments to the current draft later
today.

We know about BADA55 curves, we tried to explain our position on them in my
reply to Alyssa; for now I don't have anything to add. Anyway, thanks for
taking part in the discussion. We'll try to formulate our comments and
suggestions for the current draft later today.

Kind regards,

Stanislav

2015-01-28 20:22 GMT+03:00 Tony Arcieri <[email-masked]>:

> On Wed, Jan 28, 2015 at 6:14 AM, Stanislav V. Smyshlyaev <
> [email-masked]> wrote:
>

---

From: CodesInChaos <[email-masked]>
Date: Thu, 29 Jan 2015 16:24:41 +0100

On Thu, Jan 29, 2015 at 9:08 AM, Stanislav V. Smyshlyaev
<[email-masked]> wrote:
> by a group of experts where the condition mentioned by Paul ("a
> group where even if a single person is trusted") is satisfied

How did the generation process work?

When just hashing together input from trusted and untrusted sources,
the last source to pick their value can run a brute-force search, to
manipulate the output. Depending on the time and money restrictions on
that attacker, it should be possible to execute such an attack even if
weak curves were significantly rarer than 2^{18}. I'd guess somewhere
around 2^{-40} to 2^{-60} is in range for a powerful attacker.

If generation was done using a commitment followed by revealing the
inputs only after all participants commited, then this is indeed
random as long as at least one participant is honest.