Siegenthaler bound verständlich erklärt - Versionsgeschichte

Niki am 2. Mai 2009 um 20:52 Uhr

2009-05-02T20:52:55Z

Niki: /* Lösung des Siegenthaler bounds */

2008-06-20T12:05:57Z

Lösung des Siegenthaler bounds

Niki am 11. Juni 2008 um 19:24 Uhr

2008-06-11T19:24:05Z

Niki: /* Nonlinear order */

2008-06-10T21:21:58Z

Nonlinear order

Niki: /* Die Parity Funktion */

2008-06-10T21:20:50Z

Die Parity Funktion

Niki: /* Correlation immunity */

2008-06-10T21:11:53Z

Correlation immunity

Niki: /* Lösung des Siegenthaler bounds ([3]) */

2008-06-10T21:11:08Z

Lösung des Siegenthaler bounds ([3])

Niki: /* Siegenthaler bound */

2008-06-10T21:10:28Z

Siegenthaler bound

Niki: /* Siegenthaler bound */

2008-06-10T21:10:02Z

Siegenthaler bound

Niki: /* Lösung des Siegenthaler bounds ([1]) */

2008-06-10T21:09:19Z

Lösung des Siegenthaler bounds ([1])

@@ Zeile 12: / Zeile 12: @@
 <section end="head"/>
-== Siegenthaler bound ==
+= Siegenthaler bound =
 Der Siegenthaler Bound ist definiert mit:
@@ Zeile 34: / Zeile 34: @@
 so ergibt die Verknüpfung von <math>Y</math> und einem Plaintext zu einem Ciphertext eine hohe Korrelation zwischen Ciphertext und Plaintext, da der Ciphertext mit einer höheren Wahrscheinlichkeit 0 als 1 wird. AND ist eine nichtlineare Funktion und kann als Multiplikation modulo 2 betrachtet werden.
-== Correlation immunity ==
+= Correlation immunity =
 Die ''correlation immunity'' <math>m</math> ist ein Maß dafür, wie resistent eine boolesche Funktion gegen Korrelationsattacken ist bzw. ob und wieviel Information man aus der Ausgabe einer Funktion über deren Argumente ziehen kann. Nach dem Beispiel oben ist <math>m</math> für eine XOR-Funktion hoch und für eine AND-Funktion niedrig.
@@ Zeile 48: / Zeile 48: @@
 Eine Funktion <math>f</math> ist correlation immune mit der Ordnung <math>m</math> genau dann, wenn der Funktionswert <math>f(X_1, X_2, \dots, X_n)</math> statistisch unabhängig von den Eingabewerten <math>X_1, X_2, \dots, X_n</math> ist und zwar genau für jede Kombination aus <math>m</math> Eingabevariablen und weniger. Was diese verwirrende Definition genau heisst, möchte ich nun anhand von ein paar Beispielen erklären.
-=== Die XOR Funktion ===
+== Die XOR Funktion ==
 Die XOR-Funktion ist definiert mit:
@@ Zeile 75: / Zeile 75: @@
 Die Bedingung ist also für <math>m=2</math> nicht erfüllt, also ist die correlation immunity für die XOR-Funktion 1.
-=== Die AND Funktion ===
+== Die AND Funktion ==
 Die AND-Funktion ist definiert mit:
@@ Zeile 100: / Zeile 100: @@
 Die Bedingung ist also bereits für einen Funktionswert nicht erfüllt, also ist <math>m=0</math>.
-=== Die Parity Funktion ===
+== Die Parity Funktion ==
 Als nächstes Beispiel die Parity-Funktion für 3 Inputs:
@@ Zeile 132: / Zeile 132: @@
 Als letztes Beispiel erfüllt die Funktion <math>f(X_1,X_2,X_3) = (X_1 \oplus X_2) \land X_3</math> nicht einmal die notwendige Bedinung. Die correlation immunity ist also null.
-== Nonlinear order ==
+= Nonlinear order =
 Als letzter unbekannter Parameter im Siegenthaler bound bleibt der Parameter <math>d</math> übrig. Verwirrend dabei ist, dass dieser in der Literatur viele Namen hat:
@@ Zeile 148: / Zeile 148: @@
 Nachfolgend zwei Beispiele:
-=== Die XOR Funktion ===
+== Die XOR Funktion ==
 <math>f(X_1,X_2) = X_1 \oplus X_2 = a_0 + a_1 X_1 + a_2 X_2 + a_{12} X_1 X_2</math> mit <math>a_0 = 0</math> und <math>a_{12} = 0</math> sowie <math>a_1 = 1</math> und <math>a_2 = 1</math>. Man erkennt sofort: Es handelt sich um ein Polynom ersten Grades, also ist der nonlinear order <math>d=1</math>
-=== Die AND Funktion ===
+== Die AND Funktion ==
 <math>f(X_1,X_2) = X_1 \land X_2 = a_0 + a_1 X_1 + a_2 X_2 + a_{12} X_1 X_2</math> mit <math>a_{12} = 1</math> und allen anderen Koeffizienten null. Man erkennt sofort: Es handelt sich um ein Polynom zweiten Grades, also ist der nonlinear order <math>d=2</math>
-== Lösung des Siegenthaler bounds ==
+= Lösung des Siegenthaler bounds =
 Um den Kompromiss zwischen Linearität und correlation immunity zu umgehen, kann man interne Speicher verwenden und so eine lineare Funktion mit hoher correlation immunity verwenden und mit dem Output einer nichtlinearen Funktion aus dem letzten Durchgang kombinieren [2]:
@@ Zeile 167: / Zeile 167: @@
 Allerdings schafft diese Lösung wieder neue Angriffsmöglichkeiten (low 2-adic complexity)
-== Referenzen ==
+= Referenzen =
 * [1] http://www.isical.ac.in/~crg/tech_reports/tech9.ps
 * [2] Unterlagen zu "Angewandte Kryptographie" von [http://de.wikipedia.org/wiki/Vincent_Rijmen Vincent Rijmen] an der TU Graz: http://www.iaik.tugraz.at/teaching/00_angewandte%20kryptografie/slides2008/streamciphers.pdf
 * [3] Original Paper von Siegenthaler: http://ieeexplore.ieee.org/search/wrapper.jsp?arnumber=1056949
 [[Kategorie:Weblog]]

@@ Zeile 159: / Zeile 159: @@
 == Lösung des Siegenthaler bounds ==
-Um den Kompromiss zwischen Linearität und correlation immunity zu umgehen, kann man interne Speicher verwenden und so eine lineare Funktion mit hoher correlation immunity verwenden und mit dem Output einer nichtlinearen Funktion aus dem letzten Durchgang kombinieren [3]:
+Um den Kompromiss zwischen Linearität und correlation immunity zu umgehen, kann man interne Speicher verwenden und so eine lineare Funktion mit hoher correlation immunity verwenden und mit dem Output einer nichtlinearen Funktion aus dem letzten Durchgang kombinieren [2]:
 <math>s_j = a_j \oplus b_j \oplus c_{j-1}</math>

@@ Zeile 170: / Zeile 170: @@
 * [1] http://www.isical.ac.in/~crg/tech_reports/tech9.ps
-* [2] Unterlagen zu "Angewandte Kryptographie" von [http://de.wikipedia.org/wiki/Vincent_Rijmen Vincent Rijmen] an der TU Graz:
+* [2] Unterlagen zu "Angewandte Kryptographie" von [http://de.wikipedia.org/wiki/Vincent_Rijmen Vincent Rijmen] an der TU Graz: http://www.iaik.tugraz.at/teaching/00_angewandte%20kryptografie/slides2008/streamciphers.pdf
 * [3] Original Paper von Siegenthaler: http://ieeexplore.ieee.org/search/wrapper.jsp?arnumber=1056949
 [[Kategorie:Weblog]]

@@ Zeile 140: / Zeile 140: @@
 * algebraic degree
-Mit all diesen Namen ist aber das gleiche und in Wirklichkeit leicht verständliche gemeint: Jede Funktion lässt sich durch seine algebraische Form als Polynome anschreiben:
+Mit all diesen Namen ist aber das gleiche und in Wirklichkeit leicht verständliche gemeint: Jede Funktion lässt sich durch seine algebraische Form als Polynom anschreiben:
 <math>f(X_1,X_2,\dots,X_n) = a_0 + a_1 X_1 + a_2 X_2 + \dots + a_n X_n + a_{12} X_1 X_2 + a_{13} X_1 X_3 + \dots + a_{12\dots n} X_1 X_2 \dots X_n</math>

@@ Zeile 128: / Zeile 128: @@
 Setzt man <math>m=1</math> so erkennt man schnell - analog zum XOR Beispiel - die Unabhängigkeit von allen <math>X_i</math> zum Funktionswert.
 Nun wird <math>m=2</math> gesetzt. Nun müssen die Kombinationen <math>(X_1,X_2)</math>, <math>(X_1,X_3)</math> und <math>(X_2,X_3)</math> auf ihre statistische Unabhängigkeit mit dem Funktionswert geprüft werden. Dies ist für alle drei Tupel erfüllt. Zum Beispiel lässt sich durch Kenntnis des Funktionswertes nichts über <math>(X_1,X_2)</math> aussagen, da sowohl für eine Null als auch für eine Eins alle Kombinationen eines XOR Gatters möglich sind und so keine Rückschlüsse auf die Funktionsparameter möglich sind.
-Für <math>m=3</math> hingegen korreliert <math>(X_1,X_2,X_3)</math> wieder mit dem Funktionswert: Beobachtet man z.B. eine eins am Ausgang, so ist die Anzahl der Einer in den Argumenten sicher ungerade. Also ist die correlation immunity dieser Funktion 2.
+Für <math>m=3</math> hingegen korreliert <math>(X_1,X_2,X_3)</math> wieder mit dem Funktionswert: Beobachtet man z.B. eine eins am Ausgang, so ist die Anzahl der Einser in den Argumenten sicher ungerade. Also ist die correlation immunity dieser Funktion 2.
 Als letztes Beispiel erfüllt die Funktion <math>f(X_1,X_2,X_3) = (X_1 \oplus X_2) \land X_3</math> nicht einmal die notwendige Bedinung. Die correlation immunity ist also null.

@@ Zeile 36: / Zeile 36: @@
 == Correlation immunity ==
-Die ''correlation immunity'' <math>m</math> ist ein Maß dafür, wie resistent eine boolesche Funktion gegen Korrelationsattacken ist, d.h. ob und wieviel Information man aus der Ausgabe einer Funktion über deren Argumente ziehen kann. Nach dem Beispiel oben ist <math>m</math> für eine XOR-Funktion hoch und für eine AND-Funktion niedrig.
+Die ''correlation immunity'' <math>m</math> ist ein Maß dafür, wie resistent eine boolesche Funktion gegen Korrelationsattacken ist bzw. ob und wieviel Information man aus der Ausgabe einer Funktion über deren Argumente ziehen kann. Nach dem Beispiel oben ist <math>m</math> für eine XOR-Funktion hoch und für eine AND-Funktion niedrig.
 Eine notwendige Bedingung für correlation immunity ist die Gleichverteilung der Ausgabe einer Funktion: Eine Funktion <math>f(X_1, X_2, \dots, X_n)</math> ist genau dann correlation immune wenn [1]:

@@ Zeile 16: / Zeile 16: @@
 Der Siegenthaler Bound ist definiert mit:
-If <math>f</math> has <math>n</math> inputs and <math>f</math> is <math>m</math>-th order correlation immune, then the nonlinear order of <math>f</math> is at most <math>n-m</math> [3]. Mathematisch:
+If <math>f</math> has <math>n</math> inputs and <math>f</math> is <math>m</math>-th order correlation immune, then the nonlinear order of <math>f</math> is at most <math>n-m</math> [2]. Mathematisch:
 <math>n - m \leq d</math>

@@ Zeile 157: / Zeile 157: @@
 <math>f(X_1,X_2) = X_1 \land X_2 = a_0 + a_1 X_1 + a_2 X_2 + a_{12} X_1 X_2</math> mit <math>a_{12} = 1</math> und allen anderen Koeffizienten null. Man erkennt sofort: Es handelt sich um ein Polynom zweiten Grades, also ist der nonlinear order <math>d=2</math>
-== Lösung des Siegenthaler bounds ([1])==
+== Lösung des Siegenthaler bounds ([3])==
 Um den Kompromiss zwischen Linearität und correlation immunity zu umgehen, kann man interne Speicher verwenden und so eine lineare Funktion mit hoher correlation immunity verwenden und mit dem Output einer nichtlinearen Funktion aus dem letzten Durchgang kombinieren: