Re: [Cfrg] Tight security proofs for practical memory-hard password-hashing

Joel Alwen <> Wed, 21 September 2016 16:05 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id B6FA012B4DA for <>; Wed, 21 Sep 2016 09:05:13 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -6.617
X-Spam-Status: No, score=-6.617 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, RCVD_IN_DNSWL_MED=-2.3, RP_MATCHES_RCVD=-2.316, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (2048-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id C0Jsy5V79-Go for <>; Wed, 21 Sep 2016 09:05:11 -0700 (PDT)
Received: from ( []) (using TLSv1.2 with cipher DHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 2CA3812B23A for <>; Wed, 21 Sep 2016 09:05:10 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;;; q=dns/txt; s=ist2009; t=1474473911; x=1506009911; h=subject:to:references:from:message-id:date:mime-version: in-reply-to:content-transfer-encoding; bh=5vON9cK9rQY58rcCSZq6BV35CD9MHn3P+plB/MxmgDU=; b=soXtOiA/U6v2uLVSmdwuHXCkFjiIWVyOS6TIRZ7CGbBxaDz3XxkcDqxz 0phQcom/ZGgYY1xOlEJvJdBS7UgMV8P7o5zFKQST05X0lb/YzOs1DPjoz hzpqaoUBzuAIJKkIQqatG/ht/YkvVEMYfjw47uiOG7sRjgdx5LzzrRODl aM+oSyvL7GIP5AVBaGOjM/WABmqr7GSIUBp53SAbvNBVro1eov4ankHbV V49yG2twt/fAwjNcHjYEttvUXagunR2b2oilqyCX2AAL1GctYMsEP+bOB FtHPtu3WQk6qZUMJmWEE/lwg9oJ2V+P2YtV0Ec286nqY8K4sBdqriF4u1 g==;
X-IronPort-AV: E=Sophos;i="5.30,374,1470693600"; d="scan'208";a="6123988"
Received: from lserv46.ista.local ([]) by ironport-intern.ista.local with ESMTP; 21 Sep 2016 18:05:07 +0200
Received: from (sslmail1.ista.local []) by lserv46.ista.local (8.14.4/8.14.4/Debian-4+deb7u1) with ESMTP id u8LG56Xu008528; Wed, 21 Sep 2016 18:05:07 +0200
Received: from [] ( []) (authenticated bits=0) by (8.14.4/8.14.4/Debian-4+deb7u1) with ESMTP id u8LG55P1021046 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES128-SHA bits=128 verify=NOT); Wed, 21 Sep 2016 18:05:06 +0200
To: Samuel Neves <>, "" <>
References: <> <> <>
From: Joel Alwen <>
Message-ID: <>
Date: Wed, 21 Sep 2016 18:05:01 +0200
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101 Thunderbird/45.2.0
MIME-Version: 1.0
In-Reply-To: <>
Content-Type: text/plain; charset=windows-1252
Content-Transfer-Encoding: 8bit
Archived-At: <>
Subject: Re: [Cfrg] Tight security proofs for practical memory-hard password-hashing
X-Mailman-Version: 2.1.17
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Wed, 21 Sep 2016 16:05:14 -0000

> The very last open question on this paper says that it is not known
> whether scrypt is optimally memory hard. But in the introduction it
> is claimed, citing an unpublished manuscript, that this is indeed the
> case. So which is it? Is the open question referring strictly to the
> \pi_cc value which is not used in the "direct" proof of the
> manuscript?

Good catch, that part of the intro needs some fixing.

AFAIK here is what we do and don't know about provable security of
scrypt. First, by "full security" in this context I mean having
amortized-AT = Theta(n^2) amortized per instance even when given
arbitrary parallelism. (Notice that CC =< AT so lower-bounding
amortized-CC would be good enough.)

The two main results right now are the proof in the original scrypt
paper by Colin and proof in the Eurocrypt 2015 paper(eprint/2016/100) on
scrypt. Here's my take on why both fall short of full security in
several ways.
 - Both consider only a one-off cost, i.e. the memory-hardness of
computing a single instance; i.e. non-amortized. But when brute-forcing
passwords or solving a proof-of-work we compute many, even highly
correlated, instances. So ultimately an adversary does care about
amortized, not one-off cost.
 - The former proof is for AT complexity instead of CC like the later.
Unfortunately one-off AT really implies very little about amortized AT.
In contrast, (for these types of functions) one-off CC is probably a
better indicator for amortized-AT since intermediary hash values when
computing scrypt on distinct inputs are likely not compressible.
 - The former also assumes an upper bound on the amount of memory (and
parallelism) used by an adversary.
 - Both papers also assume that the next position in the memory array
needed by ROMix is chosen uniformly and independently of all previous
computation. This simplifies the proofs but in reality its actually
totally deterministic since it is fixed by the inputs and the choice of
hash function.
 - The former also (implicitly) assumes that the adversary does nothing
other then read and write intermediary hash values to memory. (No
encoding, storing partial values, XORing, etc.)
 - Finally the proof in the latter is based on an unproven conjecture
and only gets Omega((n/log(n))^2) instead of n^2 like the former.

So basically as far as I know scrypt is *not* known to be provably fully
secure. And, to be sure, I think it's a great (if surprisingly
difficult) open problem.

> A second question is whether the results on scrypt easily transfer to
> Argon2d, which is also up for standardization, along with Argon2i. A
> footnote on 2016/100 suggests that this is the case.

Actually this is probably the biggest reason I am personally interested
in proofs for scrypt. My intuition for why Argon2d should be memory hard
follows very much the same lines as to why I think scrypt is memory
hard. So whatever techniques we do develop for scrypt will hopefully be
easy enough to adapt to Argon2d (and other data-dependent MHFs). And
that would be awesome because there are other reasons to prefer Argon2d
over scrypt. At least for the Eurocrypt 2015 proof technique I think
this hope does play out. It's just that I don't see how to use that
technique to prove the type of "full security" I'd been hoping for. Thus
the explicit open problem for scrypt.

Why not go straight for Argon2d (or another dMHF)? If we can prove
something directly then great! It's just that ROMix is the simplest
algorithm I know of which tries to get memory-hardness via the
"unpredictable pointer chasing" technique also used in Argon2d so
(besides its comparatively wide deployment) I think this makes
scrypt/ROMix a good candidate to study.

> Also, somewhat of a nitpick, why refer to Argon2-A and -B instead of
> v1.0 and v1.3, which is (in my opinion, anyway) easier to
> unambiguously refer to the distinct Argon2 versions under study?

Yes, in retrospect you're right. I think we first introduced the -A / -B
notation as a quick & easy way to clarify amongst ourselves what we were
talking about. Those were the two versions we were most concerned with.
Of course, at the end we probably should have gone back and changed this
to something more like what you suggested. TBH, we just didn't think
about it. For any more formal (i.e. published / not eprint) version
we'll probably do this though.

- Joel