Subject: Re: [Cfrg] Balloon-Hashing or Argon2i.

From: krzysztof pietrzak <[email-masked]>
Date: Tue, 16 Aug 2016 04:38:23 +0200

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 <[email-masked]> wrote:
> On Sun, Aug 14, 2016 at 11:17 PM, Stefano Tessaro <[email-masked]>
> 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: +43(0)2243 90004601
Cell:     +43-(0)664 88687692
Email:  [email-masked]

---

From: "Blocki, Jeremiah Martin" <[email-masked]>
Date: Tue, 16 Aug 2016 05:48:30 +0000

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 <[email-masked]> on behalf of krzysztof pietrzak <[email-masked]>
Sent: Monday, August 15, 2016 10:38 PM
To: IRTF CFRG
Subject: Re: [Cfrg] Balloon-Hashing or Argon2i.

Hi,

n^c + cost(R,n)

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

Krzysztof

--
Krzysztof Pietrzak

Professor
Cryptography

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

---

From: Bill Cox <[email-masked]>
Date: Mon, 15 Aug 2016 23:48:34 -0700

On Mon, Aug 15, 2016 at 7:38 PM, krzysztof pietrzak <[email-masked]>
wrote:

> parameter for AT in MHF attacks papers).

This is an interesting model, but does not match real hardware very well,
IMO.  Instead of modeling the DRAM power by the static power which is
comparatively low, why not model the power as a constant plus a constant
times the rate of read/writes?  I think that would be a lot closer to what
we see in DDR3 and GDDR5.  I think it also will hold with a theoretical
through-silicon-via based stacked-die DRAM + ASIC.

Then evaluating Scrypt
> << n).

Since R is the cost of evaluating H, can I assume r is the number of times
we call H?  In Scrypt, normally r = 2*n.  In this case, I assume n^2 is the
static power loss in the memory.  If so, then I think R >> n.  Also, we've
left out the dynamic power of the memory, which is likely on the order of
the power of computing H for a read or write.

I would prefer to model the power more like this.  Assume h is the power of
evaluating H and m is the power of a read or write to memory of one block.
I would ignore static power in the DRAM, which contributes little to
heading real DRAMs.  For Scrypt, the normal energy used would be 2*h + 2*m.

Recently it was shown that, assuming the underlying building
> exponentially many calls, will have cost z*n^2 for some constant z>0.

You lost me there.  If I can compute H for free (zero power), then I'd
simply recompute every value from the initial block, and avoid the power
needed to read or write to DRAM.  Wouldn't the total power be zero?  Is the
argument that the cores each need to have 1 block saved, and the static
power of storing those block is still O(n^2)?  Is this some sort of
hardened by static power defense?

Foundries routinely design low-power processes with many orders of
magnitude less static power than what we see in modern CPUs.  Hardening
MHFs based on static power is not going to work out well for the defender.
The energy cost of storing bits that are not accessed can be made very
close to zero.  Consider flash memory.  The power to read and write is
huge, but just sitting there waiting to be accessed, these tiny capacitors
holding the charge will maintain that charge reliably for over 10 years.
We should assume that the power is dominated by read/write, not the power
required to store some number of bits over time.

> for Catena (for Pomelo and Lyra this only applies to the first -- data

Is the n^c term the static power term for storing the data?  If so, it
would be best to ignore it.  Read/write costs will dominate over it.

> is greater than 1.

What about the read/write cost?  If n^2 is the static power loss, which we
can reduce by a factor of a million easily in the fab, then I would not
count on n^2 being significant.

> The cost(R,n) term is different for the various

I do prefer the data-dependent modes, like Argon2id for most use cases.
The data-independent algorithms are much harder to make secure, IMO, and I
think that we saw that when Argon2i-A was partially broken, forcing
Argon2i-B to be created.  I don't mean to sound negative on the research
into iMHFs.  These are required in some cases, and I think the research
will likely yield significant improvements.

I would try to argue that it makes sense to move one of the data-dependent
algorithms forward in CFRG while waiting on results from current research
on the data-independent version, but I think pretty much everyone would
hate that idea, so I do not propose it :)

Bill

---

From: Joel Alwen <[email-masked]>
Date: Tue, 16 Aug 2016 15:32:54 -0700

Hi Bill,

First, thanks for all the details. I greatly appreciate hearing about
the perspective of someone working closely with hardware about this stuff.

Let me see if I understood correctly.

So one thing you saying is that if we want to talk about total energy
consumption we should really be including the cost of read/write to memory.

One way to incorporate this into the PROM model (at least for all
algorithms we've ever considered in it) is to change the definition of R
so that it also includes that energy consumption. In particular data is
only ever read/written in conjunction with one call to the compression
function. However if we do this then my understanding is your saying
then R >> n.

To me that sounds like (assuming for a second that energy consumption is
what matters most) the adversary cares primarily about using an
algorithm that minimize the number of calls to the compression function.
So then the optimal algorithm is always going to be the honest one for
pretty much any iMHF I can think of so then really there isn't a lot to
be done here...

However, this line of reasoning is quite sensitive to the relation
between R and n. It would be great to have more concrete data on this
(see bellow).

One thing I want to add is that the way "Energy-complexity" in the PROM
is defined has the following property. If we use

         R = area-core / area-storing-one-block

which is roughly how we actually set R in our experiments in the recent
paper, then

      Energy-complexity =< AT-complexity per instance

Moreover, I think the gap between the two is relatively small.
Especially if R is set to be large enough to account for the area not
just of a core but also the routing needed per core. Though, in this
case, your previous comments on how ASIC routing scales implies one
should probably also have R scale with the the number of parallel cores.

Security Statements in the PROM
-------------------------------
So with that in mind a statement of the form:

       "No algorithm can compute F() with less than X energy-complexity
in the PROM model."

is then really also making a statement about the amortized AT-complexity
of an adversary. My understanding is that the consensus in various works
(including the scrypt paper, the Catena paper and the cryptanalysis of
various MHFs be Biryukov and Khovratovich) is that large AT complexity
is indeed a desirable defence. In fact, in the former works bounding
area for just the memory components is actually already a good defence.
While in the latter (and most of the PROM works) we also take into
account the area of the cores on chip. So with this in mind I believe
such "security statements" in the PROM remain of interest.

Attack Complexity in the PROM
-----------------------------
Turning to statements of the form:

     "Algorithm A evaluates F() with Energy-complexity at most X in the
PROM."

like in AB16, it seems to me that when we evaluate its practical
implications it is key to have the right value of R set. If we care
about the energy efficiency of A then we can derive a meaningful
statement about the actual energy consumption of a custom device
implementing algorithm A as long as we set R to include both the energy
for evaluating a core and the energy for one read and one write.

Similarly, if we want to derive a statement about the AT complexity of
such a device (amortized per instance) then we should set R to include
not just the area of a core but also of the routing.

What do you guys think about this line of reasoning? does it make sense?
are there serious issues here?

And what do you guys think realistic values of R would be. Lets say in
the case of the Argon2 compression function for say 10, 25, 50, 200, 500
and 1000 cores (if such a device with that amount of cores is even
possible of course). I'd love to have data both when R captures the
energy consumption of read+core+write and when R captures area of
core+routing.

- Joel

> This is an interesting model, but does not match real hardware very 
> well, IMO.  Instead of modeling the DRAM power by the static power
> which is comparatively low, why not model the power as a constant
> plus a constant times the rate of read/writes?  I think that would be
> a lot closer to what we see in DDR3 and GDDR5.  I think it also will
> hold with a theoretical through-silicon-via based stacked-die DRAM +
> ASIC.
> 
> 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).
> 
> 
> Since R is the cost of evaluating H, can I assume r is the number of 
> times we call H?  In Scrypt, normally r = 2*n.  In this case, I
> assume n^2 is the static power loss in the memory.  If so, then I
> think R >> n.  Also, we've left out the dynamic power of the memory,
> which is likely on the order of the power of computing H for a read
> or write.
> 
> I would prefer to model the power more like this.  Assume h is the
> power of evaluating H and m is the power of a read or write to memory
> of one block.  I would ignore static power in the DRAM, which
> contributes little to heading real DRAMs.  For Scrypt, the normal
> energy used would be 2*h + 2*m.
> 
> 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 
> You lost me there.  If I can compute H for free (zero power), then
> I'd simply recompute every value from the initial block, and avoid
> the power needed to read or write to DRAM.  Wouldn't the total power
> be zero?  Is the argument that the cores each need to have 1 block
> saved, and the static power of storing those block is still O(n^2)?
> Is this some sort of hardened by static power defense?
> 
> magnitude less static power than what we see in modern CPUs.
> Hardening MHFs based on static power is not going to work out well
> for the defender.  The energy cost of storing bits that are not
> accessed can be made very close to zero.  Consider flash memory.  The
> power to read and write is huge, but just sitting there waiting to be
> accessed, these tiny capacitors holding the charge will maintain that
> charge reliably for over 10 years.  We should assume that the power
> is dominated by read/write, not the power required to store some
> number of bits over time.
> 
> 
> for Catena (for Pomelo and Lyra this only applies to the first --
> data independent -- phase).
> 
> 
> Is the n^c term the static power term for storing the data?  If so,
> it would be best to ignore it.  Read/write costs will dominate over
> it.
> 
> 
> 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.
> 
> 
> What about the read/write cost?  If n^2 is the static power loss,
> which we can reduce by a factor of a million easily in the fab, then
> I would not count on n^2 being significant.
> 
> 
> 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 
> 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
> 
> 
> I do prefer the data-dependent modes, like Argon2id for most use
> cases. The data-independent algorithms are much harder to make
> secure, IMO, and I think that we saw that when Argon2i-A was
> partially broken, forcing Argon2i-B to be created.  I don't mean to
> sound negative on the research into iMHFs.  These are required in
> some cases, and I think the research will likely yield significant
> improvements.
> 
> I would try to argue that it makes sense to move one of the 
> data-dependent algorithms forward in CFRG while waiting on results
> from current research on the data-independent version, but I think
> pretty much everyone would hate that idea, so I do not propose it :)
> 
> Bill
> 
> 
> _______________________________________________ Cfrg mailing list 
> [email-masked] https://www.irtf.org/mailman/listinfo/cfrg
>

---

From: Bill Cox <[email-masked]>
Date: Wed, 17 Aug 2016 00:52:53 -0700

> the perspective of someone working closely with hardware about this stuff.

I enjoy it, too.  I hope I can help.  I believe I made some mistakes above
(I make a lot of them).

> consumption we should really be including the cost of read/write to memory.

I think so.  The concept of energy per read/write captures the idea that
moving data is what takes significant energy, not keeping it in one place.
However, this model breaks when scaling memory size.  Power per read/write
grows roughly as the square root of memory size, as does the distance the
data travels.

> function. However if we do this then my understanding is your saying

In the context of R >> n or R << n, if I understand correctly, n represents
the energy for storing n blocks of memory 1 tick, and R is the power of
computing H.  In a "low power" process, leakage power will be insignificant
for on-chip SRAM, and it is typically pretty low in DRAM modules.  I think
this equation will look different when read/write power is added, and I
think leakage power can be probably dropped, assuming we're using a
low-power process like we see in BitCoin mining ASICs.

> pretty much any iMHF I can think of so then really there isn't a lot to

There are cases where power is reduced when reducing memory usage in a TMTO
attack.  The simple deep TMTO against Scrypt yields a 4X reduction in naive
At cost (max memory used times total computations of H).  Cutting the
memory by 4X in a TMTO attack reduces memory power per read/write by about
2X, in addition to reducing the number of read/writes.  There is certainly
room for reducing power here against Scrypt by reducing memory.  However, I
see less room in attacks against Balloon hashing and Argon2i-B (for tcost
>=3), though I thought the same thing about Argon2i-A and was wrong.

>       Energy-complexity =< AT-complexity per instance

Looks right to me.

> should probably also have R scale with the the number of parallel cores.

Yes, I think it needs to scale as the square root of the number of parallel
cores.  I'd just do a rule-of-thumb check to get a WAG for the routing
power.  I've never been able to route data on a chip using less than 1pF
per cm.  The last chip I worked on was a minimum of 2.5pF per cm, so
assuming 1pF/cm is probably close enough.  Given that, and the bits per
block is all you need to get a WAG for routing power, which could be added
to R.

BTW, if we know the exact paths data will need to be routed over, as we do
in Argon2i-B then we can run a place-and-route algorithm to assign
computation nodes in the DAG to cores to minimize the distance data is
routed while keeping the cores working in parallel.  This can significantly
reduce routing power.

> is indeed a desirable defence.

I agree.  If you prove either a high AT cost, or a high power cost, that
counts as "provably secure" to me, though to be competitive, the algorithm
would still need a lot of optimizations for the various defenses such as
those that were considered in the PHC.

In fact, in the former works bounding
> such "security statements" in the PROM remain of interest.

I agree.  I look forward to future results.

Bill