AES Schlüsselsuche und Wahrscheinlichkeitsrechnung

Aufrufe: 165     Aktiv: 22.04.2022 um 12:01

0



Hallo Leute,
ich brauche mal wieder einen Tipp!
Ich verstehe die Lösung zur Aufgabe im Foto nicht.

Wieso brauche ich bei AES mit 192 Bit Schlüssel und 128 Bit Blockbreite \(2^{63}\) Klartext-Chiffrat-Paare, um mit einer Wahrscheinlichkeit von 50% den richtigen Schlüssel gefunden zu haben?

Ich verstehe die Logik nicht; die Lösung kommt mir unrealistisch groß vor. Im Buch stellen die Autoren auf Seite 158 folgende Formel vor: \(2^{k-tn}\) mit k = Schlüssellänge, t = Anzahl der Klartext-Chiffrat-Paare und n = Blockbreite der Blockverschlüsselung. Mit dieser Formel berechnet man die Wahrscheinlichkeit, den gleichen falschen Schlüssel mehrfach gefunden zu haben.
Unter den gegebenen Umständen (192-Bit-Schlüssel und 128 Bit Blockbreite) käme ich ja bereits bei 2 Klartext-Chriffrat-Paaren auf eine Wahrscheinlichkeit von \(2^{192-2*128}\) = \(2^{-64}\), also eine extrem geringe Wahrscheinlichkeit, dass ich zweimal den gleichen falschen Schlüssel gefunden habe. Kann es dann ernsthaft sein, dass ich für eine Wahrscheinlichkeit von 50% den richtigen Schlüssel gefunden zu haben, \(2^{63}\) Klartext-Chiffrat-Paare benötige? Das scheint mir einfach nicht zusammen zu passen.

Wer kann mir einen Tipp geben, wie ich das zusammen bringe, bzw. wie die Autoren eigentlich auf ihre Lösung kommen?

EDIT vom 20.04.2022 um 21:52:

Update1:
Da bisher leider niemand mit Tipps weitergeholfen hat, ergänze ich hier mal einige Ideen von mir:

Für das erste Klartext-Chiffrat-Paar ermitteln wir Schlüssel. Davon ist nur einer richtig, alle anderen nicht. An dieser Stelle wäre die Wahrscheinlichkeit, den richtigen Schlüssel unter den ermittelten Schlüsseln zu finden, also \(\frac{1}{2^{64}}\). Die Autoren möchten aber eine Wahrscheinlichkeit von 50 % (also \(\frac{1}{2}\)) und behaupten, dass man dafür weitere Klartext-Chiffrat-Paare benötige. Bis hierhin habe ich das doch wohl richtig verstanden?
Leider liefern die Autoren keine Begründung dafür, warum man weitere Klartext-Chiffrat-Paare benötigen soll, um auf die Wahrscheinlichkeit von 50 % für den richtigen Schlüssel zu kommen. Eine Wahrscheinlichkeit von 50 % bedeutet ja, dass neben dem richtigen Schlüssel nur noch ein falscher Schlüssel übrig geblieben ist. Alle anderen falschen Schlüssel konnten aussortiert werden.
Beim ersten Klartext-Chiffrat-Paar starteten wir mit
falschen Schlüsseln, und nach weiteren Klartext-Chiffrat-Paaren soll dann den Autoren zufolge nur noch ein falscher Schlüssel übrig geblieben sein. Wir haben also Klartext-Chiffrat-Paare benötigt, um falsche Schlüssel auszusortieren. Wir hätten dann also im Durchschnitt nur \(\frac{2^{64}-2}{2^{63}} \approx 2\)  falsche Schlüssel pro Klartext-Chifftat-Paar aussortiert. Liege ich bis hierhin richtig? (Das Ergebnis scheint mir nicht sehr plausibel zu sein.)

EDIT vom 20.04.2022 um 22:04:

Für das erste Klartext-Chiffrat-Paar ermitteln wir \(2^{64}\) Schlüssel. Davon ist nur einer richtig, alle anderen nicht. An dieser Stelle wäre die Wahrscheinlichkeit, den richtigen Schlüssel unter den ermittelten Schlüsseln zu finden, also \(\frac{1}{2^{64}}\). Die Autoren möchten aber eine Wahrscheinlichkeit von 50 % (also \(\frac{1}{2}\)) und behaupten, dass man dafür weitere \(2^{63}\) Klartext-Chiffrat-Paare benötige. Bis hierhin habe ich das doch wohl richtig verstanden?
Leider liefern die Autoren keine Begründung dafür, warum man weitere \(2^{63}\) Klartext-Chiffrat-Paare benötigen soll, um auf die Wahrscheinlichkeit von 50 % für den richtigen Schlüssel zu kommen. Eine Wahrscheinlichkeit von 50 % bedeutet ja, dass neben dem richtigen Schlüssel nur noch ein falscher Schlüssel übrig geblieben ist. Alle anderen falschen Schlüssel konnten aussortiert werden.
Beim ersten Klartext-Chiffrat-Paar starteten wir mit \(2^{64}-1\)
falschen Schlüsseln, und nach \(2^{63}\) weiteren Klartext-Chiffrat-Paaren soll dann den Autoren zufolge nur noch ein falscher Schlüssel übrig geblieben sein. Wir haben also \(2^{63}\) Klartext-Chiffrat-Paare benötigt, um \(2^{64}-1-1 = 2^{64}-2\) falsche Schlüssel auszusortieren. Wir hätten dann also im Durchschnitt nur \(\frac{2^{64}-2}{2^{63}} \approx 2\) falsche Schlüssel pro Klartext-Chifftat-Paar aussortiert. Liege ich bis hierhin richtig? (Das Ergebnis scheint mir nicht sehr plausibel zu sein.)

EDIT vom 20.04.2022 um 22:42:

Texte, die Mathjax enthalten zu kopieren, ist leider für mich nicht so einfach, wie man sieht. Hier ein letzter Versuch:

Für das erste Klartext-Chiffrat-Paar ermitteln wir \(2^{64}\) Schlüssel. Davon ist nur einer richtig, alle anderen nicht. An dieser Stelle wäre die Wahrscheinlichkeit, den richtigen Schlüssel unter den \(2^{64}\) ermittelten Schlüsseln zu finden, also \(\frac{1}{2^{64}}\). Die Autoren möchten aber eine Wahrscheinlichkeit von 50 % (also \(\frac{1}{2}\)) und behaupten, dass man dafür weitere \(2^{63}\) Klartext-Chiffrat-Paare benötige. Bis hierhin habe ich das doch wohl richtig verstanden?
Leider liefern die Autoren keine Begründung dafür, warum man weitere \(2^{63}\) Klartext-Chiffrat-Paare benötigen soll, um auf die Wahrscheinlichkeit von 50 % für den richtigen Schlüssel zu kommen. Eine Wahrscheinlichkeit von 50 % bedeutet ja, dass neben dem richtigen Schlüssel nur noch ein falscher Schlüssel übrig geblieben ist. Alle anderen falschen Schlüssel konnten aussortiert werden.
Beim ersten Klartext-Chiffrat-Paar starteten wir mit \(2^{64}-1\) falschen Schlüsseln, und nach \(2^{63}\) weiteren Klartext-Chiffrat-Paaren soll dann den Autoren zufolge nur noch ein falscher Schlüssel übrig geblieben sein. Wir haben also \(2^{63}\) Klartext-Chiffrat-Paare benötigt, um \(2^{64}-1-1 = 2^{64} -2\) falsche Schlüssel auszusortieren. Wir hätten dann also im Durchschnitt nur \(\frac{2^{64}-2}{2^{63}} \approx 2 \) falsche Schlüssel pro Klartext-Chifftat-Paar aussortiert. Liege ich bis hierhin richtig? (Das Ergebnis scheint mir nicht sehr plausibel zu sein.)

Diese Frage melden
gefragt

Punkte: 12

 

Frag doch mal bei informatikfragen.de   ─   mikn 08.04.2022 um 21:53

Ja, ok. Werde ich tun.   ─   bisam2000 09.04.2022 um 12:43

Bei informatikfragen.de gab es bislang leider auch keine Tipps. Also schreibe ich hier einfach mal selbst ein paar Ideen auf.

Für das erste Klartext-Chiffrat-Paar ermitteln wir \(2^{64}\) Schlüssel. Davon ist nur einer richtig, alle anderen nicht. An dieser Stelle wäre die Wahrscheinlichkeit, den richtigen Schlüssel unter den \(2^{64}\) ermittelten Schlüsseln zu finden, also \(\frac{1} {2^{64}}\). Die Autoren möchten aber eine Wahrscheinlichkeit von 50 % (also\(\frac{1}{2}\)) und behaupten, dass man dafür weitere \(2^{63}\) Klartext-Chiffrat-Paare benötige. Bis hierhin habe ich das doch wohl richtig verstanden?
Leider liefern die Autoren keine Begründung dafür, warum man weitere \(2^{63}\) Klartext-Chiffrat-Paare benötigen soll, um auf die Wahrscheinlichkeit von 50 % für den richtigen Schlüssel zu kommen. Eine Wahrscheinlichkeit von 50 % bedeutet ja, dass neben dem richtigen Schlüssel nur noch ein falscher Schlüssel übrig geblieben ist. Alle anderen falschen Schlüssel konnten aussortiert werden.
Beim ersten Klartext-Chiffrat-Paar starteten wir mit \(2^{64}-1\) falschen Schlüsseln, und nach \(2^{63}\) weiteren Klartext-Chiffrat-Paaren soll dann den Autoren zufolge nur noch ein falscher Schlüssel übrig geblieben sein. Wir haben also \(2^{63}\) Klartext-Chiffrat-Paare benötigt, um \(2^{64}-1-1 = 2^{64}-2\) falsche Schlüssel auszusortieren. Wir hätten dann also im Durchschnitt nur \(\frac{2^{64}-2}{2^{63}} \approx2\) falsche Schlüssel pro Klartext-Chifftat-Paar aussortiert. Liege ich bis hierhin richtig? (Das Ergebnis scheint mir nicht sehr plausibel zu sein.)
  ─   bisam2000 20.04.2022 um 12:03

Dann ist es schon ok, das hier zu fragen. Wäre aber besser, wenn Du Deine Gedanken oben in die Frage ergänzt. Im Kommentar gehen sie eher unter und oben sind sie auch besser lesbar.   ─   mikn 20.04.2022 um 13:55

Ja, ok. Ich werde das überarbeiten.   ─   bisam2000 20.04.2022 um 21:32
Kommentar schreiben
2 Antworten
1
Achtung: In der Lösung steht nicht, dass man $2^{63}$ weitere Paare benötigt, sondern genau $2^{63}$ Paare. Durch jedes Paar erhälts du einen weiteren richtigen Schlüssel, so dass du bei insgesamt $2^{64}$ Schlüsseln dann auf $2^{63}$ richtige Schlüssel kommst. Wie man die Wahrscheinlichkeit berechnet, weißt du ja.
Diese Antwort melden
geantwortet

Selbstständig, Punkte: 22.2K

 

Es gibt doch insgesamt nur einen richtigen Schlüssel.   ─   bisam2000 20.04.2022 um 22:12

Das war vielleicht etwas falsch ausgedrückt. Im Video von mikn wird das doch recht anschaulich mit den Mappings erklärt. Wenn du mehr Paare hast, hast du entsprechend mehr "richtige Zuordnungen".   ─   cauchy 20.04.2022 um 22:52

Ich werde mir das Video morgen noch einmal ansehen.
Es gibt ja nur einen richtigen Schlüssel. Dieser wird bei jedem Klartext-Chiffrat-Paar auftauchen. Beim ersten Klartext-Chiffrat-Paar habe ich zusätzlich zu dem richtigen Schlüssel auch noch \(2^{64}\) falsche Schlüssel. Die Frage ist doch: Wie viele von den falschen Schlüsseln tauchen auch beim zweiten Klartext-Chiffrat-Paar (rein zufällig) wieder auf? Und wie viele von den falschen Schlüsseln tauchen dann auch wieder beim dritten Klartext-Chiffrat-Paar (rein zufällig) auf? Wie viele Klartext-Chiffrat-Paare benötige ich, bis neben dem richtigen Schlüssel nur noch ein falscher Schlüssel auftauchen wird (50%-Chance). So habe ich diese Frage verstanden. Und ich kann mir beim besten Willen nicht vorstellen, dass das \(2^{63}\) Paare sein sollen.
  ─   bisam2000 20.04.2022 um 23:11

Auch hier wieder falsch: Nicht ZUSÄTZLICH, sondern du hast insgesamt $2^{64}$ Schlüssel, wovon einer richtig ist.

Der Gedankengang "ein richtiger Schlüssel und ein falscher Schlüssel" führt eher in die Irre. Versuch es mal lieber mit dem Gedanken "viele richtige Mappings und genauso viele falsche Mappings". Dann ist nämlich die Wahrscheinlichkeit, ein richtiges Mapping und damit den richtigen Schlüssel zu erwischen genau 50 %. Deswegen kommt die die Zahl $2^{63}$ auch so falsch vor. Aber schau da nochmal die entsprechend erwähnte Stelle im Video.
  ─   cauchy 20.04.2022 um 23:16

Ja, ok. Jetzt habe ich das wohl verstanden. Jetzt stelle ich mir das so vor:
Die Schlüsselsuchmaschine spuckt pro Durchlauf (1 Schlüssel-Chiffrat-Paar) nur einen Schlüssel aus. Dann ist die Chance, dass dieser richtig ist \(\frac{1}{2^{64}}\).
Wie viele Versuche (Schlüssel-Chiffrat-Paare) brauche ich dann, bis die Wahrscheinlichkeit \(\frac{1}{2}\) ist, dass der Schlüssel als Ergebnis ausgespuckt wurde?
\(\frac{1}{2^{64}}*x = \frac{1}{2}\)

Oder anders:
Ich habe \(2^{64}\) Schlüssel. Darunter ist nur einer richtig und er ist zufällig darunter gemischt. Wie viele Schlüssel müsste ich dann im Durchschnitt ausprobieren, bis ich den richtigen habe? Im Durchschnitt müsste man natürlich die Hälfte der Schlüssel durchprobieren, bis man den richtigen hat. Also \(\frac{2^{64}}{2} = 2^{63}\).
(Auch hier wäre wieder unterstellt, dass die Schlüsselsuchmaschine pro Klartext-Chiffrat-Paar nur einen Schlüssel ausgibt.)

Wenn ich so eine Schlüsselsuchmaschine hätte, würde ich allerdings anders vorgehen. Dann würde ich, so wie es im Buch und im Video ja auch erläutert wird, für ein Schlüssel-Chiffrat-Paar alle \(2^{64}\) möglichen Schlüssel ausrechnen lassen und speichern und dies dann für ein zweites Schlüssel-Chiffrat-Paar wiederholen. Wenn man dann die Schlüssel vergleicht, würde man sehr schnell den richtigen finden (entsprechend der Formel im Buch), denn es werden nur extrem wenige in der Schnittmenge auftauchen. Und dann bräuchte ich mit hoher Wahrscheinlichkeit auch nur 2 bis 3 Schlüssel-Chiffrat-Paare, und nicht \(2^{63}\).

Vielen Dank für die Hilfe! Von selbst wäre ich nicht darauf gekommen.
  ─   bisam2000 21.04.2022 um 19:52

Dann speichere mal diese Menge... Du wirst da auf ganz andere Probleme stoßen. Außerdem will man ja nicht, dass man die Schlüssel finden kann, sonst wäre die Verschlüsselung schlecht.   ─   cauchy 22.04.2022 um 03:49

Naja, es geht bei dieser Aufgabe ja nunmal um einen Brute-Force-Angriff. :-)   ─   bisam2000 22.04.2022 um 11:48

Herr Paar hat ja auch eine solche Maschine gebaut, wie im Buch und im Video (von dem es übrigens auch eine deutschsprachige Version gibt) erläutert. Die Maschine (Copacobana) ist wohl nur nicht ganz so schnell wie in der Übungsaufgabe.
Ich wäre schneller auf den Lösungsweg gekommen, wenn die Übungsaufgabe so formuliert worden wäre, dass keine Schlüssel gespeichert werden sollen bzw. dass man nicht so an die Aufgabe herangehen soll, wie im Buch beschrieben.
  ─   bisam2000 22.04.2022 um 12:01

Kommentar schreiben

0
Ich kenne mich da nicht wirklich aus, hab versucht etwas nachzulesen. Hab das Buch auch nicht zur Verfügung und weiß nicht, was die Grundlage (Lehrveranstaltung) dieser Aufgabe für Dich ist.
Mir geht in der Lösung durcheinander, dass mit der selben Formel einmal eine Anzahl keys ausgerechnet, und ein anderes Mal eine Wahrscheinlichkeit, was ja grundverschiedene Zahlen sind.
Es gibt im Internet die komplette Lehrveranstaltung von Christof Paar dazu als video, die relevante Vorlesung hier ist https://www.youtube.com/watch?v=M10BVpTCzGg
im Abschnitt brute force (ab Min. 58:30) leitet er diese Formel her, mit Beispiel. Auch da verstehe ich aber nicht, wieso aus einer Anzahl plötzlich eine Wahrscheinlichkeit wird. VIelleicht hilft es Dir trotzdem.
Diese Antwort melden
geantwortet

Lehrer/Professor, Punkte: 23.98K

 

Das Video kenne ich natürlich. Leider hilft mir das eben bei dieser Übungsaufgabe nicht weiter.   ─   bisam2000 20.04.2022 um 22:07

Kann ich ja nicht wissen, war nur ein Versuch zu helfen.   ─   mikn 20.04.2022 um 22:28

Ja, klar. Vielen Dank für deine Hilfe! War auch nicht böse gemeint.   ─   bisam2000 20.04.2022 um 22:43

Kommentar schreiben