Re: [Cfrg] Task looming over the CFRG

Michael Hamburg <mike@shiftleft.org> Mon, 05 May 2014 23:10 UTC

Return-Path: <mike@shiftleft.org>
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 027251A03F9 for <cfrg@ietfa.amsl.com>; Mon, 5 May 2014 16:10:26 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 1.557
X-Spam-Level: *
X-Spam-Status: No, score=1.557 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FH_HOST_EQ_D_D_D_D=0.765, FH_HOST_EQ_D_D_D_DB=0.888, HELO_MISMATCH_ORG=0.611, HOST_MISMATCH_NET=0.311, HTML_MESSAGE=0.001, RDNS_DYNAMIC=0.982, SPF_PASS=-0.001] autolearn=no
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 0K3iJbN4Rkw0 for <cfrg@ietfa.amsl.com>; Mon, 5 May 2014 16:10:23 -0700 (PDT)
Received: from aspartame.shiftleft.org (199-116-74-168-v301.PUBLIC.monkeybrains.net [199.116.74.168]) by ietfa.amsl.com (Postfix) with ESMTP id 012E91A03EF for <cfrg@irtf.org>; Mon, 5 May 2014 16:10:22 -0700 (PDT)
Received: from [10.184.148.249] (w035.z205158021.lax-ca.dsl.cnc.net [205.158.21.35]) by aspartame.shiftleft.org (Postfix) with ESMTPSA id ECCF93AA3F; Mon, 5 May 2014 16:08:07 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=shiftleft.org; s=sldo; t=1399331288; bh=Knc+kfkWFaovSTiX2SNAoVZ5vYQUGNqXSqe1v3bq2Uw=; h=Subject:From:In-Reply-To:Date:Cc:References:To:From; b=OkqnttD734kU66YREKW5zf0cRyqiO6eAWVSaED4Oupu/d328fk6RDD2C7aC7WCt1N Vjn6c/nEbbDDdq1ihUukUbwQd3sZrYsqVr93guJvlOaJWIZhArGmClkvKBinX0wzl7 HazO819Fv4wYOeens0wfXEcgkmG++IglaAIqz04w=
Content-Type: multipart/alternative; boundary="Apple-Mail=_3C5FF19B-209F-4F5B-832F-2B9F2B720911"
Mime-Version: 1.0 (Mac OS X Mail 7.2 \(1874\))
From: Michael Hamburg <mike@shiftleft.org>
In-Reply-To: <10B251F2-C589-4AFD-BAD8-9AA1B11E68E6@ll.mit.edu>
Date: Mon, 05 May 2014 16:10:16 -0700
Message-Id: <85E8DDF9-2AF6-4CD3-91D6-7FDDC5DD526E@shiftleft.org>
References: <3C4AAD4B5304AB44A6BA85173B4675CABAA4022F@MSMR-GH1-UEA03.corp.nsa.gov> <E98B42D5-610C-4532-B765-5819A35A456C@shiftleft.org> <3C4AAD4B5304AB44A6BA85173B4675CABAA404E9@MSMR-GH1-UEA03.corp.nsa.gov> <B8586319-F1E6-4CA6-B70E-4D6153DC19A5@shiftleft.org> <10B251F2-C589-4AFD-BAD8-9AA1B11E68E6@ll.mit.edu>
To: "Blumenthal, Uri - 0668 - MITLL" <uri@ll.mit.edu>
X-Mailer: Apple Mail (2.1874)
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/HdljbfpdY67FCZsYKRCXyvBnRWk
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] Task looming over the CFRG
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: Mon, 05 May 2014 23:10:26 -0000

Hi Uri,

Security levels aren’t comparable across primitives.  They technically represent resistance to brute force, but brute force past about 128 bits will not be possible in the foreseeable future.  So instead they represent design conservatism, including features like resistance against quantum attacks (obtainable for AES but not for ECC) or resistance to mathematical breakthroughs.

You should match security at lower levels because a chain isn’t stronger than its weakest link.  But the weakest link in a stronger-than-brute-force system is the one which falls to a math breakthrough, not the one with the fewest bits of security.  Extra bits in the security rating are just extra chances that the breakthrough won’t be big enough.  Since the threats against each system are different, and the math techniques they use are different, each system will stand or fall separately.  Instead of just matching security levels, the optimum will be about performance budgeting.

This is why people don’t use AES-192.  Some engineers are designing for performance- or memory-sensitive applications, or don’t like overengineering, and they pick AES-128.  Others would rather be more conservative, and they pay the extra 40% to go to AES-256.  The halfway solution of AES-192 isn’t used, because it isn’t the optimum for anyone’s performance budget.

So it makes sense that people commonly use AES-256 and sometimes use p384, but rarely p521 and never AES-192.  Going from AES-192 to AES-256 costs 20% on a function which is hardware-accelerated and probably not the bottleneck anyway.  Going from p384 to p521 doubles an already expensive computation (and maybe also gets you sued for patent infringement, but hopefully we can avoid that this time around).

If you want an argument for my specific curve, it’s designed around what I suspect is an inflection point in the security/cost graph — near 448 bits on 32-bit platforms, and 480 bits on 64-bit platfoms.  So Longa et al’s ed-382-mers (their fastest 384-ish-bit curve) costs 590kcy for ECDH on Sandy Bridge.  My curve (Ed448-Goldilocks) costs 674kcy — 14% slower than ed-382-mers, and it includes point compression.  Longa et al’s ed-511-mers costs 1372Mcy — 132% slower than ed-382-mers.  A hypothetical Ed480-Goldeneye built on the same principles might cost 730kcy, but I think it would be worse on ARM.

Anyway, an engineer balancing performance and security might consider the 14% cost hit worthwhile to go from 382 bits to 448 bits (plus point compression), but might not want to pay the 132% cost hit to go all the way to 511 bits.  So perhaps just one curve is enough, particularly if that curve is 448 bits.

Anyway, this argument might not be convincing, but I hope it at least sounds reasonable and worth further discussion.

Cheers,
— Mike

On May 5, 2014, at 2:34 PM, Blumenthal, Uri - 0668 - MITLL <uri@ll.mit.edu> wrote:

> IMHO, the logic/reason of matching security levels of the cryptographic algorithms employed in a protocol suite is fairly obvious and does not need an explicit justification. There might be a reason to have the key-protecting/key-wrapping algorithm a bit (no pun intended! :) stronger than the one that uses that key. I can't think of a reason to protect a key with a weaker algorithm than the key-using one. 
> 
> You observed that strength-matching was not done with RSA (considering the key sizes involved, and where those keys may need to be stored and processed, one possible reason for that mismatch pops up automatically :).
> 
> More surprisingly, matching was not done with ECC either. We don't have an explanation for this design choice. Copying designs we don't understand (or do we?) does not sound like a good recipe.
> 
> Let me ask you: could you explain why you want to mix algorithms of different cryptographic strength? What benefit do you derive from including a stronger algorithm in a chain made of weaker algorithms? How big would your performance gain be?
> --
> Regards,
> Uri               <uri@ll.mit.edu>
> 
> 
> On May 5, 2014, at 16:55 , Michael Hamburg <mike@shiftleft.org>
>  wrote:
> 
>> Kevin,
>> 
>> Sorry to be ambiguous: the curve I designed has a 448-bit field and a 446-bit prime-order subgroup, so a parallel rho attack should cost just under 2^223 point operations on average.  So it sits between the 192 and 256-bit security levels.
>> 
>> I’m not particularly invested in getting this curve into TLS, but I’d like to know whether there’s a point in submitting it for this purpose, or if it will be rejected for having the “wrong security level".
>> 
>> Matching the nominal security level of the asymmetric part to that of the symmetric part sounds obvious on its face, but in fact it is not usually done above the 128-bit level.  For example, Suite B doesn’t specify a direct matching of nominal security levels: it specifies AES-256 with SHA-384 and ECDSA-NIST-p384 for TOP SECRET communications.  Likewise, almost nobody pairs AES-256 with the matching RSA-15k, and even AES-128 is usually paired with the nominally weaker RSA-2048.
>> 
>> This actually makes sense.  Nobody is going to do a 128-bit exhaust for many decades.  Not Google, not the NSA, not the KGB, nobody.  With today’s most efficient supercomputers, the heat output from 2^128 operations would be far more than enough to boil the oceans dry [1].  So we’re talking about defenses against sub-128-bit attacks, and defense in depth against hypothetical advances in cryptography, and quantum resistance for primitives that can resist at all.  Stronger curves, ciphers and hashes will stand or fall on their own, not all together as computer power surpasses their nominal security level.
>> 
>> Also, nobody uses AES-192.
>> 
>> So I don’t think it’s obvious that matching the AES security levels is a requirement.  If the RG thinks it is, or if there’s some obscure legal requirement that the levels match, then fine.  Just describe why.
>> 
>> Cheers,
>> — Mike
>> 
>> [1] Lenstra, Kleinjung, Thomé.  “Universal security: from bits and mips to pools, lakes — and beyond”.  https://eprint.iacr.org/2013/635.pdf
>> 
>> On May 5, 2014, at 12:49 PM, Igoe, Kevin M. <kmigoe@nsa.gov> wrote:
>> 
>>> Mike:
>>>  
>>>   Being off by a few bits isn’t a show stopper. but 32-bits is probably too
>>> much.  The security levels echo the AES security levels of AES-128, AES-192
>>> and AES-256.  Using a 224 bit curve with AES-128 only provides roughly 112-bits
>>> of security versus the 128 bits ostensibly provided by AES-128.  I just want to ensure
>>> that a user who thinks they are getting 128 bits of security gets 128 bits of 
>>> security.
>>>  
>>>                               Kevin
>>>  
>>> From: Michael Hamburg [mailto:mike@shiftleft.org] 
>>> Sent: Monday, May 05, 2014 2:25 PM
>>> To: Igoe, Kevin M.
>>> Cc: cfrg@irtf.org
>>> Subject: Re: [Cfrg] Task looming over the CFRG
>>>  
>>> Hi Kevin,
>>>  
>>> As the designer of an ECC system which is aimed at 224-ish-bit security, I’m curious: is it a firm requirement that the curves be set at 128, 192 and 256 bits?  Or was there consensus in the meeting that the curves should be set at these security levels?  Patrick Longa aimed his talk at these security levels, but I don’t recall this being stated as a requirement.
>>>  
>>> Cheers,
>>> — Mike
>>>  
>>>  
>>> On May 5, 2014, at 10:58 AM, Igoe, Kevin M. <kmigoe@nsa.gov> wrote:
>>> 
>>> 
>>> As most the folks who read this list have noticed, a virtual interim meeting of the CFRG
>>> was held on Tues 29 April to discuss the way forward for elliptic curve cryptography
>>> in the IETF.  This was driven by an earnest plea from the TLS WG for firm guidance from 
>>> the CGRG on the selection of elliptic curves for use in TLS.  They need an answer before 
>>> the Toronto IETF meeting in late July.  TLS needs curves for several levels of security (128, 
>>> 192 and 256), suitable for use in both key agreement and in digital signatures.
>>>  
>>> ·         The consensus of the attendees was that it would be best for TLS to have a single
>>> “mandatory to implement” curve for each of the three security levels.
>>>  
>>> ·         Though the attendees were reluctant to make a formal commitment, there
>>> was clearly a great deal of support for the Montgomery curve curve25519 (FYI, the 
>>> 25519 refers to the fact that arithmetic is done modulo the prime 2**255 – 19 ).
>>>  
>>> ·         curve25519 only fills one of the three required security levels.  We still need
>>> curves of size near 384 bits and 512 bits.
>>>  
>>> ·         NIST curves: I doubt TLS will be willing to revisit the question of elliptic curves once the 
>>> CFRG has made their recommendation.  Another option to consider is advising TLS to
>>> use of the NIST curves in the short term, buying time for the CFRG to do an unrushed 
>>> exploration of the alternatives, drawing academia and other standards bodies into the 
>>> discussion.
>>>  
>>> P.S.  It has been suggested that the CFRG hold a session at the Crypto conference in
>>> Santa Barbara in an effort to draw in more participation from the academic community.
>>> No guarantees we can pull this off, but it is worth the attempt. Thoughts? Volunteers?
>>>  
>>> P.P.S. We need to start lining up speakers for the CFRG session at IETF-90 (Toronto).
>>>  
>>>  
>>> ----------------+--------------------------------------------------
>>> Kevin M. Igoe   | "We can't solve problems by using the same kind
>>> kmigoe@nsa.gov  | of thinking we used when we created them."
>>>                 |              - Albert Einstein -
>>> ----------------+--------------------------------------------------
>>>  
>>>  
>>>  
>>> _______________________________________________
>>> 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
>