Subject: Re: [Cfrg] I-D Action: draft-irtf-cfrg-argon2-02.txt

From: "Paterson, Kenny" <[email-masked]>
Date: Thu, 15 Jun 2017 14:16:46 +0000

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"
<[email-masked] on behalf of [email-masked]> 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, <[email-masked]> 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
>[email-masked]
>https://www.irtf.org/mailman/listinfo/cfrg
>
>
>
>
>
>
>
>-- 
>Best regards,
>Dmitry Khovratovich
>
>

---

From: "Blocki, Jeremiah M" <[email-masked]>
Date: Thu, 15 Jun 2017 15:36:34 +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:[email-masked]] On Behalf Of Paterson, Kenny
Sent: Thursday, June 15, 2017 10:17 AM
To: [email-masked]
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:

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:

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"
<[email-masked] on behalf of [email-masked]> 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.
>completely invulnerable to this attack, and  the ID variant provides 
>only a constant factor improvement for the attacker.
>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.
>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 
>MT = 228,230,232  (measured in iteration-bytes)
>
>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]
>submission until the htmlized version and diff are available at