Subject: Re: [Cfrg] [MASSMAIL]Re: adopting Argon2 as a CFRG document

From: Dmitry Khovratovich <[email-masked]>
Date: Sat, 21 May 2016 10:38:43 +0200

Some clarifications due to the increased attention to the paper by Alwen
and Blocki, which has been presented at the recent Eurocrypt CFRG meeting.

1. One of security parameters of memory-hard password hashing functions is
how much an ASIC attacker can reduce the area-time product (AT) of a
password cracker implemented on ASIC. The AT is conjectured to be
proportional to the amortized cracking cost per password.

2. The memory-hard functions with input-independent memory access (such as
Argon2i) have been known for its relatively larger AT-reduction factor
compared to functions with input-dependent memory access (such as Argon2d).
To mitigate this, the minimum of 3 passes over memory for Argon2i was set.

3. The best attacks on Argon2, published in the original design document in
early 2015, have factor 1.3 for Argon2d and factor 3 for Argon2i.

4. The best attack found by Alwen and Blocki has factor 2 for Argon2i.

5. In a bit more details, the advantage of the Alwen-Blocki attack is upper
bounded by (M^{1/4})/36, where M is the number of kilobytes used by
Argon2i. Thus the attack has factor 2 with memory up to 16 GB, and less
than 1 for memory up to 1 GB. Details in Section 5.6 of
https://www.cryptolux.org/images/0/0d/Argon2.pdf

Best regards,
Argon2 team

On Mon, Feb 1, 2016 at 10:06 PM, Dmitry Khovratovich <[email-masked]
> wrote:

> Dear all,
>
> as explained in a recent email
> http://article.gmane.org/gmane.comp.security.phc/3606 , we are fully
> aware of the analysis of Argon2i made by Corrigan-Gibbs et al. , we know
> how to mitigate the demonstrated effect, and have already made some
> benchmarks on the patch.
>
> Soon after the Crypto deadline (Feb-9) we will develop a new release
> including code, rationale, and test vectors.
>
> --
> Best regards,
> the Argon2 team.
>

-- 
Best regards,
Dmitry Khovratovich

---

From: Joel Alwen <[email-masked]>
Date: Wed, 25 May 2016 15:44:16 -0400

> 3. The best attacks on Argon2, published in the original design 
> document in early 2015, have factor 1.3 for Argon2d and factor 3 for
>  Argon2i.
> 
> 5. In a bit more details, the advantage of the Alwen-Blocki attack
> is upper bounded by (M^{1/4})/36, where M is the number of kilobytes
>  used by Argon2i. Thus the attack has factor 2 with memory up to 16 
> GB, and less than 1 for memory up to 1 GB. Details in Section 5.6 of 

I believe the results of Alwen-Blocki (AB16) actually show that at least
6 passes over memory are required for the above suggested parameters.
 - See Corollary 5.6 in [1]
 - See Figure 1(a) in [1] and paragraph titled "Parameter Optimization"

[1] https://eprint.iacr.org/2016/115

Moreover, I think it important to note that the analysis of the attack
complexity in [1] is very "worst case" in several ways and that this
leaves room for significantly improvements in practice. And of course
the analysis was not optimized for concrete parameters such as those
mentioned above.

Basically I think there are several good reasons to believe that 6
passes over memory are also not sufficient to avoid the attack.

- Joel

On 05/21/2016 04:38 AM, Dmitry Khovratovich wrote:
> Some clarifications due to the increased attention to the paper by 
> Alwen and Blocki, which has been presented at the recent Eurocrypt 
> CFRG meeting.
> 
> 1. One of security parameters of memory-hard password hashing 
> functions is how much an ASIC attacker can reduce the area-time 
> product (AT) of a password cracker implemented on ASIC. The AT is 
> conjectured to be proportional to the amortized cracking cost per 
> password.
> 
> 2. The memory-hard functions with input-independent memory access 
> (such as Argon2i) have been known for its relatively larger 
> AT-reduction factor compared to functions with input-dependent memory
> access (such as Argon2d). To mitigate this, the minimum of 3 passes
> over memory for Argon2i was set.
> 
> 3. The best attacks on Argon2, published in the original design 
> document in early 2015, have factor 1.3 for Argon2d and factor 3 for
>  Argon2i.
> 
> 5. In a bit more details, the advantage of the Alwen-Blocki attack
> is upper bounded by (M^{1/4})/36, where M is the number of kilobytes
>  used by Argon2i. Thus the attack has factor 2 with memory up to 16 
> GB, and less than 1 for memory up to 1 GB. Details in Section 5.6 of 
> Best regards, Argon2 team
> 
> On Mon, Feb 1, 2016 at 10:06 PM, Dmitry Khovratovich 
> <[email-masked] <mailto:[email-masked]>> wrote:
> 
> Dear all,
> 
>  aware of the analysis of Argon2i made by Corrigan-Gibbs et al. , we
>  know how to mitigate the demonstrated effect, and have already made
>  some benchmarks on the patch.
> 
> -- Best regards, the Argon2 team.
> 
> 
> 
> 
> -- Best regards, Dmitry Khovratovich
> 
> 
> _______________________________________________ Cfrg mailing list 
> [email-masked] https://www.irtf.org/mailman/listinfo/cfrg
>

---

From: Jean-Philippe Aumasson <[email-masked]>
Date: Tue, 31 May 2016 07:49:30 +0000

Hi,

I've been told that at the latest CFRG meeting, someone suggested to re-run
PHC. I wasn't there so I don't know if it was serious or just a joke, but as
lead organizer of PHC I confirm that this won't happen.

Furthermore, my understanding is that the Alwen-Blocki attack on Argon2i
isn't more efficient than attacks already documented, as discussed in 5.6
in https://www.cryptolux.org/images/0/0d/Argon2.pdf. So I don't see these
new results as a showstopper.

I therefore totally support Argon2 standardization efforts.

Best,

JP

---

From: Joel Alwen <[email-masked]>
Date: Tue, 31 May 2016 12:00:37 +0200

> Furthermore, my understanding is that the Alwen-Blocki attack on 
> Argon2i isn't more efficient than attacks already documented, as 
> discussed in 5.6 in
> https://www.cryptolux.org/images/0/0d/Argon2.pdf. So I don't see
> these new results as a showstopper.

Actually the Alwen-Blocki is more efficient then other known attacks
both in terms of asymptotic and exact constants for interesting
parameter ranges. This is already true for the worst case analysis in
the paper. (See my earlier email in this thread for and references on
this.) Moreover there is good reason to believe that it will behave far
better in practice and that it can also be further improved.

To be clear: I am neither advocating for nor against Argon2i (or any
other algorithm). My intention at this point is to clarify what is
actually known about Argon2i.

As to why I responded positively to Kenny's question about having a new
PHC *in an ideal world*; the reason is that recent results both in terms
of attacks and security proofs all point towards a new desirable
property of an iMHF. That is the underlying DAG of the iMHF should have
a specific combinatoric property (called depth-robustness). Not only is
being depth-robust necessary to avoid the AB16 attack, it also allows us
to make provable security type statements. However constructing the most
efficient & simple such graphs is not a trivial task, especially not
ones which result in the strongest possible provable security
statements. As such a, concerted effort to produce the best such graph
combined with other properties we have learned about in the previous PHC
would likely result in a significantly improved iMHF compared to
everything we currently have available. Of course we may not want to
wait for this, nor spend the energy on it. My reasoning and response
were mindful of the "in an ideal world" part of the question.

- joel

 On Wed, May 25, 2016 at 9:44 PM Joel Alwen <[email-masked]
> <mailto:[email-masked]>> wrote:
> 
> 
>> document in early 2015, have factor 1.3 for Argon2d and factor 3 
>> for Argon2i.
>> 
>>  is upper bounded by (M^{1/4})/36, where M is the number of 
>> kilobytes used by Argon2i. Thus the attack has factor 2 with
>> memory up to 16 GB, and less than 1 for memory up to 1 GB. Details
>> in Section 5.6 of https://www.cryptolux.org/images/0/0d/Argon2.pdf
> 
> I believe the results of Alwen-Blocki (AB16) actually show that at 
> least 6 passes over memory are required for the above suggested 
> parameters. - See Corollary 5.6 in [1] - See Figure 1(a) in [1] and 
> paragraph titled "Parameter Optimization"
> 
> Moreover, I think it important to note that the analysis of the 
> attack complexity in [1] is very "worst case" in several ways and 
> that this leaves room for significantly improvements in practice.
> And of course the analysis was not optimized for concrete parameters
> such as those mentioned above.
> 
>> AT-reduction factor compared to functions with input-dependent 
>> memory access (such as Argon2d). To mitigate this, the minimum of
>> 3 passes over memory for Argon2i was set.
>> 
>> document in early 2015, have factor 1.3 for Argon2d and factor 3 
>> for Argon2i.
>> 
>>  is upper bounded by (M^{1/4})/36, where M is the number of 
>> kilobytes used by Argon2i. Thus the attack has factor 2 with
>> memory up to 16 GB, and less than 1 for memory up to 1 GB. Details
>> in Section 5.6 of https://www.cryptolux.org/images/0/0d/Argon2.pdf
>> 
>> <[email-masked] <mailto:[email-masked]>
> <mailto:[email-masked] <mailto:[email-masked]>>> 
> wrote:
>> 
>> Dear all,
>> 
>> http://article.gmane.org/gmane.comp.security.phc/3606 , we are 
>> fully aware of the analysis of Argon2i made by Corrigan-Gibbs et 
>> al. , we know how to mitigate the demonstrated effect, and have 
>> already made some benchmarks on the patch.
>> 
>> Soon after the Crypto deadline (Feb-9) we will develop a new 
>> release including code, rationale, and test vectors.
>> 
>> [email-masked] <mailto:[email-masked]>
> https://www.irtf.org/mailman/listinfo/cfrg
>> 
> 
-

---

From: Jean-Philippe Aumasson <[email-masked]>
Date: Tue, 31 May 2016 10:44:15 +0000

I haven't read the AB16 paper, but I observe that

1) Argon2 designers say "the AB16 attack is less efficient than known
attacks"

2) Joel says "the AB16 attack is more efficient than known attacks"

Are you guys both right for different notions of "efficient", or is one of
your analyses wrong?

Specifically: Joel, is there something that strikes you as incorrect in the
analysis in 5.6 of https://www.cryptolux.org/images/0/0d/Argon2.pdf?

---

From: Stefano Tessaro <[email-masked]>
Date: Tue, 31 May 2016 10:07:41 -0700

This may be obvious to many, but a point that I believe is not
stressed enough in the on-going discussion is that the AB16 attack
shows a substantial *asymptotic* improvement over what could be
expected from a memory-hard function.

In contrast, comparisons here are focusing on the *concrete*
complexity of the AB16 attack for actual real-world parameters,
compared with the best known attacks against Argon2i. (The latter
attacks do not seem to have an obvious asymptotic generalization
outperforming the AB16 attack, but I am happy to be corrected on
this.)

Regardless of which attack performs best, asymptotic breaks typically
tell us more about a construction than just a number.

Indeed, constants and log-factors are likely to be improved in future
works, and the real question seems to be how much value one should put
in asymptotic attacks and how much Argon2i (or any other design
affected by the attacks) is resilient to potential future improvements
of AB16.

I am not advocating for any particular design. As a passive observer,
I just feel the attacks should be compared more carefully.

Stefano

On Tue, May 31, 2016 at 3:44 AM, Jean-Philippe Aumasson
<[email-masked]> wrote:
> [email-masked]

-- 
Stefano Tessaro
Assistant Professor of Computer Science
University of California, Santa Barbara
http://cs.ucsb.edu/~tessaro/