Eindeutigkeit von Schlüssel

Fragen zu mathematischen Problemen
Antworten
Benutzeravatar
fat-lobyte
Beiträge: 1398
Registriert: Sa Jul 05, 2008 12:23 pm
Wohnort: ::1
Kontaktdaten:

Eindeutigkeit von Schlüssel

Beitrag von fat-lobyte » Fr Aug 20, 2010 6:34 pm

Hallo, ich hacke mal wieder an meinem Chatprogramm.
Nun bin ich bei einer Frage angekommen, die mich interessiert.

Die Aufgabe ist folgendes: ich will eine Benutzeridentifikation einführen, die N Bytes lang ist.
Das heißt, es gibt (2^8)^N, also 256^N Möglichkeiten dafür.

Nehmen wir N mal mit N = 8 an. Das heißt es gibt 256^8, also 1.8447*10^19 Möglichkeiten. Ne 1, ne 8, und 18 Nullen, mit ein paar zerquetschten. Klingt erstmal mal viel...
Jetzt wüsste ich aber gerne "wie viel" das ist. Um mir das begreiflich zu machen, würde ich gerne ein paar Dinge wissen:

Nehmen wir an, ich habe eine bestimmte Kombination ausgewählt.
1) Wie lange braucht ein Mensch (M=1), der jede Minute (f=1/min) eine neue Kombination erzeugt. Wie lange (T=?) braucht der Mensch, bis er mit einer Wahrscheinlichkeit von 66 % (P=0.66) meine Kombination errät?
2) Wie lange dauert es bei mehr Menschen (M=100, M=10 000, M=10^9)? Wie lange wenn sie schneller sind? (F=1/s, F= 1000/s), wie lange für eine andere Wahrscheinlichkeit (P=0.95, P=0.99)?
3) Was passiert wenn ich nicht alle Möglichkeiten eines Bytes nutzen will, sondern z.B. nur die Druckbaren Zeichen (94), oder noch weniger (z.B. "ASCII-Armor" Format)?
4) Wie sieht das ganze aus, wenn ich weniger Zeichen verwende, wenn N kleiner ist, oder N größer?


Toll wäre natürlich eine Formel, mit erklärung. Ich wär aber schon mit ein paar Hinweisen, oder mathematischen Gebieten zufrieden, oder einfach mit guten Ideen.

Ich hoffe da kann mir wer weiterhelfen...
Haters gonna hate, potatoes gonna potate.

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8485
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Eindeutigkeit von Schlüssel

Beitrag von Xin » Sa Aug 21, 2010 12:44 pm

Vielleicht sehe ich das Problem nicht, aber ich sehe nur ein paar Multiplikationen und Divisionen!?
Ich gehe nicht davon aus, dass diese Dein Problem darstellen?
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

AnGaiNoR
Beiträge: 212
Registriert: Sa Jul 19, 2008 7:07 pm
Wohnort: Dresden

Re: Eindeutigkeit von Schlüssel

Beitrag von AnGaiNoR » Sa Aug 21, 2010 1:13 pm

Ich nehme mal an, dass man keine Kombination zweimal benutzt, wenn man deine knacken möchte.
Desweiteren lege ich folgendes fest:
n: Gesamtanzahl der Kombinationen.
h(x): Wahrscheinlichkeit, beim x-ten Versuch richtig zu tippen.
H(x): Wahrscheinlichkeit, bis zum x-ten Versuch richtig zu tippen.
P(X): Wahrscheinlichkeit des Ereignisses X.
A /\ B: Konjunktion (UND-Ereignis).
A \/ B: Disjunktion (ODER-Ereignis).

Die Wahrscheinlichkeit, die Kombination beim ersten Mal zu erraten beträgt h(1) = 1/n.
Um erst beim zweiten Versuch richtig zu liegen, muss man natürlich beim ersten danebenliegen. Außerdem wurde beim ersten Versuch eine Kombination "verbraucht" und wird somit nicht mehr verwendet.
h(2) = [ 1 - p(1) ] * [ 1/(n-1) ]
= [ 1 - (1/n) ] * [ 1/(n-1) ]
= [ (n-1)/n ] * [ 1/(n-1) ]
= 1/n
Das könnte man jetzt fortführen, aber man sieht, dass h(x) = 1/n gilt.

Ereignis E1: Kombination wird beim ersten Versuch erraten.
Ereignis E2: Kombination wird beim zweiten Versuch erraten.
Ereignis E1 \/ E2: Kombination wird bis zum zweiten Versuch erraten.
Ereignis E1 /\ E2: Kombination wird beim ersten und zweiten Versuch erraten... unmöglich.
P(E1 \/ E2) = P(E1) + P(E2) - P(E1 /\ E2)
P(E1 /\ E2) = 0
P(E1 \/ E2) = P(E1) + P(E2)
P(E1 \/ E2) = 2/n = H(2)

Verallgemeinert:
Ereignis Ek: Kombination wird beim k-ten Versuch erraten.
Ereignis E1 \/ E2 \/ ... \/ Ek: Kombination wird bis zum k-ten Versuch erraten.
P(E1 \/ E2 \/ ... \/ Ek) = P(E1) + P(E2) + ... + P(Ek) - P(E1 /\ E2 /\ ... /\ Ek)
P(E1 /\ E2 /\ ... /\ Ek) = 0
P(E1 \/ E2 \/ ... \/ Ek) = P(E1) + P(E2) + ... + P(Ek)
P(E1 \/ E2 \/ ... \/ Ek) = k/n = H(k)

Mit einer Wahrscheinlichkeit von H(k) = k/n hat man also die Kombination bis zum k-ten Versuch erraten.
Das klingt - mathematisch gesehen - erstaunlich einfach, ist es auch.
Physics is like sex: sure, it may give some practical result, but that's not why we do it.
(Richard P. Feynman)

Benutzeravatar
cloidnerux
Moderator
Beiträge: 3081
Registriert: Fr Sep 26, 2008 4:37 pm
Wohnort: Ram (Gibts wirklich)

Re: Eindeutigkeit von Schlüssel

Beitrag von cloidnerux » Sa Aug 21, 2010 1:44 pm

Um das ganze mal in einen Reelen kontext zu bringen mal folgende Überlegungen:
Brute Force:
Wir haben mit ~5z/s getippt, jemand geübtes schafft vlt auch 10z/s.
Das bedeutet das man nur für die Eingabe eines Schlüssels n/5s benötigt. Dann noch menschliche Reaktionszeit und Verzögerung dazu macht nochmal ca 2s.
Dann gilt erstmal diese Formel: t(max) = N(Kombinationen) * (n(länge)/5s + 2s)
Das macht für 2^64 t(max)=2^64 * (8/5s + 2s) = 6.640*10^19s = 7.68614 * 10^14 Tage bei 24h einsatz.
Wie AnHaiNor bewiesen hat, ist jede Kombiantion mit 1/n Wahrscheinlichkeit richtig, das heißt es käme hier darauf an, wie der Schlüssel anfängt oder wie man Passwörter auswählt.
Auch wenn du ganz Berlin daran setzten würdest 24h am Tag kombiantionan auszuprobieren kann das immer noch Millionen Jahre dauern.
Was aber viel eher der Fall sein kann, ist das man durch Wörterbuchattacken oder eine Ahnung über das PW die Erfolgschancen erhöhen kann, aber allgemein ist Passwort cracken für Menschen schon lange vorbei.
Jetzt kommt der interessantere Fall: Ein Computer
Rein Thereotisch kann man das Pw innerhalb von 100 Takten testen, ja nach dem wie es Gestaltet ist(z.B Xor-Verknüpfung), da aber auf jeder neueren Kiste das OS noch so viel im Hintergrund arbeitet, gehen wir mal von 10.000 Taktzyklen aus, was aber immernoch übertreiben ist. Würde aber bedeuten, dass eine CPU mit 3Ghz ca. 300.000 PW pro Sekunde verarbeiten kann. Das macht dann für alle PWs 1.84467*10^15 s = 2.135*10^10 Tage...
Auf einem Modernen Core i7 mit 4 + 4 kernen wäre dass dann nur noch ein 8 der Zeit: 2668799799Tage, hat ja auch jeder...
Wenn man jetzt noch die Grafikarte als GpGPU nutzt und man davon ausgehen kann das man dort ca 1000 Takte braucht um ein PW zu testen wären das auf einer ATI Readon 5970 immer noch 3975591395 Tage rechenzeit, um alle PWs durch zugehen, wenn man die Zeit hat....
Redundanz macht wiederholen unnötig.
quod erat expectandum

Benutzeravatar
fat-lobyte
Beiträge: 1398
Registriert: Sa Jul 05, 2008 12:23 pm
Wohnort: ::1
Kontaktdaten:

Re: Eindeutigkeit von Schlüssel

Beitrag von fat-lobyte » Di Aug 24, 2010 3:10 pm

@AnGaiNoR: Irgendwie kommt mir die Sache etwas spanisch vor. Du sagst:
AnGaiNoR hat geschrieben:Um erst beim zweiten Versuch richtig zu liegen, muss man natürlich beim ersten danebenliegen.
Muss man das? Ich meine ja, es wäre nicht sinnvoll. Aber die Bedingung dazuzunehmen verschlechtert die Warhscheinlichkeit. Nachdem ich von einem "worst case" ausgehe, soll die beste Wahrscheinlichkeit gewährt werden.
AnGaiNoR hat geschrieben:...
Das könnte man jetzt fortführen, aber man sieht, dass h(x) = 1/n gilt.
Tut mir leid, vielleicht bin ich zu blöd aber ich seh das Grad nicht. Ich will jetzt keine vollständige Induktion oder so, aber das 3. und 4. Glied wären schonmal nicht schlecht.
Nach meiner Rechnung gibts bei h(3) ein Problem:
Beim 3. mal probieren hat man schon zwei Schlüsseln verbraucht, also die Wahrscheinlichkeit den Schlüssel zu finden ist 1/(n-2) . Wenn, wie du sagst (was mir eben ein bisschen seltsam vorkommt) man bei den vorherigen versuchen falsch liegen muss, so kommt man auf:
h(3) = [ 1/(n-2) ] * [ 1 - h(1) ] * [ 1 - h(2) ]
Hab ich das richtig verstanden?
Wenn man das allerdings ausrechnet, kommt man allerdings auf:
h(3) = [ 1/(n-2) ] * [ 1 - (1/n) ]^2 = ... = 1/n + 1/(n^2*(n-2)) != 1/n
Hab ich mich da verrechnet?
AnGaiNoR hat geschrieben:dass h(x) = 1/n gilt.
Das heißt nun, in Worte gefasst, dass ich bei jedem Versuch die gleiche Wahrscheinlichkeit habe, den Schlüssel zu erraten? Und das obwohl es jedes mal einen Schlüssel weniger gibt?
Irgendwie seltsam...
Vielleicht steh ich da total auf der Leitung.
Haters gonna hate, potatoes gonna potate.

AnGaiNoR
Beiträge: 212
Registriert: Sa Jul 19, 2008 7:07 pm
Wohnort: Dresden

Re: Eindeutigkeit von Schlüssel

Beitrag von AnGaiNoR » Mi Aug 25, 2010 6:57 pm

Wenn man schon beim ersten Versuch richtig liegt, dann muss man ja gar nicht erst einen zweiten Versuch wagen. Deshalb gehe ich davon aus, dass man einen zweiten Versuch nur tätigt, wenn man beim ersten falsch lag.
Da ich außerdem davon ausgehe, dass man immer andere Schlüssel benutzt, kann man bei einem richtigen ersten Versuch ja sowieso keine Treffer mehr landen.
fat-lobyte hat geschrieben: h(3) = [ 1/(n-2) ] * [ 1 - h(1) ] * [ 1 - h(2) ]
Hab ich das richtig verstanden?
Du hast es demzufolge falsch verstanden, denn um beim dritten richtig zu liegen, muss man ja eigentlich nur beim zweiten falsch raten. Den zweiten kann man meiner Logik zufolge aber nur dann verhauen, wenn man den ersten auch schon verrissen hat.

Ereignis A: Erster Versuch in den Sand gesetzt.
Ereignis B: Zweiter Versuch in den Sand gesetzt.
Ereignis C: Erster und zweiter Versuch in den Sand gesetzt.
h(3) = [ 1/(n-2) ] * P(C)
C = A /\ B
P(C) = P(A /\ B) = P(A) + P(B) - P(A \/ B)

Da aber das Misslingen der Versuche nichts miteinander zu tun hat, muss gelten:
P(A \/ B) = 0
P(C) = P(A) + P(B)
P(C) = 2/n

h(3) = [ 1/(n-2) ] * [ 1 - (2/n) ]
h(3) = [ 1/(n-2) ] * [ (n-2)/n ]
h(3) = 1/n

Stell es dir einfach so vor: Du hast alle Schlüssel vor dir liegen und willst sie bloß in die Probierreihenfolge bringen.
Physics is like sex: sure, it may give some practical result, but that's not why we do it.
(Richard P. Feynman)

Benutzeravatar
Kerli
Beiträge: 1456
Registriert: So Jul 06, 2008 10:17 am
Wohnort: Österreich
Kontaktdaten:

Re: Eindeutigkeit von Schlüssel

Beitrag von Kerli » Fr Sep 10, 2010 6:50 pm

Im Prinzip braucht man gar nicht betrachten wie hoch die Wahrscheinlichkeit in jeder Runde des Probierens ist das Passwort zu erraten, sondern nur ausrechnen wie viele Passwörter in einer gewissen Zeit durchprobieren kann. Wenn man beispielsweise in einer Stunde 60% aller möglichen Kombinationen durchgehen kann, dann hat man nach einer Stunde auch mit einer 60%-igen Wahrscheinlichkeit das Passwort erraten. Natürlich nur unter Laplace'scher Annahme, also das das Passwort völlig zufällig erstellt wird und derjenige der es erraten muss keine Ahnung über die Beschaffung des Passworts hat.
fat-lobyte hat geschrieben:3) Was passiert wenn ich nicht alle Möglichkeiten eines Bytes nutzen will, sondern z.B. nur die Druckbaren Zeichen (94), oder noch weniger (z.B. "ASCII-Armor" Format)?
Da hängt es davon ob der Angreifer das weiß oder nicht. Wenn er es weiß dann werden es insgesamt weniger Kombination und die Wahrscheinlichkeit des Erratens größer, ansonsten ändert sich nichts.

Schau dir dazu auch einmal diese Seite an...
"Make it idiot-proof and someone will invent an even better idiot." (programmers wisdom)

OpenGL Tutorials und vieles mehr rund ums Programmieren: http://www.tomprogs.at

Antworten