Re: [Cfrg] Balloon-Hashing or Argon2i.

["Blocki, Jeremiah Martin" <[e-mail]>]

I would like to add a couple of thoughts to the discussion:
1) One of the main points of the new paper is that we don’t actually need so much parallelism/bandwidth to obtain effective attacks (specifically see Section 6.6 in the paper). Just to highlight one result: for single pass Argon2i we can get high quality attacks even with parallelism <=50.

2) The routing costs are being amortized over *many* Argon2i instances.

3) We could already view routing costs as being included in the core memory-energy ratio R. We defined R as “the energy cost to compute the compression function on chip” divided by “the energy necessary to store one block (e.g., 1KB) in memory for one round.” However, one could just as easily view R as "the energy cost to compute the compression function and route one block from memory to the appropriate core” divided by "the energy necessary to store one block (e.g., 1KB) in memory for one round".

4) The value of R is architecture and technology dependent. It would be productive to have a discussion of the range of values we might expect R to take. We used the value R=3000 in our experiments (following previous works).

For example, unless the cost to route one block from memory is significantly higher than the cost to compute the compression function the value of R will not increase significantly when we roll routing costs into the core memory-energy ratio. I am open to hearing dissenting opinions!

One observation we made already is that the concrete quality of the attack is not very sensitive to variations in the value of R. For example doubling R seems to only marginally decreases attack quality.

Dmitry:

First, thanks for pointing out that the block size for Balloon Hashing is 512bits as opposed to 512 Bytes. This means that the graphs should be shifted left as you pointed out. In particular, the AB16 attacks are even *more* effective against the Balloon Hashing iMHF.

> I have not checked the details of improvements yet, but I feel that 
> one of conclusions is incorrect.
>
> The authors say  "More generally, the parameter selection process in 
> the proposal is flawed in that it tends towards producing parameters 
> for which the attack is successful". Concretely, for 1 GB on Figure 1 
> we see that the attack on 1-pass Argon2i has quality 5, 3-pass -- 
> quality 3, 4-pass -- quality 2.5, 6-pass -- quality 2, 10 passes -- quality 1.5.

The sentence may have been worded too strongly. Our point was that the parameter selection process will often lead to the selection of parameters (e.g., \tau=1 pass) for which attack quality is highest. Our measure of attack quality quantifies how attractive the [AB16] attacks would be for the adversary once all of the parameters are fixed.

If the goal is instead to maximize the adversary’s costs subject to a constraint on honest running time with no additional constraints on maximum honest memory usage then \tau=1 pass may indeed be the right choice of parameter. Whether or not this is the case does depend on the exact quality of the attack for different settings of honest memory usage and number of passes.

________________________________________
From: Cfrg <[e-mail]> on behalf of krzysztof pietrzak <[e-mail]>
Sent: Monday, August 15, 2016 10:38 PM
To: IRTF CFRG
Subject: Re: [Cfrg] Balloon-Hashing or Argon2i.

Hi,

Evaluating for which parameters/hardware the AB16 attack is successful
certainly requires an understanding of the underlying hardware, and
looking at the ongoing discussion I don't think there will be any
consent on where the bound which makes the attack practical lies until
someone actually implements it in hardware.

But fortunately, if you need an MHFs and you're not paranoid about
using a provably secure one, we do know how to construct (data
dependent and independent) MHFs which are secure for all parameters
independent of the properties of the underlying hardware.

The comparison made with AES in a previous post is not very good, as
AES or SHA3 are cryptographic building blocks, but an MHF is a mode of
operation. Whereas evaluating building blocks requires cryptanalysis,
modes of operation usually can be proven secure unconditionally making
assumptions on the underlying building blocks, and MHFs are no
different in this aspect.

For example, assume storing one block (512 bits) for one unit of time
cost 1, and evaluating the underlying building block costs R (cost can
be e.g. electricity or AT complexity, R=3000 has been used as a
parameter for AT in MHF attacks papers). Then evaluating Scrypt
(RoMix) using the naive algorithm (which only has sequential access to
H(.)) for n blocks of memory costs n^2+R*r \approx n^2 (as typically R
<< n). Recently it was shown that, assuming the underlying building
block H(.) is modelled as a random function, even an adversary who can
make exponentially many calls to H(.) *for free* and amortize over
exponentially many calls, will have cost z*n^2 for some constant z>0.

So, even as n goes to infinity and evaluating H(.) is free (for the
adversary), any adversarial strategy can save at most a constant
factor 1/z in cost (of course, if the memory of the attacker is
cheaper/more energy efficient than the honest parties' to start with,
that factor comes in additionally). We also have data independent MHFs
that satisfy this.

All of the iMHF submitted to the PHC can be evaluated at amortized cost

n^c + cost(R,n)

for some constant c<2 and where cost(R,n) is the cost of evaluating
H(.) n^c' (for some c'<2) times. The constant c is <1.75 for
Argon2i,Rig.v2 and Gambit, <1.83 for Pomelo, <1.63 for Lyra2, <1.67
for Catena (for Pomelo and Lyra this only applies to the first -- data
independent -- phase).

Unlike in the security proof, for an attack we cannot ignore the
cost(R,n) term; whether we have a practical attack depends on whether
the attack quality

n^2 / (n^c+cost(R,n))

is greater than 1. The cost(R,n) term is different for the various
constructions and depends on the hardware. So, if you want to use any
of these constructions, you must certify that for the parameters
you're interested in, any hardware options and all trade-offs (e.g. on
the number of parallel cores) that the [AB16] attacks allows, this
quality is small, and then pray that no better attacks are found. Or
you could not care about that and use a mode where the parallel
cumulative memory complexity and the sequential space/time complexity
are proven to be of the same order (Scrypt for data dependent or a
mode based on an optimally depth-robust graph for data-independent
MHFs).

Krzysztof

On Mon, Aug 15, 2016 at 4:34 PM, Bill Cox <[e-mail]> wrote:
> On Sun, Aug 14, 2016 at 11:17 PM, Stefano Tessaro <[e-mail]>
> wrote:
>>
>>
>> Concretely, for memory hardness, I think there are two questions:
>>
>> = Are the metrics in the [AB16] attacks realistic or not? If not
>> (which seems to be the claim), can we state precise metrics that would
>> be appealing to practitioners and that theoreticians can work with?
>
>
> Correct, I do claim they are unrealistic.  I like their quality measure:
> total energy.  The problem is their model was simplified too much.  In
> particular:
>
> 1) The energy in DRAM is dominated by the high-speed interface.  Adding
> additional size to the DRAM increases power slightly, and not at all
> proportionally.  Storing data in a tiny capacitor continues to be super
> efficient in terms of power in general.
>
> 2) There was no model for the power required for parallel cores to
> communicate between them, and as a die gets large (they assumed up to
> 500mm^2), this power will dominate in their attack.
>
> The right approach to analyzing ASIC attacks is to iterate with the ASIC
> design community.  Every new model is an advance, but to make them more
> effective we need to adapt them to make them more realistic.
>
> I strongly agree with Jean-Philippe Aumasson above.  Any theoretical notion
> of security needs to be tested fleshed out and tested in more realistic
> attacks.  Any realistic ASIC attack will have to specify H.  We'll hear
> about how the attacker takes advantage of deep pipelining and interleaving
> to do multiple attacks in parallel more efficiently.  We'll hear about
> custom cache architectures.  We'll also hear about exactly how data will get
> routed between cores, and all of these various components will have size and
> power estimates.
>
> I have worked with ASICs for many years, but I do not consider myself a
> world-class expert in ASIC design, nor am I familiar with changes in ASIC
> design in the age of fin-fets.  However, I would be happy to help flesh out
> more realistic attacks for anyone who wants to see how their model might
> work in a real ASIC attack.
>
> Bill



--
Krzysztof Pietrzak

Professor
Cryptography

Institute of Science and Technology Austria (IST Austria)
Am Campus 1
A-3400 Klosterneuburg
Austria
Web:    http://pub.ist.ac.at/crypto/
Phone: [phone]
Cell:     [phone]
Email:  [e-mail]

_______________________________________________
Cfrg mailing list
[e-mail]
https://www.irtf.org/mailman/listinfo/cfrg