Message-ID: <CALW8-7+zZ2X+hu5+8yEzHzOC-OEhq=z4U36zvo3CFuX=FfcG_Q@mail.gmail.com>
Date: Wed, 15 Apr 2015 12:43:35 +0200
From: Dmitry Khovratovich <khovratovich@...il.com>
To: "discussions@...sword-hashing.net" <discussions@...sword-hashing.net>
Subject: Re: [PHC] "Attack on the iterative compression function"

Hi Alexander,

your original interpretation is correct. The idea is that even though
the computation latency may be high, the recomputation latency can be
very low if the attacker stores appropriate intermediate values. This
applies to Lyra2 and other iterative designs.

I guess Percival felt there is an attack of this kind, that is why he
introduced this subblock shuffling. The authors of Lyra2 did the same
after they have seen our attack.This countermeasure helps a bit, but
for small recomputation depth it is not good enough (it is my
feeling), and it adds complexity. Our approach is to avoid this
situation for all, requiring that there simply must not be any
tradeoff attack on the compression function, or, in other words, the
computational latency must be tradeoff-resistant. The Argon2
parallelism that you have mentioned is somewhat unavoidable if we want
this resistance.

The attack, apparently, also applies to yescrypt. I was not sure about
that until you released the pseudo-code, but then I started thinking
about storing the last subblock of each block to break the chain. For
the full attack I would still have to plug yescrypt mode of operation
(and its addressing) into our ranking method.

Your question prompted me to finish the attack, write a small
description, and adapt the ranking algorithm to yescrypt. Here is a
fresh draft:
https://www.cryptolux.org/images/0/0f/Tradeoff_for_Yescrypt.pdf

The consequences are better than for the original Lyra2 due to rather
small number of subblocks and different addressing. Assuming unlimited
parallelism, the time-memory product can be kept the same while the
memory is reduced by the factor of 6.


On Wed, Apr 15, 2015 at 12:39 AM, Solar Designer <solar@...nwall.com> wrote:
> On Wed, Apr 15, 2015 at 01:29:30AM +0300, Solar Designer wrote:
>> Dmitry - you claim that "[...] it allows to reduce the memory by the
>> factor of 12 or even higher while still reducing the area-time product."
>> Since table 2.1 only goes to 1/11, for depth 32.8, and you say that "In
>> concrete proposals, s can be 64, 128, 256 and even larger", I guess this
>> "factor of 12" applies to the next column in the table (not shown),
>> where depth would presumably be in the 32.8 to 64 range?  Do I interpret
>> this correctly?
>
> Hmm, probably not correct interpretation.  I was thinking of needing to
> store occasional full blocks anyway, but then the attack doesn't make
> sense.  So this probably corresponds to storage of one sub-block per
> block (and then re-running the whole thing storing 2nd sub-block, etc.),
> and some column in the middle of the table.  Right?
>
> Doesn't appear to apply to yescrypt, because:
>
>> However, the attack would appear to rely not only on the last
>> sub-blocks, but also on occasional full blocks, so I don't see how it'd
>> improve upon the higher-level TMTO attack alone.  The last sub-block of
>> output of each BlockMix_pwxform depends on the entire input block, and
>> if you never store entire blocks then you'd need to restart computation
>> from block 0 in order to reach a block's last sub-block.
>
> Alexander



-- 
Best regards,
Dmitry Khovratovich

Powered by blists - more mailing lists