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

[Joel Alwen <[e-mail]>]

> 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 <[e-mail]
> <mailto:[e-mail]>> wrote:
> 
> 
>> 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
> 
> 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.
>> 
>> 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 
>> <[e-mail] <mailto:[e-mail]>
> <mailto:[e-mail] <mailto:[e-mail]>>> 
> 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
>> 
>> 
>> _______________________________________________ Cfrg mailing list 
>> [e-mail] <mailto:[e-mail]>
> https://www.irtf.org/mailman/listinfo/cfrg
>> 
> 
-