文字列のパスワード強度を数値化する

ある文字列がパスワードとしての強度がどのくらいか数値化します、本ロジックで言う強度とは”既存の英単語とは似ていない”度合いの事とします
例えば以下について考えます

compliance（既存の英単語）
ccopilnmea（compliance をランダムに並べ替えた文字列）
dmsfyqex（ランダムな文字列）

これらの文字列のパスワード強度を考えた時に

dmsfyqex　＞　ccopilnmea　＞　compliance

という大小関係になる数値が出せれば便利だと考えます、具体的にはパスワード入力画面で一定スコア以下だった場合に警告を出すという使い方を想定します。
今回解説するロジックにおいて以下のスコアが出ました

compliance: score = 0.2868966957306085
ccopilnmea: score = 0.6242194273850281
dmsfyqex: score = 0.9749742578498471

想定通りのスコアが出ています

単語構成文字列が含まれていたらスコアを低くする仕組み

単語郡から単語構成文字列を学習する

学習というと大げさな感じがしますが、３文字に分割して辞書を作り使用されている数の合計を取るだけです
例えば compliance という文字列であれば以下のように３文字ずつ取り出します

取り出した３文字は連想配列等に入れて既に存在すればカウンターを加算、存在しなければカウンターに１をセットしキーとして該当文字列を登録といったふうにして各文字パーツの集計を取ります
３文字ずつに分割して各パーツの集計を取ると以下のような感じになります

出現頻度に比例してスコア算出

出現頻度をそのまま正規化してスコアにすれば良さそうではありますが、そのままでは都合が悪いので加工を行います
・出現回数の差が激しいため log で差の激しさを大人しくする
・高いほどに不規則性がある事にしたいので正規化後に １ － ｎ　としてスコアの大小を逆にする
という加工を行います

強度算出手順

compliance という文字列の強度を出すために辞書を作った時同様に３文字パーツに分解し、各々のスコアを当てはめていきます
・３文字パーツに分解
　com, omp, mpl, pli, lia, ian, anc, nce
・各々のスコアを出し平均値を取る
com score=0.21246313927796934
omp score=0.30720005124440175
mpl score=0.3626175921788861
pli score=0.3705815810316746
lia score=0.3790384929824562
ian score=0.25322273936979667
anc score=0.23946097632816377
nce score=0.1705889934315199
平均値＝0.2868966957306085

といった手順で既存英単語 compliance のパスワード強度は低いだろうと考えられる数値が出せました
※すべての文字列を小文字で処理すること

実装、実装準備

単語郡の準備(words.txtの準備)

学習対象としたい英単語を改行区切りでテキストに保存します
ANC単語頻度準拠_英和辞典/ANC Frequency Dictionary
から
ANC 30,000+ words - Excel(.xls) file, 36.4M
をダウンロードします
"Japanese+" タブの "Ａ" 列をコピーして "words.txt" としてプログラムと同じディレクトリに保存します。
他の単語郡を準備しても構いません、改行区切りで words.txt に列挙されていれば問題ありません

ソースコード

文字列集計ソースコード

# word_stats.py
import json

def split_units(s):
    if len(s) < 3:
        return []
    n = len(s) - 3
    units = []
    for i in range(n + 1):
        units.append(s[i:i + 3])
    return units

def train_words():
    allunits = []
    words = []
    count = []
    with open("./words.txt", "r") as f:
        x = f.read()
        lines = x.split("\n")
        
        #lines = lines[:100]
        
        for l in lines:
            l = l.lower()
            units = split_units(l)
            for u in units:
                try:
                    idx = words.index(u)
                    count[idx] += 1
                except:
                    words.append(u)
                    count.append(1)
        v = {
            "words": {
                "length": len(words),
                "value": words
            },
            "count": {
                "length": len(count),
                "value": count,
                "min": min(count),
                "max": max(count)
            }
        }
        with open("./word_feature.json", "w") as wf:
            wf.write(json.dumps(v))

def main():
    train_words()

if __name__ == "__main__":
    main()

# python word_stats.py

実験ソースコード

# main.py
import json
import numpy as np
import sys

import word_stats

def load_word_feature():
    with open("word_feature.json", "r") as f:
        x = f.read();
        x = json.loads(x)
        return x

def calc_word_score(feat):
    length = feat["words"]["length"]
    counts = np.array(feat["count"]["value"])
    counts = np.log(counts)
    #counts = np.power(counts, 2)
    count_min = min(counts)
    count_max = max(counts)
    scale = count_max - count_min
    score = (counts - count_min) / scale
    return score


def calc_word_strength(words, score, s):
    units = word_stats.split_units(s)
    strength = []
    for u in units:
        try:
            idx = words.index(u)
            strength.append(score[idx])
        except:
            strength.append(1.0)
    return strength

def test_print(words, word_score, s):
    print("{}: score = {}".format(
        s,
        np.mean(calc_word_strength(words, word_score, s.lower())))
    )


def Test1(words, word_score):
    arr = ["com", "omp", "mpl", "pli", "lia", "ian", "anc", "nce"]
    score = []
    for x in arr:
        print("{} score={}".format(x, word_score[words.index(x)]))
        score.append(word_score[words.index(x)])
    print(score)
    print(np.mean(score))
    

def main():
    word_feature = load_word_feature()
    words = word_feature["words"]["value"]
    word_score = calc_word_score(word_feature)
    word_score = 1 - word_score # 高い＝ポジティブとしたいのでスコアを逆転させる
    
    
    #idx = words.index("com")
    #print(words[idx])
    #print(word_score[idx])
    #print(word_score[idx] - 1)
    #Test1(words, word_score)
    #sys.exit()
    
    
    test_print(words, word_score, "compliance")
    test_print(words, word_score, "remorseful")
    test_print(words, word_score, "proprietor")
    test_print(words, word_score, "underneath")
    test_print(words, word_score, "concerning")
    
    test_print(words, word_score, "ccopilnmea")
    test_print(words, word_score, "rsroefelmu")
    test_print(words, word_score, "oeirtroprp")
    test_print(words, word_score, "dhnuneeart")
    test_print(words, word_score, "icgcnonner")
    
    test_print(words, word_score, "dmsfyqex")

if __name__ == "__main__":
    main()

# python main.py

実行順序

word_stats.py を実行し words.txt から word_feature.json を作成します
main.py を実行します

実行結果

compliance: score = 0.2868966957306085
remorseful: score = 0.4101328195017412
proprietor: score = 0.3605496834657159
underneath: score = 0.3056502524650927
concerning: score = 0.2725657566209919
ccopilnmea: score = 0.6242194273850281
rsroefelmu: score = 0.7358370599956099
oeirtroprp: score = 0.5973599062478352
dhnuneeart: score = 0.6126002537025075
icgcnonner: score = 0.6963947190776706
dmsfyqex: score = 0.9749742578498471

実際に使用する場合に考えること

本ロジックだけでは 111, 222, aaa, bbb みたいなシンプルなＮＧパターンに対応していません
他には辞書にはないけど繰り返しているような場合、例えば zpxpzpxpzpxpzpxpzpxpzpxp みたいな文字列も明らかにパスワード強度が弱そうでも１．０近いスコアが出てしまいます
そのあたりについては専用のロジックを追加したほうが良さそうです
小文字、大文字、数字、記号をすべて含んでいるかという処理もありませんのでそれも追加で実装が必要だと思います

以上です