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: 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

Powered by blists - more mailing lists