Re: [Cfrg] I-D Action: draft-irtf-cfrg-argon2-02.txt
"Blocki, Jeremiah M" <jblocki@purdue.edu> Thu, 15 June 2017 15:36 UTC
Return-Path: <jblocki@purdue.edu>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 875781294F8 for <cfrg@ietfa.amsl.com>; Thu, 15 Jun 2017 08:36:40 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -4.2
X-Spam-Level:
X-Spam-Status: No, score=-4.2 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_MED=-2.3, RP_MATCHES_RCVD=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=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 82AX9Rf1YH0q for <cfrg@ietfa.amsl.com>; Thu, 15 Jun 2017 08:36:37 -0700 (PDT)
Received: from mailhub131.itcs.purdue.edu (mailhub131.itcs.purdue.edu [128.210.5.131]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 79B77126B6E for <cfrg@ietf.org>; Thu, 15 Jun 2017 08:36:37 -0700 (PDT)
Received: from exchange.purdue.edu (exchange.purdue.edu [128.210.1.29]) by mailhub131.itcs.purdue.edu (8.14.4/8.14.4/mta-nopmx.smtp.purdue.edu) with ESMTP id v5FFaZ7Q011033 (version=TLSv1/SSLv3 cipher=AES256-SHA bits=256 verify=NOT); Thu, 15 Jun 2017 11:36:36 -0400
Received: from wppexc07.purdue.lcl (172.30.136.180) by wppexc12.purdue.lcl (172.30.136.185) with Microsoft SMTP Server (TLS) id 15.0.1178.4; Thu, 15 Jun 2017 11:36:35 -0400
Received: from wppexc07.purdue.lcl ([fe80::49db:3fa0:d668:8da4]) by wppexc07.purdue.lcl ([fe80::49db:3fa0:d668:8da4%14]) with mapi id 15.00.1178.000; Thu, 15 Jun 2017 11:36:35 -0400
From: "Blocki, Jeremiah M" <jblocki@purdue.edu>
To: "Paterson, Kenny" <Kenny.Paterson@rhul.ac.uk>, "cfrg@ietf.org" <cfrg@ietf.org>
Thread-Topic: [Cfrg] I-D Action: draft-irtf-cfrg-argon2-02.txt
Thread-Index: AQHSpudr72kny3qHWUqPlyLx0FrlmqGoxV6AgH3z6wD//8H0gA==
Date: Thu, 15 Jun 2017 15:36:34 +0000
Message-ID: <dd40d721470e4ba58a7e86c561ce293c@wppexc07.purdue.lcl>
References: <149061159741.30566.11599293166376872082@ietfa.amsl.com> <CALW8-7+BL5dLJiTh_yn_OD8pNNwLvEz5ZPhqK=-TfUH3xvohBg@mail.gmail.com> <D56853D6.96722%kenny.paterson@rhul.ac.uk>
In-Reply-To: <D56853D6.96722%kenny.paterson@rhul.ac.uk>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
x-ms-exchange-transport-fromentityheader: Hosted
x-originating-ip: [128.10.9.85]
Content-Type: text/plain; charset="utf-8"
Content-Transfer-Encoding: base64
MIME-Version: 1.0
X-PMX-Version: 6.0.2.2308539
X-PerlMx-URL-Scanned: Yes
X-PerlMx-Virus-Scanned: Yes
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/V17fLSZvFaHBwCQ3Kf6b--GCkTE>
Subject: Re: [Cfrg] I-D Action: draft-irtf-cfrg-argon2-02.txt
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.22
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Thu, 15 Jun 2017 15:36:40 -0000
Hi All, 1) I agree with the recommendation to use Argon2id for password hashing as it appears to strike a reasonable balance between side-channel resistance and parallel attacks. If there are no side channel attacks then Argon2id resists recent parallelization attacks [AB16], and if there are side channel attacks then security should hopefully just reduce to that of Argon2i. 2) Regarding the data-independent mode (Argon2i) I wanted to highlight two recent results from my own work which I believe are relevant to the discussion: a) Samson Zhou and I recently proved new *lower bounds* for Argon2i (the proof encompasses versions 1.2+). The paper is available on ePrint http://eprint.iacr.org/2017/442.pdf. In summary, the cumulative memory cost (cmc) of computing Argon2iB (versions 1.2+) is at least Omega(n^{1.75}) (ignoring logarithmic factors), which means that in an asymptotic sense the existing attacks are nearly optimal. The new lower bound demonstrates that Argon2iB (versions 1.2+) improves on Argon2iA (v.1.1) and other competing data-independent memory hard functions (iMHFs) such as Balloon Hashing (cmc <= O(n^1.708)) or Catena (cmc <= O(n^{1.625})). b) For an iMHF the best one can hope for is cmc >= n^2/log(n) [AB16]. There are matching constructions [ABP17], but until recently these constructions have been purely theoretical e.g., relying on an expensive combinatorial construction of Erdos, Graham and Szemeredi of depth-robust graphs. Joel Alwen, Ben Harsha and I recently gave a very simple construction of a depth-robust graph, which is easy to implement as part of an iMHF. Our empirical analysis indicates that the new iMHF construction provides strong resistance to parallel attacks. We also modified the Argon2i implementation to use this new edge distributed. The modifications do not adversely affect performance. For the curious we have code available at https://github.com/Practical-Graphs/Argon2-Practical-Graph. The paper is available on ePrint at http://eprint.iacr.org/2017/443.pdf. Thanks, Jeremiah -----Original Message----- From: Cfrg [mailto:cfrg-bounces@irtf.org] On Behalf Of Paterson, Kenny Sent: Thursday, June 15, 2017 10:17 AM To: cfrg@ietf.org Subject: Re: [Cfrg] I-D Action: draft-irtf-cfrg-argon2-02.txt Dear CFRG, Dmitry Khovratovich kindly presented the latest draft for Argon2 at the interim CFRG meeting in Paris. For those of you who could not attend, his slides can be found here: https://www.ietf.org/proceedings/interim-2017-cfrg-01/slides/slides-interim -2017-cfrg-01-sessa-argon2-00.pdf My sense from the constructive discussion that took place after Dmitry's talk in Paris was that there are now no remaining serious objections to the recommended parameters in the latest version of the draft: https://datatracker.ietf.org/doc/draft-irtf-cfrg-argon2/ If there are further substantive technical comments from the CFRG membership, the chairs would be grateful if they could be brought to the list in the next few days. Assuming we have indeed reached consensus, then we will be in a position to move to last call for this ID. Thanks, Kenny (for the chairs) On 27/03/2017 11:51, "Cfrg on behalf of Dmitry Khovratovich" <cfrg-bounces@irtf.org on behalf of khovratovich@gmail.com> wrote: >Some comments on a new draft:VariantsArgon2 fills M bytes of memory in >T iterations over it, with M and T being the parameters supplied to >Argon2 and determining its performance. Speed on a typical server is >linear in the MT product. > >The Argon2 family has three variants: I, D, and ID, which differ in >the way of reusing memory that has been filled. The I variant makes >queries with predictable addresses, whereas D determines the addresses >on the fly depending on the current state (and thus the password). The >ID variant follows I for the first half of the memory used and D for >the rest and while overwriting. >Side-channelsThe side-channel attacks, which are of still rising >concern in the security community, are applicable to the D variant as >the memory addresses and thus information about the password or other >secret inputs can be determined from the timing leaks. The I variant is >completely invulnerable to this attack, and the ID variant provides >only a constant factor improvement for the attacker. >Hardware and tradeoffsThe M and T parameters determine the cost of >bruteforcing passwords on custom hardware, which is proportional to >M2T if we follow the traditional time-area product metric. The >time-memory tradeoff analysis [2] shows that the bruteforce cost for >the I variant can be changed to M2T/Q(M,T) for some quality function >Q. For instance, Q(230,1)=5, Q(230,4)=2.5. > >The D variant is invulnerable to the approach [2], and the savings >factor in the ID variant is upper bounded by factor 2 for all >parameters. >Defender tradeoff and ultimate > recommendationsIn public and private conversations with security >architects in the industry we learned that the bottleneck in a system >employing the password-hashing function is the function latency rather >than memory costs. We then assume that a rational defender would like >to maximize the bruteforce costs for the attacker equipped with a list >of hashes, salts, and timing information, for fixed computing time on >the defender’s machine. In this assumption the defender keeps the MT >product constant and maximizes the losses M/Q(M,T). > The authors of [2] provides us with attack cost estimates for constant >MT = 228,230,232 (measured in iteration-bytes) > >We ultimately recommend the ID variant with T=1 and maximum M as a >default setting for all environments, which is secure against >side-channel attacks and prohibit adversarial advantage on dedicated >bruteforce hardware. > > >References[1] >“Efficiently Computing Data-Independent Memory-Hard Functions” ><http://eprint.iacr.org/2016/115.pdf> >[2] >“Towards Practical Attacks on > Argon2i and Balloon Hashing” <http://eprint.iacr.org/2016/759.pdf> > > > > > >On Mon, Mar 27, 2017 at 12:46 PM, <internet-drafts@ietf.org> wrote: > > >A New Internet-Draft is available from the on-line Internet-Drafts >directories. >This draft is a work item of the Crypto Forum of the IETF. > > Title : The memory-hard Argon2 password hash and >proof-of-work function > Authors : Alex Biryukov > Daniel Dinu > Dmitry Khovratovich > Simon Josefsson > Filename : draft-irtf-cfrg-argon2-02.txt > Pages : 26 > Date : 2017-03-27 > >Abstract: > This document describes the Argon2 memory-hard function for password > hashing and proof-of-work applications. We provide an implementer > oriented description together with sample code and test vectors. The > purpose is to simplify adoption of Argon2 for Internet protocols. > > >The IETF datatracker status page for this draft is: >https://datatracker.ietf.org/doc/draft-irtf-cfrg-argon2/ > >There are also htmlized versions available at: >https://tools.ietf.org/html/draft-irtf-cfrg-argon2-02 >https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-argon2-02 > >A diff from the previous version is available at: >https://www.ietf.org/rfcdiff?url2=draft-irtf-cfrg-argon2-02 > > >Please note that it may take a couple of minutes from the time of >submission until the htmlized version and diff are available at >tools.ietf.org <http://tools.ietf.org>. > >Internet-Drafts are also available by anonymous FTP at: >ftp://ftp.ietf.org/internet-drafts/ > >_______________________________________________ >Cfrg mailing list >Cfrg@irtf.org >https://www.irtf.org/mailman/listinfo/cfrg > > > > > > > >-- >Best regards, >Dmitry Khovratovich > > _______________________________________________ Cfrg mailing list Cfrg@irtf.org https://www.irtf.org/mailman/listinfo/cfrg
- [Cfrg] I-D Action: draft-irtf-cfrg-argon2-02.txt internet-drafts
- Re: [Cfrg] I-D Action: draft-irtf-cfrg-argon2-02.… Dmitry Khovratovich
- Re: [Cfrg] I-D Action: draft-irtf-cfrg-argon2-02.… Paterson, Kenny
- Re: [Cfrg] I-D Action: draft-irtf-cfrg-argon2-02.… Blocki, Jeremiah M
- Re: [Cfrg] I-D Action: draft-irtf-cfrg-argon2-02.… Paterson, Kenny
- Re: [Cfrg] I-D Action: draft-irtf-cfrg-argon2-02.… Dmitry Khovratovich