phc-discussions - Re: [PHC] PHC: survey and benchmarks

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: <591670431.585454.1427164408474.JavaMail.open-xchange@oxuslxltgw10.lxa.perfora.net>
Date: Mon, 23 Mar 2015 21:33:28 -0500 (CDT)
From: Steve Thomas <steve@...tu.com>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] PHC: survey and benchmarks

> On March 23, 2015 at 1:29 PM Krisztián Pintér <pinterkr@...il.com> wrote:
>
> maybe i just don't understand something, but i have the impression
> that the authors had problems finding information about useful
> parameter ranges? maybe it would be helpful to assemble a table
> containing parameter-cost values for each candidate.
>

Yeah I saw that too it kind of invalidates most of their findings. Since we know
they didn't pick the parameters correctly.

Name       | Min m_cost | Bytes of memory        | Min t_cost* | Rounds
-----------+------------+------------------------+-------------+---------------
Argon      | 1          | 1,024*m_cost           | 2 or "3"?   | t_cost
battcrypt  | 0          | 8,192*2**m_cost        | 0           | Too long **
Catena     | ?          | HASH_LEN*2**m_cost     | 2           | t_cost
Lyra2      | 3?         | 24,576*m_cost          | 1?          | t_cost
Makwa      | -          | -                      | 0           | t_cost+1
Parallel   | -          | -                      | 0           | Too long ***
POMELO     | 0          | 8,192*2**m_cost        | 0           | 2**t_cost
Pufferfish | 0          | 1,024*2**m_cost+144    | 0           | 2*2**t_cost+1
yescrypt   | 0          | 8,192*2**m_cost+11,264 | 0           | Too long ****

* Minimum safe t_cost may be higher than min t_cost
** {2,3, 4,6, 8,12, 16,24, ...}[t_cost]
*** 1,920*{1, 2,3, 4,6, 8,12, 16,24, ...}[t_cost]
**** {1/3,2/3, 1,2,3,4,5,6,7,8,9,10,...}[t_cost]


To be fairer you probably want to match the number of times the memory is looped
through "round". Since we can't do this we need to do different runs:

Name       | t_cost for 2x | t_cost for 3x | t_cost for 4x | t_cost for 5x
-----------+---------------+---------------+---------------+---------------
Argon      | 2             | 3             | 4             | 5
battcrypt  | 0             | 1             | 3             | -
Catena     | 2             | 3             | 4             | 5
Lyra2      | 2             | 3             | 4             | 5
POMELO     | 1             | -             | 2             | -
Pufferfish | -             | 0             | -             | 1
yescrypt   | 3             | 4             | 5             | 6


Luckily from this we can match most m_costs:

Name       | m_cost for X KiB
-----------+------------------
Argon      | X
battcrypt  | log2(X) - 3
Catena     | log2(X) + 4
Lyra2      | X / 24
POMELO     | log2(X) - 3
Pufferfish | log2(X)
yescrypt   | log2(X)


For the lazy people:

Name       | 128 KiB | 256 KiB | 512 KiB | 1 MiB | 2 MiB | 4 MiB | 8 MiB
-----------+---------+---------+---------+-------+-------+-------+-------
Argon      | 128     | 256     | 512     | 1,024 | 2,048 | 4,096 | 8,192
battcrypt  | 4       | 5       | 6       | 7     | 8     | 9     | 10
Catena     | 11      | 12      | 13      | 14    | 15    | 16    | 17
Lyra2*     | 5*      | 11      | 21*     | 43    | 85*   | 171   | 341*
POMELO     | 4       | 5       | 6       | 7     | 8     | 9     | 10
Pufferfish | 7       | 8       | 9       | 10    | 11    | 12    | 13
yescrypt** | 4       | 5       | 6       | 7     | 8     | 9     | 10

Name       | 16 MiB | 32 MiB | 64 MiB | 128 MiB | 256 MiB | 512 MiB
-----------+--------+--------+--------+---------+---------+---------
Argon      | 16,384 | 32,768 | 65,536 | 131,072 | 262,144 | 524,288
battcrypt  | 11     | 12     | 13     | 14      | 15      | 16
Catena     | 18     | 19     | 20     | 21      | 22      | 23
Lyra2*     | 683    | 1,365* | 2,731  | 5,461*  | 10,923  | 21,845*
POMELO     | 11     | 12     | 13     | 14      | 15      | 16
Pufferfish | 14     | 15     | 16     | 17      | 18      | 19
yescrypt** | 11     | 12     | 13     | 14      | 15      | 16

Name       | 1 GiB     | 2 GiB     | 4 GiB     | 8 GiB
-----------+-----------+-----------+-----------+-----------
Argon      | 1,048,576 | 2,097,152 | 4,194,304 | 8,388,608
battcrypt  | 17        | 18        | 19        | 20
Catena     | 24        | 25        | 26        | 27
Lyra2*     | 43,691    | 87,381*   | 174,763   | 349,525*
POMELO     | 17        | 18        | 19        | 20
Pufferfish | 20        | 21        | 22        | 23
yescrypt** | 17        | 18        | 19        | 20

* All Lyra2 numbers are rounded up or down by 8 KiB. Numbers marked with * are
rounded down 8 KiB.
** All yescrypt numbers are rounded down by 11 KiB.


------------------------------------------------------------------

Now the two non-memory hard algorithms:

Makwa can't be compared to any current algorithm.

Parallel can be compared to PBKDF2. Just divide the number of rounds in half to
match the number of hash function block calls.
t_cost = 0 is 1,920 rounds which is 960 iterations for PBKDF2.