lists.openwall.net  lists / announce owlusers owldev johnusers johndev passwdqcusers yescrypt popa3dusers / osssecurity kernelhardening musl sabotage tlsify passwords / cryptdev xvendor / Bugtraq FullDisclosure linuxkernel linuxnetdev linuxext4 linuxhardening PHC  
Open Source and information security mailing list archives
 

Date: Fri, 28 Aug 2015 06:33:53 0700
From: Bill Cox <waywardgeek@...il.com>
To: "discussions@...swordhashing.net" <discussions@...swordhashing.net>
Subject: Flaw in Argon2 TMTO ASIC analysis
I objected to this flawed analysis when applied to Lyra2 and Yescrypt, so
it's only fair I object when applied to Argon2 :)
The Argon2 paper states:
"We conclude that for datadependent onepass schemes the adversary is
always able to reduce the memory
by the factor of 4 and still keep the timearea product the same."
This is wrong. Given their simple attack, there is no memory reduction
factor that results in any timearea product reduction. The algorithm is
far more TMTO resistant than the authors claim (as is Lyra2).
In their attack, they assume the simple model where alpha is an integer and
we keep every 1/alpha memory location in external DRAM. When using 1/2 the
memory (alpha = 1/2), and a uniform random index function (the square
function used now is better), the average recomputations, which are called
C(alpha), goes to 2 for large memory hashing. Their table incorrectly
shows C(alpha) = 1.5.
The function D(alpha) is used to compute the additional runtime factor.
However, it is assumed to be no longer than the deepest computation path
required to recompute missing blocks. This function D(alpha) is a clear
theoretical lowerbound on recomputation speed, but it is incorrect to use
this number in theiir timearea ASIC attack analysis.
The paper correctly states that the fastest ASIC bandwidths to memory are
on the order of 400 GiB/s. An ASIC attack will optimize many factors, and
one of the most critical is ASIC cost for the resulting bandwidth.
Assuming this results in a 400 GiB/s ASIC (probably incorrect, but the
analysis is the same for other choices), the runtime is proportional to
C(alpha), the number of recomputations, not D(alpha), the computation tree
depth. This is because the required bandwidth is increased by a factor of
C(alpha), and the ASIC will be bandwidth limited when attacking Argon2. I
can think of no reasonable ASIC attack for largememory hashing (>= 1 GiB)
that would be limited by any other speed factor, as the paper did not
include multiplication based computetime hardening in this analysis.
Thus the time is proportional to C(alpha) and the area is proportional to
alpha. The timearea product is alpha/C(alpha). When using the corrected
C(alpha) for the simple attack (keeping every 1/alpha block), C(alpha) is
2, and at the 1/2 memory level timearea = (1/2)/2 = 1. At lower alpha
(higher memory reduction factors), recomputations increase faster than the
memory reduction, increasing the areatime cost to the ASIC attacker.
Therefore, there is no choice for alpha that reduces the timearea product.
Improved attacks will keep less memory at high memory addresses and more at
lower addresses. Against a uniform random index function, this can only
decrease the timearea product by about 15% at most. With the improved
index function, the maximum TMTO improvement is even less. I believe the
potential benefit is so small, no significant ASIC attack will ever bother
to do a TMTO against 1pass Argon2d.
If this were the Argon2 team claiming a competitor had a simple attack
resulting in a 4X areatime reduction, I would be upset. Since it is their
own algorithm they are talking about, I'll simply correct their math :)
Bill
Content of type "text/html" skipped
Powered by blists  more mailing lists