Po przeczytaniu różnych zasobów na temat siły hasła próbuję stworzyć algorytm, który zapewni przybliżoną ocenę ilości entropii hasła.
Próbuję stworzyć algorytm, który jest możliwie jak najbardziej wyczerpujący. W tym momencie mam tylko pseudokod, ale algorytm obejmuje następujące elementy:
- długość hasła
- powtarzające się postacie
- wzory (logiczne)
- różne przestrzenie znaków (LC, UC, numeryczne, specjalne, rozszerzone)
- ataki słownikowe
NIE obejmuje to i POWINNY BYĆ to DOBRZE (choć nie idealnie):
- porządkowanie (hasła można ściśle uporządkować według danych wyjściowych tego algorytmu)
- wzory (przestrzenne)
Czy ktoś może dać wgląd w to, do czego ten algorytm może być słaby? W szczególności, czy ktoś może pomyśleć o sytuacjach, w których podanie hasła do algorytmu ZAWRACA SIĘ jego siłę? Niedocenianie jest mniejszym problemem.
Algorytm:
// the password to test
password = ?
length = length(password)
// unique character counts from password (duplicates discarded)
uqlca = number of unique lowercase alphabetic characters in password
uquca = number of uppercase alphabetic characters
uqd = number of unique digits
uqsp = number of unique special characters (anything with a key on the keyboard)
uqxc = number of unique special special characters (alt codes, extended-ascii stuff)
// algorithm parameters, total sizes of alphabet spaces
Nlca = total possible number of lowercase letters (26)
Nuca = total uppercase letters (26)
Nd = total digits (10)
Nsp = total special characters (32 or something)
Nxc = total extended ascii characters that dont fit into other categorys (idk, 50?)
// algorithm parameters, pw strength growth rates as percentages (per character)
flca = entropy growth factor for lowercase letters (.25 is probably a good value)
fuca = EGF for uppercase letters (.4 is probably good)
fd = EGF for digits (.4 is probably good)
fsp = EGF for special chars (.5 is probably good)
fxc = EGF for extended ascii chars (.75 is probably good)
// repetition factors. few unique letters == low factor, many unique == high
rflca = (1 - (1 - flca) ^ uqlca)
rfuca = (1 - (1 - fuca) ^ uquca)
rfd = (1 - (1 - fd ) ^ uqd )
rfsp = (1 - (1 - fsp ) ^ uqsp )
rfxc = (1 - (1 - fxc ) ^ uqxc )
// digit strengths
strength =
( rflca * Nlca +
rfuca * Nuca +
rfd * Nd +
rfsp * Nsp +
rfxc * Nxc ) ^ length
entropybits = log_base_2(strength)
Kilka danych wejściowych oraz ich pożądane i rzeczywiste dane wyjściowe entropy_bits:
INPUT DESIRED ACTUAL
aaa very pathetic 8.1
aaaaaaaaa pathetic 24.7
abcdefghi weak 31.2
H0ley$Mol3y_ strong 72.2
s^fU¬5ü;y34G< wtf 88.9
[a^36]* pathetic 97.2
[a^20]A[a^15]* strong 146.8
xkcd1** medium 79.3
xkcd2** wtf 160.5
* these 2 passwords use shortened notation, where [a^N] expands to N a's.
** xkcd1 = "Tr0ub4dor&3", xkcd2 = "correct horse battery staple"
Algorytm zdaje sobie sprawę (poprawnie), że zwiększenie rozmiaru alfabetu (nawet o jedną cyfrę) znacznie wzmacnia długie hasła, co pokazuje różnica w bitach entropii dla 6. i 7. hasła, które oba składają się z 36 a, ale drugie 21 to skapitalizowane. Jednak nie biorą pod uwagę faktu, że posiadanie hasła 36 a nie jest dobrym pomysłem, łatwo go złamać słabym narzędziem do łamania haseł (i każdy, kto go obserwuje, zobaczy to), a algorytm tego nie odzwierciedla .
Odzwierciedla to jednak fakt, że xkcd1 jest słabym hasłem w porównaniu do xkcd2, mimo że ma większą gęstość złożoności (czy to w ogóle rzecz?).
Jak mogę ulepszyć ten algorytm?
Dodatek 1
Ataki słownikowe i ataki oparte na wzorcach wydają się być wielką rzeczą, więc postaram się je rozwiązać.
Mógłbym przeprowadzić kompleksowe wyszukiwanie hasła za pomocą słów z listy słów i zastąpić je tokenami unikalnymi dla słów, które reprezentują. Tokeny słowne byłyby wówczas traktowane jak znaki i miałyby własny system wag oraz dodawałyby własne wagi do hasła. Potrzebowałbym kilku nowych parametrów algorytmu (nazywam je lw, Nw ~ = 2 ^ 11, fw ~ = .5 i rfw) i dodam wagę do hasła, tak jak każdy inny ciężary
To wyszukiwanie słów może być specjalnie zmodyfikowane w celu dopasowania zarówno małych i wielkich liter, jak i zwykłych podstawień znaków, takich jak E z 3. Gdybym nie dodał dodatkowej wagi do takich dopasowanych słów, algorytm nie doceniłby ich siły lub dwa na słowo, co jest OK. W przeciwnym razie ogólną zasadą byłoby, że dla każdego niedokładnego dopasowania znaków, nadać słowu dodatkowy bonus.
Mógłbym wtedy wykonać proste kontrole wzorców, takie jak wyszukiwanie serii powtarzających się znaków i testy pochodnych (weź różnicę między każdym znakiem), które zidentyfikowałyby wzorce, takie jak „aaaaa” i „12345”, i zastąpiłyby każdy wykryty wzór wzorkiem token, unikalny dla wzoru i długości. Parametry algorytmu (w szczególności entropia na wzór) mogą być generowane w locie na podstawie wzoru.
W tym momencie wziąłbym długość hasła. Każdy token słowa i wzór będzie liczył się jako jeden znak; każdy token zastąpi znaki, które symbolicznie reprezentują.
Stworzyłem coś w rodzaju zapisu wzoru, ale zawiera on długość wzoru l, kolejność wzoru o i element podstawowy b. Informacje te można wykorzystać do obliczenia dowolnej arbitralnej wagi dla każdego wzorca. Zrobiłbym coś lepszego w rzeczywistym kodzie.
Zmodyfikowany przykład:
Password: 1234kitty$$$$$herpderp
Tokenized: 1 2 3 4 k i t t y $ $ $ $ $ h e r p d e r p
Words Filtered: 1 2 3 4 @W5783 $ $ $ $ $ @W9001 @W9002
Patterns Filtered: @P[l=4,o=1,b='1'] @W5783 @P[l=5,o=0,b='$'] @W9001 @W9002
Breakdown: 3 small, unique words and 2 patterns
Entropy: about 45 bits, as per modified algorithm
Password: correcthorsebatterystaple
Tokenized: c o r r e c t h o r s e b a t t e r y s t a p l e
Words Filtered: @W6783 @W7923 @W1535 @W2285
Breakdown: 4 small, unique words and no patterns
Entropy: 43 bits, as per modified algorithm
Dokładna semantyka obliczania entropii na podstawie wzorów jest przedmiotem dyskusji. Myślałem o czymś takim:
entropy(b) * l * (o + 1) // o will be either zero or one
Zmodyfikowany algorytm znalazłby wady i redukował siłę każdego hasła w oryginalnej tabeli, z wyjątkiem s^fU¬5ü;y34G<, który nie zawiera słów ani wzorców.