lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
Open Source and information security mailing list archives
| ||
|
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