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]

Date: Wed, 17 Sep 2014 06:30:36 -0400
From: Bill Cox <waywardgeek@...hershed.org>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] omegacrypt and timing

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 09/17/2014 05:53 AM, Krisztián Pintér wrote:
> On Wed, Sep 17, 2014 at 11:30 AM, Bill Cox 
> <waywardgeek@...hershed.org> wrote:
>> However, AntCrypt, OmegaCrypt, and Schvrch all tried to
>> introduce data based branching
> 
> i picked omegacrypt because i just spotted this. out of the 3, 
> antcrypt seems to be the worst, the other two can get away with 
> some blinding (dummy operations), but you can't compensate for 
> differences in floating point, as the timing is just unknown and 
> depends on zillions of factors, including the data itself.
> 

I forgot to mention POMELO.  It also does data-based branching to
thwart SIMD.  That's 4 entries with the same idea!

Of the four, AntCrypt does the best job of making it's case for using
data-based branching for SIMD defense.  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.

I would love to explore more in this direction of data-based branching
for GPU defense.  None of these code bases seems like the right
starting point, so... I think may have some fun hacking up a non-entry.

Of all the authors, I think I win at using other people's good ideas
:-)  I bet I can make something cool with this one.

Specifically what I'm thinking of is a simple m_cost loop like my
original "keystretch" algorithm, but I'd replace hashing with with
3-cycle AND/OR/ADD/SUB-XOR-ROTATE combinations.  Like Schvrch and
POMELO, I'd drop an calls to existing cryptographic hashes, and depend
on the unpredictable 3-instruction combinations to randomize a "state".

I think I'll go code it and post back :-)

Bill
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1

iQIcBAEBAgAGBQJUGWLIAAoJEAcQZQdOpZUZOgoQAKakzgffcA4UDQ0YVF8UdLZw
OlkW+86jKQLgZw0ybM7zanx8WsNtGMlb+BAUWHk3vfvzsyaQnxXa/V5Jqy+sOxZA
bDl++C8EwlZj+Zeaq+9QsQ/Q5LZ5b2KOvljwvOh+OVUOqS9XfzfKbUTvowmhvNxG
hBdRz+gl5acvsuN7jWHL3iZonkj1UUFOxCuz/UtKzsiHzhCYx/kAThztRCbsDoAl
wNVNNF8iEH2Ghu/wT3FurmXUIXYf3eEGJCgfEPDue57ZGv5k7QdkCRh6i+gs5MWt
F+vy74/GrTGrWDrmMEHJUhDMq7fgHj/dbAGjY8ypUW65jKRg5RFA7s/5rmqPHnLf
y7C+a8V5L6cezCoYEXASjl0OWqhTdKSv3tZWVX7C+rZPh4R4g9ceXbEE+1GS8Ntd
gUROW5SMlYOW3erbuuSvloezqMIPV4N9sICH4YbsHu/ZnW1xYJ8Jx1j9zFMHfHwv
7+ZieMjmPTo7Cq966gWmTvWO15sTwNHAC8zo4uzVlnsKKXZUtWWbnNGwZbTSi1dG
LmyRqc3CBzsE2iV+oVE3+wEshRERhbFOvYzkWrY8g2xEYGNzAsmSA3iz9nYbHJ5n
si+sAgGxdnW/NvH7HD+maK6ZYV44gWFJCmowzcwa/cCJwL9Rt9e9zsqf0vZAu0Zq
GVIaQQWYraJNJKACeQ8k
=K0VJ
-----END PGP SIGNATURE-----