[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 [127.0.0.1]) 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-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 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 [193.170.152.99]) (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 ([10.15.21.55]) by ironport2-intern.ista.local with ESMTP; 20 Sep 2016 15:02:36 +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 u8KD2ZuI023643 for <cfrg@irtf.org>; Tue, 20 Sep 2016 15:02:36 +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 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
Hi, 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 function. https://eprint.iacr.org/2016/875 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. ---------------------------------Snip--------------------------------