Using salted hash as password for easy memorization without reuse?

Question

I had an idea earlier: Secure passwords are a) long, and b) unpredictable. A hash is both of these. Would it be safe to reuse a key between sites, and include the site's name as a salt? For example:

SHA256("kFnU7Ra%P1_stackexchange")
SHA256("kFnU7Ra%P1_google")

And so on. As long as nobody discovers your key, it seems better than password reuse.

Answer 1

This is better than password reuse, but still not cryptographically strong, for it is vulnerable to (extensive) brute-force search of the relatively short key (your 11-character kFnU7Ra%P1_, which is optimistically worth 66 bit of entropy) for someone who knows the salt (your stackexchange) and a password. As a theoretical aside, although we know no practical attack if the key was longer, we have no strong argument that there is not.

Critical: each user should have a different salt for each site, thus you really should add the user's name in the salt.

If you want the key to remains short, what you want is a key derivation function purposely slowed-down for use with a short key. That could be scrypt, bcrypt, or PBKDF2. It brings you vastly improved, and parameterizable resistance to that attack.

If the key can be long and high-entropy, you could use HMAC-SHA256, with the salt as the message.

Also, a minor, tractable problem is that hashes, KDFs, and MACs, produce arbitrary bytes, some of which are not acceptable in a password by many sites. You need a post-processing to turn that into something acceptable, but the rules vary from site to site: different minimum and maximum length, different (and occasionally incompatible) caveats on the required or prohibited presence of certain special characters.

Note: the idea, and the variations suggested, are well known.

Update: using a 21-character string with each character chosen at random among a set of $64=2^6$ gives you $126=21\cdot6$ bits of entropy, which is ample even if you use a non-slowed-down KDF, or MAC, rather than scrypt/bcrypt/PBKDF2.

It is an entirely different thing if you are using a 21-character string that Joe User can choose. A significant fraction of Joes will choose terrible keys, and be unsafe. A compromise is something like diceware, that Joes can not choose (or can only choose among a few hundred random choices), but can be asked to memorize (he will likely write it down or store it in a "secret" clear text file; also, some Joes will forget the key, loose the paper, or/and accidentally destroy the file). In this way, you can hope to pack 48 bits of entropy in 21 characters. I would recommend a longer string that can be memorized over a shorter that can not, see the obligatory XKCD cartoon. Combined with scrypt or even the lesser bcrypt, and settings resulting in 0.2 second of CPU work per use, this is good enough for most uses: if an attacker manages to be $2^5$ times more efficient than the legitimate Joe, the expected work per attack is still $2^{48-5-1}\cdot 0.2$ CPU.second, that is $>130.000$ CPU.year; and sizable RAM (resp. some, little) for each CPU during the whole attack time, if scrypt (resp. bcrypt, PBKDF2) is used; for scrypt, RAM is where a lot of the investment cost of the attacker would be.

Answer 2

This might be overly simplified, but what if you expanded the website name. Then, using some Pseudo-random-function, encrypt it, such that it is highly incalculable, but simple (depending on your PRF) to find.

Of course, this leads to some security measure that would need to be taken, and implementing the PRF would be a hassle to do securely, but I think it could work.