Hi Joel,

Since I am one of the designers of the Balloon Hashing algorithm, it 
would be difficult for me to give an unbiased opinion on the pros and 
cons of Argon2i versus Balloon.

That said, we just updated the Balloon Hashing paper on ePrint:
http://eprint.iacr.org/2016/027

The revised paper includes some new results that might be relevant to 
CFRG discussions on password hashing. Let me summarize the new results here:


(1) We prove (in the single-instance, random-oracle model) a new, 
stronger memory-hardness claim about the Balloon algorithm. We show that 
computing one instance of the Balloon function with space S and time T 
requires a space-time product that (roughly) satisfies:
S . T >= n^2 / 8.
As the adversary's space usage drops below a certain threshold (which 
depends on the parameter settings) the trade-off gets even worse for the 
adversary.


(2) We refine the analysis of the single-buffer Balloon algorithm, and 
the refined analysis allows us to dramatically improve the parameters of 
the scheme. After this change, the performance of the single-buffer 
Balloon function *meets or exceeds* that of Argon2i when we instantiate 
both with Blake2b as the underlying cryptographic hash function. 
(Consult the paper for the details on this.) The single-buffer Balloon 
algorithm runs so quickly now that we decided that the other two Balloon 
variants (double-buffer and linear) were superfluous. The revised paper 
includes only the single-buffer scheme, which we now just call the 
"Balloon algorithm".


(3) We discuss your (very cool) recent paper on parallel attacks on 
iMHFs and give some ideas on how to ameliorate them in the context of 
password hashing. Our recommendation is to follow Balloon Hashing with 
one round of scrypt (or even data-dependent Balloon). This composition 
apparently defends against either parallel attacks or cache attacks -- 
just not both at the same time. The design of the Argon2id function uses 
a similar idea. To us, this seems like a nice compromise between 
functionality and security.


(4) We apply our analysis techniques to prove that Argon2i and a 
simplified variant of scrypt are also memory-hard, though with looser 
constants than one might like. We show that these two algorithms (again, 
in the single-instance random-oracle model) require space S and time T 
such that:
S . T >= n^2 / C
to compute with good probability. For Argon2i, we can prove this 
statement for C=192, and for scrypt with C=24. In contrast, we prove the 
claim with C=8 for Balloon, and we additionally prove much stronger 
time-space trade-offs for Balloon for very-small-space adversaries. From 
a "provable security" perspective then, Balloon seems to have an edge 
over the other practical constructions out there.


If you find bugs or omissions in the ePrint draft, please let me know.

Henry


On 05/25/2016 12:50 PM, Joel Alwen wrote:
> I was wondering what peoples opinion is on standardizing the
> double-buffer balloon hashing (DB) construction rather than Argon2i.
> Both in terms of arguments for and against.
>
> I'm sure other people have thought about this much more though so I'd
> love to hear what people think...
>
> - Joel
>
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg
>