Re: [Cfrg] Balloon-Hashing or Argon2i.

Henry Corrigan-Gibbs <henrycg@stanford.edu> Mon, 30 May 2016 17:53 UTC

Return-Path: <henrycg@stanford.edu>
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 5D36012D55B for <cfrg@ietfa.amsl.com>; Mon, 30 May 2016 10:53:54 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -4.867
X-Spam-Level:
X-Spam-Status: No, score=-4.867 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_MED=-2.3, RCVD_IN_MSPIKE_H3=-0.01, RCVD_IN_MSPIKE_WL=-0.01, RP_MATCHES_RCVD=-1.426, SPF_NEUTRAL=0.779] autolearn=ham autolearn_force=no
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 WoG5YlDaXaZW for <cfrg@ietfa.amsl.com>; Mon, 30 May 2016 10:53:51 -0700 (PDT)
Received: from smtp1.cs.Stanford.EDU (smtp1.cs.stanford.edu [171.64.64.25]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id B4D1112D5FA for <cfrg@irtf.org>; Mon, 30 May 2016 10:53:48 -0700 (PDT)
Received: from mbarara.scs.stanford.edu ([171.66.3.71]:60890) by smtp1.cs.Stanford.EDU with esmtpsa (TLSv1.2:DHE-RSA-AES128-SHA:128) (Exim 4.84_2) (envelope-from <henrycg@stanford.edu>) id 1b7RNr-0003oA-FI for cfrg@irtf.org; Mon, 30 May 2016 10:53:48 -0700
To: cfrg@irtf.org
References: <574601EF.60205@ist.ac.at>
From: Henry Corrigan-Gibbs <henrycg@stanford.edu>
Message-ID: <574C7E2B.5080700@stanford.edu>
Date: Mon, 30 May 2016 10:53:47 -0700
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101 Thunderbird/38.8.0
MIME-Version: 1.0
In-Reply-To: <574601EF.60205@ist.ac.at>
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding: 7bit
X-Scan-Signature: 2ecb59bd28923317bd193fe54b7794cd
Archived-At: <http://mailarchive.ietf.org/arch/msg/cfrg/1RlBuJp3S08NSYkFw3anNqrZsA0>
Resent-From: <alias-bounces@ietf.org>
Resent-To: @ietf.org
Subject: Re: [Cfrg] Balloon-Hashing or Argon2i.
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: Mon, 30 May 2016 17:53:54 -0000

Hi Joel,

Since I am one of the designers of the Balloon Hashing algorithm, it 
would be difficult for me to give an unbiased opinion on the pros and 
cons of Argon2i versus Balloon.

That said, we just updated the Balloon Hashing paper on ePrint:
http://eprint.iacr.org/2016/027

The revised paper includes some new results that might be relevant to 
CFRG discussions on password hashing. Let me summarize the new results here:


(1) We prove (in the single-instance, random-oracle model) a new, 
stronger memory-hardness claim about the Balloon algorithm. We show that 
computing one instance of the Balloon function with space S and time T 
requires a space-time product that (roughly) satisfies:
S . T >= n^2 / 8.
As the adversary's space usage drops below a certain threshold (which 
depends on the parameter settings) the trade-off gets even worse for the 
adversary.


(2) We refine the analysis of the single-buffer Balloon algorithm, and 
the refined analysis allows us to dramatically improve the parameters of 
the scheme. After this change, the performance of the single-buffer 
Balloon function *meets or exceeds* that of Argon2i when we instantiate 
both with Blake2b as the underlying cryptographic hash function. 
(Consult the paper for the details on this.) The single-buffer Balloon 
algorithm runs so quickly now that we decided that the other two Balloon 
variants (double-buffer and linear) were superfluous. The revised paper 
includes only the single-buffer scheme, which we now just call the 
"Balloon algorithm".


(3) We discuss your (very cool) recent paper on parallel attacks on 
iMHFs and give some ideas on how to ameliorate them in the context of 
password hashing. Our recommendation is to follow Balloon Hashing with 
one round of scrypt (or even data-dependent Balloon). This composition 
apparently defends against either parallel attacks or cache attacks -- 
just not both at the same time. The design of the Argon2id function uses 
a similar idea. To us, this seems like a nice compromise between 
functionality and security.


(4) We apply our analysis techniques to prove that Argon2i and a 
simplified variant of scrypt are also memory-hard, though with looser 
constants than one might like. We show that these two algorithms (again, 
in the single-instance random-oracle model) require space S and time T 
such that:
S . T >= n^2 / C
to compute with good probability. For Argon2i, we can prove this 
statement for C=192, and for scrypt with C=24. In contrast, we prove the 
claim with C=8 for Balloon, and we additionally prove much stronger 
time-space trade-offs for Balloon for very-small-space adversaries. From 
a "provable security" perspective then, Balloon seems to have an edge 
over the other practical constructions out there.


If you find bugs or omissions in the ePrint draft, please let me know.

Henry


On 05/25/2016 12:50 PM, Joel Alwen wrote:
> I was wondering what peoples opinion is on standardizing the
> double-buffer balloon hashing (DB) construction rather than Argon2i.
> Both in terms of arguments for and against.
>
> I'm sure other people have thought about this much more though so I'd
> love to hear what people think...
>
> - Joel
>
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg
>