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: <20140406020055.GA20679@openwall.com>
Date: Sun, 6 Apr 2014 06:00:55 +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...)

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.

If the attacker swaps two inputs to a dual-function and its two outputs
on a trivial condition (like "i < j"), which can be done in a
branch-less manner, then the required number of dual-functions reduces
almost by half - e.g., to 136 for 16 original functions, or to 55 for 10
original functions.  This may be worthwhile if the functions are costly
enough that this overhead is relatively cheap, or/and if the
dual-functions would otherwise not fit in L1i cache.

Alexander