Nachdem ich verschiedene Ressourcen zur Kennwortstärke gelesen habe, versuche ich, einen Algorithmus zu erstellen, der eine grobe Schätzung der Entropie eines Kennworts liefert.
Ich versuche, einen möglichst umfassenden Algorithmus zu entwickeln. Zu diesem Zeitpunkt habe ich nur Pseudocode, aber der Algorithmus deckt Folgendes ab:
- Passwortlänge
- wiederholte Zeichen
- Muster (logisch)
- verschiedene Zeichenräume (LC, UC, Numeric, Special, Extended)
- Wörterbuchangriffe
Es deckt NICHT das Folgende ab und SOLLTE es GUT abdecken (wenn auch nicht perfekt):
- Bestellung (Passwörter können durch Ausgabe dieses Algorithmus streng geordnet werden)
- Muster (räumlich)
Kann jemand einen Einblick geben, wozu dieser Algorithmus schwach sein könnte? Kann sich jemand Situationen vorstellen, in denen die Eingabe eines Kennworts in den Algorithmus dessen Stärke überschätzen würde ? Unterschätzungen sind weniger ein Thema.
Der Algorithmus:
// 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)
Einige Eingaben und ihre gewünschten und tatsächlichen entropy_bits-Ausgaben:
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"
Der Algorithmus erkennt (korrekt), dass durch Erhöhen der Alphabetgröße (sogar um eine Ziffer) lange Passwörter erheblich gestärkt werden, wie der Unterschied in entropy_bits für das 6. und 7. Passwort zeigt, die beide aus 36 a bestehen, das 21. a jedoch aus dem zweiten aktiviert. Sie berücksichtigen jedoch nicht die Tatsache, dass es keine gute Idee ist, ein Passwort von 36 a zu haben. Es kann leicht mit einem schwachen Passwort-Cracker gebrochen werden (und jeder, der zuschaut, wie Sie es eingeben, wird es sehen), und der Algorithmus spiegelt dies nicht wider .
Es spiegelt jedoch die Tatsache wider, dass xkcd1 im Vergleich zu xkcd2 ein schwaches Passwort ist, obwohl es eine höhere Komplexitätsdichte aufweist (ist das überhaupt eine Sache?).
Wie kann ich diesen Algorithmus verbessern?
Anhang 1
Wörterbuchangriffe und musterbasierte Angriffe scheinen die große Sache zu sein, also werde ich mich mit diesen beschäftigen.
Ich könnte eine umfassende Suche im Passwort nach Wörtern aus einer Wortliste durchführen und Wörter durch Token ersetzen, die für die Wörter, die sie darstellen, eindeutig sind. Word-Token werden dann als Zeichen behandelt und haben ein eigenes Gewichtungssystem. Sie fügen dem Kennwort ihre eigenen Gewichte hinzu. Ich brauche ein paar neue Algorithmusparameter (ich nenne sie lw, Nw ~ = 2 ^ 11, fw ~ = .5 und rfw) und würde das Gewicht wie jedes andere im Passwort berücksichtigen Gewichte.
Diese Wortsuche könnte speziell modifiziert werden, um sowohl Klein- und Großbuchstaben als auch häufige Zeichenersetzungen wie die von E mit 3 zu berücksichtigen. Wenn ich solchen übereinstimmenden Wörtern kein zusätzliches Gewicht hinzufügen würde, würde der Algorithmus ihre Stärke ein wenig unterschätzen oder zwei pro Wort, was in Ordnung ist. Andernfalls wäre es eine allgemeine Regel, dem Wort für jede nicht perfekte Zeichenübereinstimmung ein Bonusbit zu geben.
Ich könnte dann einfache Musterprüfungen durchführen, beispielsweise die Suche nach Serien wiederholter Zeichen und abgeleitete Tests (die Differenz zwischen den einzelnen Zeichen ermitteln), um Muster wie "aaaaa" und "12345" zu identifizieren und jedes erkannte Muster durch ein Muster zu ersetzen Token, einzigartig für das Muster und die Länge. Die algorithmischen Parameter (insbesondere die Entropie pro Muster) könnten im laufenden Betrieb auf der Grundlage des Musters erzeugt werden.
An diesem Punkt würde ich die Länge des Passworts nehmen. Jedes Wort- und Mustertoken zählt als ein Zeichen. Jedes Token würde die symbolisch dargestellten Zeichen ersetzen.
Ich habe mir eine Art Musternotation ausgedacht, die aber die Musterlänge l, die Musterreihenfolge o und das Basiselement b enthält. Diese Information könnte verwendet werden, um ein beliebiges Gewicht für jedes Muster zu berechnen. Ich würde etwas besseres im eigentlichen Code machen.
Modifiziertes Beispiel:
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
Die genaue Semantik, wie Entropie aus Mustern berechnet wird, steht zur Diskussion. Ich dachte etwas wie:
entropy(b) * l * (o + 1) // o will be either zero or one
Der modifizierte Algorithmus würde Fehler in der ursprünglichen Tabelle finden und die Stärke jedes Kennworts verringern, mit Ausnahme von s^fU¬5ü;y34G<, das keine Wörter oder Muster enthält.
Antworten:
Anhang A auf Seite 46 von NIST SP 800-63 beschreibt die Arbeit von Claude Shannon , der die Kennwortentropie anhand einer Anzahl von Bits schätzt. In der Tat ist dies das Dokument, mit dem die XKCD-Karikatur die Entropiebits berechnet. Speziell:
Die Idee ist, dass ein Authentifizierungssystem bestimmte Entropiestufen als Schwellenwerte auswählen würde. Beispielsweise können 10 Bits schwach, 20 mittel und 30 stark sein (Zahlen, die als Beispiel willkürlich ausgewählt werden, keine Empfehlung). Leider werden solche Schwellenwerte im Dokument nicht empfohlen, wahrscheinlich weil die Rechenleistung, die für Brute Force oder das Erraten von Passwörtern zur Verfügung steht, mit der Zeit zunimmt:
Dies kann oder kann nicht das sein, wonach Sie suchen, ist aber kein schlechter Bezugspunkt, wenn nichts anderes.
[Bearbeiten: Folgendes hinzugefügt.]
Das oben beschriebene Shannon-Modell ist kein genaues Entropiemodell für vom Menschen generierte Passwörter. Dies wurde anhand der Papierprüfungsmetriken für Richtlinien zur Passworterstellung durch Angriffe auf große Mengen enthüllter Passwörter (von Matt Weir, Sudhir Aggarwal, Michael Collins und Henry Stern) demonstriert. Ich würde empfehlen, in "Abschnitt 5 Erstellen neuer Richtlinien zur Passworterstellung" nach genaueren Vorschlägen zu suchen.
quelle
Schauen Sie sich den Quellcode für KeePass unten auf dieser Seite an . Die
QualityEstimationKlasse implementiert einen ziemlich netten Algorithmus, der mit dem übereinstimmt, was Sie suchen. Meine Ergebnisse sehen so aus:quelle
Du fragst
Aber Sie haben ein Beispiel in der Frage. Xkcd2 hat entwurfsbedingt ~ 44 Bit Entropie, aber Ihre Schätzung liegt bei 160,5 Bit.
quelle
Sie haben einige in der Präambel angedeutet (Wörterbuchangriffe usw.). Im Wesentlichen gibt es eine Reihe gängiger Vorgehensweisen, die der Angreifer erraten kann und die den Suchraum erheblich verringern. Ich bin mir ziemlich sicher, dass Ihr Algorithmus Folgendes "überschätzen" wird:
Das Passwort ist ziemlich lang, aber trivial zu knacken, da das ursprüngliche Wort in einem Basiswörterbuch erscheint und die Änderungen als häufig genug angesehen werden, um Teil eines anständigen Wörterbuchangriffs zu sein. Typische Umrechnungen von Buchstaben -> Zahlen (z. B. 3v3rywh3r3) sollten ebenfalls als ziemlich schwach eingestuft werden, und Sie sollten dafür eine Strafe zahlen.
Zu einem viel geringeren Grad können andere Problemkennwörter solche sein, die offensichtliche Muster aufweisen, wie zum Beispiel:
Obwohl es wahrscheinlich weniger wahrscheinlich ist, dass diese Angriffe in tatsächlichen Wörterbuchangriffen ausgeführt werden, leiden sie unter ähnlichen Problemen wie in Ihrem Beispiel "aaaaa ...".
Ich bin mir nicht sicher, ob die meisten Wörterbuchangriffe derzeit auf Passwortphrasen abzielen, aber mit zunehmender Popularität werden sie zweifellos immer häufiger abzielen. Ich denke, das berühmte xkcd-Beispiel berücksichtigt dies, da nur 11 Bits für jedes "gemeinsame Wort" zugewiesen sind. Ihr Algorithmus überschätzt auch diese Arten von Passwörtern.
Zusammenfassend kann gesagt werden, dass der Algorithmus die Schätzung ziemlich gut durchführt, jedoch die Struktur des Passworts und die üblichen, bekannten Muster berücksichtigen sollte.
quelle