Probeklausur Aufgabe 3

[planlosindarmstadt]

Hallo,

eine Frage zur Musterlösung zur Probeklausuraufgabe 3:

Es ist dort angegeben, dass der Angreifer (sk1,pk1) aus KGen1(1^n) generieren kann. Weiter unten heißt es dann, dass er die Antwort einer Anfrage an die Entschlüsselungsbox von B mit sk1 und Dec1 entschlüsseln kann. Meiner Meinung nach geht das nicht, da das innere Verfahren ja nur IND-CPA ist und somit kann ein Angreifer nicht auf die Entschlüsselungsbox Dec1 zugreifen. Habe ich da jetzt etwas grundsätzlich nicht verstanden oder ist da ein Fehler aufgetreten?

Vielen Dank für die Hilfe und einen schönen Sonntag Abend!

[Maeher]

Der Angreifer muss für \(Dec_1\) kein Orakel/Box anfragen.
Er ist ein Agreifer gegen \(\mathcal{E}_2\).
Die Schlüssel für Verfahren \(\mathcal{E}_1\) hat er selber erzeugt, um dem inneren Angreifer das kombinierte Verfahren simulieren zu können.

Da er den geheimen Schlüssel \(sk_1\) kennt, kann er selbstverständlich einfach den Entschlüsselungsalgorithmus \(Dec_1(sk_1,\cdot)\) ausführen.

[r1chard]

Hallo,

bei der Aufgabe geht es um einen Widerspruchsbeweis, also angenommen man hätte einen Angreifer gegen das kombinierte Verfahren, dann hätte man auch einen Angreifer gegen das äußere Verfahren, darum kann es den Angreifer gegen das kombinierte Verfahren nicht geben.

kurz gesagt:
man hat einen Angreifer gegen die CCA Sicherheit von \(\epsilon_{2}(\epsilon_{1})\) und konstruiert daraus einen Angreifer gegen die CCA Sicherheit von \(\epsilon_{2}\), indem man \(\epsilon_{1}\) selbst ausführt/simuliert.

Da es sonst einen Angreifer gegen die CCA Sicherheit von \(\epsilon_{2}\) geben würde, ist \(\epsilon_{2}(\epsilon_{1})\) auch CCA Sicher.


Für den Beweis ist die Sicherheit des inneren Verfahrens eigentlich egal, solang man es einfach selbst ausführen kann (wovon man ja ausgehen kann).

[planlosindarmstadt]

vielen Dank für die schnellen Antworten. So steht es ja auch in der Musterlösung und das habe ich auch alles schon soweit verstanden. Aber ich glaube, dass ich dann doch auf die gleiche Art und Weise einen erfolgreichen Angriff gegen das äußere Verfahren in dem Aufgabenteil b) durchführen könnte, indem analog das Schlüsselpaar \((sk_2,pk_2)\) generiert wird und dann eine Ciphertext-Anfrage vom Angreifer gegen das kombinierte Verfahren zunächst durch \(Dec_2(sk_2,\cdot)\) entschlüsselt und der entschlüsselte Ciphertext noch an die Entschlüsselungsbox \(Dec_1\) geschickt wird... Wo ist da der Haken?

[R_Egert]

Ich hoffe ich habe deine Frage einigermaßen verstanden. In dem ersten Teil beweisen wir ja gerade durch widerspruch, dass das Verfahren CCA sicher sein muss, da wir, wenn dem nicht so wäre, einen erfolgreichen Angreifer gegen das äußere Verfahren bauen könnten. (Dieses ist aber laut Def. CCA sicher --> Widerspruch)

In Teil b) können wir ja direkt zeigen, dass das Verfahren nicht CCA sicher ist, indem wir einen CCA Angriff auf das Kombinierte Verfahren ausführen und dieser auch gelingt. Da müssen wir also nichts über irgendwelche Widerspruchsbeweise belegen, sondern zeigen es konkret Anhand von El Gamal.

mfg Rolf

[FidorDewski]

Der Angreifer muss für \(Dec_1\) kein Orakel/Box anfragen.
Er ist ein Agreifer gegen \(\mathcal{E}_2\).
Die Schlüssel für Verfahren \(\mathcal{E}_1\) hat er selber erzeugt, um dem inneren Angreifer das kombinierte Verfahren simulieren zu können.

Da er den geheimen Schlüssel \(sk_1\) kennt, kann er selbstverständlich einfach den Entschlüsselungsalgorithmus \(Dec_1(sk_1,\cdot)\) ausführen.

So richtig "zufrieden" bin ich damit nicht. Das hieße doch, dass ich mir mein Schlüsselpaar für das innere Verfahren dann immer selbst wählen kann (richtig?) - somit ist dann aber doch durch die Art und Weise des Beweises, dass die Sicherheit des Gesamtsystems immer maximal die Sicherheit des äußeren Verfahrens sein kann, denn das innere System steht ja unter meine Kontrolle. Oder sehe ich da etwas grundlegend falsch?

[planlosindarmstadt]

Danke, Rolf, auch das habe ich schon so verstanden.

Meine Frage bezieht sich darauf, warum mein oben beschriebener "Wiederspruchsangriff" nicht funktioniert, mit dem ich aber bewiesen hätte, dass auch b) gilt. Ich dürft ihn ja nicht führen können, wenn es ein Gegenbeispiel gibt.

Und so wirklich verstehe ich nicht, warum ich mir das Schlüsselpaar einfach generieren darf, weil ich so doch dann einen erfolgreichen Angriff gegen ein beliebiges Verfahren führen könnte oder sehe ich das falsch? Wo ist da die Einschränkung? Liegt es daran, dass er die Ver- und Entschlüsselung quasi nur für seine Zwecke verwendet oder so? Ich hoffe, es ist verständlich, was ich meine.

[r1chard]

Wenn ich dich richtig verstehe willst du das äußere Verfahren Simulieren, was aber zu dem Problem führt:
Man kann an die \(Dec_{1}\)-Box nicht ein Chifrat schicken, dass man so von der \(Enc_{1}\)-Box bekommen hat, bei CPA Sicherheit, könnte man wie in der Lösung ein Chifrat abändern, so dass es verschieden von dem ist, dass man von der Enc Box bekommen hat, aber die gleich Nachricht verschlüsselt

also kann es sein das \(Enc_{1}(Enc_{2}(m)) \neq Enc'_{1}(Enc_{2}(m))\) aber \(Enc_{2}(m) = Enc_{2}(m)\) , so dass man es nicht Entschlüsseln und an die Dec Box schicken kann, weil der Angreifer nur das äußere Chifrat abgeändert hat


ich hoffe es ist verständlich, warum der Beweis so nicht funktioniert

[planlosindarmstadt]

Jetzt bin ich mir nicht sicher, ob ich deine Antwort verstehe und ob du vielleicht die Verfahren vertausch hast?
Um meine Probleme vielleicht etwas deutlicher zu formulieren:

Meinen Angriff bei der b) würde ich folgendermaßen gestalten:
Sei \(A^*\) ein Angreifer eff. erf. gegen IND-CCA Sicherheit von \(\epsilon_2(\epsilon_1)\). Konstruiere daraus einen Angreifer \(A\) gegen IND-CCA Sicherheit von \(\epsilon_1\) wie folgt:
Zunächst generiert sich \(A\) das Schlüsselpaar \((sk_2,pk_2)\) aus \(KGen_2(1^n)\). Bei Anfragen von zwei Nachrichten \(m_0,m_1\), schickt \(A\) diese direkt weiter an seine Verschlüsselungsbox, wo eine der beiden zufällig gewählt und durch \(Enc_1\) verschlüsselt wird. Den erhaltenen Ciphertext, verschlüsselt er mit \(Enc_2(pk_2,\cdot)\) und leitet in an \(A^*\) weiter. Ciphertextanfragen werden erst entschlüsselt durch \(Dec_2(sk_2,\cdot)\) und dann an die Entschlüsselungsbox geleitet, die erhaltene Nachricht dann an \(A^*\) weitergeleitet.

So simuliere ich das kombinierte Verfahren. - Angreifer \(A^*\) gibt also mit gleicher Wahrscheinlichkeit \(a = b\) aus, wie bei einem echten Angriff. Diese ist nicht vernachlässigbar angenommen. Liegt mein Fehler darin, dass ich aus irgendeinem Grund keinen ordentlichen Angriff gegen \(\epsilon_1\) führe?

Vielen Dank für die Mühe!

[Maeher]

Jetzt bin ich mir nicht sicher, ob ich deine Antwort verstehe und ob du vielleicht die Verfahren vertausch hast?
Um meine Probleme vielleicht etwas deutlicher zu formulieren:

Meinen Angriff bei der b) würde ich folgendermaßen gestalten:
Sei \(A^*\) ein Angreifer eff. erf. gegen IND-CCA Sicherheit von \(\epsilon_2(\epsilon_1)\). Konstruiere daraus einen Angreifer \(A\) gegen IND-CCA Sicherheit von \(\epsilon_1\) wie folgt:
Zunächst generiert sich \(A\) das Schlüsselpaar \((sk_2,pk_2)\) aus \(KGen_2(1^n)\). Bei Anfragen von zwei Nachrichten \(m_0,m_1\), schickt \(A\) diese direkt weiter an seine Verschlüsselungsbox, wo eine der beiden zufällig gewählt und durch \(Enc_1\) verschlüsselt wird. Den erhaltenen Ciphertext, verschlüsselt er mit \(Enc_2(pk_2,\cdot)\) und leitet in an \(A^*\) weiter.

Bis hierhin funktioniert das auch, aber dann gibt es ein Problem:

Ciphertextanfragen werden erst entschlüsselt durch \(Dec_2(sk_2,\cdot)\) und dann an die Entschlüsselungsbox geleitet, die erhaltene Nachricht dann an \(A^*\) weitergeleitet.

Du bekommst hier einen ciphertext \(c^*\). DIeser unterscheidet sich von allen \(c\), die du zurückgegeben hast.
Wenn du \(c^*\) aber mit \(Dec_2(sk_2,c^*)\) entschlüsselst, erhälst du einen ciphertext \({c^*}'\), den du an dein Orakel schicken möchtest.
Das Problem ist nun, dass nicht garantiert ist, dass sich \({c^*}'\) von den \(c\) unterscheidet, die dir dein Orakel geliefert hat.
Demnach kannst du das Decryption Orakel nicht korrekt simulieren.

[r1chard]

Ja genau das Problem daran Liegt an:

Ciphertextanfragen werden erst entschlüsselt durch \(Dec_2(sk_2,\cdot)\) und dann an die Entschlüsselungsbox geleitet, die erhaltene Nachricht dann an \(A^*\) weitergeleitet.

Wenn du im das Chiffrat c <- \(Enc_{2}(Enc_{1}(m)) = Enc_{2}(c_1)\) schickst, wobei du \(c_1 = Enc_{1}(m)\) von der \(Enc_{1}\) - Box bekommst

und er ein Chiffrat c' \(\neq\) c erzeugt, hast du keine Sicherheit, dass

\(Dec_2(c') \neq Dec_2(c) = c_1\)

so dass du es gegenfalls nicht an die Entschlüsselungsbox weiterschicken kannst,
da jedes c' das du an diese Box schickst verschieden von jedem c sein muss, dass du bis zu dem Zeitpunkt bekommen hast.

[R_Egert]

Das sieht so aus als würdest du das Verfahren Angreifen was du selbst simulierst^^ du willst aber ja das äußere Verfahren angreifen^^. Indem Moment wo du ein Verfahren angreifst, welches bekannt ist und noch dazu die Schlüssel dazu selbst generiert ist, funktioniert der Angriff natürlich immer... Oder isses schon so spät das ichs wieder falsch verstehe?^^

grüsse Rolf

[Maeher]

Der Angreifer muss für \(Dec_1\) kein Orakel/Box anfragen.
Er ist ein Agreifer gegen \(\mathcal{E}_2\).
Die Schlüssel für Verfahren \(\mathcal{E}_1\) hat er selber erzeugt, um dem inneren Angreifer das kombinierte Verfahren simulieren zu können.

Da er den geheimen Schlüssel \(sk_1\) kennt, kann er selbstverständlich einfach den Entschlüsselungsalgorithmus \(Dec_1(sk_1,\cdot)\) ausführen.

So richtig "zufrieden" bin ich damit nicht. Das hieße doch, dass ich mir mein Schlüsselpaar für das innere Verfahren dann immer selbst wählen kann (richtig?)

richtig

- somit ist dann aber doch durch die Art und Weise des Beweises, dass die Sicherheit des Gesamtsystems immer maximal die Sicherheit des äußeren Verfahrens sein kann, denn das innere System steht ja unter meine Kontrolle. Oder sehe ich da etwas grundlegend falsch?

Du zeigst, dass du mindestens die Sicherheit des äußeren Verfahrens hast, nicht maximal.

[Maeher]

Danke, Rolf, auch das habe ich schon so verstanden.
Und so wirklich verstehe ich nicht, warum ich mir das Schlüsselpaar einfach generieren darf, weil ich so doch dann einen erfolgreichen Angriff gegen ein beliebiges Verfahren führen könnte oder sehe ich das falsch? Wo ist da die Einschränkung? Liegt es daran, dass er die Ver- und Entschlüsselung quasi nur für seine Zwecke verwendet oder so? Ich hoffe, es ist verständlich, was ich meine.

Nun, \(KGen(1^n)\) ist erstmal einfach nur ein Algorithmus, der dir auch bekannt ist, demnach kannst du den ausführen so oft du möchtest.
Um ein Verfahren anzugreifen hilft dir das natürlich erstmal nichts, denn du erzeugst ja einen zufälligen Schlüssel, und nur mit vernachlässigbarer Wahrscheinlichkeit den, der vom Orakel benutzt wird.

[fischlin]

Ja genau das Problem daran Liegt an:

Ciphertextanfragen werden erst entschlüsselt durch \(Dec_2(sk_2,\cdot)\) und dann an die Entschlüsselungsbox geleitet, die erhaltene Nachricht dann an \(A^*\) weitergeleitet.

Wenn du im das Chiffrat c <- \(Enc_{2}(Enc_{1}(m)) = Enc_{2}(c_1)\) schickst, wobei du \(c_1 = Enc_{1}(m)\) von der \(Enc_{1}\) - Box bekommst

und er ein Chiffrat c' \(\neq\) c erzeugt, hast du keine Sicherheit, dass

\(Dec_2(c') \neq Dec_2(c) = c_1\)

so dass du es gegenfalls nicht an die Entschlüsselungsbox weiterschicken kannst,
da jedes c' das du an diese Box schickst verschieden von jedem c sein muss, dass du bis zu dem Zeitpunkt bekommen hast.

Diese Antwort macht es am Deutlichsten: Die Simulation könnte hier scheitern, da ich den Ciphertext evtl. nicht mittels Dec-Box dekodieren kann, da er identisch zu einem vorher erhaltenem ist. Und das ElGamal-Beispiel setzt genau an dieser Lücke an, indem es den gleichen inneren Ciphertext äußerlich neu verschlüsselt bzw. re-randomisiert.

Etwas philosophischer gesprochen kann es durchaus sein, dass man wie im Teil (a) sich selbst Schlüssel für das eine Verfahren wählen kann und gegen das andere Verfahren spielt. Wir hatten das auch im Fall von Enc+Mac im symetrischen Fall, wo wir einmal gegen die CPA-Sicherheit von Enc spielen, und dann den MAC-Schlüssel kennen,
und in einem weiteren Schritt dann gegen das MAC-Verfharen spielen, und dazu den Schlüssel von Enc kennen.
Nut ist es hier im Fall (a) eben so, dass man nur gegen das äußere Verfahren spielen muss. Das zeigt, dass das
innere Verfahren nur eine Umkodierung ist, die keinen Einfluss auf die Sicherheit hat (wir spielen nie gegen
die Sicherheit des inneren Verfahrens).