Schlüssellänge vs. Brute-Force

[LadyDie]

Ich habe mal eine bescheidene Frage zur Rolle der Schlüssellänge bei Brute-Force-Attacken.

Sehr häufig liest man, daß die Zeit zur Durchführung einer Brute-Force-Attacke exponentiell ansteigt mit der Schlüssellänge. Durch geringfügig höhere Schlüssellängen ließe sich also die erwartete Rechenzeit in astronomische Größenordnungen bewegen.
Das klingt soweit ja plausibel: Ein um 1bit längerer Schlüssel verdoppelt den Suchraum, der nun auch doppelt so lange abgesucht werden muss.
Wenn sagen wir einfach mal (ich habe keine realistischen Zahlen) ein 64bit Schlüssel im Mittel 1 Jahr zur Entschlüsselung hält, dann hält ein 74bit Schlüssel ein Jahrtausend.

Nun wächst aber doch mit der Zeit ebenfalls die Rechengeschwindigkeit (verdoppelt sich etwa alle 2 Jahre). D.h. ein Rechner in 20 Jahren ist tausendmal leistungsfähiger als ein Rechner in diesem Jahr. Dann sollte also doch der 74bit Schlüssel nicht erst einem Jahrtausend, sondern schon in 20 Jahren geknackt sein.

...Ich finde das ein ziemlich großen Unterschied...

[c3rl]

LadyDie schrieb:
--------------------------------------------------------------------------------
> Nun wächst aber doch mit der Zeit ebenfalls die Rechengeschwindigkeit
> (verdoppelt sich etwa alle 2 Jahre).

Ja, aber nein. Mittlerweile wächst die Geschwindigkeit kaum noch. Die derzeitigen Topmodelle an x86/AMD64-CPUs sind gerade mal noch 10-20% schneller als die vor 2 Jahren.

Mit dem Rest hast du natürlich Recht. Darum ist es auch so wichtig, dass die Leute endlich verstehen, dass Passwortlänge wichtiger als zufälligkeit ist. Abstruse Sätze eignen sich hervoragen als Passwörter, und bringen sehr schnell 30-40 Zeichen, und somit weit mehr als 128 Bit, welche mit herkömmlicher Technik und selbst einer Verzehnfachung der Rechenleistung pro Jahr viele Millionen Jahre zur Berechnung benötigen würden.

[shoggothe]

c3rl schrieb:
--------------------------------------------------------------------------------
> LadyDie schrieb:
> ---------------------------------------------------------------------------
> -----
> > Nun wächst aber doch mit der Zeit ebenfalls die Rechengeschwindigkeit
> > (verdoppelt sich etwa alle 2 Jahre).
>
> Ja, aber nein. Mittlerweile wächst die Geschwindigkeit kaum noch. Die
> derzeitigen Topmodelle an x86/AMD64-CPUs sind gerade mal noch 10-20%
> schneller als die vor 2 Jahren.

Das Gegenteil ist der Fall. Der OP hat das Problem vollkommen richtig erkannt! Die Rechengeschwindigkeit wächst seit ein paar Jahren schneller als Moore's Law, was zur Zeit der Entstehung der Verschlüsselungsalgorithmen nicht abzusehen war. Und zwar durch die Grafikkarten. Hier ein aufschlussreicher Artikel zum Thema, es geht ums Knacken von Passwort-Hashes:

http://www.codinghorror.com/blog/2012/04/speed-hashing.html

Leistungsvergleich von GPU vs CPU im Artikel:

Radeon 7970 8213.6 M c/s
6-core AMD CPU 52.9 M c/s
(c/s sind Passwort-Checks/sek)

Sinngemäß aus dem Artikel:
Heutige Grafikkarten testen mit brute-force alle möglichen Kombinationen für 6-stellige Passwörter mit Ziffern, ohne Sonderzeichen in 3 Sekunden. Mit Sonderzeichen dauert es 47 Sekunden.

Das ist schon böse, nicht? Jedes Passwort mit weniger als 10 Zeichen ist heutzutage unsicher wie c3rl schon angemerkt hat.

Die Daten oben und im Artikel beziehen sich auf MD5 (gilt als geknackt). Das spielt aber kaum eine Rolle, da der Angriff brute-force erfolgt. Andere, nicht geknackte Hashes sind zwar schon rechenaufwändiger, aber nicht um Größenordnungen.



2 mal bearbeitet, zuletzt am 25.05.12 00:21 durch shoggothe.

[blackbirdone]

"Die Rechengeschwindigkeit wächst seit ein paar Jahren schneller als Moore's Law"

Na wenn man ihnen da mal nicht nen Kukuk ins Nest gelegt hat, sie wächst genauso wie es die gesetzmäßigkeit aussagt , eine Verdoppelung der Komponenten alle 2 Jahre. und ja das tut sie auch weiterhin.

Mit Rechnengeschwindigkeit hat sein Gesetzt garnichts zu tun.

"Das ist schon böse, nicht?"
Hängen sie mal 2 zeichen dran und man rechnet sich dumm und dämlich, und wer paranoit ist nimmt einfach nen 16 stelliges.

[der-eichi.de]

was interessierten "kurze passwörter" ?
pgp generiert als privaten key eine kryptographisch sichere Zufallszahl, das hat nichts mit Passwörtern zu tun?
verdoppelt man halt alle 2 Jahre seine Schlüssellänge?
ca 4000 bit. viel Spaß bei bruteforce

[Anonymer Nutzer]

Wichtig ist, dass sobald sich die Geschwindigkeit der Entschlüsselung erhöht, auch die für die Verschlüsselung zur Verfügung stehende Rechenleistung steigt.

Dieses Katz und Maus Spiel verliert sicher nicht der Verschlüsselnde.

[syntax error]

Kann man nicht eigentlich einfach seine Sachen mehrfach und mit mehreren Verfahren verschlüsseln? ^^ Einmal PGP drüberjagen und das Ergebnis dann mit irgendnem anderen Verfahren verschlüsseln. Oder bringt das nix?

[druckertinte]

Naja, wenn du's zwei mal mit unterschiedlichen Keys verschlüsselst, musst du es wohl oder übel zwei mal knacken :D