Can Levenshein distance prevent password abuse?

Learning about passwords by writing an app around flask's auth utilities. I'ved crammed all the approaches I can think of in one function cleanpassword(). Later I will decide which ones are more trouble than they are worth.

This is the fragment in question. The rest of the function is below for context.
I downloaded a list of the worst passwords known to man (in English -- I bet the lists for others are just as funny). I archive each password as it is used. There is a timestamp if I ever need to allow reuse after a while. The archived passwords are stored hashed because seeing a users last five passwords would make it pretty easy to guess what his next five will be or what he uses on another site. The historically bad passwords are in plain text.

Storing them plain allows the use of Levenshein distance to prevent trivial modification of bad passwords ('football' 'f00tball' and 'futball!') are all treated the same.

#    # are they on the list of 10k really bad passwords?
#    if BadPasswords.query.filter(BadPasswords.baddie == password).first():
#        flash('Password '+ password +' is on the list of really bad passwords.','error')
#        return False

    # are close to the list of 10k really bad passwords?
    badwords = BadPasswords.query.all()
    for b in badwords:
        if lev_distance(b.baddie, password) < levenshtein_limit:
        flash('Password '+ password +' is on or near the list of really bad passwords.','error')
        return False

    # are they on the list old passwords?
    if bcrypt.check_password_hashpassword in OldPasswords.query.all():
        flash('Password '+ password +' is on the list of previous passwords.','error')
        return False

So the question is, can I use a similar edit distance test to prevent reuse of originally acceptable passwords? I think the answer is no, but it is hard to prove a negative -- particularly when authorization technology get very deep very close to shore. My understanding is elementary on a good day.

    # check for safe password

from password_strength import PasswordPolicy
from Levenshtein import distance as lev_distance
from app import bcrypt, db
from models import BadPasswords, OldPasswords
from extensions import environ

forgive = environ.get('FORGIVE_BAD_PASSWORDS')
#forgive = True

levenshtein_limit = environ['LEVENSHTEIN_LIMIT']


# class BadPasswords(db.Model):
#     __tablename__ = 'BadPasswords'
#     id = db.Column(db.Integer, primary_key=True) 
#     baddie = db.Column(db.String(25)) 

# class OldPasswords(db.Model):
#     __tablename__='OldPasswords'
#     id = db.Column(db.Integer, primary_key=True) 
#     oldie = db.Column(db.String(255)) 
#     created = db.Column(db.DateTime)


policy = PasswordPolicy.from_names(
    length     = environ['PASSWORD_LENGTH'],
    uppercase  = environ['PASSWORD_REQUIRE_UPPERCASE'],
    nonletters = environ['PASSWORD_REQUIRE_NON_LETTERS'],
    strength   =(environ['PASSWORD_REQUIRE_STRENGTH'], environ['PASSWORD_REQUIRE_ENTROPY_BITS'])
)

def cleanpassword(password,verify):
    # forgive bad passwords for debugging
    if forgive:
        return True

    # do they match?
    if not password == verify:
        flash ("Passwords don't match")
        return False

#    are they on the list of 10k really bad passwords?
#    if BadPasswords.query.filter(BadPasswords.baddie == password).first():
#        flash('Password '+ password +' is on the list of really bad passwords.','error')
#        return False

    # are close to the list of 10k really bad passwords?
    badwords = BadPasswords.query.all()
    for b in badwords:
        if lev_distance(b.baddie, password) < levenshtein_limit:
        flash('Password '+ password +' is on or near the list of really bad passwords.','error')
        return False

    # are they on the list old passwords?
    if bcrypt.check_password_hashpassword in OldPasswords.query.all():
        flash('Password '+ password +' is on the list of previous passwords.','error')
        return False

    # use the quality tests      
    test = policy.test(password)
    if test:
        for t in test:
            fault = t.name()
            if fault == 'length':
                flash('Password needs at least '+ str(t.length) +' letters.','error')
            if fault == 'uppercase':
                flash('Password needs at least '+ str(t.count)  +' upper-case letters.','error')
            if fault == 'nonletters':
                flash('Password needs at least '+ str(t.count)  +' non-letter characters.','error')
            if fault == 'strength':
                flash('Password needs more entropy.')
        return False

    # seems to have passed all the tests
    return True

Can you? Yes. Should you? Absolutely not. Since you say you only know the basics, I'll explain.

Hashing basics

As you said, stored passwords should always be hashed for safety. I hope you're salting them as well as hashing - or maybe flask does it for you, I don't know.

For the hash function to be any good, it has to create essentially random output. If you hash two values that differ only by a single character - like foobar and foobaz - the hash output should be completely different. If all you have is the hashes, there's no way to tell whether the inputs are related (like foobar and foobaz) or completely different (like foobar and elephant). Otherwise your hash function is not secure and your passwords can be compromised.

So the properties of a good hash function make hash values completely useless for levenstein distance or any other measures of similarity. All relations between the inputs are destroyed by the hash.

How it affects your approach

This means you can only run levenstein distance on unhashed (plaintext) passwords. That solution is wrong for so many reasons. Passwords should never be stored anywhere in plaintext (your bad passwords list is ok because you reject those as passwords). Passwords should never be sent in plaintext. Passwords should never be sent to the server at all under any conditions. The password should only leave the client in an already hashed state.

If you follow this important rule then you can only runs password checks on the client side. Client enters possible password, local code checks it's validity. If it's ok, then password is hashed before being sent to server. Server should never see the plaintext, or it can be compromised.

What you're attempting is impossible in this situation. Your auth server stores previous passwords, hashed. There's no way to compute a meaningful distance metric between hashed passwords and new password, either before or after hashing it. Doesn't matter if you send hashed previous passwords to client, or send plaintext new password to server (VERY BAD). Either way, you can't compute meaningful comparisons with hashed values.

How it should be done

Hopefully your password checks are done client side - it's not clear where your sample code runs. If server side, then stop immediately and rethink your design. Passwords should never be sent to the server.

Even sending hashed passwords is insecure. If my password is "foobar" which hashes to "vsfsevssdfsdga", and I send "vsfsevssdfsdga" to authenticate to the server every time, then I've accomplished nothing. An attacker can snoop the magic token ""vsfsevssdfsdga" " and use it to gain access, defeating the purpose of hashing.

What you should really be doing is a challenge-response system where the client and server both know a shared secret (such as a hashed password) that's never exchanged directly. Instead, the server sends a challenge like "send me the hash of your password, hashed with random string XYZ". It works like this:

Example

Take the example above : password foobar with hash "vsfsevssdfsdga". Server stores "vsfsevssdfsdga" and computes hash ("vsfsevssdfsdga" + XYZ) = klojhsvndfb. User enters foobar and client computes hash (hash (foobar) + XYZ) = klojhsvndfb. Client sends klojhsvndfb. The only data exchanged each login is XYZ from server to client, which is a random string each time ; and klojhsvndfb from client to server. If an attacker learns the hash value klojhsvndfb, they can't use it to login in the future. It's useless because the server will send a new challenge string instead of XYZ on every login attempt.

In this example, client and server still need to exchange "vsfsevssdfsdga" at the beginning for subsequent logins to work. But there are protocols for client and server to establish a shared secret without directly exchanging any compromising info (i.e. someone can snoop on the entire conversation and still not be able to compute the shared secret). If a password must be involved, probably the best approach is to create a secure shared secret between client and server, then store it client side encrypted with the user's password. On login, client enters password to decrypt shared secret on local machine, then does challenge-response with server.

Conclusion

That's the basic idea. However please DO NOT try to implement this or any other type of authentication scheme yourself. There are many, many subtle ways to screw up and compromise your security. It's far better to use an established security library or framework to handle authentication for you. Security is hard. Trust me, it's very easy to get wrong.

Hope this helps.