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: <20140917181205.089c2681@lambda> Date: Wed, 17 Sep 2014 18:12:05 +0000 From: Brandon Enright <bmenrigh@...ndonenright.net> To: Steve Thomas <steve@...tu.com> Cc: discussions@...sword-hashing.net, bmenrigh@...ndonenright.net Subject: Re: [PHC] omegacrypt and timing -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On Wed, 17 Sep 2014 12:14:57 -0500 (CDT) Steve Thomas <steve@...tu.com> wrote: > > For the very first round of branching the GPU could run all 4 in > > parallel and select the correct one. But, for the second round, the > > GPU would have to run branch 1 for each of the possible previous > > branches, and branch 2 for each of the possible branches, and so > > forth. > > > > The carry value is modified from start to finish through each > > branch. There is no realistic way to perform the attack you describe > > because the previous branch path possibilities grows exponentially. > > After just a few rounds you'd be doing an exponential amount of > > work. > > When you run out of the ChaCha block data you conditionally generate > another. There is no exponential cost increase for GPUs. Hi Steve, have you looked carefully at how the branching is done? ChaCha is used for more than just choosing the branches. It also chooses which memory gets read and written. Generating the ChaCha stream is a non-issue. You could pre-generate a few MB of it if you wanted. The issue is that after a round is run, depending on which branch was taken a different amount of the ChaCha stream is consumed which makes both the branch and the the memory locations of the next round depend how much ChaCha stream has been consumed. So it's not just a matter of running the next 4 branches in parallel and picking one because each branch has multiple different memory locations depending on where that branch falls in the stream. The carry value would also be unpredictable. To avoid misalignment, if you ran all 4 for round 1, and then selected the right one, then all 4 for round 2, then selected the right one, etc., you'd be doing 4x as many memory operations and you'd need a way of discarding the memory changes made by the 3 wrong branches. Is this the attack you're suggesting? Brandon -----BEGIN PGP SIGNATURE----- Version: GnuPG v2 iEYEARECAAYFAlQZzwkACgkQqaGPzAsl94I6EgCeLtN6Xk2yGC0jJ0xgiHt4NmYz 2aQAn3ojeT/vnWEQ5YAnxdPHMJmNivto =s32s -----END PGP SIGNATURE-----
Powered by blists - more mailing lists