phc-discussions - An API for Efficiently Obtaining t

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

Message-ID: <1444596728.8329.86.camel@bqp.io>
Date: Sun, 11 Oct 2015 14:52:08 -0600
From: Taylor Hornby <taylor@....io>
To: discussions@...sword-hashing.net
Subject: An API for Efficiently Obtaining t_cost

Hi,

I'm not sure if it's the PHC's job to standardize on an API for the
winning hash function, but I'm going to strongly argue that
implementations MUST to provide an API similar to the following:

int PHS_find_t_cost(
	void *out,                 /* same */
	size_t outlen,             /* same */
	const void *in,            /* same */
	size_t inlen,              /* same */
    	const void *salt,          /* same */
	size_t saltlen,            /* same */
	unsigned int target_msec,  /* target milliseconds */
        unsigned int *t_cost,      /* output parameter */
	unsigned int m_cost        /* same */
);

Calling this API should *efficiently* find the best t_cost for the
given m_cost and target running time, on the current system under its
current workload, while at the same time computing a hash. In other
words, for a fixed m_cost, it should find the smallest valid t_cost
such that the time taken is longer than target_msec milliseconds.

The problem is that on memory-constrained devices, you might want to
use as much memory you can, and then keep computing on that memory for
a certain amount of time, say 5 seconds, when you don't know which
t_cost to use for that amount of time, and you don't want to do trial-
and-error or extrapolation from faster calls.

I think this is an extremely important API to mandate, since if the
developer needs it, and it isn't provided for them, they either have to
do trial-and-error or heuristically guess-then-check t_cost which is
not efficient, OR they have to modify or even re-implement the
password-hashing library, likely losing important optimizations and
thus giving the attacker an advantage in the process.

It will also result higher t_cost being chosen in practice. Developers
can hard-code the time cost in units of seconds, so that t_cost is
always as high as it can be without impacting usability. Without this
API, they'd have to run benchmarks on the system to select t_cost, or
hard-code non-optimal costs, like the libsodium API [1,2,3] does.

It's possible to efficiently provide this API for the iteration count
in PBKDF2 as well as for 'p' in scrypt. I think it is also possible for
Argon2.

Even if we decide not to require this API, please consider adding it to
your implementations.

Thanks,
-Taylor

[1] http://doc.libsodium.org/password_hashing/index.html
[2] https://github.com/jedisct1/libsodium/blob/e326ef90301cf570a5e6691c
46d4a1d37adc1e07/src/libsodium/include/sodium/crypto_pwhash_scryptsalsa
208sha256.h#L28
[3] https://github.com/jedisct1/libsodium/blob/e326ef90301cf570a5e6691c
46d4a1d37adc1e07/src/libsodium/crypto_pwhash/scryptsalsa208sha256/pwhas
h_scryptsalsa208sha256.c#L18

p.s. Apologies if this has been discussed before. There's a lot on this
list I haven't read.