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

Hi Watson,

On 01/14/2014 08:40 PM, Watson Ladd wrote:
> On Tue, Jan 14, 2014 at 5:33 PM, Paul Lambert <paul@marvell.com> wrote:
>>
>>
>>
>> From: Cfrg [mailto:cfrg-bounces@irtf.org] On Behalf Of David McGrew
>> Sent: Tuesday, January 14, 2014 12:21 PM
>>
>>
>> To: Dan Brown
>> Cc: 'cfrg@irtf.org'
>> 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.
> 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.

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
> the paper cited makes me doubt whether
> the person citing the paper bothered to read it.

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

regards,

David

>
> 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
>>
>>
>>
>> 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:
>>
>> -----Original Message-----
>>
>> From: Alyssa Rowan
>>
>> Sent: Monday, January 13, 2014 7:27 PM
>>
>>
>>
>> On 13/01/2014 23:07, Dan Brown wrote:
>>
>>
>>
>> For a given field, pseudorandom curve better resists secret attacks
>>
>> than rigidity.
>>
>>
>>
>> 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.
>>
>>
>>
>>
>>
>> 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.
>>
>>
>>
>> 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.
>>
>>
>>
>> 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.
>>
>>
>>
>>
>>
>>
>>
>>
>> ---------------------------------------------------------------------
>>
>> 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
>>
>> Cfrg@irtf.org
>>
>> http://www.irtf.org/mailman/listinfo/cfrg
>>
>>
>>
>>
>> _______________________________________________
>> Cfrg mailing list
>> Cfrg@irtf.org
>> http://www.irtf.org/mailman/listinfo/cfrg
>>
>
>