Re: [Cfrg] 2^40. I can't exhibit it, but it exists.

Paul Lambert <paul@marvell.com> Tue, 04 February 2014 22:06 UTC

Return-Path: <paul@marvell.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 53D601A015A for <cfrg@ietfa.amsl.com>; Tue, 4 Feb 2014 14:06:49 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.566
X-Spam-Level:
X-Spam-Status: No, score=-1.566 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, HTML_MESSAGE=0.001, IP_NOT_FRIENDLY=0.334, 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 D4zZqmjsZx3X for <cfrg@ietfa.amsl.com>; Tue, 4 Feb 2014 14:06:47 -0800 (PST)
Received: from mx0a-0016f401.pphosted.com (mx0a-0016f401.pphosted.com [67.231.148.174]) by ietfa.amsl.com (Postfix) with ESMTP id 06F481A0163 for <cfrg@irtf.org>; Tue, 4 Feb 2014 14:06:46 -0800 (PST)
Received: from pps.filterd (m0045849.ppops.net [127.0.0.1]) by mx0a-0016f401.pphosted.com (8.14.5/8.14.5) with SMTP id s14M48St021597; Tue, 4 Feb 2014 14:06:44 -0800
Received: from sc-owa01.marvell.com ([199.233.58.136]) by mx0a-0016f401.pphosted.com with ESMTP id 1hsj9vx5v2-1 (version=TLSv1/SSLv3 cipher=RC4-MD5 bits=128 verify=NOT); Tue, 04 Feb 2014 14:06:44 -0800
Received: from SC-vEXCH2.marvell.com ([10.93.76.134]) by SC-OWA01.marvell.com ([10.93.76.21]) with mapi; Tue, 4 Feb 2014 14:06:42 -0800
From: Paul Lambert <paul@marvell.com>
To: Watson Ladd <watsonbladd@gmail.com>, "rransom. 8774" <rransom.8774@gmail.com>, "cfrg@irtf.org" <cfrg@irtf.org>
Date: Tue, 04 Feb 2014 14:06:41 -0800
Thread-Topic: 2^40. I can't exhibit it, but it exists.
Thread-Index: Ac8h5VnQAI7gf5fFRcaXZSLocEKoowAALzEg
Message-ID: <7BAC95F5A7E67643AAFB2C31BEE662D018B81B7F7C@SC-VEXCH2.marvell.com>
References: <20140203192451.6268.76511.idtracker@ietfa.amsl.com> <7af2f9df96e5867d493c614806235363.squirrel@www.trepanning.net> <CACsn0cm1f-P95je5AbEbZ02Ut3+HM7Hx28P6j46TqE-=06eZDg@mail.gmail.com> <52F00EF3.3040505@cisco.com> <CACsn0c=zS5GKex3eF_hKgTsL1kH=TiBi3iAP9oMrJ9hDQcT4Gw@mail.gmail.com> <7BAC95F5A7E67643AAFB2C31BEE662D018B81B7DE5@SC-VEXCH2.marvell.com> <CACsn0cn0TaHsDkyN2ewOorxxBzXivCg=QGR-ZnBiC3nJhvhpRg@mail.gmail.com> <14AB44E0-4C90-4E4C-A656-885A31CF4C02@checkpoint.com> <CACsn0cmDT-FAN8uMZ0w8TX6GKPAZjnrexLeFQd7QhRfoY6AGFQ@mail.gmail.com> <75e1e853dc391b418062ee5e51adeb2f.squirrel@www.trepanning.net> <CABqy+sr7ZKrACj4Ga2_75d9Kea0aKbrp2P5fWWu4YZP53zijxw@mail.gmail.com> <CACsn0cmS152wYQWHiX8ykzaMM=6b=r=fwVuLfPj_u0wmoq0jKw@mail.gmail.com>
In-Reply-To: <CACsn0cmS152wYQWHiX8ykzaMM=6b=r=fwVuLfPj_u0wmoq0jKw@mail.gmail.com>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
acceptlanguage: en-US
Content-Type: multipart/alternative; boundary="_000_7BAC95F5A7E67643AAFB2C31BEE662D018B81B7F7CSCVEXCH2marve_"
MIME-Version: 1.0
X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10432:5.11.87, 1.0.14, 0.0.0000 definitions=2014-02-04_06:2014-02-04, 2014-02-04, 1970-01-01 signatures=0
X-Proofpoint-Spam-Details: rule=outbound_notspam policy=outbound score=0 spamscore=0 suspectscore=0 phishscore=0 adultscore=0 bulkscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=7.0.1-1305240000 definitions=main-1402040126
Subject: Re: [Cfrg] 2^40. I can't exhibit it, but it exists.
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: Tue, 04 Feb 2014 22:06:49 -0000

>From: Cfrg [mailto:cfrg-bounces@irtf.org] On Behalf Of Watson Ladd
>Sent: Tuesday, February 04, 2014 12:12 PM


>This attack is interesting because of the limits it puts on reductions, which are
>the main tool for doing cryptography. If dragonfly could be shown to have no
>other weaknesses this would be fine, but no such proof is forthcoming.

When you say ‘no other’ you continue to imply that you have identified a realistic exploitable weakness. The difficulty in ‘reducing’ the Dragonfly proposal is not a exploitable flaw.  The changes necessary in protocol to allow a formal proof may in fact weaken the overall security of the protocol (reference below).

                        On the Security Loss in Cryptographic Reductions
Proceeding: EUROCRYPT '09 Proceedings of the 28th Annual International Conference on Advances in Cryptology: the Theory and Applications Cryptographic Techniques
Pages 72 - 87
Almost all the important cryptographic protocols we have today base their security on unproven assumptions, which all imply NP $\ne$ P, and thus having unconditional proofs of their security seems far beyond our reach. One research effort then is to identify more basic primitives and prove the security of these protocols by reductions to the security of these primitives. However, in doing so, one often observes some security loss in the form that the security of the protocols is measured against weaker adversaries, e.g., adversaries with a smaller running time. Is such a security loss avoidable? We study two of the most basic cryptographic reductions: hardness amplification of one-way functions and constructing pseudorandom generators from one-way functions. We show that when they are done in a certain black-box way, such a security loss is in fact unavoidable.


Your adamancy to make up issues with Dragonfly seems to imply you feel this is a ‘down selection’ between multiple protocols.  It is not.  TLS is one possible application, but the Dragonfly protocol was written in a generic manner to specifically allow the analysis independent of the target application.  Other schemes would be viable for TLS and I would strongly support publication and review of multiple password protocol  alternatives for TLS.

The Dragonfly protocol has been in other standards act ivies for quite a few years (usually called  SAE).  The review in this forum has improved side channel security.  Your suggestions for other TLS solutions should not block the analysis of this protocol if it is secure.  Making sure we have clarity on the actual security of a fielded solution in critical and we should be professional and correct in our analysis.  Mesh networking networks are using SAE (aka Dragonfly).  Other consumer oriented applications will appear based on the analysis that the protocol has no exploitable weakness.

Do also note that the  IPR disclosures for AugPAKE that you advocate have limitations and are constrained to the IETF and TLS.  AugPAKE is completely unacceptable for any broader application in consumer equipment (IMHO).  There are many engineering criteria to balance in the section of appropriate algorithms for the industry.  Support of ‘reductions’ for a formal proof are way down the list in my priorities.  I see that we disagree on this point, and hope that you would look at the broader set of industry requirements  and tone down your rhetoric.  If you continue to have objections, please be clear and correct with the analysis.  You still owe the group a clarification or a retraction on your claimed  2^40th attack on Dragonfly.

Thanks,

Paul



From: Cfrg [mailto:cfrg-bounces@irtf.org] On Behalf Of Watson Ladd
Sent: Tuesday, February 04, 2014 12:12 PM
To: rransom. 8774; cfrg@irtf.org
Subject: Re: [Cfrg] I-D Action: draft-irtf-cfrg-dragonfly-03.txt


On Feb 4, 2014 11:41 AM, "Robert Ransom" <rransom.8774@gmail.com<mailto:rransom.8774@gmail.com>> wrote:
>
> On 2/4/14, Dan Harkins <dharkins@lounge.org<mailto:dharkins@lounge.org>> wrote:
>
> >   This is mentioned in section 6.3 of RFC 5931 (dragonfly as an EAP
> > method), knowledge of r where PE = r * G can enable a dictionary
> > attack. But knowledge of r requires doing a discrete logarithm. A discrete
> > logarithm is assumed to be "computationally infeasible" and you're talking
> > about doing 2^40 of them!?!
>
> <http://cr.yp.to/papers.html#nonuniform> is relevant here.  It
> discusses several other ‘attacks’ of this general type, and explains
> why they should not be taken seriously.

Bernstein actually argues that one should define complexity measures to exclude such attacks. This is clear in the paper. Unfortunately time memory product for the weak password variation is only 2^40.

The problem with foundations of hashing usually isn't a real problem: one can sign r,H (r, m) with r random to bypass it.

This attack is interesting because of the limits it puts on reductions, which are the main tool for doing cryptography. If dragonfly could be shown to have no other weaknesses this would be fine, but no such proof is forthcoming.

Such a proof would be in the ROM, but as the IETF 88 slides show it would be tricky.
>
>
> Robert Ransom