Date: Thu, 16 Mar 2017 20:32:10 +0100
From: Solar Designer <solar@...nwall.com>
To: discussions@...sword-hashing.net
Subject: [PHC] trivial delegation

Hi,

This is something many of us probably had in mind (I did), but I don't
recall us discussing it.  So here goes.

I'll start with the counterpart of delegation: what Catena calls server
relief.  It's computation of almost-final hash on the client, with the
hash function being defined such that the computation can be completed
on the server without needing to transfer a lot of internal state from
client to server (but rather just a tiny pre-final hash).

Delegation of heavy computation by a client or a server to another
server (e.g., Facebook backend node to Facebook frontend node, as Alec
Muffett mentioned in his talk) can similarly be trivially accomplished
by computing a fast pre-hash on the requesting system and finishing the
computation on a delegation server (then having this hash sent back to
the requesting system).

Both things can readily be done on top of any existing password hashing
scheme - in fact, this is why some of us (including me) were skeptical
about Catena's server relief as a built-in feature.  However, PHC being
a competition I ended up adding an equivalent (and more: also usable in
challenge/response) to yescrypt, and I am now thinking whether built-in
trivial delegation support would also be worth it.

In order to minimize the exposure of sensitive information to the
server, the requesting system should include a secret in its pre-hash
computation.  It can be a global secret (per deployment) or it can be a
second per-account salt.  This is fine, but this extra data will then
need to be stored somewhere, and the computation will need to precede
our hashing scheme's computation each time, even if the delegation is
not always used or is dismantled later.  So we can't just say that this
e.g. yescrypt standard hash encoding includes all of the inputs to this
hash computation (sans the password and optional encryption key) and
that the entire algorithm is specified by yescrypt - rather, there would
be site-specific pre-hashing algorithms (we could recommend some
"standard" for pre-hashing, but technically it'd remain separate).

What I am thinking is that similarly to built-in server relief, we could
instead structure the hashing scheme such that it'd include the
separable pre-hashing as a standard step that is always done (whether
there's delegation or not).  Then delegation-computed hashes will not
require extra storage for an extra secret key and/or secret salt.

Specifically, it means that the main and only salt will also serve this
purpose, and in a delegation setup will not be revealed to the server.
The hashing scheme will then start by combining the password and salt
inputs e.g. with HMAC, and then will never use the salt directly again.
In a delegation setup, the requester will compute the HMAC on its end,
send it and yescrypt parameters (but not the salt) to the server, and
receive the hash value, which it will re-combine with the parameters and
the salt to form a standard yescrypt hash encoding string for storage or
comparison.

For cost-upgraded hashes, this means that each upgrade should not
require the original salt either, or else upgraded hashes would not be
fully computable in a delegation setup like the above.  As long as we
use strong cryptography like HMAC-SHA256 at the beginning and end of
each hash "body" computation (each upgrade step), this should be OK -
we'll have entropy bypasses over the heavy computation (like SMix) via
the HMAC-combined password and salt values (gradually HMAC-combined with
the heavy computation intermediate results, as yescrypt already does,
and overwritten).

Here are my past concerns on pre-hashing, where I ended up using HMAC of
the password along with a personalization string:

http://lists.openwall.net/phc-discussions/2015/01/31/3

To better support trivial delegation as above, I am now thinking of
revising this HMAC to use the salt instead of the personalization string
(or along with it if there's a good reason, or to avoid the need for
reasoning on why dropping the personalization would be safe).

I think using the salt instead of the personalization string would be
fine, and as a bonus could allow some existing frameworks/apps using
HMAC-SHA256 to upgrade to yescrypt easier (without keeping custom code),
although unfortunately most (maybe all?) of them appear to use
key=password, message=salt, which we should not (should do it the other
way around, because of HMAC's optional pre-hashing of the key).

If anyone knows of examples of frameworks, web apps, or whatever that
use HMAC-SHA256 with key=salt, message=password, please let me know.

As I'm only aware of private uses of yescrypt for password hashing so
far (plus two cryptocoins), which is no surprise given I never made an
official release of it outside of PHC, I still feel empowered to make
adjustments like this for the official 1.0 release, and it's OK, even
though not ideal, that PHC's 0.8 is slightly different.  (FWIW, the
privately used 0.9.x is still compatible with PHC's 0.8.1 - it just has
some extras in its reversible string encoding and optional encryption.)

Seeing how even Argon2i was tweaked post-PHC is empowering, too. ;-)

I'd appreciate any comments on any/all of the above.

Thanks,

Alexander

Powered by blists - more mailing lists