Subject: Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid v Pseudorandom

From: Dan Brown <[email-masked]>
Date: Mon, 13 Jan 2014 23:07:51 +0000

Watson,

I had requested to keep this thread focused, specifically in the impact pseudorandom v rigid on security, but you declined to engage. Is it that you think this security issue unimportant, even though you concede with my narrow point?

Instead, you mostly repeated the general speed and side channel benefits of Chicago, which I was not yet disputing.

Also, you suggested that I was referring to the field choices. I did not intend to, but I should clarify.

For a given field, pseudorandom curve better resists secret attacks than rigidity.

Field size would on my list of issues, but way, way down on my ranking of importance.

A couple people have suggested to me (off list) to generate new curves with explainable seeds but the same fields as NIST curves.

The result would seem to be intermediate between Brainpool and Chicago.

My main reluctance with that would further babble, and yet more difficulty with interoperability.

From: Watson Ladd
Sent: Monday, January 13, 2014 4:26 PM
To: Dan Brown
Cc: [email-masked]
Subject: Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid v Pseudorandom

On Mon, Jan 13, 2014 at 8:55 AM, Dan Brown <[email-masked]> wrote:
>
> Last week I wrote that I would soon write up my disagreements with the safe curves site.
>
>
>
> My first disagreement is written up below, but first two editorial issues:
>
>
>
> - My last email was in the context of Watson’s draft spec for the Chicago (Bernstein?) curves, but I would like to detach the issue from the I-D. My comment about the reference in Watson’s I-D to a website was just an editorial comment.
>
>
>
> - These technical issues that I hope CFRG discusses just might be resolved and written into a CFRG I-D cataloging of elliptic curves and their relative merits and so on, which should be independent of Watson’s spec for the Chicago curves. For now, I opted to discuss via email list, rather than placing these arguments into my own one-sided individual I-D. Please advise me if such an I-D is preferred to email.

I think this is an excellent idea (the catalogue of good curves).

>
>
>
> Today, I checked that
>
>
>
> http://safecurves.cr.yp.to/rigid.html
>
> <snip>

Rather then engage a peripheral argument, let me lay out the case for
the Chicago curves (named after the city in which Bernstein resides,
and in a long IETF tradition starting with TCP Reno, Oakley key
agreement protocol, and fundamentally of no import: see Shakespeare,
Romeo and Juliet, Act 2, Scene 2, or Wittgenstein, Philosophical
Investigations for more information) in the fairest light.

First efficiency: point addition on an Edwards curve costs 11
multiplications, doubling 7 multiplications. This is for a complete,
strongly unified addition formula, which requires no work for special
cases. By contrast on a short Weierstrass curve addition costs 16
multiplications, doubling 8.
This is with no assumptions on Z, which if we impose reduce the cost
of addition on a short Weierstrass curve to 11 multiplications. But if
we impose the same condition on the Edwards curve, the cost is 10
multiplications.

However, I've forced the Edwards curve to represent the identity,
which if we are willing to drop, slices off two more multiplications.
By contrast the
Weierstrass curve has special cases that need additional work to
handle in a secure manner. Most people just don't bother. I also let
the Weierstrass form be special with a=-3, while keeping the Edwards
curve fully general.

So given the same prime Edwards has short Weierstrass beat. This is
true no matter what algorithm for exponentiation is used. And I even
gave short Weierstrass curves a handicap by letting them avoid
representing the entire curve and having exceptional cases, and fix
some parameters.

Montgomery form is even better: differential addition costs 10M, and
calculates a doubling for free. Sadly the differential part makes
radix-k algorithms tough, but in memory constrained environments (like
hardware) Montgomery form can't be beat. (And we haven't even used
nonuniform differential addition chains yet.. I'm still hopeful).

Then there is the prime shape: Brainpool uses a random prime, which is
a terrible idea from an efficiency perspective. NIST primes are sized
for 32 bit machines, and have some hiccups on 64 bit machines. But the
Chicago primes are primes for all seasons: 2^k-c with small c is nice
no matter what radix you adopt. Unsaturated arithmetic makes addition
faster because reductions aren't necessary at all times, and the
Chicago primes are good from that perspective.

Now security: having an efficient complete addition formula makes
writing timing, cache, and branch side channel free code a piece of
cake. By contrast short Weierstrass curves have all sorts of wrong
curve, or invalid point, or somewhere the calculation messes up
issues. Usually the defense is a final check on the result being on
the code, but that isn't the same as knowing that no attack is
possible because your code always generates the right answer.

Lastly, many websites want to deploy PFS ciphersuites but are deterred
by the computation expense involved. Minimizing that expense is
essential. In the wider IETF context we are catering to devices from
the lowly MSP430, to the latest and greatest supercomputer. What does
Brainpool let us do? We should stick to the NIST and Chicago curves:
NIST for those who require it, and Chicago for those who require the
extra speed.

I would like to hear good arguments against this position. Robert
Ransom I understand wants twisted Edwards curves for an extra bit of
speed, using isogenies to keep them the same as the Chicago curves,
but selecting only those with small parameters and particularly nice
prime shapes.
Dan Brown believes that the Brainpool primes are less special in a way
that has to do with ECC security, despite this never affecting ECC
before.

Sincerely,
Watson Ladd
---------------------------------------------------------------------
This transmission (including any attachments) may contain confidential information, privileged material (including material protected by the solicitor-client or other applicable privileges), or constitute non-public information. Any use of this information by anyone other than the intended recipient is prohibited. If you have received this transmission in error, please immediately reply to the sender and delete this information from your system. Use, dissemination, distribution, or reproduction of this transmission by unintended recipients is not authorized and may be unlawful.

---

From: Alyssa Rowan <[email-masked]>
Date: Tue, 14 Jan 2014 00:26:56 +0000

> For a given field, pseudorandom curve better resists secret

With respect, I disagree.

With zero knowledge of a hypothetical attack, we have zero knowledge
about what may, or may not, be affected by it.

A point to note here: brainpoolP256r1 has a _very_ weak twist
(ρ @ 2^44) - a practical problem only in a flawed implementation that
doesn't check for invalid points. But here nevertheless, we actually
have a curve generated in a documented pseudorandom manner, yet has at
least one desirable property distinctly less secure than all of its
tested peers.

Why? Bad luck, it seems.

I for one prefer sound, well-explained, reproducibly verifiable curve
design which resists all known attacks, to rolling the dice and hoping
it resists a hypothetical attack that we know nothing about.

Hence my preference for the "Safecurves" approach, and thus the
"Chicago" curves.

That some of them can be (and have been) implemented in an extremely
efficient way, and thus are exceptionally well-suited for the
important task of accelerating wide adoption of forward security in
internet protocols, I also find a highly desirable point in their
favour - as, it seems, do many others.

I can find no remotely compelling argument against them.

- -- 
/akr

---

From: Watson Ladd <[email-masked]>
Date: Mon, 13 Jan 2014 16:36:10 -0800

> I had requested to keep this thread focused, specifically in the impact pseudorandom v rigid on security, but you declined to engage. Is it that you think this security issue unimportant, even thou…

I think it's completely bogus. People aren't primarily interested in
the Chicago curves because of unknown attacks, but NSA cookery over
NIST+the efficiency and security benefits they offer.

> Instead, you mostly repeated the general speed and side channel benefits of Chicago, which I was not yet disputing.

You know, when it comes to speed there is a way to decide which is
faster: eBATS. And what eBATS says about P256 vs Curve25519 is not
good.
Want to argue about speed? Submit code. Want to argue about
multiplications? Get formulas into EFD.

Furthermore, what is your position on the question of ECC choices?
Instead of going around in circles of increasing irrelevance, let's
have it between these options:

0: Nothing
1: NIST
2: Brainpool
3: Chicago
4: NIST+Brainpool
5: Brainpool+Chicago
6: NIST+Chicago
7:NIST+Brainpool+Chicago

Each of these options has costs. Each has advantages. And I've not
even scratched the surface: maybe P256 stays, along with
Ed448-Goldilocks,
and P521. So far I think that 2 alone is terrible, 1 alone okay, 3
alone superior (but anything sans NIST is a nonstarter for DOD), so 6
seems good,
because no one will pick brainpool from 7.

> For a given field, pseudorandom curve better resists secret attacks than rigidity.

What about the known attacks which Brainpool implementations suffer
from? There still isn't a side-channel clean one
that gets correct answers all the time. Contrast with NIST and the new
curves. (Yes, we need to churn out some code, but
it's clear it can be done). I admire your persistence in
necroequoflagellation,  but as DJB observed the previous time
this came up, you've simply declared 486662 special, with no evidence
that the curve is actually special.
If you noticed a particularly unusual endomorphism, or an interesting
map to some other scheme, or the Q-lift having unusually
large rank, or an infinite Tate-Sharavich group, that would be reason
to worry or consider it special. But the coefficient being small?
What's so special about that?

> A couple people have suggested to me (off list) to generate new curves with explainable seeds but the same fields as NIST curves.

These people should not be listened to: the world does not need more
short Weierstrass curves. Pick rigid Edwards curves over the same
field, and make a small for speed. I understand the field
proliferation concern, particularly for hardware, but that's where a
lot of speed comes from: ask AGL or Rich Salz how much speed they want
to give up. We have Rich Salz on record as saying that Akamai is held
back from PFS by the CPU demand, and with Curve25519 that will be
solved. In software additional fields cost little.

> My main reluctance with that would further babble, and yet more difficulty with interoperability.

Interop solution: MTI. Odds are people will pick a hardness, and the
fastest thing that delivers that hardness will win out. Also,
make clear standards can exclude curves, even to the extent of picking
one and saying "This is it!". I think the majority of protocols where
performance in software is a concern and correctness of implementation
an issue should consider Curve25519 carefully, but I am not going to
argue that I know better than the communities around these protocols
what is appropriate for the hardware they are looking at running on
and the constraints they face. Some protocols will need to dispense
with choices because of these limitations I am going to argue that I
know cryptography better than they do in most cases, and that's how I
see this question: making a catalog of curves, where you can reach in
and go "Oh, this one has high software performance, acceptable
hardware performance, good security, useful for ECDH" or "This one is
great in hardware, ok in software, moderate security (and some
gotchas), all protocols" and make a choice easily.

Sincerely,
Watson Ladd

-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin

---

From: Michael Hamburg <[email-masked]>
Date: Mon, 13 Jan 2014 16:56:41 -0800

> NIST+the efficiency and security benefits they offer.

Speak for yourself.  I’m interested in a standard which has a better chance of resisting unknown attacks, and I’m not as concerned about NSA cookery as you are.

I agree that random (or pseudorandom) curves are preferable to rigid ones, so long as they are generated with the rest of the Safecurves properties.  The problem is, they are much harder to generate.  Maybe shake up some dice or Boggle boards at the CRYPTO rump session?  Or make a Bitcoin donation to EFF annotated with the hash of your software, and use the hash of its block?  Dunno.  The Brainpool method has too many degrees of freedom to convince everyone.

Either way, I feel that the highest practical ECC security level would come from a verifiably pseudorandom curve over a verifiably pseudorandom field.  This is because it will take either a significant mathematical breakthrough or a quantum computer to break existing 120s-ish-bit-secure curves such as Curve25519, anytime in the foreseeable future.  If it’s a quantum computer or a breakthrough that kills all curves, we’re screwed.

So that leaves a breakthrough which kills only curves with special properties, or only improves speed somewhat (eg, p^1/4 instead of p^1/2).  Given that, should we choose curves with known special properties that aren’t required for security?  (Small d, special fields?)  Or should we try to be as random as possible, constrained only by properties that have a good security argument?

The downsides are difficulty of generation, and speed: a random field would be at least twice as slow.  So if I had to take 3 next-gen curves to a desert island, I’d go for:

* Ed25519.  It’s deployed, it’s implemented, it’s significantly faster and easier to make secure than NIST P256.  There are other options, but this one works.  Once again, probably nobody is going to break this with a rho attack in the next couple of decades.

* Something with a bigger fast field.  Ed448-Goldilocks is my entry for that, but the others are also fine.  A pseudorandom $d$ value would probably improve things, if you could get confidence that it’s not rigged.  Whichever way this goes, ops on such a curve will take about 4x as long as Ed25519 in software.

* A pseudorandom curve over a pseudorandom 512-bit field.  Operations on such a curve will probably take at least 12x as long as Ed25519, and at least 16x if it’s a short Weierstrass curve.

In any case, if we list any pseudorandom curves, they should have most of the Safecurves properties except rigidity.  Some of the properties really aren’t necessary (eg, Elligator), and basically end up just requiring Edwards curves.  There’s a decent case that Edwards is a better shape than short Weierstrass anyway though, and in that case we should go for all the properties except rigidity.

Cheers,
— Mike

---

From: Paul Lambert <[email-masked]>
Date: Mon, 13 Jan 2014 17:21:51 -0800

> 7: NIST+Brainpool+Chicago
> 
> Each of these options has costs. Each has advantages. And I've not even
> scratched the surface: maybe P256 stays, along with Ed448-Goldilocks,
> seems good, because no one will pick brainpool from 7.

It's naïve to think that we can make 'choices' here in the CFRG or IETF.
I am not sure of your prior experience in the standards 
making process, but it is a consensus building effort that builds on
clear documentation.  The best we can do is to clearly document new
options and fairly show the potential benefits.

Individual products, industry consortiums, Governments may mandate
specific choices.  Even then, it is impossible to rapidly remove
any type of standard once fielded - even if there are clear security
problems (SHA-1, WEP, etc.)

There are no known significant attacks against the NIST/SECG curves,
only a fashionable suspicion of NIST and the NSA.  They will
be in use for a long time.  Fashion does have its place and
we do need to consider and document the real level of confidence
that we have as an industry in any algorithm.

Curves based on 'new ECC math' for Edwards curves shows significant
potential for more efficient and easier implementations (I include
side channel protection under easier implementations).  A major
challenge we have is to provide clarity that we are introducing new
math ways to make calculations on elliptic curves.  The Small
Weierstrass curves have been so dominate in literature and 
standards that they are described as 'the' elliptic curve.

I am very supportive of our introduction of these families of
new curves.  Speed and ease of correct/secure implementation
are significant benefits of the 'new math'.

So ... on choices, we can strongly recommend based on the benefits.
Suite B will live on for a long time based on the slow pace 
of Government initiatives.

Brainpool, the previous fashionable alternative seems less fashionable today.

Edwards based curves seem an optimal choice where new 
curves are able to be introduced. They are both fashionable (not NIST)
and have demonstrable benefits.

Now ... the current draft does seem confusing to me in this context on
benefits and clear curve recommendations.  There are a few too many and
we could trim or clarify when each would be used.

Paul

> from? There still isn't a side-channel clean one that gets correct
> answers all the time. Contrast with NIST and the new curves. (Yes, we
> need to churn out some code, but it's clear it can be done). I admire
> your persistence in necroequoflagellation,  but as DJB observed the
> previous time this came up, you've simply declared 486662 special, with
> no evidence that the curve is actually special.
> map to some other scheme, or the Q-lift having unusually large rank, or
> an infinite Tate-Sharavich group, that would be reason to worry or
> consider it special. But the coefficient being small?
> > A couple people have suggested to me (off list) to generate new
> curves with explainable seeds but the same fields as NIST curves.
> 
> field, and make a small for speed. I understand the field proliferation
> concern, particularly for hardware, but that's where a lot of speed
> comes from: ask AGL or Rich Salz how much speed they want to give up.
> We have Rich Salz on record as saying that Akamai is held back from PFS
> by the CPU demand, and with Curve25519 that will be solved. In software
> additional fields cost little.
> 
> >
> fastest thing that delivers that hardness will win out. Also, make
> clear standards can exclude curves, even to the extent of picking one
> and saying "This is it!". I think the majority of protocols where
> what is appropriate for the hardware they are looking at running on and
> the constraints they face. Some protocols will need to dispense with
> choices because of these limitations I am going to argue that I know
> cryptography better than they do in most cases, and that's how I see
> this question: making a catalog of curves, where you can reach in and
> go "Oh, this one has high software performance, acceptable hardware
> performance, good security, useful for ECDH" or "This one is great in
> hardware, ok in software, moderate security (and some gotchas), all
> protocols" and make a choice easily.
> 
> Sincerely,
> Watson Ladd
> 
> >
> >
> > From: Watson Ladd
> >> - My last email was in the context of Watson’s draft spec for the
> Chicago (Bernstein?) curves, but I would like to detach the issue from
> the I-D. My comment about the reference in Watson’s I-D to a website
> was just an editorial comment.
> >>
> >>
> >>
> >> - These technical issues that I hope CFRG discusses just might be
> resolved and written into a CFRG I-D cataloging of elliptic curves and
> their relative merits and so on, which should be independent of
> Watson’s spec for the Chicago curves. For now, I opted to discuss via
> email list, rather than placing these arguments into my own one-sided
> individual I-D. Please advise me if such an I-D is preferred to email.
> >
> >
> > This transmission (including any attachments) may contain
> confidential information, privileged material (including material
> protected by the solicitor-client or other applicable privileges), or
> constitute non-public information. Any use of this information by
> anyone other than the intended recipient is prohibited. If you have
> received this transmission in error, please immediately reply to the
> sender and delete this information from your system. Use,
> dissemination, distribution, or reproduction of this transmission by
> unintended recipients is not authorized and may be unlawful.
> 
> 
> 
> --
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg

---

From: Watson Ladd <[email-masked]>
Date: Mon, 13 Jan 2014 17:38:04 -0800

> standards that they are described as 'the' elliptic curve.

'New'. I'm sorry, but Montgomery form is from 1985.
Granted that's a century after Weierstrass form, but it actually
is contemporaneous with ECC being invented.

If the fact that the equations look different doesn't tip someone off
to the difference, I'm not sure what will. Do we need great big flashing
lights *this is not in short Weierstrass form*? And what does it say
about our implementors that they do not know the basics of the algorithms
they are asked to implement?

> we could trim or clarify when each would be used.

Feel free to make suggestions offlist. In fact, you can even submit diffs.

Sincerely,
Watson Ladd

---

From: Paul Lambert <[email-masked]>
Date: Mon, 13 Jan 2014 18:37:56 -0800

> > Weierstrass curves have been so dominate in literature and standards
> > that they are described as 'the' elliptic curve.
> 
> Granted that's a century after Weierstrass form, but it actually is
> contemporaneous with ECC being invented.

Not intended to be disparaging ... just true that they are new in standards.
I agree that the math has some history, but the standards
have been completely inbred with just Small Weierstrass equations.
Only point is that it's not the same jump of NIST to Brainpool 
(only tweaking a few domain parameters in an implementation).

There is a extra effort and diligence required to fill in the
gaps in our recommendations.

> to the difference, I'm not sure what will. Do we need great big
> flashing lights *this is not in short Weierstrass form*? And what does
> it say about our implementors that they do not know the basics of the
> algorithms they are asked to implement?
> 
> >
> > I am very supportive of our introduction of these families of new
> > curves.  Speed and ease of correct/secure implementation are
> > significant benefits of the 'new math'.
> >
> > Suite B will live on for a long time based on the slow pace of
> > Government initiatives.
> >
> > Edwards based curves seem an optimal choice where new curves are able
> > to be introduced. They are both fashionable (not NIST) and have
> > demonstrable benefits.
> >
> >
> > benefits and clear curve recommendations.  There are a few too many
> > and we could trim or clarify when each would be used.
> 
Perhaps ... after I get my implementation to work.

I'm having trouble understanding the literatures recommendations for multiplying ...

Paul

> 
> Sincerely,
> Watson Ladd
> >
> > Paul
> >
> >> >
> >> > Also, you suggested that I was referring to the field choices. I
> >> > did
> >> not intend to, but I should clarify.
> >> >
> >> > For a given field, pseudorandom curve better resists secret
> attacks
> >> than rigidity.
> >
> >
> >>
> >> previous time this came up, you've simply declared 486662 special,
> >> with no evidence that the curve is actually special.
> >> map to some other scheme, or the Q-lift having unusually large rank,
> >> or an infinite Tate-Sharavich group, that would be reason to worry
> or
> >> lot of speed comes from: ask AGL or Rich Salz how much speed they
> want to give up.
> >> We have Rich Salz on record as saying that Akamai is held back from
> >> PFS by the CPU demand, and with Curve25519 that will be solved. In
> >> software additional fields cost little.
> >>
> >> >
> >> performance in software is a concern and correctness of
> >> implementation an issue should consider Curve25519 carefully, but I
> >> am not going to argue that I know better than the communities around
> >> these protocols what is appropriate for the hardware they are
> looking
> >> at running on and the constraints they face. Some protocols will
> need
> >> to dispense with choices because of these limitations I am going to
> >> argue that I know cryptography better than they do in most cases,
> and
> >> that's how I see this question: making a catalog of curves, where
> you
> >> can reach in and go "Oh, this one has high software performance,
> >> acceptable hardware performance, good security, useful for ECDH" or
> >> "This one is great in hardware, ok in software, moderate security
> >> (and some gotchas), all protocols" and make a choice easily.
> >>
> >> Sincerely,
> >> Watson Ladd
> >>
> >> >
> >> >
> >> > From: Watson Ladd
> >> >> Last week I wrote that I would soon write up my disagreements
> with
> >> the safe curves site.
> >> >>
> >> >>
> >> >>
> >> >> My first disagreement is written up below, but first two
> editorial
> >> issues:
> >> >>
> >> >>
> >> >>
> >> Chicago (Bernstein?) curves, but I would like to detach the issue
> >> from the I-D. My comment about the reference in Watson’s I-D to a
> >> website was just an editorial comment.
> >> >>
> >> >>
> >> >>
> >> resolved and written into a CFRG I-D cataloging of elliptic curves
> >> and their relative merits and so on, which should be independent of
> >> > Rather then engage a peripheral argument, let me lay out the case
> >> > for the Chicago curves (named after the city in which Bernstein
> >> > resides, and in a long IETF tradition starting with TCP Reno,
> >> > Oakley key agreement protocol, and fundamentally of no import: see
> >> > Shakespeare, Romeo and Juliet, Act 2, Scene 2, or Wittgenstein,
> >> > Philosophical Investigations for more information) in the fairest
> light.
> >> >
> >> > multiplications, doubling 7 multiplications. This is for a
> >> > complete, strongly unified addition formula, which requires no
> work
> >> > for special cases. By contrast on a short Weierstrass curve
> >> > addition costs 16 multiplications, doubling 8.
> >> > This is with no assumptions on Z, which if we impose reduce the
> >> > cost of addition on a short Weierstrass curve to 11
> >> > multiplications. But
> >> if
> >> > handle in a secure manner. Most people just don't bother. I also
> >> > let the Weierstrass form be special with a=-3, while keeping the
> >> > Edwards curve fully general.
> >> >
> >> > true no matter what algorithm for exponentiation is used. And I
> >> > even gave short Weierstrass curves a handicap by letting them
> avoid
> >> > Montgomery form is even better: differential addition costs 10M,
> >> > and calculates a doubling for free. Sadly the differential part
> >> > makes radix-k algorithms tough, but in memory constrained
> >> > environments
> >> (like
> >> > Then there is the prime shape: Brainpool uses a random prime,
> which
> >> is
> >> > a terrible idea from an efficiency perspective. NIST primes are
> >> > sized for 32 bit machines, and have some hiccups on 64 bit
> >> > machines. But
> >> the
> >> > Chicago primes are primes for all seasons: 2^k-c with small c is
> >> > nice no matter what radix you adopt. Unsaturated arithmetic makes
> >> > addition faster because reductions aren't necessary at all times,
> >> > and the Chicago primes are good from that perspective.
> >> >
> >> > essential. In the wider IETF context we are catering to devices
> >> > from the lowly MSP430, to the latest and greatest supercomputer.
> >> > What does Brainpool let us do? We should stick to the NIST and
> Chicago curves:
> >> > NIST for those who require it, and Chicago for those who require
> >> > the extra speed.
> >> >
> >> > Ransom I understand wants twisted Edwards curves for an extra bit
> >> > of speed, using isogenies to keep them the same as the Chicago
> >> > curves, but selecting only those with small parameters and
> >> > particularly nice prime shapes.
> >> > ------------------------------------------------------------------
> -
> >> > -- This transmission (including any attachments) may contain

---

From: Manuel Pégourié-Gonnard <[email-masked]>
Date: Tue, 14 Jan 2014 13:48:04 +0100

On 14/01/2014 02:38, Watson Ladd wrote:
> Do we need great big flashing
> lights *this is not in short Weierstrass form*?

As a matter of fact, yes, I think it couldn't hurt.

Historical matters are of not practical importance. What matters is the current
state of the ECC literature. And I can only agree with Paul here: for most
existing (practical) documentation, an elliptic curve is *by definition* an
elliptic curve in short Weierstrass form.

> And what does it say
I'm not sure despising implementers will actually help improving the quality of
implementations. Clear documentation, however, might help. (Though not everyone
reads the (right) documentation, unfortunately.)

Manuel.

---

From: Dan Brown <[email-masked]>
Date: Tue, 14 Jan 2014 16:51:11 +0000

> -----Original Message-----
> From: Alyssa Rowan
> Sent: Monday, January 13, 2014 7:27 PM
> 
> With zero knowledge of a hypothetical attack, we have zero knowledge about
> what may, or may not, be affected by it.
> 

We have zero knowledge that Curve25519 resists the hypothetical attack for which P256 has hypothetically been manipulated to be affected by. [Sorry to grammarians!]

So, what is rigidity is claiming to resist, under your reasoning?

Under my reasoning, I assume that there is a set of curves, partitioned into two subsets: curves vulnerable to a secret attack known the generator (NIST/NSA) and those not..

It's possible that trial and error was used for P256 until landed in the vulnerable subset.  I think that is implicit in the safecurves ... rigidity page.  No?

Now, suppose I were tasked to find my own curve to minimize the chance of landing in the vulnerable set?

Choose a curve with small coefficients?  Since I do not know what the vulnerable set is, and rightly want to assume zero knowledge about it, I cannot presume that small coefficients protect me from the hypothetical secret attack, unless presume nonzero knowledge the vulnerable set.  [Sorry for the tedious redundancy.] 

Granted: small coefficients would help my persuade others that I did not select the curve maliciously by exhaustive search.  

What about a pseudorandom curve? More precisely, where the coefficients are derived from PRF(rigid-seed).  

Assuming independence of the vulnerable set from the PRF and rigid-seed, and the pseudorandomness of the PRF, then it seems that the pseudorandom curve lands in the vulnerable subset with probability p, where p is the density of the vulnerable subset within the larger set of curves from which one draws the curve from.

Under this hypothesis, the manipulation of P256 would have been expected to take on the order of 1/p trials.  

One can plug in any value for p, based on whatever assumptions one thinks is reasonable.

For example, my personal belief had been p = 2^(-128), perhaps because I was super biased toward, and committed to, ECC.  In that case, the manipulation phase for NIST P256 would be infeasible, and I could dismiss this whole issue rigidity v pseudorandom as didactic, distraction, irrelevant, baseless, stalling, bogus, moot, FUD, or whatever.

But I recognize that maybe I am too optimistic.  Others have suggested p =2^(-30), and I am listening to them.  Then a malicious NIST P256 would be very feasible.  In my view, the resulting assurance provided by pseudorandom, probability of 2^(-30) seems a little low, but then maybe I am just not yet used to thinking this way.  Others could say that any public key algorithm always has a similar risk of new attacks being discovered, and therefore that this risk, if not actually acceptable, is unavoidable.

What about small coefficient curves?  They don't have the argument of probability p of avoiding the vulnerable set, but they do have some legitimate security arguments: (1, resp.) no attacks are known, and (2, resp.) known attacks do not seem related to coefficient size. As I see it, these arguments assume more about the hypothetical secret attacks than the NIST curves: (1, resp.) either they do not exist (but that puts back to negligible p), or (2, resp.) the hypothetical secret attack is similar to existing known attacks to the extent that it cannot possibility depend on coefficient size.  The latter argument has tremendous merit in that it is a very plausible assumption, but pseudorandom curves do not rely on this assumption.  Again, it presumes virtually nonzero knowledge about the secret attack (other than the partition of the set of curves into vulnerable and non-vulnerable).  No?  

It's certainly possible to vilify me for suggesting the possibility of a small coefficient attack, call it baseless, etc., but what I'm saying is that pseudorandom curves do not rely this.  Instead they rely on more falsifiable assumptions, e.g. the effective of the PRF, etc.  

This general strategy of reasoning to avoid unknown attacks is used in the field of "provable security" and also seems to be used in the "rigidity" page of the safecurves strategy.

I've a tried to explain this before on the TLS.  In so doing, I reconsidering, or setting aside, my own beliefs and preferences, to try to engage the rigidity arguments.

> 
> A point to note here: brainpoolP256r1 has a _very_ weak twist (ρ @ 2^44) - a
> practical problem only in a flawed implementation that doesn't check for invalid
> points. But here nevertheless, we actually have a curve generated in a
> documented pseudorandom manner, yet has at least one desirable property
> distinctly less secure than all of its tested peers.
> 
> Why? Bad luck, it seems.

Thanks for the pointing this out, I hadn't noticed it before. 

> 
> 
> I for one prefer sound, well-explained, reproducibly verifiable curve design
> which resists all known attacks, to rolling the dice and hoping it resists a
> hypothetical attack that we know nothing about.

Don't quite follow, based on my understanding above.

Also, publishing a seed and curve-PRF, is verifiable, and reproducible.

I guess that you refer to the NIST seeds being not well-explained. 

Brainpool certainly seeds seem to be.

> 
> Hence my preference for the "Safecurves" approach, and thus the "Chicago"
> curves.
> 
> efficient way, and thus are exceptionally well-suited for the important task of
> accelerating wide adoption of forward security in internet protocols, I also find
> a highly desirable point in their favour - as, it seems, do many others.
> 
 
People really want fast, because it reduces cost.  

But they also want secure.

Fast and secure are both important, but orthogonal.

People need to balance both sides.

I had wanted to focus on the security side, to get a thorough understanding of that side.

Granted, I may be taking a too narrow focus, from an engineering viewpoint, where action is the order of the day, not reflection.  I was hoping CFRG to be more receptive to a (hypothetical) security-focus.

Anyway, once one has a thorough understanding on both sides, one can make a balanced decision.

---

From: "Igoe, Kevin M." <[email-masked]>
Date: Tue, 14 Jan 2014 17:24:10 +0000

It has been a long time since I've looked at the complex multiplication 
method for generating elliptic curve, but I believe that with some care
the CM method might satisfy your criterion for being rigid.

Should use of the CM method be encouraged, tolerated, or prohibited?

> From: Cfrg [mailto:[email-masked]] On Behalf Of Dan Brown
> Sent: Monday, January 13, 2014 6:08 PM
> To: Watson Ladd
> Cc: [email-masked]
> I had requested to keep this thread focused, specifically in the impact
> pseudorandom v rigid on security, but you declined to engage. Is it
> that you think this security issue unimportant, even though you concede
> with my narrow point?
> 
> Instead, you mostly repeated the general speed and side channel
> benefits of Chicago, which I was not yet disputing.
> 
> A couple people have suggested to me (off list) to generate new curves
> with explainable seeds but the same fields as NIST curves.
> 
> This is with no assumptions on Z, which if we impose reduce the cost of
> addition on a short Weierstrass curve to 11 multiplications. But if we
> impose the same condition on the Edwards curve, the cost is 10
> multiplications.
> 
> However, I've forced the Edwards curve to represent the identity, which
> if we are willing to drop, slices off two more multiplications.
> By contrast the
> Weierstrass curve has special cases that need additional work to handle
> in a secure manner. Most people just don't bother. I also let the
> Weierstrass form be special with a=-3, while keeping the Edwards curve
> fully general.
> 
> curve, or invalid point, or somewhere the calculation messes up issues.
> Usually the defense is a final check on the result being on the code,
> but that isn't the same as knowing that no attack is possible because
> your code always generates the right answer.
> 
> speed, using isogenies to keep them the same as the Chicago curves, but
> selecting only those with small parameters and particularly nice prime
> shapes.
> This transmission (including any attachments) may contain confidential
> information, privileged material (including material protected by the
> solicitor-client or other applicable privileges), or constitute non-
> public information. Any use of this information by anyone other than
> the intended recipient is prohibited. If you have received this
> transmission in error, please immediately reply to the sender and
> delete this information from your system. Use, dissemination,
> distribution, or reproduction of this transmission by unintended
> recipients is not authorized and may be unlawful.

---

From: Mike Hamburg <[email-masked]>
Date: Tue, 14 Jan 2014 10:12:03 -0800

My two cents:

The goal of rigidity is to constrain the curves without giving them any extra properties that might be relevant to an attacker.  It seems to me that for this purpose, CM is worse than small coefficients.  As a result, Bernstein's Safecurves criteria ban curves with small CM discriminant, despite no attacks being known.

However, the endomorphisms on such curves can speed up implementation, and I could definitely see a use for CM curves or GF(p^2) curves with a 256-ish-bit prime, a la GLS/GLV.  It reduces the computation required for perfect forward secrecy, right?  But in terms of protecting against hypothetical unknown attacks, I don't think it makes sense to use CM curves at high security levels.

I'd be very interested to hear the opinion of someone who is more versed in the subject.

Cheers,
-- Mike

---

From: Dan Brown <[email-masked]>
Date: Tue, 14 Jan 2014 19:08:55 +0000

Hi Mike,

Further to your suggestion below, why not consider a modified version of Curve25519, with same underlying field, (Montgomery) equation y^2 = x^3 + Zx^2 + x, where

Z = PRF("Chicago"||counter)

Where PRF is some reasonable pseudorandom function mapping into the field of definition of Curve25519, and counter is some unambiguously encoded bit string representation of an integer is value is the minimal among these meeting as many as possible of the various criteria used for selection of the A coefficient in Curve25519, in particular resistance to known attacks, e.g. twist security, MOV resistance, and SASS.  (Hey, why not throw in other criteria too, strong DHP safety, high discriminant, and that other thing related to isogenies that Brainpool considers (is it endomorphism class number or something?).)

Given that Z would be larger than A, the resulting curve would certainly be slower than Curve25519.  But how much slower?  Surely it would be almost as easy to implement, and have similar side channel resistance, unless I have a severe misunderstanding.

I think one could then make a formal (if heuristic) argument that if an adversary knows of a secret weak class of some small, but non-negligible density subset of curves (over the given field), that this curve is drawn from a sample space of sufficient size such that it inherits the small fraction property.  My algebraic geometry is a little weak, but I assume that varying this single coefficient in the equation walks through a good fraction of the isomorphism classes (J-invariants).  This security argument may assume the attack works across birational equivalence, if one is concerned about an attack specifically on NIST P256.

Just to be clear, the gain here would only to be not rely on the plausible presumption a secret attack is independent of coefficient size.

Just to be extra clear, the claim is not the some particular size of Z resists attacks better, but the fact that Z is random is pseudorandomly selected.

Best regards,

Dan

From: Michael Hamburg [mailto:[email-masked]]
Sent: Monday, January 13, 2014 7:57 PM
To: Watson Ladd
Cc: Dan Brown; [email-masked]
Subject: Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid v Pseudorandom

On Jan 13, 2014, at 4:36 PM, Watson Ladd <[email-masked]<mailto:[email-masked]>> wrote:

On Mon, Jan 13, 2014 at 3:07 PM, Dan Brown <[email-masked]<mailto:[email-masked]>> wrote:

Watson,

Speak for yourself.  I'm interested in a standard which has a better chance of resisting unknown attacks, and I'm not as concerned about NSA cookery as you are.

Either way, I feel that the highest practical ECC security level would come from a verifiably pseudorandom curve over a verifiably pseudorandom field.  This is because it will take either a significant mathematical breakthrough or a quantum computer to break existing 120s-ish-bit-secure curves such as Curve25519, anytime in the foreseeable future.  If it's a quantum computer or a breakthrough that kills all curves, we're screwed.

So that leaves a breakthrough which kills only curves with special properties, or only improves speed somewhat (eg, p^1/4 instead of p^1/2).  Given that, should we choose curves with known special properties that aren't required for security?  (Small d, special fields?)  Or should we try to be as random as possible, constrained only by properties that have a good security argument?

The downsides are difficulty of generation, and speed: a random field would be at least twice as slow.  So if I had to take 3 next-gen curves to a desert island, I'd go for:

* Ed25519.  It's deployed, it's implemented, it's significantly faster and easier to make secure than NIST P256.  There are other options, but this one works.  Once again, probably nobody is going to break this with a rho attack in the next couple of decades.

* Something with a bigger fast field.  Ed448-Goldilocks is my entry for that, but the others are also fine.  A pseudorandom $d$ value would probably improve things, if you could get confidence that it's not rigged.  Whichever way this goes, ops on such a curve will take about 4x as long as Ed25519 in software.

* A pseudorandom curve over a pseudorandom 512-bit field.  Operations on such a curve will probably take at least 12x as long as Ed25519, and at least 16x if it's a short Weierstrass curve.

In any case, if we list any pseudorandom curves, they should have most of the Safecurves properties except rigidity.  Some of the properties really aren't necessary (eg, Elligator), and basically end up just requiring Edwards curves.  There's a decent case that Edwards is a better shape than short Weierstrass anyway though, and in that case we should go for all the properties except rigidity.

Cheers,
- Mike

---

From: David McGrew <[email-masked]>
Date: Tue, 14 Jan 2014 15:21:09 -0500

Hi Dan,

thanks for sharing your thoughts.  It seems to me that the arguments in 
favor of rigid curves comes down to the "nothing up my sleeve" argument: 
if there are no free parameters to be chosen when constructing an 
elliptic curve group, then there is no need to trust the person doing 
the construction.

There is another consideration: the cost of attacking multiple instances 
of the EC discrete log problem can be amortized across multiple such 
instances, using techniques such as Kuhn and Struik's "Random Walks 
Revisited: Extensions of Pollard's Rho Algorithm for Computing Multiple 
Discrete Logarithms", or a time-memory tradeoff like Shanks' baby step - 
giant step method, in which the number of stored elements exceeds the 
square root of the group size.   Some users may be motivated by the 
logic that by avoiding a particular well-known curve, they prevent 
potential attackers from amortizing the cost of finding their private 
within a batch of other attacks.    If the cost of solving a single 
discrete logarithm problem are within the attacker's budget, then these 
considerations would come into play.   It would then be valuable to have 
a way to generate multiple curves, which could be pseudorandom and 
verifiable, or perhaps could be sequential and based on the "smallest 
number greater than p" sort of logic.

In any case, the suggestion to document the rationale behind elliptic 
curve parameter choices is a good one!

David

On 01/14/2014 11:51 AM, Dan Brown wrote:
>> A point to note here: brainpoolP256r1 has a _very_ weak twist (? @ 2^44) - a

---

From: Alyssa Rowan <[email-masked]>
Date: Tue, 14 Jan 2014 21:01:02 +0000

On 14/01/2014 16:51, Dan Brown wrote:

>> With zero knowledge of a hypothetical attack, we have zero 
>> knowledge about what may, or may not, be affected by it.
> We have zero knowledge that Curve25519 resists the hypothetical 
> attack for which P256 has hypothetically been manipulated to be 
> affected by. [Sorry to grammarians!]

Of course, in truth, we have zero actual knowledge about any such
attack, full stop - including whether it actually exists, or whether
P256 was actually manipulated to be affected by it.

> So, what is rigidity is claiming to resist, under your reasoning?

Simply put, rigidity assures "nothing up my sleeve".

For example, using the Safecurves criteria, three separate groups of
people independently came up with the exact same parameters for E-521.

> It's possible that trial and error was used for P256 until landed 
> in the vulnerable subset.

I gather that the SEC team at Certicom at the time _did_ perform a
trial-and-error search of SHA-1 seeds so that the resulting outputs
would meet certain criteria.

My information suggests that the criteria for selection were the
applicability of Certicom-patented techniques for fast arithmetic over
the curves so generated.

I have not been able to uncover any evidence that they were
intentionally weakened - although sadly, due to the breathtakingly
exceptional opacity of the process, I am unable to comprehensively
rule it out.

We do know they were working closely with NSA during the affected time
(we don't know to which end). We definitely know the NSA have had a
line item on their SIGINT Enabling Project's budget specifically about
influencing public-key standards in a way which makes them amenable to
attacks (although we don't know whether it did at the relevant time,
or what that precisely referred to).

The rest, sadly, is probably lost in some file somewhere. You may very
well be in a better position to uncover their precise provenance than
I (in the absence of nothing-up-my-sleeve numbers, I am not sure to
what degree it would actually assure anyone, but it would still be
nice to have some idea).

Happily, the "Chicago" curves have no such shadow, are faster and
easier to implement well, it is possible to make them extremely fast -
which will strongly aid the requirements of many parties wanting to
deploy forward secrecy (an important defence against nation state
adversaries performing mass surveillance). They make a pretty damn
good replacement.

> chance of landing in the vulnerable set?

With no knowledge of the vulnerable set, any such choice is, sadly, blind.

We can, of course guess. We may or may not be right.

If we guess that such an attack perhaps resembles an existing attack
but with a new twist (if you'll pardon the pun!), then probably the
best we can do to avoid it is to avoid existing attacks in a
conservative manner, and thoroughly explain any such heuristic.

The question is simply whether our heuristic guesses are better than
random at avoiding an unknown attack, worse, or equivalent.

Obviously, we don't know which. But the strategy seems sensible.

>> [brainpoolP256r1 weak twist] Why? Bad luck, it seems.

It's simply bad luck. brainpoolP384r1 doesn't have the same issue.
Neither, actually, does secp256r1, although secp224r1 does.

I presume it simply wasn't considered under the selection criteria or
thought of as relevant at the time.

That feeds into my point, however: with no thought that such a thing
might be relevant, psuedorandomness in fact did not protect
brainpoolP256r1 against such a flaw.

>> I for one prefer sound, well-explained, reproducibly verifiable 
>> curve design which resists all known attacks, to rolling the
>> dice and hoping it resists a hypothetical attack that we know
>> nothing about.
> Don't quite follow, based on my understanding above. Also, 
> publishing a seed and curve-PRF, is verifiable, and reproducible.

Naturally, provided the seeds are chosen in a verifiable manner.

I think if we start rolling the dice repeatedly until we get numbers
we'd like, we may as well just use what we know to pick good ones via
defined criteria.

But it seems like we simply disagree on that point - you prefer a
random approach, others including me prefer a solidly-explained
heuristic approach.

We are probably unlikely to reach consensus on that point, although
there's nothing stopping us having it both ways.

> Brainpool certainly seeds seem to be.

I don't dispute that. It's a slightly odd process, but it's explained,
and seems to have been done that way to mirror the SECP process.

> People really want fast, because it reduces cost. But they also 
> want secure. Fast and secure are both important, but orthogonal. 

Orthogonal, but not necessarily always _opposites_. Slow things are
not necessarily insecure; fast things not necessarily weak; not all
secure things are slow; not all insecure things are fast.

They are both separate, desirable criteria. I am familiar with a
number of primitives which have the unenviable properties of being
weak _and_ slow, as I am sure are you.

The only areas where they clearly fall into direct conflict are for
example where more rounds would make a function slower but more
secure, or where all other things being equal, a larger field or key
size would be more resistant to an attack than a smaller one. (Hence
the specification of multiple curves, to trade off performance and
size for estimated security margin.)

Here, we appear to have the rare and treasured opportunity of a useful
set of primitives which are both secure against all known and
reasonably conjectured attacks over the foreseeable future _and_ fast
- - when we need it most. I think we should take that opportunity:
because quite honestly, many aren't going to wait any longer than they
have to, and these curves are in fact already being used in the wild
in several applications.

> I had wanted to focus on the security side, to get a thorough 
> understanding of that side. Granted, I may be taking a too narrow 
> focus, from an engineering viewpoint, where action is the order of 
> the day, not reflection.  I was hoping CFRG to be more receptive
> to a (hypothetical) security-focus. Anyway, once one has a
> thorough understanding on both sides, one can make a balanced
> decision.

You are of course entirely welcome to come up with your own open
criteria and/or generate pseudorandom curves according to those
criteria; it appears that you may wish to do this. From the sounds of
it so far, it would end up broadly like Brainpool - pseudorandom
Edwards curves, not optimised for efficient implementation, but
selected to avoid known attacks, with the hope of avoiding unknown
attacks.

Any such draft can of course be discussed separately, should you wish
to put it forward. Whether anyone would wish to use them is up to
implementers.

- -- 
/akr

---

From: Paul Lambert <[email-masked]>
Date: Tue, 14 Jan 2014 17:33:03 -0800

From: Cfrg [mailto:[email-masked]] On Behalf Of David McGrew
Sent: Tuesday, January 14, 2014 12:21 PM
To: Dan Brown
Cc: [email-masked]'
Subject: Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid v Pseudorandom

Hi Dan,

thanks for sharing your thoughts.  It seems to me that the arguments in favor of rigid curves comes down to the "nothing up my sleeve" argument: if there are no free parameters to be chosen when constructing an elliptic curve group, then there is no need to trust the person doing the construction.

There is another consideration: the cost of attacking multiple instances of the EC discrete log problem can be amortized across multiple such instances, using techniques such as Kuhn and Struik's "Random Walks Revisited: Extensions of Pollard’s Rho Algorithm for Computing Multiple Discrete Logarithms", or a time-memory tradeoff like Shanks' baby step - giant step method, in which the number of stored elements exceeds the square root of the group size.   Some users may be motivated by the logic that by avoiding a particular well-known curve, they prevent potential attackers from amortizing the cost of finding their private within a batch of other attacks.    If the cost of solving a single discrete logarithm problem are within the attacker's budget, then these considerations would come into play.   It would then be valuable to have a way to generate multiple curves, which could be pseudorandom and verifiable, or perhaps could be sequential and based on the "smallest number greater than p" sort of logic.
[ ⨳]  Interesting … so we could have a curve of the day site.  Order is hard to create, but could be generated and used by many.
Paul

In any case, the suggestion to document the rationale behind elliptic curve parameter choices is a good one!

David

-----Original Message-----

From: Alyssa Rowan

For a given field, pseudorandom curve better resists secret attacks

than rigidity.

Why? Bad luck, it seems.

curves.

Cfrg mailing list

[email-masked]<mailto:[email-masked]>

---

From: Watson Ladd <[email-masked]>
Date: Tue, 14 Jan 2014 17:40:45 -0800

On Tue, Jan 14, 2014 at 5:33 PM, Paul Lambert <[email-masked]> wrote:
> favor of rigid curves comes down to the "nothing up my sleeve" argument: if
> there are no free parameters to be chosen when constructing an elliptic
> curve group, then there is no need to trust the person doing the
> construction.
>
> There is another consideration: the cost of attacking multiple instances of
> the EC discrete log problem can be amortized across multiple such instances,
> using techniques such as Kuhn and Struik's "Random Walks Revisited:
> Extensions of Pollard’s Rho Algorithm for Computing Multiple Discrete
> Logarithms", or a time-memory tradeoff like Shanks' baby step - giant step
> method, in which the number of stored elements exceeds the square root of
> the group size.   Some users may be motivated by the logic that by avoiding
> a particular well-known curve, they prevent potential attackers from
> amortizing the cost of finding their private within a batch of other
> attacks.    If the cost of solving a single discrete logarithm problem are
> within the attacker's budget, then these considerations would come into
> play.   It would then be valuable to have a way to generate multiple curves,
> which could be pseudorandom and verifiable, or perhaps could be sequential
> and based on the "smallest number greater than p" sort of logic.

No one uses time-memory tradeoff: why have silicon store data it can work on?
This also misstates the issue. Parallel search for AES-128 keys cuts
the work by the number of keys,
and the time to the first key falls linearly with the number of keys.
Parallel rho isn't any faster for the first answer: the remaining
answers come out fast, but getting the first
one still takes the same time. The fact that this is stated clearly in
the paper cited makes me doubt whether
the person citing the paper bothered to read it.

Sincerely,
Watson Ladd
>
> [ ⨳]  Interesting … so we could have a curve of the day site.  Order is hard
> to create, but could be generated and used by many.
>
> Paul
>
>
>
> We have zero knowledge that Curve25519 resists the hypothetical attack for
> which P256 has hypothetically been manipulated to be affected by. [Sorry to
> grammarians!]
>
>
>
> Under my reasoning, I assume that there is a set of curves, partitioned into
> two subsets: curves vulnerable to a secret attack known the generator
> (NIST/NSA) and those not..
>
>
>
> It's possible that trial and error was used for P256 until landed in the
> vulnerable subset.  I think that is implicit in the safecurves ... rigidity
> page.  No?
>
>
>
> Choose a curve with small coefficients?  Since I do not know what the
> vulnerable set is, and rightly want to assume zero knowledge about it, I
> cannot presume that small coefficients protect me from the hypothetical
> secret attack, unless presume nonzero knowledge the vulnerable set.  [Sorry
> for the tedious redundancy.]
>
>
>
> Granted: small coefficients would help my persuade others that I did not
> select the curve maliciously by exhaustive search.
>
>
>
> Assuming independence of the vulnerable set from the PRF and rigid-seed, and
> the pseudorandomness of the PRF, then it seems that the pseudorandom curve
> lands in the vulnerable subset with probability p, where p is the density of
> the vulnerable subset within the larger set of curves from which one draws
> the curve from.
>
>
>
> For example, my personal belief had been p = 2^(-128), perhaps because I was
> super biased toward, and committed to, ECC.  In that case, the manipulation
> phase for NIST P256 would be infeasible, and I could dismiss this whole
> issue rigidity v pseudorandom as didactic, distraction, irrelevant,
> baseless, stalling, bogus, moot, FUD, or whatever.
>
>
>
> But I recognize that maybe I am too optimistic.  Others have suggested p
> =2^(-30), and I am listening to them.  Then a malicious NIST P256 would be
> very feasible.  In my view, the resulting assurance provided by
> pseudorandom, probability of 2^(-30) seems a little low, but then maybe I am
> just not yet used to thinking this way.  Others could say that any public
> key algorithm always has a similar risk of new attacks being discovered, and
> therefore that this risk, if not actually acceptable, is unavoidable.
>
>
>
> What about small coefficient curves?  They don't have the argument of
> probability p of avoiding the vulnerable set, but they do have some
> legitimate security arguments: (1, resp.) no attacks are known, and (2,
> resp.) known attacks do not seem related to coefficient size. As I see it,
> these arguments assume more about the hypothetical secret attacks than the
> NIST curves: (1, resp.) either they do not exist (but that puts back to
> negligible p), or (2, resp.) the hypothetical secret attack is similar to
> existing known attacks to the extent that it cannot possibility depend on
> coefficient size.  The latter argument has tremendous merit in that it is a
> very plausible assumption, but pseudorandom curves do not rely on this
> assumption.  Again, it presumes virtually nonzero knowledge about the secret
> attack (other than the partition of the set of curves into vulnerable and
> non-vulnerable).  No?
>
>
>
> It's certainly possible to vilify me for suggesting the possibility of a
> small coefficient attack, call it baseless, etc., but what I'm saying is
> that pseudorandom curves do not rely this.  Instead they rely on more
> falsifiable assumptions, e.g. the effective of the PRF, etc.
>
>
>
> This general strategy of reasoning to avoid unknown attacks is used in the
> field of "provable security" and also seems to be used in the "rigidity"
> page of the safecurves strategy.
>
>
>
> I've a tried to explain this before on the TLS.  In so doing, I
> reconsidering, or setting aside, my own beliefs and preferences, to try to
> engage the rigidity arguments.
>
>
>
>
>
> Granted, I may be taking a too narrow focus, from an engineering viewpoint,
> where action is the order of the day, not reflection.  I was hoping CFRG to
> be more receptive to a (hypothetical) security-focus.
>
>
>
> solicitor-client or other applicable privileges), or constitute non-public
> information. Any use of this information by anyone other than the intended
> recipient is prohibited. If you have received this transmission in error,
> please immediately reply to the sender and delete this information from your
> system. Use, dissemination, distribution, or reproduction of this
> transmission by unintended recipients is not authorized and may be unlawful.
>
>
>
>

---

From: David McGrew <[email-masked]>
Date: Wed, 15 Jan 2014 08:18:33 -0500

Hi Watson,

On 01/14/2014 08:40 PM, Watson Ladd wrote:
> one still takes the same time.

Right, which is why I said "If the cost of solving a single discrete 
logarithm problem are within the attacker's budget, then these 
considerations would come into play. "    So these considerations would 
be more valid at an 80-bit security level than a 256-bit security level, 
say.

> The fact that this is stated clearly in

Comments like this run the risk of making the environment on this list 
less friendly.

regards,

David

---

From: Watson Ladd <[email-masked]>
Date: Wed, 15 Jan 2014 08:19:37 -0800

On Wed, Jan 15, 2014 at 5:18 AM, David McGrew <[email-masked]> wrote:
>>> of
> considerations would come into play. "    So these considerations would be
> more valid at an 80-bit security level than a 256-bit security level, say.

Well, the only reason to use an 80-bit security level is performance,
and really a marginal amount
at that: TLS doesn't have 80-bit ECC for example, and the existing 80
bit asymmetric algorithms are slower
then Curve25519.

But when you send someone a curve and ask them to use it they have to
make the following verifications
1) They have to check that the modulus is prime.
2) They have to check the order is what you say it is, or find it.
Finding it involves a gigantic table, checking an expoentation
which will test some exceptional cases.
3) They have to check for additive and multiplicative embeddings,
which involves a lot of modular exponentiation.
4) They have to check the order is prime

Put all of this together, and the performance gain is gone.
Furthermore, batch calculations don't work anymore.
Per system parameters don't give the anti-attackability gain.

Sincerely,
Watson
> Comments like this run the risk of making the environment on this list less
> friendly.
>
> regards,
>
> David
>
>
>>
>> Sincerely,
>> Watson Ladd
>>>
>>> about
>>> What about a pseudorandom curve? More precisely, where the coefficients
>>> are
>>> derived from PRF(rigid-seed).
>>>
>>>
>>>
>>> Under this hypothesis, the manipulation of P256 would have been expected
>>> to
>>> take on the order of 1/p trials.
>>>
>>>
>>>
>>> One can plug in any value for p, based on whatever assumptions one thinks
>>> is
>>> reasonable.
>>>
>>>
>>>
>>> design
>>> efficient way, and thus are exceptionally well-suited for the important
>>> task
>>> of
>>>
>>> accelerating wide adoption of forward security in internet protocols, I
>>> also
>>> find
>>>
>>> understanding
>>> of that side.
>>> Anyway, once one has a thorough understanding on both sides, one can make
>>> a
>>> balanced decision.
>>>
>>>
>>>
>>>
>>>
>>>
>>>
>>>

---

From: "Igoe, Kevin M." <[email-masked]>
Date: Wed, 15 Jan 2014 17:00:42 +0000

> From: Cfrg [mailto:[email-masked]] On Behalf Of Watson Ladd
> Sent: Wednesday, January 15, 2014 11:20 AM
> To: David McGrew
> >>> thanks for sharing your thoughts.  It seems to me that the
> arguments
> >>> in favor of rigid curves comes down to the "nothing up my sleeve"
> argument:
> >>> if
> >>> there are no free parameters to be chosen when constructing an
> >>> elliptic curve group, then there is no need to trust the person
> >>> doing the construction.
> >>>
> >>> There is another consideration: the cost of attacking multiple
> >>> instances of the EC discrete log problem can be amortized across
> >>> multiple such instances, using techniques such as Kuhn and Struik's
> >>> "Random Walks Revisited:
> >>> Extensions of Pollard’s Rho Algorithm for Computing Multiple
> >>> Discrete Logarithms", or a time-memory tradeoff like Shanks' baby
> >>> step - giant step method, in which the number of stored elements
> >>> exceeds the square root of
> >>> attacks.    If the cost of solving a single discrete logarithm
> problem
> >>> are
> >>> play.   It would then be valuable to have a way to generate
> multiple
> >>> curves,
> >>> which could be pseudorandom and verifiable, or perhaps could be
> >>> sequential and based on the "smallest number greater than p" sort
> of
> >>> logic.
> >>
> >> the work by the number of keys, and the time to the first key falls
> >> linearly with the number of keys.
> >> answers come out fast, but getting the first one still takes the
> same
> >> time.
> >
> >
> and really a marginal amount at that: TLS doesn't have 80-bit ECC for
> example, and the existing 80 bit asymmetric algorithms are slower then
> Curve25519.
> 

> Finding it involves a gigantic table, checking an expoentation which
> will test some exceptional cases.

Typically the specification of a cryptographic group requires you to 
provide an element G of prime order q, generating the cryptographic 
subgroup of order q. (q must, of course, be sufficiently large).
This makes life easier.  You need to check:
 a) q is prime
 b) G is indeed on the curve
 c) G != Identity_element
 d) q*G == Identity_element. 

You might want to require G be generated in a predetermined way. In theory, 
all non-identity elements of a prime order subgroup are effectively 
interchangeable, but in practice it is conceivable the security analysis of 
protocols using the curve might be simplified if G is "rigid".  

> 3) They have to check for additive and multiplicative embeddings, which
> involves a lot of modular exponentiation.
> >> The fact that this is stated clearly in the paper cited makes me
> >> doubt whether the person citing the paper bothered to read it.
> >
> >
> >>> [ ⨳]  Interesting … so we could have a curve of the day site.
> Order is
> >>> hard
> knowledge
> attack
> >>> for
> >>> which P256 has hypothetically been manipulated to be affected by.
> [Sorry
> >>> to
> >>> grammarians!]
> >>>
> >>>
> >>>
> >>> Under my reasoning, I assume that there is a set of curves,
> partitioned
> >>> into
> in the
> >>> Now, suppose I were tasked to find my own curve to minimize the
> chance of
> >>> landing in the vulnerable set?
> >>>
> >>>
> >>>
> >>> Assuming independence of the vulnerable set from the PRF and rigid-
> seed,
> >>> and
> >>> the pseudorandomness of the PRF, then it seems that the
> pseudorandom
> >>> curve
> >>> lands in the vulnerable subset with probability p, where p is the
> density
> >>> of
> >>> the vulnerable subset within the larger set of curves from which
> one
> >>> draws
> >>> the curve from.
> >>>
> >>>
> >>>
> >>> For example, my personal belief had been p = 2^(-128), perhaps
> because I
> >>> was
> >>> =2^(-30), and I am listening to them.  Then a malicious NIST P256
> would
> >>> be
> >>> pseudorandom, probability of 2^(-30) seems a little low, but then
> maybe I
> >>> am
> >>> key algorithm always has a similar risk of new attacks being
> discovered,
> >>> and
> >>> resp.) known attacks do not seem related to coefficient size. As I
> see
> >>> it,
> >>> these arguments assume more about the hypothetical secret attacks
> than
> >>> the
> >>> coefficient size.  The latter argument has tremendous merit in that
> it is
> >>> a
> >>> assumption.  Again, it presumes virtually nonzero knowledge about
> the
> >>> secret
> >>> This general strategy of reasoning to avoid unknown attacks is used
> in
> >>> the
> >>> reconsidering, or setting aside, my own beliefs and preferences, to
> try
> >>> to
> >>> A point to note here: brainpoolP256r1 has a _very_ weak twist (ρ @
> 2^44)
> >>> - a
> >>>
> >>> practical problem only in a flawed implementation that doesn't
> check for
> >>> invalid
> >>>
> curve
> "Chicago"
> important
> >>> where action is the order of the day, not reflection.  I was hoping
> CFRG
> >>> to
> confidential
> >>> please immediately reply to the sender and delete this information
> from
> >>> your

---

From: Dan Brown <[email-masked]>
Date: Wed, 15 Jan 2014 17:02:03 +0000

Hi David,

Good point about the "nothing up my sleeve" (NUMS) property.  That's what I meant when I earlier wrote the paragraph "Yes, rigidity helps more to prevent malicious generation of the curve.  I am not disagreeing with the safecurves site on that point. ".

I re-read the safecurves rigidity page today. The safecurves rigidity page does not use the NUMS term, but, in its strictest, to-the-letter interpretation, I think it coincides with the meaning of NUMS.  I.e. rigid == NUMS.

I did ask earlier in this thread if I was misinterpreting the rigidity page. Specifically, I was trying to ask if it was claiming something stronger than NUMS.  Apparently I was indeed misinterpreting, at least in to-the-letter sense, because I was construing the page to say something more than NUMS.  Furthermore, in previous discussion with Bernstein on the TLS mailing list, I had thought Bernstein was making stronger claims than just NUMS, which may have reinforced my misinterpretation above.  In retrospect, the TLS email exchange may also have been mutual misunderstanding.

David, your email and others are consistent with my rambling prose being ineffective to explain my main point to a wider audience, so I'll now try out some more emphatic language.

Consider a "nothing up their sleeves" (NUTS) property.  What it means: if X has the NUTS property, then X is not affected by some attack that "they" might know. Just to be clear, NUTS is an orthogonal property to NUMS (i.e. they vs me).  For a potential example, perhaps P256 has the NUTS property but not the NUMS property.  Also, achieving the NUMS and NUTS properties are tasks, for which various tools can be used, and arguments present as to whether, or to what extent, they are achieved.

Next, consider a "nothing up nobody's sleeve" (NUNS) property.  [Please forgive the double negative used to make this mnemonic acronym.  Think additive negation, instead of standard English grammar's multiplicative negation.  Think additive notation for ECC, as an additional mnemonic.] It seems to me that NUMS+NUTS==NUNS.

It seems to me that NUNS is not only formally stronger than NUMS, but is also preferable to just NUMS only, because we usually define algorithm security independently who the attacker is (not to be confused with the capabilities they have, where we might make distinctions.)

If I understand Watson and Alyssa correctly (although I am not too confident of my understanding), they think NUTS is irrelevant and unachievable, respectively.

If I understand Dan Bernstein's emails from the TLS list correctly, he thinks NUTS is much less important than NUMS, because of the quantities involved (and I agree), but nevertheless, that there are arguments that the safe curves provide the NUTS property, namely the all known attacks are independent of coefficient size (and I agree).  So, it is reasonable to argue the NUTS property to the safe curves (and I agree).

My primary point in this thread was meant to be that PRF(NUMS) => NUNS (summarizing the Brainpool curve selection process), without relying about the assumption on attacks being independent of coefficient size, so that random curve selection, as in Brainpool, provides better NUNS than the curve selection process outlined in the safe curves site.   Unfortunately, I did use Brainpool in the subject, which may have undermined my own point, opening the door to speed comparisons, field size issues, etc.

I was really expecting, to no avail, somebody to finally concede this point, but contend that the improvement was just very slight, because of the reasonableness of the coefficient-size-independence assumption.  Oh well.

My secondary point was that some people may be confusing NUMS and NUNS. Well, that's an ad hominem point, so my confidence is very low there. Also, it is clearly nearly impossible to argue, since a person's thoughts can change quickly.  I'm pretty Watson and Alyssa disagree on this secondary point.

Best regards,

Dan

From: David McGrew [mailto:[email-masked]]
Sent: Tuesday, January 14, 2014 3:21 PM
To: Dan Brown
Cc: [email-masked]'; [email-masked]'
Subject: Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid v Pseudorandom

Hi Dan,

---

From: Manuel Pégourié-Gonnard <[email-masked]>
Date: Wed, 15 Jan 2014 22:36:35 +0100

Hi Dan,

On 15/01/2014 18:02, Dan Brown wrote:
> I did ask earlier in this thread if I was misinterpreting the rigidity
> page. Specifically, I was trying to ask if it was claiming something
> stronger than NUMS.  Apparently I was indeed misinterpreting, at least
> in to-the-letter sense, because I was construing the page to say
> something more than NUMS.

We can probably take this as an indication that the document should be
very clear on that point (like, clearer that the safecurves pages).

> It seems to me that NUNS is not only formally stronger than NUMS, but
> is also preferable to just NUMS only, because we usually define
> algorithm security independently who the attacker is (not to be
> confused with the capabilities they have, where we might make
> distinctions.)
> 
I think we can agree that NUNS is a very desirable property, but that
almost by definition we can't produce a curve for which it holds with
absolute certainty: all we can do it try to maximise the probability,
under reasonable assumptions, that the curve has this property.

> I was really expecting, to no avail, somebody to finally concede this
> point, but contend that the improvement was just very slight, because
> of the reasonableness of the coefficient-size-independence assumption.
> Oh well.
> 
For what it's worth, my current understanding is that, for a
Brainpool-like construction to maximise the NUNS probability, the only
necessary assumption is that the PRF and the "NUMS" seed have no special
relationship with the potential attacks on curves, which certainly looks
like a very reasonable assumption to make. OTOH, for a Curve25519-like
"rigid" selection to provide NUNS (with high probability), a necessary
assumption is that the upcoming (or currently known only to a few)
attacks don't have a higher probability to apply on a curve with small
coefficients than on the set of all curves (resisting known attacks).

IIRC the discussions on the TLS list, Daniel Bernstein quite strongly
holds the opinion that this assumption is reasonable, and if I
understand your last email correctly, you're not claiming it's an
unreasonable assumption to make.

Obviously, a point in favour of the "PRF(NUMS seed)" construction is
that it's probably easier to believe in it without any particular
knowledge of the attacks on ECDLOG and the deeper properties that make them
work or not.

But my very humble opinion, mostly based on comments by people with more
knowledge than me on this topic, is that both assumptions are
reasonable enough to give us confidence in the security of the curves (both
Brainpool and "rigid" ones) against upcoming attacks.

Manuel.

---

From: David McGrew <[email-masked]>
Date: Wed, 15 Jan 2014 19:04:17 -0500

Hi Dan,

On 01/15/2014 12:02 PM, Dan Brown wrote:
>
> Hi David,
>
> Good point about the "nothing up my sleeve" (NUMS) property. That's 
> what I meant when I earlier wrote the paragraph "Yes, rigidity helps 
> more to prevent malicious generation of the curve.  I am not 
> disagreeing with the safecurves site on that point. ".
>
> I re-read the safecurves rigidity page today. The safecurves rigidity 
> page does not use the NUMS term, but, in its strictest, to-the-letter 
> interpretation, I think it coincides with the meaning of NUMS.  I.e. 
> rigid == NUMS.
>
> something more than NUMS.  Furthermore, in previous discussion with 
> Bernstein on the TLS mailing list, I had thought Bernstein was making 
> stronger claims than just NUMS, which may have reinforced my 
> misinterpretation above.  In retrospect, the TLS email exchange may 
> also have been mutual misunderstanding.
>
> David, your email and others are consistent with my rambling prose 
> being ineffective to explain my main point to a wider audience, so 
> I'll now try out some more emphatic language.
>

Sure.  I think that I did follow most of your previous post, but I was 
not sure that I could add more illumination on the subject, so I 
refrained from commenting.

> Consider a "nothing up their sleeves" (NUTS) property.  What it means: 
> if X has the NUTS property, then X is not affected by some attack that 
> "they" might know. Just to be clear, NUTS is an orthogonal property to 
> NUMS (i.e. they vs me).  For a potential example, perhaps P256 has the 
> NUTS property but not the NUMS property.  Also, achieving the NUMS and 
> NUTS properties are tasks, for which various tools can be used, and 
> arguments present as to whether, or to what extent, they are achieved.
>

I am sorry, I am not sure that I follow you.  My own thinking has been 
that NUMS would apply to the process used to generate the curve, rather 
than a curve itself.   I can see that some processes might generate 
trustworthy curves no matter who runs the process (which seems to be the 
NUTS case) and other processes might generate curves that I trust only 
if I run the process (which seems to be the NUMS case).

> Next, consider a "nothing up nobody's sleeve" (NUNS) property. [Please 
> forgive the double negative used to make this mnemonic acronym.  Think 
> additive negation, instead of standard English grammar's 
> multiplicative negation.  Think additive notation for ECC, as an 
> additional mnemonic.] It seems to me that NUMS+NUTS==NUNS.
>
> If I understand Watson and Alyssa correctly (although I am not too 
> confident of my understanding), they think NUTS is irrelevant and 
> unachievable, respectively.
>
> If I understand Dan Bernstein's emails from the TLS list correctly, he 
> thinks NUTS is much less important than NUMS, because of the 
> quantities involved (and I agree), but nevertheless, that there are 
> arguments that the safe curves provide the NUTS property, namely the 
> all known attacks are independent of coefficient size (and I agree).  
> So, it is reasonable to argue the NUTS property to the safe curves 
> (and I agree).
>
> My primary point in this thread was meant to be that PRF(NUMS) => NUNS
>

I think the advocates of "rigid" curves mean to highlight the fact that 
the rigid process can generate only a small number of curves. In 
contrast, when we are presented by a verifiably pseudorandom curve that 
was generated with an input seed of unknown provenance, it might be the 
case that many seeds were tested and rejected until one was found that 
generated a curve on which the DL problem could be solved more easily.   
(Your model of "each curve has some probability of being vulnerable to 
an unknown attack" I think captures the concern, though one could 
generalize to a situation in which the expected running time of the DLP 
varied with the parameters.)

Now, it would be possible to make a "rigid" process out of a 
pseudorandom process by using a seed value that nobody can control (say, 
the sha512 hash of SP500 prices on a given future date). Perhaps this is 
what you mean by PRF(NUMS) -> NUNS?

regards,

David

> (summarizing the Brainpool curve selection process), without relying 
> about the assumption on attacks being independent of coefficient size, 
> so that random curve selection, as in Brainpool, provides better NUNS 
> than the curve selection process outlined in the safe curves site.  
>  Unfortunately, I did use Brainpool in the subject, which may have 
> undermined my own point, opening the door to speed comparisons, field 
> size issues, etc.
>
> of the reasonableness of the coefficient-size-independence 
> assumption.  Oh well.
>
> My secondary point was that some people may be confusing NUMS and 
> NUNS. Well, that's an ad hominem point, so my confidence is very low 
> there. Also, it is clearly nearly impossible to argue, since a 
> person's thoughts can change quickly.  I'm pretty Watson and Alyssa 
> disagree on this secondary point.
>
> Best regards,
>
> Dan
>
> *From:*David McGrew [mailto:[email-masked]]
> *Sent:* Tuesday, January 14, 2014 3:21 PM
> *To:* Dan Brown
> *Cc:* [email-masked]'; [email-masked]'
> *Subject:* Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid v Pseudorandom
>
> Hi Dan,
>
> thanks for sharing your thoughts.  It seems to me that the arguments 
> argument: if there are no free parameters to be chosen when 
> constructing an elliptic curve group, then there is no need to trust 
> the person doing the construction.
>
> solicitor-client or other applicable privileges), or constitute 
> non-public information. Any use of this information by anyone other 
> than the intended recipient is prohibited. If you have received this

---

From: Johannes Merkle <[email-masked]>
Date: Thu, 16 Jan 2014 11:59:23 +0100

David McGrew schrieb am 16.01.2014 01:04:
> 
> I think the advocates of "rigid" curves mean to highlight the fact that the rigid process can generate only a small
> number of curves. In contrast, when we are presented by a verifiably pseudorandom curve that was generated with an input
> seed of unknown provenance, it might be the case that many seeds were tested and rejected until one was found that
> generated a curve on which the DL problem could be solved more easily.   (Your model of "each curve has some probability
> of being vulnerable to an unknown attack" I think captures the concern, though one could generalize to a situation in
> which the expected running time of the DLP varied with the parameters.)
> 
My understanding of Dan's reasoning is different. I think, the "unknown" in "probability of being vulnerable to an
unknown attack" relates to the entity generating the curve, i.e. NUTS captures the objective of generating curves in a
way that minimizes the "probability" that the curve may be or become vulnerably to attacks unknown by the party
generating the curve.

Of course, "probability" refers more to a "feeling in the guts" than to a (Bayesian) probability.

> Now, it would be possible to make a "rigid" process out of a pseudorandom process by using a seed value that nobody can
> control (say, the sha512 hash of SP500 prices on a given future date). Perhaps this is what you mean by PRF(NUMS) -> NUNS?
> 

In retrospective this approach would be less convincing because some might still speculate that seed definition had been
specified at a later point of time, in spite of all evidence records.

And still, DJB could argue that the freedom in choices made for the derivation of the parameters, e.g. SHA-512, leaves
some questions unanswered, and he would probably label these curves (on the safecurve page) as being only "somewhat rigid".

regards,
Johannes

---

From: Adam Back <[email-masked]>
Date: Thu, 16 Jan 2014 13:04:34 +0100

You know in principle we ought to stick to something with low entropy for
the NUMs/rigidity seed.  I commented previously for example that someone can
do a fair bit of grinding by building a catalog of headlines, quote
dictionaries, and permuting their punctuation, white space etc.  Also
permuting arbitrary implementation choices (encoding, endianness, equally
plausible rigid choices, etc) So possibly the digits of pi are more
convincing than some obscure literary quote or a headline.  The point is to
start from an ungrindable starting point, with canonicalized choices at each
step.  I think so far the NUMS argument is probably gamable to a non-trivial
extent due to the above effects.

ie for secure NUMs you actually need to canonically encode all fo the
arbitrary choices in a standardized language, sort them, and select the
arbitrary choices at all levels, using the deterministic PRNG seed off pi. 
And even the PRNG design itself needs to be standardized, otherwise its
design variants also admit yet more bits.

The NUMs argument is good but so far is probably itself gameble, we need a
NUMs standard to remove as many of those variabilities as possible.

Adam

ps people might want to trim the quoted text in places, I almost missed some
comments they were that many pages down of recursive unedited quoting!

---

From: David McGrew <[email-masked]>
Date: Thu, 16 Jan 2014 07:44:08 -0500

Hi Adam,

On 01/16/2014 07:04 AM, Adam Back wrote:
> arbitrary choices at all levels, using the deterministic PRNG seed off 
> pi. And even the PRNG design itself needs to be standardized, 
> otherwise its

I think this is right.   In my comment about using a hash of the S&P 500 
prices on some future date, I had assumed that the canonicalization step 
would be fixed in advance, and used unchanged when trading closed on 
that day.    (My thinking: those prices are easily accessible in the 
public record, and would be implausibly expensive to manipulate, and are 
not under the control of any government.  There might be better 
examples, but I couldn't think of any.)

I agree that using the digits of pi is in some sense more appealing.   
With the hash-of-prices approach, and people could come along after the 
curve group had been generated and call into question whether the 
canonicalization had actually been fixed beforehand.   Using the digits 
of pi would avoid this (mis)perception issue.

Off topic: you mention obscure literary quotes, and this one comes to 
mind.   "How I need a drink, alcoholic of course, after the heavy 
lectures involving quantum mechanics".   Which is of course just a very 
arbitrary encoding of another bit of information ...

David

---

From: David McGrew <[email-masked]>
Date: Thu, 16 Jan 2014 08:13:21 -0500

Hi Johannes,

> specified at a later point of time, in spite of all evidence records.

Yes, I agree.

David

> .

---

From: Adam Back <[email-masked]>
Date: Thu, 16 Jan 2014 15:05:45 +0100

On Thu, Jan 16, 2014 at 07:44:08AM -0500, David McGrew wrote:
>I think this is right.   In my comment about using a hash of the S&P 
>500 prices on some future date, I had assumed that the 
>canonicalization step would be fixed in advance, and used unchanged 
>when trading closed on that day.  (My thinking: those prices are 
>easily accessible in the public record, and would be implausibly 
>expensive to manipulate, and are not under the control of any 
>government.  There might be better examples, but I couldn't think of 
>any.)

OK.  So what about this: if the generation progam were time-stamped, by
placing the hash of the rigid selection code into the bitcoin block chain,     
and then the containing block hash as the prng seed, and placing the hash of
the selected curve in a following block.  (The current block hash includes
the hash of the previous block hash recursively forming a hash chain).

Minimally this limits the grinding to what can be achieved within 10mins
(and most of the grinding power of an adversary is used up competing with a
17 petahash/sec = 181 exaflop/sec distributed supercomputer formed by
bitcoins hashcash-SHA256^2 ASIC miners), in a directly verifiable way with
no reference to external authority (the usual source of conspiracy
theories).  Its not quite ideal, but it is better than previous proposals
I've seen.

Note the ASIC miners are very hardware optimized 28nm/20nm high parallelism
chips, actual curve cooking selection would have to do far more complicated
selection and do it on general purpose programmable hardware not repeated
ASIC with hashcash coded into it.  Bitcoins hashrate outperforms the top 500
super computrs in *aggregate* by a factor of about 1000x.  Add in the work
to validate a curve for desired properties vs double SHA256 maybe by more.

Secondly looking back in time a month or a year later, both the code and the
rng seed become ever more difficult to retroactively modify.

Thirdly the curve selection code could have a nonce placed into it that
should be kept secret until a month after the selection.  Then people can
review the code and verify the curve.  Not knowing the nonce, a third party
could not grind the following hash.  The current hash forms a quite secure
distributed signature on the parameters.

Adam

ps I invented hashcash back in 1997 (bitcoins mining function) - might as
well get something useful out of the 35MW ongoing powerdraw otherwise only
doing a provably fair job of consensus/validation.