phc-discussions - Representing cost in a formated hash

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>] [day] [month] [year] [list]

Date: Sun, 5 Jan 2014 20:23:58 -0600 (CST)
From: Steve Thomas <steve@...tu.com>
To: discussions@...sword-hashing.net
Subject: Representing cost in a formated hash

I understand this doesn't matter too much until near the end of the competition,
but this might change some entries to work with non-nice binary numbers (not 2
** X) costs.

The question is how to represent the cost parameters in the formated hash. $5$
and $6$ chose an optional field "$rounds=xxxxx$". Which is very wasteful. The
other way is to represent the cost as two to the power of X. Where X is
represented as a base64 character (values 0 to 63). This is normally capped at
30 to avoid 32 bit signed integer overflow. The problem is this is a little
coarse and the other way is too fine and wasteful.

Would it make sense to raise the square root of 2 to the power of the cost
value:
cost' = floor(sqrt(2) ** cost)
or
cost' = floor(2 ** (cost / 2))

32 bit signed integer math:
cost % 2 = 0: cost' = 1 << (cost >> 1)
cost % 2 = 1: cost' = 0x5a827999 >> (30 - (cost >> 1))

32 bit unsigned integer math:
cost % 2 = 0: cost' = 1 << (cost >> 1)
cost % 2 = 1: cost' = 0xb504f333 >> (31 - (cost >> 1))
------

Or should we just do this (returns numbers that match 3 * 2 ** X or 2 ** X):
cost'' = 1 << (cost >> 1)
cost % 2 = 0: cost' = cost''
cost % 2 = 1: cost' = cost'' + (cost'' >> 1)

This increases the cost by 50% then 33.33% then 50%... vs increasing the cost by
41.42% every time. The nice thing about the second method is the actual costs
are fairly nice binary numbers.

You should also note that both of these new methods take only one base64
character to represent. Unless you need the cost to be larger than 3 billion.
Content of type "text/html" skipped