Subject: [Cfrg] Memory-efficient evaluation of data-independent memory-hard functions

From: Joel Alwen <[email-masked]>
Date: Fri, 12 Feb 2016 17:12:15 +0100

Hi,

I thought some of you might be interested in Jeremiah Blocki and my
recent paper that just appeared on eprint
(http://eprint.iacr.org/2016/115). It complements the recent work on
data-dependent MHF (i.e. scrypt) by instead focusing on data
*independent* MHFs (e.g. Both Catena functions, Argon2i, all three
Balloon Hashing functions, etc.). Some of you may find it relevant to
recent discussion on the list about finding a password-hashing standard.

In a nutshell we develop a new class of parallel evaluation algorithms
for several rather general classes of MHFs (including all those I just
listed) and show that the resulting memory complexity is a fair bit
lower then one might hope for when allowing parallelism (like in an
ASIC). Put differently, we give some better than hoped for
time-memory-trade-offs by using parallelism to evaluate several
instances of the MHF at once resulting in a low "Time X Memory" per
instance. In other words just the kind of algorithm one might find
useful for launching cheap(er) brute-force attacks on these iMHFs.

>From a more theoretical perspective we also show a general lower-bound.
It states that no data-independent MHF (say doing 1-pass over n memory
blocks) can have even only Omega(n^2/log(n)) cumulative
memory-complexity (let alone the Omega(n^2) which people have been
shooting for up till now).

So where do these results leave us? AFAIK the closest we've got to an
iMHF with a proof for large memory-complexity is the iMHF in my paper
with Vladimir Serbinenko. Unfortunately the construction is based on a
recursively built graph. What that boils down to is that if we want to
compute the incoming edges of a node (i.e. which blocks from memory go
into the next call to the compression function H) the straightforward
computation (unravelling the recursion) takes log(n) operations. But
really we want constant time (say a single call to a compression
function + a mod operation as in scrypt) as otherwise the throughput of
any implementation is going to suffer. Also the proof only shows
something like Omega(n^2/log^10(n)) (with probably nasty constants)
which is asymptotically way better then any of above mentioned iMHFs but
actually pretty useless for practical parameters. I think its easy  to
tighten the proof down to something closer to Omega(n^2/log^7(n)) but
thats still pretty unsatisfactory and any way it doesnt help making the
incoming-edges function easier to compute.

Anyway I hope you enjoy the paper and that it provides a bit of fuel for
thought. :-) If anything, IMHO it points out room for a lot more work in
this area (both from a practical and theoretical point of view) before I
would feel confident in proposing a standard for wider adoption.

- Joel

PS. What does the theoretical lower-bound mean for our search for a new
password-hashing standard? What can we still hope for?

Here are a couple thoughts about those questions.

1) Well, we can always just ignore it if we find an iMHF which no one
manages to attack after a convincing amount of effort has been exerted.
After all we know efficient Random Oracles can't exist yet we still
effectively ask that our now hash function candidates to behave like
one. This route does seem to give up on proof based evidence for (at
least asymptotic) security though.

2) We could decide to settle for Omega(n^2/log(n)) assuming we can find
a clean, simple and strongly explicit iMHF with accompanying proof
matching this bound with small constants. (Notice that in the recent
scrypt paper we only show Omega(n^2/log^2(n)) so its not even clear that
a data-*dependent* MHF could break that bound.)

3) Alternatively, if we want to still shoot for a proof of Omega(n^2)
complexity, then one potential way to still get there could be to make
an analysis for concrete practical parameter ranges (rather then
asymptotic behaviour). The large constants in the lower-bound do not
rule this out. (Though the parameters of our evaluation algorithms for
almost all the iMHFs I listed above do rule this out for those
functions.) See figures in the paper...

4) Another less preferable way IMHO would be to increase the number of
inputs to the underlying hash function. (Something like the Single and
Double Buffer balloon hashing functions do as they use 21 inputs.) E.g.
I think the lower-bound lets us have Omega(n^2) memory-hardness if we
use order log(n) (or maybe log^2(n)) inputs to the hash function
(instead of a constant like 2 or 3 as in most current iMHFs). There are
at least two reasons why I'm personally not super in favour of this
approach though. Practically it means worse throughput for an
implementation as evaluating the hash function takes a lot longer now.
Theoretically I'd also call it cheating because it really boils down
making log(n) calls to a compression function (as was pointed out
already in a couple papers on the subject). In particular, really we
should be looking at MHFs defined over compression functions, not
arbitrary input length hashes. But if look at what happens to any proof
of memory-hardness for the high-indegree MHF when view the function as
being over a compression function then AFAIK the proof looses a
multiplicative cubic(!) of the indegree. So if we prove O(n^2) for an
MHF with d inputs to the hash function then I only see how to prove that
the same MHF viewed over the underlying compression function really has
O(n^2/d^3) complexity. (See Alwen Serbinenko for how that works.)

Also I'd love to hear other ideas for how to deal with the lower-bound
if you have any!

---

From: Paul Grubbs <[email-masked]>
Date: Fri, 12 Feb 2016 11:47:30 -0500

Thank you for this post; the recent work in this area has been really
fascinating.

On Fri, Feb 12, 2016 at 11:12 AM, Joel Alwen <[email-masked]> wrote:

> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>

---

From: Bill Cox <[email-masked]>
Date: Fri, 12 Feb 2016 09:36:40 -0800

This is really excellent work.  We're still waiting I think, for an update
to Argon2i to fix a significant TMTO issue, but Argon2d with one-pass will
withstand the test of time, IMO.  For near-term use, if I were using Argon2
(I prefer Yescrypt in most cases), I would stick to Argon2id, which offers
some protection against certain cache-timing attacks, but still leaks
meta-data such as whether or not the user who is authenticating has been
seen before.  It also is possible for an attacker to guess the password
(with very much required computation*memory due to the data-independent
part) without having access to the password hash, but instead just the salt
and username.  AFAIK, Argon2id has the same memory*time defense as Argon2d,
so it seems like a no-brainer to use Argon2id rather than Argon2d, IMO.  If
the CFRG were to promote one single version of Argon2, I feel it should be
Argon2id, given the continued attacks against iMHFs.

In an attempt to use Argon2id in an actual application, I found that the
low-memory hashing I was doing (it fit into L3 cache) was too slow.
Argon2id seems fine for larger memory sizes.  Scrypt (and Yescrypt) can
easily be modified to do less computation per memory block with no known
loss of security, which makes them both more suitable for low-memory
applications.

Bill

---

From: Joel Alwen <[email-masked]>
Date: Mon, 15 Feb 2016 17:06:11 +0100

> I would stick to Argon2id, which offers some protection against 
> certain cache-timing attacks, but still leaks meta-data such as 
> whether or not the user who is authenticating has been seen before.

Which type of timing attacks does Argon2id protect against? (Is there
any where I can read more about timing attacks on Argon2 or other
dynamic MHFs?)

> AFAIK, Argon2id has the same memory*time defense as Argon2d, so it 
> seems like a no-brainer to use Argon2id rather than Argon2d, IMO.

I think for the same memory-cost parameter and passes over memory
Argon2d would actually be (at least somewhat) more memory-hard than
Argon2id. In particular the first pass over memory of Argon2id would
still be susceptible to the Argon2i TMTO attack. So "Argon2d level
security" only holds for subsequent passes. In contrast for Argon2d it
holds from the get-go.

There is a trade-off here. The more passes over memory the smaller the
security gap between Argon2id and Argon2d. However this also decreases
any added cache-timing attack resistance Argon2id has over Argon2d.
Moreover it makes the MHF less efficient in terms of
memory-hardness/computational-cost.

Put differently for memory-cost m and number of passes t the runtime
(i.e. computational cost) is about m*t. But the cumulative memory
complexity is (ideally) m^2*t. So to maximise
memory-hardness/computational-cost we really want t=1. However if t=1
then Argon2id collapses to Argon2i so we would only get about m^{7/4}
memory-hardness. In contrast, with Argon2d I believe we would get much
closer to m^2 memory-hardness.

So basically I would only recommend Argon2id over Argon2d for
applications that are willing to tolerate a low through-put MHF.

TBH, I don't yet see a great solution when timing-attacks are a concern
but we also want large memory-hardness for minimal computation.

- Joel

---

From: Bill Cox <[email-masked]>
Date: Tue, 16 Feb 2016 11:42:33 -0800

I think the CFRG should feel free to move forward with Agon2i and Argon2d,
once the authors address the recent TMTO against Argon2i.  You have
convinced me that bringing up alternatives like Argon2id muddies the
waters, and should be avoided for now.

> any where I can read more about timing attacks on Argon2 or other

I think the recent paper on Scrypt <http://eprint.iacr.org/2016/100.pdf> is
applicable to both Argon2d and Argon2id in terms of off-line defense
without side-channel data.  AFAIK, there has been no formal analysis of
hybrid-MHFs like Argon2id.

> security" only holds for subsequent passes. In contrast for Argon2d it

Actually, with t=1, Argon2id fills the first half of memory in a
side-channel resistant manner, and the second half in an unpredictable
data-dependent manner.  The CC metric when attacking Argon2id would be
somewhat lower than Argon2d, since less memory could be used in the first
1/2 of memory, but the difference is a small constant factor, since the
second half of memory is required just the same as Argon2d.

> memory-hardness/computational-cost.

I agree.  Generally I prefer a single-pass algorithm when using
data-dependent MHFs, though Yescrypt has an interesting mode where only a
partial second pass is done.

> memory-hardness/computational-cost we really want t=1.

In most applications, I agree t should be 1 for data-dependent MHFs.

> However if t=1
> then Argon2id collapses to Argon2i

This isn't quite right, since both iMHF and dMHF are done in one pass.

> so we would only get about m^{7/4}

I agree.  In particular, I would be surprised to hear that someone finds an
attack on 1-pass Argon2d or Argon2id that is better than O(m^2) CC
complexity.  Lowering memory by more than about 8X results in having to
recompute a significant fraction of all prior memory for each new block
computed, so I do not see how to avoid O(m^2) memory*time.

> but we also want large memory-hardness for minimal computation.

There is clearly still work to be done here.  I have yet to see a
compelling iMHF that combines both high TMTO resistance and high
performance.  However, I would be surprised to see more than a constant
factor improvement vs Argon2i, assuming it is changed to XOR over memory in
later passes.

I wrote an automated pebbler
<https://github.com/waywardgeek/twocats/tree/master/tools/pebble> to
guesstimate the hardness of the different iMHFs.  It might be due to flaws
in my pebbling algorithm, but Gambit's simple memory access pattern worked
best to defeat my pebbler, and it already XORs over memory.  I would swap
out the Keccak sponge for the much faster one used in Lyra2, but once
that's done, Gambit seems both simple and resistant to TMTOs, though I have
no proof of it's superior resistance.  It seems like a good algorithm, but
I would not recommend it without more analysis that has been done to date.

Bill