Existential Forgery of Signatures falsch definiert...?

[Patr0rc]

Hallo.
Wenn ich den Wikipediaartikel unter http://en.wikipedia.org/wiki/Forgery_(C ... al_forgery richtig verstehe, ist die "Definition" von "Existential Forgery of Signatures" von unserem Foliensatz nicht korrekt, da in den Folien (Foliensatz 5, Folie 18) steht:

neue Nachricht \(m \neq m_0,\ldots,m_n\) und ihre Signatur \(s\)

In Wikipedia und anderen Vorlesungen wird Existential Forgery so definiert, dass man ein neues Paar \((m',s')\) vorzeigen muss, welches nicht mit den vorherigen Paaren \((m_0,s_0),\ldots,(m_n,s_n)\) übereinstimmen darf, allerdings darf man z.B. sowas wie Nachricht \(m_n\) mit Signatur \(s_0\) zusammenmauscheln zu \((m',s')=(m_n,s_0)\) und hätte laut der Wiki-Definition bzw. der in anderen Vorlesungen eine gültige Existential Forgery erbracht. In den Folien hier ist dies nicht möglich, da es eine neue Nachricht sein muss, was in meinen Augen falsch ist...

Wäre schön, wenn sich der Veranstalter oder einer der Tutoren dazu mal äußern könnten!

[zeri]

Hallo.
Wenn ich den Wikipediaartikel unter http://en.wikipedia.org/wiki/Forgery_(C ... al_forgery richtig verstehe, ist die "Definition" von "Existential Forgery of Signatures" von unserem Foliensatz nicht korrekt, da in den Folien (Foliensatz 5, Folie 18) steht:

neue Nachricht \(m \ne m_0,\ldots,m_n\) und ihre Signatur \(s\)

In Wikipedia und anderen Vorlesungen wird Existential Forgery so definiert, dass man ein neues Paar \((m',s')\) vorzeigen muss, welches nicht mit den vorherigen Paaren \((m_0,s_0),\ldots,(m_n,s_n)\) übereinstimmen darf, allerdings darf man z.B. sowas wie Nachricht \(m_n\) mit Signatur \(s_0\) zusammenmauscheln zu \((m',s')=(m_n,s_0)\) und hätte laut der Wiki-Definition bzw. der in anderen Vorlesungen eine gültige Existential Forgery erbracht. In den Folien hier ist dies nicht möglich, da es eine neue Nachricht sein muss, was in meinen Augen falsch ist...

Ich bin mir nicht sicher, ob ich dich richtig verstehe. Wenn du meintest, dass der angreifer einfach eine nachricht an den judge senden darf sich die signatur geben lässt und dann nachricht und signatur an den judge schickt ... dann ist das doch langweilig oder?

Das Equivalent dazu in der wirklichkeit wäre, wenn ich hergehe und ne von dir signierte(pgp,smime oder sowas) email nehme und behaupte, dass ich deinen privatekey habe, weil ich ja erfolgreich ne nachricht mit ner signatur vorweisen kann.

[Patr0rc]

Ich bin mir nicht sicher, ob ich dich richtig verstehe. Wenn du meintest, dass der angreifer einfach eine nachricht an den judge senden darf sich die signatur geben lässt und dann nachricht und signatur an den judge schickt ... dann ist das doch langweilig oder?

Das meinte ich in der Tat nicht.

Der Angreifer darf Nachrichten \(m_0,\ldots,m_n\) an den Judge senden und erhält von diesem die Signaturen \(s_0,\ldots,s_n\) dazu zurück.
Nun kann doch der Angreifer hergehen und schauen, ob eine Signatur für Nachricht \(i\) als Signatur für Nachricht \(k\) auch gültig ist, und falls ja, dieses Pärchen \((m_k,s_i)\) mit \(i\ne k\) an den Judge schicken. Da die Signatur \(s_i\) für die Nachricht \(m_k\) seeeeeeeeeeeehr wahrscheinlich eine andere ist als die, die der Angreifer vom Judge erhalten hat (die ja bekanntlich \(s_k\) ist und höchstwahrscheinlich wohl \(s_k\not=s_i\) gilt), wird/muss der Judge das gefälschte Nachrichten-Signatur-Pärchen \((m_k,s_i)\) akzeptieren...

Das Equivalent dazu in der wirklichkeit wäre, wenn ich hergehe und ne von dir signierte(pgp,smime oder sowas) email nehme und behaupte, dass ich deinen privatekey habe, weil ich ja erfolgreich ne nachricht mit ner signatur vorweisen kann.

Das geht so nicht, denn du würdest genau das tun, was in Wiki und anderen Vorlesungen NICHT erlaubt ist, nämlich ein vorhandenes Paar \((m,s)\) nehmen und als deines ausgeben. Aber du musst ein Paar \((m',s')\) vorweisen, was nicht identisch mit den Paaren ist, für die du die Signatur erhalten hast. Also muss 1. deine Nachricht eine andere sein, wenn du eine Signatur übernimmst, 2. deine Signatur anders sein, wenn du eine Nachricht übernimmst, oder 3. beides anders (also beides neu) sein. In der Realität musst du also eine andere Nachricht für meine Signatur nehmen, eine andere Signatur für meine Nachricht nehmen oder beides komplett neu wählen.

Ok?

[zeri]

Der Angreifer darf Nachrichten \(m_0,\ldots,m_n\) an den Judge senden und erhält von diesem die Signaturen \(s_0,\ldots,s_n\) dazu zurück.
Nun kann doch der Angreifer hergehen und schauen, ob eine Signatur für Nachricht \(i\) als Signatur für Nachricht \(k\) auch gültig ist, und falls ja, dieses Pärchen \((m_k,s_i)\) mit \(i\ne k\) an den Judge schicken. Da die Signatur für die Nachricht \(m_i\) eine andere ist als die, die der Angreifer vom Judge erhalten hat, wird/muss der Judge das gefälschte Nachrichten-Signatur-Pärchen akzeptieren...

Ok, das ist nach meinem Verständniss auch ein erfolgreicher Angreifer.Aber das ist für den Angreifer, im besten Fall so schwer wie das finden einer kollision in der hashfunktion. Und das wurde ja 2 Slides vorher ausgeschlossen ... Es wurde sogar Kollisionsfreiheit gefordert nicht nur Kollisionsresistenz, Also kann dieser Fall nicht auftretten.

EDIT: Ich bin natürlich blöd es ist genau so schwer wie das finden einer Kollision in H

[Patr0rc]

Ok, das ist nach meinem Verständniss auch ein erfolgreicher Angreifer. Das ist für den Angreifer, im besten Fall so schwer wie das finden einer kollision in der hashfunktion. Und das wurde ja 2 Slides vorher ausgeschlossen ... Es wurde sogar Kollisionsfreiheit gefordert nicht nur Kollisionsresistenz, Also kann dieser Fall nicht auftretten.

Laaaangsam. Vor 2 Folien wurde für Signaturen mit RSA angenommen, dass sie sicher sind, wenn man davon ausgeht, dass die Hashfunktion kollisionsfrei ist. Nun befinden wir uns allerdings wieder in einem viel allgemeineren Kontext als dem von RSA und da "Existential Forgery of Signatures" die schwächsten Voraussetzungen hat, um die stärkste Begrifflichkeit für ein Signaturverfahren darstellen zu können, können wir auch nichts weiter annehmen über Kollisionsresistenz etc. Insofern kann das mit dem "Also kann dieser Fall nicht auftretten." nicht so stehen bleiben...
(Wer sagt eigentlich, dass wir irgendwas mit einer Hashfunktion tun? Wir haben ein allgemeines Signaturverfahren...)

[zeri]

Laaaangsam. Vor 2 Folien wurde für Signaturen mit RSA angenommen, dass sie sicher sind, wenn man davon ausgeht, dass die Hashfunktion kollisionsfrei ist. Nun befinden wir uns allerdings wieder in einem viel allgemeineren Kontext als dem von RSA und da "Existential Forgery of Signatures" die schwächsten Voraussetzungen hat, um die stärkste Begrifflichkeit für ein Signaturverfahren darstellen zu können, können wir auch nichts weiter annehmen über Kollisionsresistenz etc. Insofern kann das mit dem "Also kann dieser Fall nicht auftretten." nicht so stehen bleiben...
(Wer sagt eigentlich, dass wir irgendwas mit einer Hashfunktion tun? Wir haben ein allgemeines Signaturverfahren...)

Stimmt da hast du recht. Wenn es aber für einen Angreifer möglich ist Kollisionen in der Hashfunktion zu finden, dann könnte er die 2te nachricht einfach einbehalten und das spiel wieder gewinnen. Ich denke, dass das unter "mit sehr hoher wahrscheinlichkeit"-verlieren. Ich stimme dir aber zu, dass die Definition in wiki eine andere menge von erfolgreichen angriffen spezifiziert als die Definition in den Folien und ich würde jetzt auch gerne wissen, welche wir uns merken sollten.

[Patr0rc]

Im Endeffekt kann der Angreifer vielleicht ja gar nicht die Kollisionsresistenz der Hashfunktion brechen, sondern hat zufälligerweise durch die Wahl seiner Nachrichten diesen Fall hinbekommen, dass eine Signatur auch zu einer anderen Nachricht passt (sehr unwahrscheinlich, aber möglich).
Ich will nur wissen, ob das bei den Folien vielleicht nicht berücksichtigt wurde als eine gültige Fälschung...
Einfach mal eine Reaktion der Veranstalter abwarten

[zeri]

Im Endeffekt kann der Angreifer vielleicht ja gar nicht die Kollisionsresistenz der Hashfunktion brechen, sondern hat zufälligerweise durch die Wahl seiner Nachrichten diesen Fall hinbekommen, dass eine Signatur auch zu einer anderen Nachricht passt (sehr unwahrscheinlich, aber möglich).
Ich will nur wissen, ob das bei den Folien vielleicht nicht berücksichtigt wurde als eine gültige Fälschung...
Einfach mal eine Reaktion der Veranstalter abwarten

Eine weitere Frage ist, ob das wirklich eine Fälschung ist. Ne signatur sagt ja nur, dass der Signer die nachricht signiert hat. Welcher signaturwert da jetzt steht ist eigendlich egal. Und in dem Beispiel von dir wurden beide nachrichten ja signiert.

[peter@seceng]

Hi!

Die Definition von "existential forgery under a chosen message attack" ist in den Folien völlig korrekt. Die Definition in Wikipedia meint etwas anderes. Dort ist die sogenannte "strong unforgability" gemeint, diese Definition ist noch etwas stärker als die aus der VL. Es freut mich jedoch sehr zu sehen, dass ihr euch damit auseinandersetzt.

Viele Grüße, Andreas