Re: [Cfrg] Balloon-Hashing or Argon2i.

Bill Cox <waywardgeek@gmail.com> Thu, 11 August 2016 13:48 UTC

Return-Path: <waywardgeek@gmail.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 14CBD12D613 for <cfrg@ietfa.amsl.com>; Thu, 11 Aug 2016 06:48:09 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.699
X-Spam-Level:
X-Spam-Status: No, score=-1.699 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, FREEMAIL_REPLY=1, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_LOW=-0.7, SPF_PASS=-0.001] autolearn=no autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id xbss_a5eNyDu for <cfrg@ietfa.amsl.com>; Thu, 11 Aug 2016 06:48:08 -0700 (PDT)
Received: from mail-yw0-x22f.google.com (mail-yw0-x22f.google.com [IPv6:2607:f8b0:4002:c05::22f]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id D2AFF12D59A for <cfrg@irtf.org>; Thu, 11 Aug 2016 06:48:07 -0700 (PDT)
Received: by mail-yw0-x22f.google.com with SMTP id z8so2482207ywa.1 for <cfrg@irtf.org>; Thu, 11 Aug 2016 06:48:07 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=hQZGl1glXyPYIaWtdv/EsRieFabZeSkDr1B0zdmZ270=; b=hVvXx/rwu0hDvswLPNAffi9O6jpMjro4xaa6UU2uCTXz3B28qnpmv57E+JuFkIuV3d V351zR4D6qhp1LxJPXJz8cx6uzZF8tjHctBmdgx++E9CVVjCGFrZEMfEPdeJTnDf00nS /+aCYRV2ZgSiOFEkh+QZYWA6kYwG+2edVWHLRARyvev4q4M/cKivYFDTHApln1Gb7Z0z F3Z8iy0iu0X1zObVH+spgisSvA7rrQUDwVTOdA+08fSkJUyOEptGdl7zjPgSK9dDzLQe XzrI7AS2mWcIFRc5QjW0avZldAPtOQ/5s/+WxtHOrk+YSlGRIzYnK4DVxwJRhYBiqH5N estA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=hQZGl1glXyPYIaWtdv/EsRieFabZeSkDr1B0zdmZ270=; b=IL0p1+kSoVoFZHd0ILbRKjsnerfEZjUhhY5yHgWWhUAEx1I8FF+HefjuT1Psc/3I7m HztKb3F5hPR8UUqsFlDOKsRXCJ0KHoXC6SWmXXg4hMbBT3auHfqpTwiKhS77FdtmMEsG oCRTaDuGzDOuE/O6k2Tq3M/91oQHGAS31quucusbrF+HRlamGPQHzTnpOgR1OFTnYiB1 vXj2oxRqoaners40caM0/4Rvsgkq7hMFr3n5XeNMa01vyBFWUzyflKdbdC3V18ezYB5h Yt0SEFLICJZIUFHDBgylV8mjlpvm53m9g5Gn1uEIV0EF2nMunFfOUxGnX2RFtg2xxIV2 Jc4g==
X-Gm-Message-State: AEkooutn17zeDYpBm95DfTX7nDaD5CfkuxH2IvzW/Rz+Tbnjh4qF4d/2pQ+VNG4TCv8gzr5LSKhLQgEPTjlA2Q==
X-Received: by 10.13.250.196 with SMTP id k187mr6498225ywf.314.1470923287019; Thu, 11 Aug 2016 06:48:07 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.129.53.17 with HTTP; Thu, 11 Aug 2016 06:48:06 -0700 (PDT)
In-Reply-To: <CALW8-7+ZfnpisFXYhyYPsvSz2zzz+NaZMezpMfKxgiSohLoQ=A@mail.gmail.com>
References: <574601EF.60205@ist.ac.at> <574C7E2B.5080700@stanford.edu> <CALW8-7+D6BSzE4ufubZys=6ECn7GUvRQA2CDxKAANgvvOwddqQ@mail.gmail.com> <1cd036cd-e15b-7f9c-c3d5-28f6e2ef4c2b@stanford.edu> <CALW8-7+MZ-b1VGc+4EOReCEbvCVou+e9UbzfR9sJMZavwqp64A@mail.gmail.com> <CAKDPBw-fJo=YEy1QPT9k2OMWf511=bXtZbZdn0R-UyMaVM0djQ@mail.gmail.com> <CALW8-7+ZfnpisFXYhyYPsvSz2zzz+NaZMezpMfKxgiSohLoQ=A@mail.gmail.com>
From: Bill Cox <waywardgeek@gmail.com>
Date: Thu, 11 Aug 2016 06:48:06 -0700
Message-ID: <CAOLP8p4m7RdY-UO3XLWBpPk09GBP05ESO_pErFx1NWOqOjYwqg@mail.gmail.com>
To: Dmitry Khovratovich <khovratovich@gmail.com>
Content-Type: multipart/alternative; boundary="94eb2c05ed5003e3fa0539cc04d8"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/ZE1yu5YkJA4haKCgfx8nNlVkhRs>
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] Balloon-Hashing or Argon2i.
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.17
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Thu, 11 Aug 2016 13:48:09 -0000

On Wed, Aug 10, 2016 at 8:40 PM, Dmitry Khovratovich <khovratovich@gmail.com
> wrote:

>
> I have not checked the details of improvements yet, but I feel that one of
> conclusions is incorrect.
>

I disagreed with paper starting with the definition of "quality".  It is
defined as the cost to compute hashes times total number of hashes
performed, plus the power required to store the hashes for a period of
time.  This is a common mistake.  The actual power in their attack will
more likely be dominated by the power of routing the data, not storing or
computing it.  If routing were free, we would all be running data-flow
computers <https://en.wikipedia.org/wiki/Dataflow_architecture>.

tl;dr; Here's a quick brain-dump on the cost of routing data for people who
have never analyzed routing data before.

Routing is hard to understand and quantify, so it is often ignored.  This
is why data-flow architectures sound great but don't work out in practice.

The paper models the total power as the sum of the power for computing the
data plus the power of storing the data in DRAM.  Routing power is ignored,
which causes weird results.  The paper assumes the power of routing locally
stored data in the ASIC is zero.  This causes the authors to try to
minimize the data transferred to the external DRAM, which also improves
computation speed by maximizing the use of limited DRAM bandwidth.  It
sounds pretty good until you try to analyze routing power on the ASIC.

The power of storing a bit in DRAM is essentially zero, except that now and
then the DRAM has to do a refresh, which drives a long capacitive bit-line
of maybe 1mm with many loads.  At the speeds they're talking about
(1TiB/s), that power will be dwarfed by the routing power of the data
to/from the DRAM.  Each read/write drives a word line of maybe 1mm with
many capacitive gates, a bit line, and a good fraction of a centimeter of
wire across the DRAM to the I/O, and then another good fraction of a
centimeter of wire across the ASIC.  However, this power is very small
compared to the on-chip data-flow routing power in the ASIC.

When attacking Argon2i, which wisely uses 1KiB blocks rather than 512-bit
BLAKE2b hashes, and with 1,000 parallel cores as described in the attack,
they will need to route about 3MiB of data randomly between them in 1KiB
chunks per hashing step!  That's about 1cm of wire toggling times 24
million.

Each of these 1cm routing paths will have around ~1pF of capacitance.
Assume a 1V core power supply.  Toggling at a slow rate of 100MHz gives
C*V^2*f/2 power = 1,200 watts.  In reality, the power would be at least
double that due to the on-the-fly programmable nature.  Also, the routing
network would dominate the die area.

Once the full cost of routing data is included, deep TMTO attacks using
massive parallelism against Argon2i-B, or Balloon Hashing, when using the
author's recommended parameters, will be impractical, especially if the
Balloon hashing method of randomizing the DAG with the salt is used, so
that the ASIC has to do full data-flow routing rather than hard-wired
optimized routing.

BTW, many people will feel uncomfortable with leaking information about the
salt through side-channels, but at a minimum, a unique value per password
database should be hashed in, so that any ASIC attack that tries to
optimize the routing power vs data-flow networks will only be usable
against one database rather than globally.  Forcing an ASIC attacker to use
data-flow routing is crucial for defense.

Bill