Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20180315200813.GA660@openwall.com>
Date: Thu, 15 Mar 2018 21:08:13 +0100
From: Solar Designer <solar@...nwall.com>
To: passwords@...ts.openwall.com
Subject: keyed hash vs. encryption (was: Real world password policies)

Jim,

On Thu, Dec 07, 2017 at 02:54:21PM -0800, Jim Fenton wrote:
> On 11/8/17 2:32 PM, Jim Fenton wrote:
> > On 11/3/17 1:29 PM, Arnold Reinhold wrote:
> >>> On Oct 30, 2017, at 5:06 PM, Jim Fenton <fenton@...epopcorn.net> wrote:

> >>> The approach is different for offline attacks: in addition to salting and iterated hashing with an expensive key derivation function, SP 800-63B recommends an additional keyed hash with the key stored separately (as in an HSM, or on a separate machine not otherwise accessible). So if the verifier can keep the key secret, the hashes aren't usable by password cracking at all.
> >>>
> >>> Additional guidelines on the size and composition of blacklists is planned for the implementation guide that is a companion to SP 800-63B, currently under development.
> >>>
> >> The NIST SP800-63B recommendation to hash password verification data using a key stored separately in some sort of protected hardware is a big step forward, but it comes at the end of a string of SHOULDs (vs SHALLs) in the document. I realize the guidelines are only a few months old, but is there any momentum, either in the U.S. Government or the private sector towards implementing that recommendation?
> > The recommendation to do an additional keyed hash with a key stored
> > separately is completely new in 800-63. While I'm convinced that's a
> > really good thing to do, I don't know if anyone who is doing it yet, and
> > making it a SHALL is a bit abrupt. We need to be mindful that there are
> > many authentication systems used by the government, and we can't
> > arbitrarily make some of them (perhaps based on commerical products)
> > suddenly out of compliance.
> >
> > The specification doesn't actually call for a hardware implementation
> > (e.g., HSA) of this. A reasonable solution might be to stand up a
> > separate server, not accessible from outside, that accepts password
> > hashes and rehashes them with the private key. In my "spare time" I'm
> > working on a proof-of-concept for this that I plan to open-source.
> > Shouldn't take long.
> 
> To close the loop on this, I have published a simple utility for doing
> this. The code is at
> 
> https://github.com/jimfenton/rehash
> 
> and I have described it further at
> 
> https://altmode.org/2017/12/05/protecting-passwords-against-cracking-with-rehash/

And we discussed it on Twitter at the time, and you seemed to have
agreed with my reasoning that hash encryption (symmetric to a secret
key) has better properties than (re-)hashing with a secret, except
possibly on generic HSMs (where there's maybe-higher risk of
implementation issues, such as the HSM readily including a decryption
feature that might not be properly disabled on all deployments).

https://twitter.com/solardiz/status/938438676048162832

<jimfenton> New blog post: Protecting passwords against cracking with rehash https://altmode.org/2017/12/05/protecting-passwords-against-cracking-with-rehash/ #security #passwords
<solardiz> I recommended this in 2012, albeit with a focus on HSMs. I've since realized that at least for software implementation reversible encryption has better properties. Ideally also encrypt/decrypt the salts, to avoid precomputation & cache-timing attacks before key compromise.
<jimfenton> In what way does reversible decryption have better properties?
<solardiz> Keyed hashing requires that when merging 2+ different-key DBs, key IDs be stored along with each hash. Ditto for a new key for new hashes e.g. after a compromise. Reversible encryption avoids these maintenance issues by letting us re-encrypt to a new key.
<jimfenton> Initially I was leaning heavily toward hashing rather than reversible encryption, but in this case doesn't seem like reversible introduces any new vulnerabilities and has the operational advantages you list.
<jimfenton> Would want to encrypt and compare in normal use to discourage decryption of hashes, and only decrypt for rekeying, etc.

Now in another thread, Arnold argues in favor of changing the SHOULD to
SHALL, and you haven't objected yet:

http://www.openwall.com/lists/passwords/2018/03/15/1

So I feel I have to: please either leave it at SHOULD, or please allow
the hash encryption approach as an option as well (primary option even?)

FWIW, I also agree with your "Would want to encrypt and compare in
normal use to discourage decryption of hashes, and only decrypt for
rekeying, etc.", and this is how I had implemented it in yescrypt,
finally released:

http://www.openwall.com/yescrypt/

yescrypt's optional built-in hash encryption also en/decrypts the salts,
"to avoid precomputation & cache-timing attacks before key compromise".
This mitigates two attacks by someone with a leaked/stolen hash database,
possible when only hashes are encrypted, and salts are not:

A. The attacker could start precomputation of hashes for candidate
passwords, and then check them quickly if and when the key is also
leaked/stolen.  When salts are encrypted, the attacker's progress is
fully stalled until the key is also available.

B. If the attacker can ever execute code on a machine where the hashes
are being recomputed defensively (perhaps of users logging in), the
salts would be input to cache timing attacks on yescrypt.

Why also continue to encrypt hashes?  To mitigate insufficiently random
salts (they should be sufficiently random, but I don't want to take
unnecessarily high risk impact if they are not).

These two attacks, or at least attack A if both the hash type and its
implementation are cache timing safe, would also apply to "an additional
keyed hash" if applied only after the slow hashing.  Or, if that keyed
hash is applied only before the slow hashing, then there's attack C
possible under another scenario:

C. An attacker with temporary oracle access to a fast HSM could invoke
the key-requiring portions of the computation for many candidate
passwords (and salts, if those are also input to the HSM), without
being rate-limited by the slow hash computation that would normally
follow.  The attacker would then reuse those partial computations to
complete the slow hashing offline, even after their oracle access to the
HSM has been revoked.

The salt+hash encryption implemented in yescrypt avoids this as well.

To fully deal with these attacks with an HSM, two invocations of the HSM
per hash computation are needed.

For now, I limited the hash (re-)encryption function to yescrypt native
hashes (the "$y$" prefix).  It is easy to extend to also work for a few
other existing hash types/encodings: classic descrypt (encrypting only
the last 11 chars corresponding to the hash), BSDI extended aka FreeSec
DES-based crypt (encrypting either just the hash as well, or if we like
also the salts or even also the parameters - this one's encoding is a
very good fit), md5crypt/sha256crypt/sha512crypt/phpass (encrypting only
the hashes since the salts are not encoded and can be arbitrary - not
even necessarily using a specific base64 alphabet).  Also can easily
support hash encryption for the older scrypt encoding with the $7$
prefix (without encrypting the salts for the same reason as md5crypt,
etc.)  I will probably add the support for these in a future revision of
the yescrypt tree.  It will hardly add any code - just basic checks for
these compatible hash prefixes.  bcrypt and Argon2 are harder,
unfortunately (each of them uses its own encoding, not crypt's classic
encoding), so it's unclear whether they will ever be supported.

yescrypt's hash encryption is format-preserving (including for the
additional hash types described above), and the hash encoding string is
indistinguishable from non-encrypted unless you know/test the right
password.

A consolation for not encrypting the salts of those non-yescrypt hashes
is that the API will be easily usable in the "encrypt and compare" way.

For yescrypt hashes, the optional encryption key is passed right into
the password hashing API, which performs the two encryptions (of salt
and of hash).  And yes, even for the salt it is actually encryption
before the hashing, to directly use randomly generated and not
explicitly encrypted salts with that API, and to only require the
encryption code (not decryption code) during user authentication (the
decryption support doesn't even have to be compiled in, although it's
trivial - just reversed ordering of the Luby-Rackoff rounds).

I'm sorry that this looks like an yescrypt ad, but it's obviously not a
coincidence that I implemented what I think is right.

Alexander

Powered by blists - more mailing lists

Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.