Re: [Cfrg] Balloon-Hashing or Argon2i.

[Bill Cox <[e-mail]>]

On Tue, Aug 16, 2016 at 3:32 PM, Joel Alwen <[e-mail]> wrote:

> Hi Bill,
>
> First, thanks for all the details. I greatly appreciate hearing about
> 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).

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.
>

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.

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.
>

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.

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...
>

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.


> 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
>

Looks right to me.


> 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.
>

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.

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.


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
> 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.
>

I agree.  I look forward to future results.

Bill