Date: Sat, 13 Dec 2014 19:04:42 +0100
From: Dmitry Khovratovich <khovratovich@...il.com>
To: "discussions@...sword-hashing.net" <discussions@...sword-hashing.net>
Subject: Re: [PHC] Some KDF stumbling blocks, plus Common "memory-hard"
 approaches and amortized attack costs.

Hi Greg,

Let me answer your concerns about operating costs. We have done some
research on this problem specifically in the context of password hashing.
An early presentation about it is here
https://www.cryptolux.org/images/d/d1/Tradeoff-slides.pdf . Later it was
developed into (yet unpublished) paper, some results of which I briefly
present below.

First, in contrast to homogeneous Bitcoin-mining chips, the optimal
hardware implementation of a memory-hard function would consist of two
different parts: computational logic, where the internal hash function is
implemented, and the memory. Exploiting computational-memory tradeoffs, an
adversary may reduce the memory area at the cost of growing and more
intensive logic part. Whereas logic energy consumption can be well
approximated as in Bitcoin, the memory running costs is quite difficult to
approximate. First, memory consumes energy both in active (when
reads/writes) and idle (the so called retention energy) states. Which of
two prevails (and whether prevails on the logic part) depends on many
factors, including:
 - memory type (static or dynamic - first is smaller and more
energy-efficient, but more expensive)
  - memory size
  - memory design (prospective one, or a solution on the market, say DDR3)
  - chip organization (on-chip or off-chip memory, number of banks, etc.)
  All together, these factors may change the logic/memory power ratio by
huge factors, up to 1000 in both directions. Hence the operating costs (not
speaking of cooling, etc.) are pretty hard to estimate with reasonable
precision. Which design decisions would be chosen by an adversary, is quite
difficult to estimate right now.

  What we can do better is to compare the cracking costs in a simpler
metric, e.g. the time-area product. For it we do not need the power
numbers, but it is also less precise in reflecting the actual costs.


Regarding your other note on 60 days needed to exceed the production costs
in Bitcoin, I would note that the markets for password cracking and Bitcoin
mining would significantly differ in size, thus making the production costs
difficult to compare. The 60 days you mention may become 6 years just
because you need 10 crackers, not 1000.


> An effect of memory hard functions constructed with
> conventional hardware is that they shift costs from energy into gate
> count.  This will have the effect of increasing the amortization
> advantage for an attacker:ed with 99.9% certainty with construction A,
> another construction with an expected $10bn security level but a 5%
> chance of <$500 million security against an amortized attacker  would
> not be a good choice.
>

This is a good point. We agree that all types of adversaries must be
considered when estimating the cracking costs. Indeed, some schemes are
good only as long as an adversary does not turn to ASICs. Our own scheme,
Argon, was evaluated exactly under the assumption that an adversary can
build whatever hardware he wants up to a billion of budget.

-- 
Best regards,
Dmitry Khovratovich

Content of type "text/html" skipped

Powered by blists - more mailing lists