Re: [Cfrg] Tight security proofs for practical memory-hard password-hashing
Joel Alwen <jalwen@ist.ac.at> Wed, 21 September 2016 16:05 UTC
Return-Path: <jalwen@ist.ac.at>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id B6FA012B4DA for <cfrg@ietfa.amsl.com>; Wed, 21 Sep 2016 09:05:13 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -6.617
X-Spam-Level:
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: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=ist.ac.at
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id C0Jsy5V79-Go for <cfrg@ietfa.amsl.com>; Wed, 21 Sep 2016 09:05:11 -0700 (PDT)
Received: from mx1.ist.ac.at (mx1.ist.ac.at [193.170.152.98]) (using TLSv1.2 with cipher DHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 2CA3812B23A for <cfrg@irtf.org>; Wed, 21 Sep 2016 09:05:10 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ist.ac.at; i=@ist.ac.at; 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 ([10.15.21.55]) by ironport-intern.ista.local with ESMTP; 21 Sep 2016 18:05:07 +0200
Received: from sslmail1.ist.ac.at (sslmail1.ista.local [10.15.21.69]) 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 [192.168.0.14] (84-114-240-28.cable.dynamic.surfer.at [84.114.240.28]) (authenticated bits=0) by sslmail1.ist.ac.at (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 <samuel.c.p.neves@gmail.com>, "cfrg@irtf.org" <cfrg@irtf.org>
References: <51837072-bb17-22a4-cb42-bf4220f3f888@ist.ac.at> <04288d55-389b-79de-5a8e-4a9746ae16bc@ist.ac.at> <edd97628-8cf7-a19a-116e-8e02c566f408@gmail.com>
From: Joel Alwen <jalwen@ist.ac.at>
Message-ID: <7ca98631-f327-e13c-2d16-d05f6bdd889c@ist.ac.at>
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: <edd97628-8cf7-a19a-116e-8e02c566f408@gmail.com>
Content-Type: text/plain; charset="windows-1252"
Content-Transfer-Encoding: 8bit
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/aHOSHkVunTg2iQGCaYwVvc7O9_k>
Subject: Re: [Cfrg] Tight security proofs for practical memory-hard password-hashing
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.17
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=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