phc-discussions - Re: [PHC] data-dependent branching (Re: [PHC] A little nit which bothers me...)

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: <20140403095358.GA30855@openwall.com>
Date: Thu, 3 Apr 2014 13:53:58 +0400
From: Solar Designer <solar@...nwall.com>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] data-dependent branching (Re: [PHC] A little nit which bothers me...)

A correction:

On Thu, Apr 03, 2014 at 01:39:04PM +0400, Solar Designer wrote:
> Here's a CPU attack on AntCrypt (as I understand it): define all
> possible two-function groups.  For 16 original functions, this will
> result in 256 dual-function functions, and if they're as tiny as they
> currently are they will probably still fit in a CPU's L1i cache.  Now
> you can define a dual-AntCrypt, testing two candidate passwords at a
> time, and using the CPU core's parallel processing capabilities (SIMD,
> multiple issue, super-scalar) it'll likely run no slower than a single
> AntCrypt does.  So you get a 2x performance boost for the attacker.
> Moreover, the cost of conditional branches is amortized,

This is true, but ...

> so the speedup might be slightly higher than 2x.

... this is not.  We replace two branches and two functions with one
branch and one dual-function, which is exactly 2x speedup (at best).

Alexander