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  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]
Date: Wed, 17 Sep 2014 16:14:54 +0000
From: Brandon Enright <bmenrigh@...ndonenright.net>
To: Bill Cox <waywardgeek@...hershed.org>
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 06:30:36 -0400
Bill Cox <waywardgeek@...hershed.org> wrote:

> I think OmegaCrypt, POMELO,
> and Schvrch do too little data-based branching to badly hurt a GPU
> attack.  The GPU can simply execute each case serially, and only write
> data for the selected case, so with N cases, a GPU will not slow down
> by more than a factor of N.

This attack doesn't work against OmegaCrypt.  Each branch consumes a
different amount of the ChaCha stream used to guide future branching.
Also, there is a carry value from the previous round.

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.

Or perhaps you're imagining doing all 4 branches, then pausing to
figure out which was right, then doing another 4, pausing to figure out
which was right, and so on?  You'd need some sort of copy-on-write
memory to facilitate "backing out" of the changes made by wrong
branches.  I don't see how you'd actually be avoiding any
data-dependant branching.

Can you explain more concretely what your suggested attack is?  I don't
see how what you're describing would actually work.

Also for what it's worth, if OmegaCrypt makes it to round 2 I plan on
adjusting the branches to consume a coprime amount of the ChaCha stream
to further protect against executing future rounds by trying all the
combinations of the previous rounds.

Brandon

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2

iEYEARECAAYFAlQZs5IACgkQqaGPzAsl94JyCQCfdxKdhlAxjoxCm9nL1kMQIjcb
L1AAnjxzXPialp1EqpSgU0MS4NN1gYSA
=gcQA
-----END PGP SIGNATURE-----

Powered by blists - more mailing lists