Siegenthaler bound verständlich erklärt: Unterschied zwischen den Versionen

Aus NOBAQ
Zur Navigation springenZur Suche springen
 
(10 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt)
Zeile 12: Zeile 12:
 
<section end="head"/>
 
<section end="head"/>
  
== Siegenthaler bound ==
+
= Siegenthaler bound =
  
 
Der Siegenthaler Bound ist definiert mit:
 
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>. 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>
 
<math>n - m \leq d</math>
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.
 
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, 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:
+
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]:
  
 
<math>P(f = X_i) = \frac{1}{2}\,\,\,\,\, \forall i,\, 1 \leq i \leq n</math>
 
<math>P(f = X_i) = \frac{1}{2}\,\,\,\,\, \forall i,\, 1 \leq i \leq n</math>
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.
 
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:
 
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 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:
 
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 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:
 
Als nächstes Beispiel die Parity-Funktion für 3 Inputs:
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.
 
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.
 
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.
 
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:
 
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 140: Zeile 140:
 
* algebraic degree
 
* 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>
 
<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 148: Zeile 148:
 
Nachfolgend zwei Beispiele:
 
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>
 
<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>
 
<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 =
  
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:
+
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>
 
<math>s_j = a_j \oplus b_j \oplus c_{j-1}</math>
Zeile 167: Zeile 167:
 
Allerdings schafft diese Lösung wieder neue Angriffsmöglichkeiten (low 2-adic complexity)
 
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
 
* [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
 
* [3] Original Paper von Siegenthaler: http://ieeexplore.ieee.org/search/wrapper.jsp?arnumber=1056949
 +
 +
= Kommentare =
 +
 +
<comments />{{:{{TALKSPACE}}:{{PAGENAME}}}}
  
 
[[Kategorie:Weblog]]
 
[[Kategorie:Weblog]]

Aktuelle Version vom 2. Mai 2009, 21:52 Uhr

Bei Streamciphers in der Kryptographie ist es sehr wichtig, einen Keystream zu erstellen, der möglichst wenige Rückschlüsse auf den verschlüsselten Plaintext zulässt. Da eine Streamcipher eine Erweiterung der Vernam-Cipher ist, wird dabei der Plaintext einfach mit dem Ciphertext addiert (modulo 2):

Damit die Cipher sicher ist, soll der Keystream KS ein paar nette Eigenschaften haben:

  • Der Keystream soll wie Rauschen aussehen, das bedeutet die Autokorrelation soll sehr niedrig sein
  • Die lineare Komplexität der Folge soll möglichst hoch sein, damit die Folge eine möglichst hohe Periode hat
  • Die Folge soll von nicht-linearen Funktionen erzeugt werden (d.h. von keinem (reinen) LFSR) oder zumindest von einer Kombination aus nichtlinearen Funktionen, da für jede lineare Kombination aus LFSRs mit Berlekamp-Massey in eine alternative Darstellung als LFSR gefunden werden kann die höchstens so hoch ist, wie die LFSRs zusammen.

Siegenthaler hat 1984 gezeigt dass diese Anforderungen zum Teil im Widerspruch stehen. Da ich nach langem Suchen keine schöne Erklärung zum Siegenthaler bound, der correlation immunity und dem nonlinear order gefunden habe, versuche ich hier selbst eine verständliche Erklärung.


Siegenthaler bound

Der Siegenthaler Bound ist definiert mit:

If has inputs and is -th order correlation immune, then the nonlinear order of is at most [2]. Mathematisch:

Im Kern besagt dieser Sachverhalt, dass die Nichtlinearität einer booleschen Funktion durch die correlation immunity begrenzt ist und umgekehrt. Bei der Implementation einer Streamcipher durch nichtlineare Kombinationen aus LFSRs muss man also einen Kompromiss zwischen der correlation immunity und dem Grad der Linearität eingehen. Die Grenze ist auch abhängig von der Anzahl der Parameter n.

Intuitiv ist der Sachverhalt auch einfach nachvollziehbar: Die Wahrheitstabelle von XOR gibt genau zwei Werte mit Null aus und zwei mit Eins, der Output ist also gleichverteilt. Seien und zwei zufällige Binärfolgen (niedrige Autokorrelation), dann ergibt

ebenfalls wieder eine zufällige Folge. Verknüpft man nun einen Plaintext mit , so gibt es keine Korrelation zwischen dem resultierendem Ciphertext und dem Plaintext, da der Output der XOR Funktion gleichverteilt ist. XOR ist eine lineare Funktion.

Anders verhält es sich mit der AND Funktion: Das Ergebnis ist mit einer Wahrscheinlichkeit von Null und nur mit der Wahrscheinlichkeit von Eins. Sei nun

so ergibt die Verknüpfung von 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

Die correlation immunity 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 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 ist genau dann correlation immune wenn [1]:

Ist diese Bedingung erfüllt, so ist eine Null oder eine Eins für gleich wahrscheinlich und es gibt keine Korrelation zwischen einem Plaintext und einem Ciphertext.

Doch diese notwendige Bedingung sagt nur aus ob eine Funktion überhaupt correlation immune ist oder nicht. Besser wäre es, wenn man einen Wert für eine Funktion finden würde, die den Grad der Immunität angibt. Genau das wird auch für die Definition des Siegenthaler bound benötigt:

Eine Funktion ist correlation immune mit der Ordnung genau dann, wenn der Funktionswert statistisch unabhängig von den Eingabewerten ist und zwar genau für jede Kombination aus 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 ist definiert mit:

0 0 0
0 1 1
1 0 1
1 1 0

Beginne mit und überprüfe das erste Argument : Kennt man den Wert für , so lässt sich nichts über den Wert aussagen: Denn ist die Ausgabe Null, so kann entweder Null oder eins sein. Ist die Ausgabe eins, so ist der Wert für ebenfalls gleich wahrscheinlich. Soll nun gelten, so muss dies für alle Argumente gelten, also muss der gleiche Vorgang mit probiert werden. Es ist leicht nachvollziehbar, dass das auch für gilt. Die Funktion ist also mindestens first order correlation immune.

Setze nun . Jetzt muss die Menge der Elemente vom Ausgang statistisch unabhängig sein. Dies ist aber nicht der Fall, denn wie man leicht erkennen kann, lässt sich durch Kenntnis des Funktionswertes einiges aussagen:

  • Ist der Funktionswert null, so sind beide Eingangsvariablen gleich
  • Ist der Funktionswert eins, sind beide Eingangsvariablen unterschiedlich

Die Bedingung ist also für nicht erfüllt, also ist die correlation immunity für die XOR-Funktion 1.

Die AND Funktion

Die AND-Funktion ist definiert mit:

0 0 0
0 1 0
1 0 0
1 1 1

Setze nun wieder und überprüfe . Sehr schnell erkannt man, dass der Funktionswert von nicht statistisch unabhängig ist:

  • Sieht man am Ausgang eine Eins, so ist mit Sicherheit 1.
  • Sieht man am Ausgang eine Null, so ist mit einer Wahrscheinlichkeit von Null und mit einer Wahrscheinlichkeit von eins.

Die Bedingung ist also bereits für einen Funktionswert nicht erfüllt, also ist .

Die Parity Funktion

Als nächstes Beispiel die Parity-Funktion für 3 Inputs:

0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 0
1 1 1 1

Setzt man so erkennt man schnell - analog zum XOR Beispiel - die Unabhängigkeit von allen zum Funktionswert. Nun wird gesetzt. Nun müssen die Kombinationen , und 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 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 hingegen korreliert 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 nicht einmal die notwendige Bedinung. Die correlation immunity ist also null.

Nonlinear order

Als letzter unbekannter Parameter im Siegenthaler bound bleibt der Parameter übrig. Verwirrend dabei ist, dass dieser in der Literatur viele Namen hat:

  • nonlinear order
  • linear complexity
  • 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 Polynom anschreiben:

Analog wie in der Algebra lässt sich nun der Grad des Polynoms ablesen der gleichzeitig die Linearität einer Funktion beschreibt.

Nachfolgend zwei Beispiele:

Die XOR Funktion

mit und sowie und . Man erkennt sofort: Es handelt sich um ein Polynom ersten Grades, also ist der nonlinear order

Die AND Funktion

mit und allen anderen Koeffizienten null. Man erkennt sofort: Es handelt sich um ein Polynom zweiten Grades, also ist der nonlinear order

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]:

Allerdings schafft diese Lösung wieder neue Angriffsmöglichkeiten (low 2-adic complexity)

Referenzen

Kommentare

<comments />Diskussion:Siegenthaler bound verständlich erklärt