phc-discussions - Re: [PHC] cost upgrades (Re: [PHC] Scripting memory (not so) high vs Catena in PHP (with optimizations))

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: <20140119211534.GA22884@openwall.com>
Date: Mon, 20 Jan 2014 01:15:35 +0400
From: Solar Designer <solar@...nwall.com>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] cost upgrades (Re: [PHC] Scripting memory (not so) high vs Catena in PHP (with optimizations))

On Sun, Jan 19, 2014 at 06:49:06PM +0400, Solar Designer wrote:
> My "2x granularity":
> 
> Upgrade #	t_cost	AT cost
> 0		1	1 (100%)
> 1		2	2 (50%)
> 2		4	6 (37.5%)
> 3		8	22 (34.375%)
> 4		16	86 (33.594%)
> 
> Catena (as described by Bill above):
> 
> Upgrade #	t_cost	AT cost
> 0		1	1 (100%)
> 1		3	5 (55.556%)
> 2		7	21 (42.857%)
> 3		15	85 (37.778%)
> 4		31	341 (35.484%)
> 
> While both converge to 1/3 of AT cost of non-upgradable hashes, Catena's
> upgrades are steeper, which results in slightly higher efficiency, but
> slightly lower flexibility (especially for the very first upgrade: 2x
> vs. 3x difference in t_cost).  I'm not sure which is better.

Here's an even steeper alternative to consider:

Upgrade #	t_cost	AT cost
0		1	1 (100%)
1		5	17 (68%)
2		21	273 (61.9%)
3		85	4369 (60.5%)
4		341	69905 (60.1%)

This converges to 60% efficiency, rather than 1/3, so it is much better
in this respect - but is the flexibility good enough?  All upgrades are
4x+1 for t_cost (vs. Catena's 2x+1), meaning that first upgrade is 5x
for t_cost and further upgrades are a little over 4x for t_cost.  On one
hand, this is almost 2x steeper than Catena's, but on the other hand for
the very first upgrade the difference is only 5/3 = ~1.67, whereas the
long-term efficiency improvement is 3/5/(1/3) = 9/5 = 1.80.  The first
upgrade's efficiency improvement is only 17/25/(5/9) = 1.224, though.

And steeper yet:

Upgrade #	t_cost	AT cost
0		1	1 (100%)
1		9	65 (80.2%)
2		73	4161 (78.1%)
3		585	266305 (77.8%)
4		4681	17043521 (77.8%)

This converges to 7/9 = ~77.8% efficiency.  Are 8x to 9x t_cost upgrade
steps still acceptable?  Probably only if upgrades are expected to be
extremely infrequent anyway (only made when the previous settings are
about to become totally inadequate).

As an option, one of these schemes may be chosen on first upgrade, but
this adds complexity and confusion.

All of these schemes ensure that if the original m_cost was a power of 2,
then so will be all additional iterations' m_cost values.

Alexander