Existential Forgery of Signatures falsch definiert...?

Benutzeravatar
Patr0rc
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 260
Registriert: 8. Feb 2008 11:43

Existential Forgery of Signatures falsch definiert...?

Beitrag von 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!
Zuletzt geändert von Patr0rc am 12. Mär 2010 07:33, insgesamt 1-mal geändert.

zeri
Windoof-User
Windoof-User
Beiträge: 34
Registriert: 17. Jul 2009 23:25

Re: Existential Forgery of Signatures falsch definiert...?

Beitrag von zeri »

Patr0rc hat geschrieben: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.
don't get even, get odd!

Benutzeravatar
Patr0rc
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 260
Registriert: 8. Feb 2008 11:43

Re: Existential Forgery of Signatures falsch definiert...?

Beitrag von Patr0rc »

zeri hat geschrieben: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...
zeri hat geschrieben: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
Windoof-User
Windoof-User
Beiträge: 34
Registriert: 17. Jul 2009 23:25

Re: Existential Forgery of Signatures falsch definiert...?

Beitrag von zeri »

Patr0rc hat geschrieben: 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
don't get even, get odd!

Benutzeravatar
Patr0rc
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 260
Registriert: 8. Feb 2008 11:43

Re: Existential Forgery of Signatures falsch definiert...?

Beitrag von Patr0rc »

zeri hat geschrieben: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
Windoof-User
Windoof-User
Beiträge: 34
Registriert: 17. Jul 2009 23:25

Re: Existential Forgery of Signatures falsch definiert...?

Beitrag von zeri »

Patr0rc hat geschrieben: 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.
don't get even, get odd!

Benutzeravatar
Patr0rc
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 260
Registriert: 8. Feb 2008 11:43

Re: Existential Forgery of Signatures falsch definiert...?

Beitrag von 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
Windoof-User
Windoof-User
Beiträge: 34
Registriert: 17. Jul 2009 23:25

Re: Existential Forgery of Signatures falsch definiert...?

Beitrag von zeri »

Patr0rc hat geschrieben: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.
don't get even, get odd!

peter@seceng
Mausschubser
Mausschubser
Beiträge: 72
Registriert: 31. Aug 2009 12:30

Re: Existential Forgery of Signatures falsch definiert...?

Beitrag von 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

Antworten

Zurück zu „Archiv“