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.

Dodatek A na str. 46 NIST SP 800-63 mówi o pracy Claude'a Shannona , który szacuje entropię hasła za pomocą wielu bitów. Rzeczywiście jest to dokument używany przez kreskówkę XKCD do obliczania bitów entropii. Konkretnie:

• entropia pierwszego znaku przyjmuje się za 4 bity;
• entropia kolejnych 7 znaków to 2 bity na znak; jest to mniej więcej zgodne z szacunkami Shannona, że ​​„gdy uwzględniane są efekty statystyczne rozciągające się na nie więcej niż 8 liter, entropia ma około 2,3 bitu na znak;”
• dla 9 do 20 znaku entropia przyjmuje się jako 1,5 bitu na znak;
• dla znaków 21 i powyżej przyjmuje się, że entropia wynosi 1 bit na znak;
• „Bonus” w postaci 6 bitów entropii jest przypisany do reguły kompozycji, która wymaga zarówno wielkich, jak i niealfabetycznych znaków. Wymusza to użycie tych znaków, ale w wielu przypadkach znaki te pojawią się tylko na początku lub na końcu hasła, i nieco zmniejszy całkowitą przestrzeń wyszukiwania, więc korzyść jest prawdopodobnie skromna i prawie niezależna od długości hasło;
• Dodano premię w wysokości do 6 bitów entropii w celu szczegółowego sprawdzenia słownika. Jeśli osoba atakująca zna słownik, może uniknąć testowania tych haseł, a w każdym razie będzie w stanie odgadnąć większą część słownika, który jednak będzie najprawdopodobniej wybranym hasłem w przypadku braku reguły słownikowej. Zakłada się, że większość korzyści związanych z entropią zgadywania dla testu słownikowego przypada na stosunkowo krótkie hasła, ponieważ każde długie hasło, które można zapamiętać, musi koniecznie być „hasłem” złożonym ze słów słownikowych, więc premia spada do zera przy 20 postacie.

Chodzi o to, że system uwierzytelniania wybiera pewne poziomy entropii jako progi. Na przykład 10 bitów może być słabych, 20 średnich i 30 silnych (liczby wybrane arbitralnie jako przykład, a nie zalecenie). Niestety, dokument nie zaleca takich progów, prawdopodobnie dlatego, że moc obliczeniowa dostępna dla brutalnej siły lub odgadywania haseł wzrasta z czasem:

Jako alternatywa dla narzucania dowolnego arbitralnego zestawu reguł, system uwierzytelniania może oceniać hasła użytkowników, stosując powyższe reguły i akceptować te, które spełniają minimalny standard entropii. Załóżmy na przykład, że wymagane są hasła z co najmniej 24-bitową entropią. Możemy obliczyć oszacowanie entropii „IamtheCapitanofthePina4”, obserwując, że łańcuch ma 23 znaki i spełniałby regułę składu wymagającą wielkich i nie alfabetycznych znaków.

To może być lub nie być to, czego szukasz, ale nie jest to zły punkt odniesienia, jeśli nic więcej.

[Edycja: Dodano następujące elementy.]

W artykule Testowanie wskaźników polityki tworzenia haseł przez atakowanie dużych zestawów ujawnionych haseł (Matt Weir, Sudhir Aggarwal, Michael Collins i Henry Stern) wykazano, że opisany powyżej model Shannon nie jest dokładnym modelem entropii dla haseł generowanych przez ludzi. Poleciłbym zajrzeć do „Sekcji 5 Generowanie nowych zasad tworzenia haseł”, aby uzyskać dokładniejsze propozycje.

Sprawdź kod źródłowy KeePass na dole tej strony . Że QualityEstimationklasa implementuje raczej miły algorytm, który wydaje się być w zgodzie z tym, co szukasz mieć na swoim miejscu. Moje wyniki wyglądają tak:

aaa                              8
aaaaaaaaa                        9
abcdefghi                       18
H0ley$Mol3y_                    73
s^fU¬5ü;y34G<                   99
[a^36]*                         10
[a^20]A[a^15]*                  18
Tr0ub4dor&3                     66
correct horse battery staple    98

Ty pytasz

W szczególności, czy ktoś może pomyśleć o sytuacjach, w których podanie hasła do algorytmu ZAWRACA jego siłę?

Ale masz przykład w pytaniu. Z założenia xkcd2 ma ~ 44 bity entropii, ale twój szacunek to 160,5 bitu.

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 jego siłę?

Wskazałeś na niektóre z preambuły (ataki słownikowe itp.). Zasadniczo atakujący może odgadnąć wiele powszechnych praktyk, które znacznie zmniejszają przestrzeń poszukiwań. Jestem prawie pewien, że Twój algorytm „przecenia” następujące elementy:

• wszędzie
• Wszędzie
• Wszędzie 1

Hasło jest dość długie, ale można je łatwo złamać, ponieważ oryginalne słowo pojawia się w podstawowym słowniku, a modyfikacje są uważane za wystarczająco powszechne, aby stanowić część każdego przyzwoitego ataku słownikowego. Typowe konwersje liter -> liczb (np. 3v3rywh3r3) również należy uznać za dość słabe i należy za nie karać.

W znacznie mniejszym stopniu inne hasła problemów mogą mieć takie, które mają oczywiste wzorce, takie jak:

• abcdefghijklmnop
• abcde12345

Chociaż prawdopodobnie są one rzadziej atakowane w rzeczywistych atakach słownikowych, mają podobne problemy, jak przykład „aaaaa ...”.

Nie jestem pewien, czy frazy hasła są obecnie celem większości ataków słownikowych, ale bez wątpienia, gdy zdobędą popularność, będą atakowane coraz częściej. Myślę, że słynny przykład xkcd bierze to pod uwagę, ponieważ dla każdego „wspólnego słowa” przypisanych jest tylko 11 bitów. Twój algorytm przecenia również tego rodzaju hasła.

Podsumowując, algorytm wykonuje dość dobrą ocenę, ale tak naprawdę powinien brać pod uwagę strukturę hasła i typowe, znane wzorce.