Subject: [Cfrg] Balloon-Hashing or Argon2i.

From: Joel Alwen <[email-masked]>
Date: Wed, 25 May 2016 15:50:07 -0400

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

---

From: Henry Corrigan-Gibbs <[email-masked]>
Date: Mon, 30 May 2016 10:53:47 -0700

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

---

From: Dmitry Khovratovich <[email-masked]>
Date: Tue, 31 May 2016 16:02:02 +0200

Dear Henry,

thank you for the updated paper.

We appreciate your work on lower-bounding the Argon2i tradeoff resistance,
it is a very interesting result, and we hope to mention it in the
specification. However for your proof to work you instantiate Argon2  with
a collision resistant hash function. During the competition it became clear
that collision-resistance of the inner function is not needed in practice,
since the attacker does not control intermediate variables. It is similar
to the situation with block-ciphers like AES where a single round is
cryptographically weak, though you might want it to be a keyed PRP for the
sake of a proof. Worse enough, a full-round hash function with a narrow
block implies more frequent random memory access and more CPU load, which
together make a terrible impact on the performance. That's why we never
defined Argon2 for such hash functions, and recommend not calling such
modifications "Argon2".

This observation and possibly use of your own code for Argon2 causes
 performance comparison of your Balloon Hash design with Argon2i and other
designs to be incorrect.

in the introduction you write
"if we ... run the construction for five “rounds” of hashing, and set the
space parameter to require the attacker to use 1 MiB of working space to
compute the function, then we can compute Balloon Hashes at the rate of 13
hashes per second on a modern server, compared with 12.8 for Argon2i, and
2.1 for Catena DBG".

This statement underestimates the Argon2i performance by the factor of 30
(!) or so.

In detail. Argon2i makes much more than 13 hashes per second using 5
iterations and 1 MiB of memory. On my 2-core 2.3 GHz (i5-6200) laptop  it
computes 1000 hashes in 5.1-5.3 Gigacycles, thus averaging more than 400
hashes per second. I modified our benchmark settings for that, but even
with default ones (3 iterations, 1 hash) everyone can observe similar
performance by running 'make bench' +'./bench' using the source in
https://github.com/P-H-C/phc-winner-argon2

In the further text you write
"Let an authentication server must perform 100 hashes per second per
four-core machine, ... At the same authentication rate, Argon2i requires
the attacker to use a smaller buffer—roughly 1.5 MiB for the one-pass
variant".

This is again incorrect. Here are the numbers for 1-pass Argon2i: 2MiB:
225Mcycles, 16MiB: 1174 Mcycles, 32 MiB: 2532 Mcycles (a bit more than 1
second).

So there is a factor of 20 underestimate here. (We also remind that 1-pass
Argon2i was never  recommended for practical use.)

Best regards,
the Argon2 team

On Mon, May 30, 2016 at 7:53 PM, Henry Corrigan-Gibbs <[email-masked]>
wrote:

> 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.
>
> 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.
> (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.
>
>
> 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.
>
>

-- 
Best regards,
Dmitry Khovratovich

---

From: Henry Corrigan-Gibbs <[email-masked]>
Date: Tue, 31 May 2016 08:57:24 -0700

Hi Dmity,

Thanks for taking a look at the paper.

For the purposes of the security proofs, we model the cryptographic 
compression function used in Argon2, Balloon, and scrypt, as a random 
oracle (as is standard). In practice, it is possible to instantiate 
Argon2i or Balloon or scrypt with any cryptographic compression function 
that "behaves like a random oracle." We are agnostic to the choice of 
cryptographic compression function -- we just evaluated our design with 
a few standard ones.

My sense is that Balloon (instantiated with parameter delta=3) and 
Argon2i will run at roughly the same speed, no matter the choice of 
cryptographic compression function. That's because three-pass Argon2i on 
N blocks of memory makes roughly 3N calls to the underlying compression 
function during its execution. Two-round Balloon (the equivalent 
construction, since it makes three passes over memory) makes roughly 7N 
calls to the underlying compression function during its execution.

However, the known attacks on three-pass Argon2i allow the attacker to 
use roughly 2.5x less space than the defender with no time penalty, so 
to force the attacker to use N blocks of space requires the defender to 
run Argon2i with a ~2.5x larger memory buffer (i.e., a buffer of N' = 
2.5N blocks). In this setting, both functions would require ~7N 
invocations of the underlying cryptographic compression function, so the 
performance should be roughly equivalent for the two.

Changing the underlying cryptographic compression function will change 
the absolute performance of both Argon2i and Balloon, but I would expect 
their relative performance to stay close to constant. Indeed, if I 
instantiate Argon2i and Balloon with the compression function defined in 
the Argon2 spec, then I get, on an Intel i7-6700 @ 3.4 GHz:
   Argon2i (2.5 MB buffer): 153 hashes/sec
   Balloon (1.0 MB buffer): 167 hashes/sec

The surprise to us is that getting this sort of performance with Balloon 
is still possible, even though we are able to prove some meaningful 
statements about its security. (Of course, the Alwen-Blocki attacks 
still apply for large enough parameter sizes.)

Henry

On 5/31/16 7:02 AM, Dmitry Khovratovich wrote:
> We appreciate your work on lower-bounding the Argon2i tradeoff
> resistance, it is a very interesting result, and we hope to mention it
> in the specification. However for your proof to work you instantiate
> Argon2  with a collision resistant hash function. During the competition
> it became clear that collision-resistance of the inner function is not
> needed in practice, since the attacker does not control intermediate
> variables. It is similar to the situation with block-ciphers like AES
> where a single round is cryptographically weak, though you might want it
> to be a keyed PRP for the sake of a proof. Worse enough, a full-round
> hash function with a narrow block implies more frequent random memory
> access and more CPU load, which together make a terrible impact on the
> performance. That's why we never defined Argon2 for such hash functions,
> and recommend not calling such modifications "Argon2".
>
>  performance comparison of your Balloon Hash design with Argon2i and
> other designs to be incorrect.
>
> "if we ... run the construction for five “rounds” of hashing, and set
> the space parameter to require the attacker to use 1 MiB of working
> space to compute the function, then we can compute Balloon Hashes at the
> rate of 13 hashes per second on a modern server, compared with 12.8 for
> Argon2i, and 2.1 for Catena DBG".
>
> This statement underestimates the Argon2i performance by the factor of
> 30 (!) or so.
>
> iterations and 1 MiB of memory. On my 2-core 2.3 GHz (i5-6200) laptop
>  it computes 1000 hashes in 5.1-5.3 Gigacycles, thus averaging more than
> 400 hashes per second. I modified our benchmark settings for that, but
> even with default ones (3 iterations, 1 hash) everyone can observe
> similar performance by running 'make bench' +'./bench' using the source
> in https://github.com/P-H-C/phc-winner-argon2
>
> So there is a factor of 20 underestimate here. (We also remind that
> 1-pass Argon2i was never  recommended for practical use.)
>
> Best regards,
> the Argon2 team
>
> On Mon, May 30, 2016 at 7:53 PM, Henry Corrigan-Gibbs
> <[email-masked] <mailto:[email-masked]>> wrote:
>
>     Hi Joel,
>
>     would be difficult for me to give an unbiased opinion on the pros
>     and cons of Argon2i versus Balloon.
>
>     The revised paper includes some new results that might be relevant
>     to CFRG discussions on password hashing. Let me summarize the new
>     results here:
>
>
>     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".
>
>
>     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.
>
>
>     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
>     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.
>
>
>         [email-masked] <mailto:[email-masked]>
>     [email-masked] <mailto:[email-masked]>