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

[Stefano Tessaro <[e-mail]>]

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
<[e-mail]> wrote:
>
> 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?
>
>
>
> On Tue, May 31, 2016 at 12:00 PM Joel Alwen <[e-mail]> wrote:
>>
>> > 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
>> >>
>> >
>> -
>
>
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> https://www.irtf.org/mailman/listinfo/cfrg
>



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