Also see security.stackexchange.com/questions/121996/… "Can free WiFi hotspot providers snoop on HTTPS communications"

Alternate cracking scenario: assume cracker (me) tries to log in to a web page login that locks for 5 minutes after 3 wrong tries, for 1 day after 12, and requires reset after 24 but doesn't count "close enough". If I actually try any "close" password, that's almost like trying 1000 if I keep track of lockouts. If "opensesame" is close, then I only need test close-to-opensesame passwords. Even worse, this is a godsend to anyone trying to extend a breach of one site to others via standard login procedure given the rampant password reuse (exact or mostly similar). I can try forever!

If the cracker has the set of hashes (actual + close), then testing 1 possible hashed password eliminates all passwords that are in the set (if 1000 close, then compute 1 hash and compare it against 1001 hashes without recomputing). I am making the assumption that the pwd db -- with all the extra "close" hashes -- leaked (but see next comment).

I miss the point of this answer. You aren't comparing a hash to the real hash to see how close it is, you are constructing a set of hashes based on similar inputs. This set might be useful for validating a user (close doesn't count against max tries before lockout) but would also help an attacker if the set leaked ("tried wrong value but your close!" or "only need to try one form of password but not variant). Example: 'password' also tests 'Password', 'password1", 'password2', 'passwords', 'passwordz' -- but not the classic caps lock 'PASSWORD' and 'pASSWORD'.

@Avid - I posted an update just(?) prior to your action. Perhaps they crossed. Does it and the above comment address your concern?

@AviD - This is not a duplicate. I'm asking when/how does one know when it is safe/time to update a site password AND assuming we will. The referenced question is related but different: how does one determine whether the site was in fact compromised.

To know whether to bother updating passwords, wouldn't we also need to know whether a previously vulnerable site updated its certificates? Other actions?

Jan 2009 crawl of NASA site referenced in Imperva paper. WayBackMachine also has 2010 and other older and newer ones. web.archive.org/web/20090114141027/http://www.hq.nasa.gov/…

@Xander - Please feel free to add any citations you unearth to bottom of OP or as a comment. (Also ^ for research.)