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

[Joel Alwen <[e-mail]>]

> 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]>> 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] https://www.irtf.org/mailman/listinfo/cfrg
>