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

David McGrew <mcgrew@cisco.com> Wed, 15 January 2014 13:18 UTC

Return-Path: <mcgrew@cisco.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 41DD31AE0C8 for <cfrg@ietfa.amsl.com>; Wed, 15 Jan 2014 05:18:48 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -15.039
X-Spam-Level:
X-Spam-Status: No, score=-15.039 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, RCVD_IN_DNSWL_HI=-5, RP_MATCHES_RCVD=-0.538, SPF_PASS=-0.001, USER_IN_DEF_DKIM_WL=-7.5] autolearn=ham
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 9nDgWJVMJhfg for <cfrg@ietfa.amsl.com>; Wed, 15 Jan 2014 05:18:45 -0800 (PST)
Received: from rcdn-iport-2.cisco.com (rcdn-iport-2.cisco.com [173.37.86.73]) by ietfa.amsl.com (Postfix) with ESMTP id 293731AE259 for <cfrg@irtf.org>; Wed, 15 Jan 2014 05:18:45 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=cisco.com; i=@cisco.com; l=11561; q=dns/txt; s=iport; t=1389791914; x=1391001514; h=message-id:date:from:mime-version:to:cc:subject: references:in-reply-to:content-transfer-encoding; bh=M9dg1v5jrkldTr/2PdpBNwVqHg3ku/7jSP4LomJUq5I=; b=OsP2uDtpthimARg9PpMYm+9jX7OL293lYRHqNXyTVr2QKu9TrOi86U6s OMLxTFl2/ZA9ban42UvLeDrlOicNtrej1tUMP15Z4nx/5cUy13AGr5tKS nn/MhkL+lsH7nMd3sac/9lu/OEFT+cIVfUM8PglZw8kSRGBzIsG8AkBAv M=;
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: Ai4FAMaJ1lKtJXG+/2dsb2JhbABagws4g1S3f4EUFnSCJQEBAQMBAQEBCxUPAQUtCQUFAQUHBAsRBAEBAQICBRYIAwICCQMCAQIBFR8JCAYNAQUCAgWHcwgNqBmbcxeBKYs8KIEXXgUHBoJpgUgBA4lFinODZoZFi1CDSx4
X-IronPort-AV: E=Sophos;i="4.95,663,1384300800"; d="scan'208";a="297435823"
Received: from rcdn-core2-3.cisco.com ([173.37.113.190]) by rcdn-iport-2.cisco.com with ESMTP; 15 Jan 2014 13:18:33 +0000
Received: from [10.0.2.15] (rtp-mcgrew-8914.cisco.com [10.117.10.229]) by rcdn-core2-3.cisco.com (8.14.5/8.14.5) with ESMTP id s0FDIWa3022567; Wed, 15 Jan 2014 13:18:32 GMT
Message-ID: <52D68AA9.1020509@cisco.com>
Date: Wed, 15 Jan 2014 08:18:33 -0500
From: David McGrew <mcgrew@cisco.com>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:17.0) Gecko/20130922 Icedove/17.0.9
MIME-Version: 1.0
To: Watson Ladd <watsonbladd@gmail.com>
References: <20140113230750.6111382.6841.8590@certicom.com> <52D48450.3070701@akr.io> <810C31990B57ED40B2062BA10D43FBF5C1F190@XMB116CNC.rim.net> <52D59C35.10807@cisco.com> <7BAC95F5A7E67643AAFB2C31BEE662D018B7ED7B6F@SC-VEXCH2.marvell.com> <CACsn0ckvQGGG9Fvif25DGVYvseaB1WHC27UoTs2Xpv4hncf8gw@mail.gmail.com>
In-Reply-To: <CACsn0ckvQGGG9Fvif25DGVYvseaB1WHC27UoTs2Xpv4hncf8gw@mail.gmail.com>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Cc: Dan Brown <dbrown@certicom.com>, "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid v Pseudorandom
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <http://www.irtf.org/mail-archive/web/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Wed, 15 Jan 2014 13:18:48 -0000

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
>>
>
>