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

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 <jalwen@ist.ac.at> 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 <jalwen@ist.ac.at
> > <mailto:jalwen@ist.ac.at>> 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
> >> <khovratovich@gmail.com <mailto:khovratovich@gmail.com>
> > <mailto:khovratovich@gmail.com <mailto:khovratovich@gmail.com>>>
> > 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
> >> Cfrg@irtf.org <mailto:Cfrg@irtf.org>
> > https://www.irtf.org/mailman/listinfo/cfrg
> >>
> >
> -
>