John the Ripper proportional?

[Fears]

Hallo zusammen

Ich habe eine Frage. Mein Chef hat folgende Aussage gemacht:

John the Ripper hat für 100 Passwörter, die er versuchen muss zu knacken die Zeit t. Wenn John the Ripper nun 200 Passwörter muss knacken hat er dafür NICHT 2*t sondern weniger. Ist das so? Wenn ja warum?

Könnt ihr mir helfen? Ich suche nun seit Stunden und finde absolut nichts darüber.

Freundliche Grüsse

Fears313

 

[Fidikus]

Wenn die komplexität der Passworter gleich bleibt, dann verdoppelt sich die zu erwartende Zeit. Wenn sich aber die Komplexität der Passwörter ändert steig bei Bruteforce der Aufwand exponentiell

 

[deeptracks]

Worum geht es hier genau? Geht es um 200 Kombinationen von Benutzernamen und Passwort? Muss ein Passwort erraten werden oder alle? Sind alle Passwörter einzigartig?

 

[kuddlmuddl]

Die Frage ist ja schrecklich formuliert :-X

Sind alle Passwörter einzigartig?

Das wird genau der Punkt sein: Kein System wird einen mit der Meldung "ihr Passwort wird bereits verwendet, bitte wählen Sie ein anderes" konfrontieren
Zum einen weil natürlich dann derjenige wüsste, was einer der existierenden Benutzer für ein Passwort hat. Er müsste also nur noch die Benutzer durchprobieren.
Andererseits, weil kein System dies prüfen sollte, denn kein vernünftiges Sicherheits-System speichert direkt (gehashte) Passwörter.

Insbesonderen wenn http://de.wikipedia.org/wiki/Salt_(Kryptologie) zum Einsatz kommt würd ich die Aussage in Frage stellen. Dann ist die Wahrscheinlichkeit nämlich verschwindend gering, dass 200 schneller als 2*t geht. (nur bei gleichen pw UND gleichem Salt).

 

[GuaRdiaN]

Mh ich denke der Kontext der Aussage ist nicht unwichtig, wenn 100 Passwörter in der Zeit t getestet werden sollen, steht (lineare Komplexität) für jedes PW eine Zeit von 1/100 zur Verfügung. Sollten in der selben Zeit 200 Kombinationen getestet werden müssen, so würde für jedes Pwd nur 1/200 zur Verfügung, somit ist die Zeit halb so lange.

Generell ist das Problem der Kryptographie nicht linear. Da die Komplexität der Pwds nicht gleich sind. Daher ist so eine Aussage nicht wirklich zu treffen. Man kann Annahmen machen:

Wenn das Programm P es nicht schafft das Pwd innerhalb von 100 Sekunden zu knacken, nehmen wir die Passwortstärke für uns als "stark" an. Aber die echte Stärke eine Passwortes ist i.d.R. immer die Zeit, die für Bruteforce gebraucht wird. (Daher sollte man auch den zur Verfügung stehenden Character-Raum ausnutzen.)

 

[Backslash]

Wenn das Programm mit Brute-Force arbeitet und nicht absolut bescheuert programmiert ist (was ich bei John the Ripper nicht annehme), dann kann es natürlich während es Kombinationen ausprobiert vor Erfolg bei einem bestimmten Passwort auf andere stoßen. Der Schlechteste Fall (alle Möglichkeiten müssen ausprobiert werden) ist also (fast) unabhängig von der Zahl der Passwörter die geknackt werden sollen.

Somit ist die Zeit für mehr Passwörter im selben Anlauf (und mit gleicher Komplexität und Hash-Algorithmus) wesentlich geringer als wenn man versucht sie separat zu knacken und für jedes Passwort von vorne begonnen werden muss.

 

[mcclean]

einfach gesagt gilt generell:
Bsp: Es gibt 1000 kombinationsmöglichkeiten
Beim ersten versuch hast du die Chance 1:1000 das du es richtig errätst.
Beim zweiten hast du (im unwahrscheinlichen Fall das du das erste gleich herausgefunden hast) die Chance 1:999
Beim dritten ist die Chance noch höchstens 1:998 usw.

Je mehr Kombinationen benützt werden, desto grösser die Chance, dass du per Zufall eine knackst.


Dies geht bei Sachen wie z.B. Serials, Gutscheincodes usw. Bei Kombinationen von Benutzername und Passwort(können mehrere das selbe haben) funktioniert das Beispiel nicht.

 

[riDDi]

@mcclean: Fast richtig. Nach dieser Methode ist es zwar zunächst doppelt so wahrscheinlich, dass ich irgendein Passwort finde, aber es muss die Übereinstimmung auch für doppelte so viele Passwörter geprüft werden.
Ich vermute stark, dass nur jeweils einmal der neue Hashwert berechnet werden muss und der Vergleich mit dem tatsächlichen Hash dann kaum keine Zeit in Anspruch nimmt.
Daher wird im Mittel das Finden der ersten 100 Passwörter schneller als im Fall mit nur 100 Passwörtern vonstatten gehen und die restlichen 100 sind wegen des kleineren verbleibenden Passwortraums auch schneller gefunden.

 

[Fears]

Erstmals, vielen vielen Dank, dass ihr so schnell und so ausgiebig diskutiert. Um etwas klarheit in die Sache zu bringen.

Alle 200 Accounts haben Passwörter. Diese sind je nach dem einfacher und komplexer. Die Behauptung ist nun, wenn 100 Accounts mit John the Ripper geprüft werden. z.B. mit Brute Force, Password-list wäre auch möglich, braucht John eine gewisse Zeit t. In dieser Zeit hat er z.B. 20 geknackt und 80 nicht. Die Behauptung ist nun wenn 200 Accounts(die 100 von vorher sind darin nicht erhalten) getestet werden, ist die Zeit t nicht doppelt so gross.

Mathematisch:
100 == t
200 != 2t

Versteht ihr was ich meine? Die Frage ist nun warum ist das so?

 

[Backslash]

Aus dem von mir oben erläuterten Grund.

Wenn du per Brute-Force vorgehst musst du im schlechtesten Fall alle möglichen Passwörter ausprobieren um eines zu knacken. Ob du währenddessen noch weitere Passwörter probierst spielt (fast) keine Rolle, da die rechenintensive Operation das Hashen und nicht der Vergleich mehrerer Passwörter mit einem errechneten Hash ist.

Und deine mathematische Schreibweise macht keinen Sinn, wenn dann könntest du z.B. eine Funktion f definieren, die die Zahl der zu knackenden Passwörter n auf die dafür benötigte Zeit f(n) abbildet und dann sagen, dass

f(n) · 2 ≠ f(2n)​

bzw. sogar

f(n · x) ≤ f(n) · x​