Question

AES Schlüsselsuche und Wahrscheinlichkeitsrechnung

Aufrufe: 509 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

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.)

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.)

Teilen Diese Frage melden

gefragt 08.04.2022 um 19:15

bisam2000
Punkte: 12

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.)

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

Ja, ok. Ich werde das überarbeiten. ─ bisam2000 20.04.2022 um 21:32

Kommentar schreiben

2 Antworten

cauchy · Answer 1 · 2022-04-20T21:53:57Z

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.

Teilen Diese Antwort melden Link

geantwortet 20.04.2022 um 21:53

cauchy
Selbstständig, Punkte: 30.55K

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

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

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.

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

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

Leider scheint diese Antwort Unstimmigkeiten zu enthalten und muss korrigiert werden. Cauchy wurde bereits informiert.

mikn · Answer 2 · 2022-04-20T21:53:47Z

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.

Teilen Diese Antwort melden Link

geantwortet 20.04.2022 um 21:53

mikn
Lehrer/Professor, Punkte: 39.05K

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

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

Leider scheint diese Antwort Unstimmigkeiten zu enthalten und muss korrigiert werden. Mikn wurde bereits informiert.