Message-ID: <7D47E093-D435-47F2-9717-9DD3949BA509@telspace.co.za>
Date: Sat, 13 Dec 2014 21:27:36 +0200
From: Dimitri Fousekis <dimitri@...space.co.za>
To: <discussions@...sword-hashing.net>
Subject: Re: [PHC] Some KDF stumbling blocks, plus Common
 "memory-hard"approaches and amortized attack costs.

Is there an adversary classification that has been designed? Taking into 
account what the adversary may or may not have access to and specifically 
the budget and thus computational power they may have? By getting a good 
idea what is possible now, and in the near-future it is easier to 
understand the affects. Bitcoin has a direct ROI on cracking the 
algorithms because its instantly monetised and thus has a major incentive 
for higher up-front investment into hardware. Cracking passwords is 
monetised only for certain adversaries as others may have more social 
means to their end and thus still pose a risk but with not as much 
hardware at their disposal. Then you have to add potential govt or other 
big organisation funding too as mentioned below. The result would be a 
matrix of quite a few possible adversary types and their “most common” 
approach to cracking from a hardware perspective. 

Dimitri Fousekis
Dimitri@...space.co.za


From:  Dmitry Khovratovich <khovratovich@...il.com>
Reply-To:  <discussions@...sword-hashing.net>
Date:  Saturday 13 December 2014 at 8:04 PM
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