[gfxmonk]

One solution is to use a separate storage for salts (or hints, really - it doesn't need to be a complex scheme, since we're hashing it anyway).

I do this myself with supergenpass, for when a site's password DB gets compromised (a common enough occurrence these days).

Importantly, this augmented state is a convenience - it's not irreplaceable. If I find myself _without_ my list of hints, I am not completely screwed - I'll just have a harder time logging into those few sites, and it's quite likely I'll remember the right hint after a few tries from memory if I really need to.

[eximius]

This post kind of inspired me to whip this up (probably not original, but it's minimal): https://bitbucket.org/logannc/deterministichashpass

Basically the same idea but seeds a random number generator with the master password and the service name to have an infinite supply of passwords. Technically no state is needed because Python's random module is deterministic, but I will end up saving the state with the service name and the index of the random number so that I don't have to try each and every one (not that I change passwords that often, for better or worse).

And, for convenience, since I won't be saving the master password, I'm looking into adding a credential cache like sudo has.

[kseistrup]

I use the HMAC hash of the username, the site, and a ‘key’ generated at random. However, this does mean that I'm screwed if I cannot access the keys [and cannot remember the password].