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

Joel Alwen <jalwen@ist.ac.at> Tue, 20 September 2016 13:02 UTC

Return-Path: <jalwen@ist.ac.at>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost []) by ietfa.amsl.com (Postfix) with ESMTP id 1B00F12B30F for <cfrg@ietfa.amsl.com>; Tue, 20 Sep 2016 06:02:45 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
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: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=ist.ac.at
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id pRF5jUnayZQL for <cfrg@ietfa.amsl.com>; Tue, 20 Sep 2016 06:02:40 -0700 (PDT)
Received: from mx2.ist.ac.at (mx2.ist.ac.at []) (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 F1ACC12B30D for <cfrg@irtf.org>; Tue, 20 Sep 2016 06:02:38 -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=1474376559; x=1505912559; h=subject:references:from:to:message-id:date:mime-version: in-reply-to:content-transfer-encoding; bh=lukt8PVFDoiPJpg+Vn57FJ/m3wPDf5hgsxs6xfTtnw0=; b=WCYB+9o574dEkWWuiW9oYWTa8VbxDEjc8bqpkBdxYlVABQZ7Cny8/MmM 2KtPKV4zUmSdOgxrQJE6uMNlLNcDurDb2tiEzp7uBmQz1hiDx4ZlYEmGl teTFZ1xwOuyo2dquA/fzeQHKxbM5H8ohCtf8JT6NKf/vMvgPlLSy39mXw 2J143GgXT3sKpdZ9ot6H3rsYRBW+nepr5Pv7ha52arBxo/cGHU2i2TziF JjFjEnHr5orzpcjh5QiAMEgnuaHZDhNW7oy11yimqQsG/tGSi7I4SHPZE fIzx9vDlEgML4YyV9vS7v4zft6RDn6DFZ3H/C2fZ/Jl7k2CSQrtyfbkCJ Q==;
X-IronPort-AV: E=Sophos;i="5.30,368,1470693600"; d="scan'208";a="5498303"
Received: from lserv46.ista.local ([]) by ironport2-intern.ista.local with ESMTP; 20 Sep 2016 15:02:36 +0200
Received: from sslmail1.ist.ac.at (sslmail1.ista.local []) by lserv46.ista.local (8.14.4/8.14.4/Debian-4+deb7u1) with ESMTP id u8KD2ZuI023643 for <cfrg@irtf.org>; Tue, 20 Sep 2016 15:02:36 +0200
Received: from [] (84-114-240-28.cable.dynamic.surfer.at []) (authenticated bits=0) by sslmail1.ist.ac.at (8.14.4/8.14.4/Debian-4+deb7u1) with ESMTP id u8KD2Y0Z029387 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES128-SHA bits=128 verify=NOT) for <cfrg@irtf.org>; Tue, 20 Sep 2016 15:02:35 +0200
References: <51837072-bb17-22a4-cb42-bf4220f3f888@ist.ac.at>
From: Joel Alwen <jalwen@ist.ac.at>
To: "cfrg@irtf.org" <cfrg@irtf.org>
X-Forwarded-Message-Id: <51837072-bb17-22a4-cb42-bf4220f3f888@ist.ac.at>
Message-ID: <04288d55-389b-79de-5a8e-4a9746ae16bc@ist.ac.at>
Date: Tue, 20 Sep 2016 15:02:29 +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: <51837072-bb17-22a4-cb42-bf4220f3f888@ist.ac.at>
Content-Type: text/plain; charset="utf-8"
Content-Transfer-Encoding: 8bit
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/77JbFmVWgpxgMyuUd6f8r58KmUI>
Subject: [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: Tue, 20 Sep 2016 13:02:45 -0000


Recently Jeremiah, Krzysztof and I put some new results on eprint which
have some relevance to the push for a new memory-hard password-hashing


To help put the results in context I wanted to clarify what my take on
the concrete relevance is to the CFRG efforts in this direction are.

The paper, in general, concentrates on fleshing out / improving on some
of the theory in this area so that stuff is maybe not of direct interest
here (for the curious: see bottom of email for more info on those results).

However one contribution that I hope is more directly relevant to the
CFRG's concerns are a pair of new proof techniques for getting (certain
types of) provable memory-hardness for iMHFs. These techniques are FAR
easier to understand, work with, and easier to adapt to different
constructions, hardness notions and computational models than the
techniques used in the AS15 paper. The techniques are also tight enough
that they (can) give us really exact (non-asymptotic) security
statements. Basically they are both easy and powerful enough to use that
we can directly analyse very practical constructions (even ones not
designed with these proof techniques in mind).

As evidence we used these two techniques to show provable
memory-hardness for Argon2i-A (the PHC winning version of Argon2i.),
Balloon Hashing and Catena. Unfortunately, (though unsurprisingly given
AB16 and the new attacks in this work) the statements we prove are
really not anywhere close the memory-hardness we've been hoping for up
till now. But they do show how these techniques can be used for
algorithms we care about in practice.

Another way to think about this paper is that we now have two new simple
design criterion for an iMHF either of which automatically gives us
(certain types of) provable security. I'm willing to wager we will soon
see otherwise practically competitive iMHF constructions enjoying
security proofs using one of these techniques.

As usual, feedback, questions and criticism are very welcome. I'm all
ears people. :-)

- Joel

PS. For those who are interested what the new techniques are: in a
nutshell the most important one can be understood like this. We show
that analysing the "depth-robustness" of an underlying (graph
characterizing the) mode of operation of an iMHF automatically gives
very tight lower bounds on the memory hardness of that mode of operation
in an ideal compression function model. By "tight" I mean whatever we
know about the depth-robustness of the mode of operation translates
exactly (not asymptotically) and with a very small loss in constants
into a proof of memory hardness in the ideal compression function model.
So to get a security proof for say Argon2i-A we now only needed to
understand its (say expected) depth-robustness.

PPS. For those interested what theory results we have. I'd say at least
two are worth highlighting as they relate to what we're doing in the CFRG.

1) We present a new class of attacks on memory-hard functions
generalizing AB16. We show that they get lower asymptotic memory
complexity for Argon2i (version 1.3 from the PHC), Balloon Hashing and
Catena when compared to AB16. But, in contrast to the AB16 attack, I'm
personally less clear on whether:
 - the hidden constants & low-order-terms can be made small
 - that the attack can be made to behave well using only moderate
(rather than unbounded) amounts of parallelism on random instances.
 - Nor have we had time to address recent great questions brought up on
this mailing-list about how routing overhead in the ASIC and memory
chips will affect the attack.
So for now I'd consider these new attacks to be a theoretical result
lacking solid evidence (one-way or another) for how they behave in
practice. Understanding their practically (be it to refute or assert)
would take a fair bit more work that just hasn't been done. Still, just
to be clear though: asymptotically the new attacks are pretty severe.

2) We give a new mode of operation over a compression function with
provable asymptotically optimal memory-hardness. However, at this point
its definitely still a theoretical result because a key component we use
in the construction is a particular graph (by Erdos, Graham and
Szemeredi) which just wasn't designed for ever actually being used in
practice. Its way too complicated and has horrible constants giving us
crappy exact security (at least using our current proof techniques). So
for now I'd say that result isn't per se interesting for the CFRG's
purposes. Still, I pretty convinced this is a step in the right
direction for us.