phc-discussions - Re: [PHC] omegacrypt and timing

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

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

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-----