Title: Kryptoanalyse Symmetrischer Verfahren CheatSheet
Description: A student-made German summary of the different topics introduced in the course "Kryptoanalyse symmetrischer Verfahre" offered by Prof. Marian Margraf at the Freie Universität Berlin. This serves as a help tool in preparing for the exam.

Kryptoanalyse symmetrischer Verfahren

Document progress:

Gedächtnisprotokoll strukturell zeigen
Themengebiete und relevante Begriffe (ohne Beschreibung)
Externe nutzvolle Literatur
Wichtige Definitionen und Zusammenfassungen

Read-only access link: https://hackmd.io/@PancakeMan/B1LwQOz09

Do you have read-only access and would like to make changes? Contact me to get editorial rights.
Mail: mahmoud.gharra@gmail.com

Visuellisierung der Vorlesungsthemen

Mindmap von dem gesamten Stoff:

https://miro.com/welcomeonboard/b1JkUzl6Yk5MSGhWWUZkaUFCcjA3SFNrQ2lQeXFBd041eUZWWG8xY3BDYWYzakNWcnRXYUdnNzNGNTJuZ0l5a3wzNDU4NzY0NTMwOTIyMzQ3NjAz?share_link_id=818736228054

Gedächtnisprotokolle

Protokoll #1

Das Gedächtnis Protokoll eines Mitstudierenden, der mit Stromchiffren angefangen hat.

Stromchiffren:
- Die verschiedenen Eigenschaften
- Wie ist sowas aufgebaut?
- Was macht f besonders?
- 3 Varianten von stromchiffren: otp, lfsr und counter Mode.
OTP
Was ist "Perfect Security"?
Lineare & algebraische kryptoanalyse
- Was brauche ich?
- Was mache ich und warum?
Die Gütekriterien
Differentielle Kryptoanalyse kam nicht vor

Protokoll #2

Gerne euren eigenen einfügen

Externe nutzvolle Literatur

ALGEBRAIC ATTACKS ON CERTAIN STREAM CIPHERS: https://madoc.bib.uni-mannheim.de/1352/1/Armknecht.pdf
Correlation Attacks on Wikipedia: https://en.wikipedia.org/wiki/Correlation_attack
Paper Correlation Attack on LFSRs: https://eprint.iacr.org/2018/522.pdf
Wikipedia Article on Differential Cryptoanalysis: https://en.wikipedia.org/wiki/Differential_cryptanalysis
Very basic Article on GeeksForGeeks about differential and linear Cryptoanalysis: https://www.geeksforgeeks.org/differential-and-linear-cryptanalysis/
An explanation of algebraic Cryptanalysis https://www.esat.kuleuven.be/cosic/blog/algebraic-cryptanalysis/
Paper on Algebraic Cryptanalysis using Gröbner bases: https://tuprints.ulb.tu-darmstadt.de/1060/1/Andrey.Pyshkin_Dissertation.pdf
Die gesamte 12. VL: https://www.semanticscholar.org/paper/Algebraic-Attacks-on-Stream-Ciphers-with-Linear-Courtois-Meier/526fe83e0eb8aec7eda4ab84311f20c0dc807e42
YouTube Videos eines deutschen Prof. an der Ruhr University Bochum (Ich wünschte, ich hätte die Kanal füherrü entdeckt): https://www.youtube.com/channel/UC1usFRN4LCMcfIV7UjHNuQg/videos

Themengebiete

Hier werden alle Themen und Begriffe erwähnt, die in der VL vorkamen. Ein/e StudentIn kann die Liste durchgehen, und schauen, was er/sie versteht, und was nicht.

Einführung

Verschlüsslungsverfahren: Definition.
- Schlüssel, Plaintext, Ciphertext
- Substitution als erstes symmetrischer Kryptoverfahren
  1. Caesar
  2. Vigenere
Das Kerchoffsche Prinzip
Sicherheitsniveau: Wie messen wir Sicherheit?
Mögliche Angriffsszenarien (die wir betrachten):
- ciphertext-only, known plaintext, chosen-plaintext, chosen-ciphertext, chosen-text.

Informations- und Komplexitätstheorie

Perfekte Sicherheit
- Shannon
Beweisbare Sicherheit
- Pseudo-random Number Generator (PRNG)
Praktische Sicherheit: Sicher gegen bekannte Angriffe
- Angriffe auf symmetrische Verfahren
  - lineare- und differentielle Kryptoanalyse
  - Designkriterien zur Verhinderung der Angriffe
- Angriffe auf asymmetrische Verschlüsselung
  - Faktoriesierung, Diskretes Logarithmusproblem.
  - Ableitung von Schlüssellängen

Blockchiffren: Modes of Operation

Die Ziele von Shannon:
- Grundbausteine:
  1. Substitution
  2. Permutation
  3. Schlüsseladdition
- Die Ziele:
  1. Diffusion (Durchmischung): Permutations
  2. Konfusion (Komplexität/Nichtlinearität): Substitution
Betriebsarten:
- Elektronic Code Book (ECB)
- Cipher Block Chaining (CBC)
- Counter Mode

Lineare Kryptoanalyse

Definition:
- Verdeckte Linearität
- Nichtlinearität
- Potential
- Rundenanzahl
- Erfolgswahrscheinlichkeit
Die Rolle der Permutation bei linearen Kryptoanalyse
Beispielangriff:
- FEAL-4

Differenzielle Kryptoanalyse

Definition:
- Ein- und Ausgabediff. in einem known-plaintext Angriff
- Schlüsselkandidaten
- 1-Runden-Charakteristiken
- Anzahl benötigter Paare
Verhinderung linearer und diffrenzieller Kryptoanalyse:
- Analyse der S-Boxen
- "Bei paralleler Ausführung der S-Boxen verringern sich die W'keiten."
- "Mit Anzahl der Runden verringern sich die W'keiten ebenfalls."

Algebraische Kryptoanalyse

Definition:
- Erstellung eines Gleichungssystem zur bestimmung eines Kryptoverfahren. (known plaintext attack)
- Wie kommen Polynome ins Spiel?
  - Auswertungsfunktion
  - Monomen? Affinität?
- Linearisierung
  - Gegenmaßnahmen?
Gröbner-Basen
- Varietät
- Basensuche. (Wieso ist mir gar nicht klar)
- Umkehralgorithmus als Hintertür (?)
Interpolationsattacke
- Lagrange-Interpolationsformel
- Irreduzible Polynome
- primitive Polynome
- linear unabhängigen Zeilenvektoren

Stromchiffren 1: LFSR und Periodenlänge

Ein LFSR dient als PRNG in einem Counter Mode
LFSR Eigenschaften:
- Effizient implementierbar als Hardware
- Für den Initialzustand (0, …, 0) ist die erzeugte Folge 00…
- Für LFSR mit a₀!=0 und Initialzustand (k₀, …, k_n-1)!=(0, …, 0) gilt: (k_t-n, …, k_t-1)!=(0, …, 0) für alle t>=n
- Periode is maximal 2ⁿ-1
- Angriffe gegen LFSR
LFSR algebraisch:
- Das charakteristische Polynom f
- Hauptidealring
- Rückkoplungskoeffizienten
- eine Nullstelle von f?
- primitive Nullstelle
- Trace
- Rekursionsgleichung
- Satz 9.8 "show when an LSFR has a maximal cycle, in order to have a secure system."

Stromchiffren 2: Berlekamp-Messay-Algorithmus

NICHT PRÜFUNGSRELEVANT

Stromchiffren 3: Korrelationsattacken

m LFSRs und f : F₂^m -> F₂
Förderungen/Eigenschaften für f:
- LFSRs mit max. Periode haben sehr gute statistische Eigenschaften ähnlich viele Nullen wie Einsen.
- Ist f gleichverteilt, hat auch k₀, k₁, … diese Eigenschaft
- Der Schlüsselstrom muss eine große Periode haben
Korrelationsangriffe
- Schlüsselexhaustion benötigt 2^n₁ *…*2^n_m Schritte, n₁, …, n_m seien die Längen der LFSRs 1, …, m.
- Man kann die Ausgabe von f mir der Ausgabe der jeweiligen LFSRs vergleichen
- m-resilienz
- Korrelationsimmunität
- Trade-off: resillienz von f vs. algeb. Grad von f

Stromchiffren 4: Algebraische Angriffe

Schlüsselstrom als Gleichungssystem
Zusammenhang mit Grad
Annihalator
Algebraic Immunity
Courtois-Meier (Die ganze VL ist dafür da, um diesen Satz zu beweisen)

Effiziente Berechnung kryptographischer Gütekriterien

Bestimmung Güterkriterien:
- Grad einer boolschen Funktion f
- Lineare Approximation von f
- Verteilung von f
- Korrelationsimmunität, differenzielle Attacke, Avalanche-Kriterium
Algebraische Normalform
- Wie bestimmt man aus der Wertetabelle die Polynomdarstellung (und damit den algebraischen Grad von f)?
Approximation durch lineare Funktionen (lineare Attacke)
- Blockchiffren: boolesche Abbildungen F₂ⁿ -> F₂^m (nichtlineare S-Boxen)
- Stromchiffren: boolesche Funktionen F₂ⁿ -> F₂ (nichtlin. Combiner)
Der Satz von Parseval
Berechnung der Fourier- und Walshtransformierten
Weitere kryptographische Gu ̈tekriterien
- FFT
- Avalanche-Kriterium
- Bentfunktion

Wichtige Definitionen

VL01 Einführung

Verschlüsselungsverfahren: Ein Verschlüsselungsverfahren ist definiert als (P, K, C, E, D), wo P die Menge aller Plaintexte, K die Menge aller möglichen Schlüsseln, C die Menge aller möglichen Ciphertexte sind. Außerdem sind D und E jeweils die Entschlüsselungs- und die Verschlüsselungsfunktion unseres Verfahrens.
Das Kerchoffsche Prinzip: Sei unser Verschlüsselungsverfahren öffentlich. In so einem Fall ist die Sicherheit unseres Systems allein von Geheimhaltung des eingesetzten Schlüssels abhängig.
CAESAR-Verfahren: Jeder Buchstabe wird jeweils auf eine Zahl zwichen 0 und 25 abgebildet (A->0, B->1, …, Z->25). Unser Schlüssel ist eine Zahl zwischen 0 und 25. Verschlüsselung ist eine Addition über eine mod 26. Entschlüsselung ist eine Subraktion über mod 26.
- Potenzielle Angiffe:
  - Alle 26 Schlüsseln probieren
  - Wahrscheinlichkeitsangriffe: Der Buchstabe E kommt im Englischen am Ehesten vor.
- Man kann ebenfalls jeden Buchstaben auf bijektiv auf eine Beliebige Zahl abbilden, um die Schlüsselsuche zu erschweren, dies ist aber nicht sicherer nach Tscherhov, bzw. auch nicht sicher gegen statistische Angriffe. Das führt zu einer Schlüsselmenge der Größe 26!
Vigenére-Verfahren: Ahnlich wie CAESAR, aber mir einer Schlüsselmenge!=1
- Potenzieller Angriff:
  - Vermittlung der Schlüssellänge durch Untersuchung wiederkehrender Buchstabenfolgen.
  - Nach bestimmung der Schlüsselmenge wird ein statischer Angriff gegen jeden Schlüsselbuchstaben ausgeführt.
Sicherheitsniveau: Anzahl benötigter Versuche zur Bestimmung des Schlüssels. n-Bit sicher, wenn 2ⁿ Versuche benötigt sind.
- Heute 128-Bit benötigt
Mögliche Angriffsszenarien (die wir betrachten):
- ciphertext-only: Angreifer kennt nur den Ciphertext Sekunden.
- known plaintext: Angreifer kennt einige Plaintext-Ciphertext-Paare
- chosen-plaintext: Angreifer kann zu frei wählbaren Plaintexten Ciphertexte berechnen lassen (adaptive chosen-plaintext)
- chosen-ciphertext: Angreifer kann zu frei wählbaren Ciphertexten Plaintexte berechnen lassen (adaptive chosen-ciphertext)
- chosen-text: Sowohl Plain-, als auch Ciphertext sind frei wählbar

VL02 Informations- und Komplexitätstheorie

Sicherheitsbegriffe:
- Perfekt: Sicher bei Angreifern mit unbeschränkten Ressourcen
- Beweisbar: Reduktion auf bekannte schwere Probleme
- Praktisch: Sicher gegenüber allen bekannten Angriffen
  Note: Der 2. und 3.: Nur sicher gegenüber Angreifern mit beschränkten Ressourcen.
Perfekte Sicherheit: Ein Verschlüsselungsverfahren heißt perfekt sicher, wenn für alle
$m \in P$ und
$c \in C$ gilt
$Pr (m | c) = Pr (m)$ .
Mit anderen Worten:
$m$ zu erraten ist mit oder ohne Wissen des Ciphertextes
$c$ gleich schwer. Ciphertext liefert keine Information über Plaintext.
- Satz von Shannon zur perfekten Sicherheit (Shannon 1949): Ein Verschlüsselungsverfahren mit
  $| P | = | C | \geq | K |$ und
  $Pr (m) > 0$ für alle
  $m \in P$ ist genau dann perfekt sicher, wenn gilt:
  1. die Schlüssel sind gleichverteilt,
  2. für alle
    $m \in P$ und
    $c \in C$ ex. genau ein
    $k \in K$ mit
    $E (m, k) = c$ .
    Beispiel: OTP ist perfekt sicher
Beweisbare Sicherheit: Reduktion auf bekannte schwere Probleme:
- Klassische Komplexitätsklassen (z.B. NP-schwer) nicht geeignet
- Probleme sind schwer, wenn mind. eine Instanz schwer ist. In Krypto: Problem soll für jede Instanz schwer sein
- Man kann aber zeigen: Gilt
  $P = N P$ , dann gibt es keine sichere Krypto
- Beispiel (PRNG): Unter vorraussetzung
  $P \neq N P$
Praktische Sicherheit: Sicher gegenüber allen bekannten Angriffen.

VL03 Blockchiffren, Modes of Operation

Konstruktionsprinzipien nach Shannon 1948:
- Grundbausteine:
  - Permutation: Spezielle bijektive lineare Abbildung. Wird über Listen umgesetzt. Auf den gesamten Block
  - Subtitution: Nichtlineare bijektive Abbildung. Wird über Listen umgesetzt (SBOXes). Sboxen weren auf Teilblöcken angewandt.
  - Schlüsseladdition: XOR eines Rundenschlüssels. Aus einem Schlüssel werden direkt mehrere Rundenschlüsseln erzeugt. Es darf aus einem Rundenschlüssel nicht ein weiterer Rundenschlüssel erzeugt werden.
- Shannons Ziele:
  1. Diffusion (Durchmischung): Permutationen
  2. Konfusion (Komplexität/Nichtlinearität): Substitutionen
  - wiederholte Diffusion und Konfusion erhöht Sicherheit
Modes of operation:
- Electronic Code Box (ECB)
  - Einfachste Lösung
  - Gleiche Plaintextblöcke führen zum selben Ciphertextblock
- Cipher Block Chaining (CBC)
  - Initialition Vector serves as key
  - Cipher text is used as key of next block
- Counter Mode (CTR)
  - Nonce and counter serve as key
  - counter is incremented after every block.
  - The nonce+key is hashed

VL04 Lineare Kryptoanalyse

Lineare Blockchiffren sind unsicher -> man sucht lineare Zusammäennhge zwischen m, k, und c.
Mit einer linearen Relation
$(α, β, γ)$ erhält man Information über k:
- Sammle N Plaintext-Geheimtextpaare
  $(m_{1}, c_{1}), . . ., (m_{N}, c_{N})$ Ist also eine known-plaintext Attacke
- Bestimme
  $t := | {i \leq N; ⟨ α, m_{i} ⟩ \oplus ⟨ γ, c_{i} ⟩ = 0} |$
- Ist
  $t > N / 2$ , setze
  $⟨ γ, k_{i} ⟩ = 0$ , sonst
  $⟨ γ, k_{i} ⟩ = 1$
Man greift die SBox an und versucht die Linearität des einzelnen SBoxes zu untersuchen.
das Potential
$λ_{α, β, γ}$ ist ein Wert zwischen 0 und 1 und dessen Stärke beschreibt die Zuneigung einer Funktion zu einer linearen Abbildung, die sich mit
$α$ ,
$β$ , und
$γ$ definieren lässt.
Wie lassen sich SBoxen innerhalb einer Runde kombinieren?
- Sei
  $p_{α, β, γ}$ die Wahrscheinlichkeit der Übereinstimmung einer linearen Relation mit einem SBox. Diese lassen wir al
  $1 / 2 + ϵ$ definieren.
- Das Kombinieren mehrerer SBoxen lässt sich wie folgt zeigen:
  
  $p_{α, β} = 1 / 2 + 2^{7} \prod_{i = 1}^{8} ϵ_{i}$
Die Permutation ist per Definition lineare und deren Hinzunahme hat keinen Einfluss auf die Kryptoanalyse
Lineare Kryptoanalyse über mehrere Runden
- Erfolgsw'keit sinkt bei mehreren Runden, das die W'keiten sich multiplizieren lassen. Aber nur unter der Voraussetzung, dass die Rundenschlüsseln unabhängig voneinander gewählt wurden.
  $p \leq 1 / 2 + 2^{r - 1} \prod_{i = 1}^{r} ϵ_{i}$
Anmerkungen
- Wir können nur eine untere Schranke für die Erfolgswkeit zeigen
- Für Sicherheit wird aber eine obere Schranke benötigt
- Unabhängigkeit der Rundenschlüssel ist eine wichtige Voraussetzung: Andernfalls können wir die Wkeiten nicht abschätzen
Abhängige Rundenschlüssel können die Wkeit deutlich erhöhen (siehe Dissertation von Rijmen)
Wkeit, bei N Versuchen > N/2 richtige Paare zu ziehen
- $Wkeit \approx \frac{1}{\sqrt{2 π}} \int_{- \infty}^{\sqrt{N λ}} e^{t^{2} / 2} d t$ mit
  $λ = (2 p - 1)^{2}$ (Potenzial),
  $p \approx 1 / 2$ und
  $N << 2^{n}$ .
- Für Erfolgswkeit 97.7% werden
  $N \approx 4 / λ$ Paare benötigt.
FEAL-4:
- You need to know the basic structure
- The attack:
  - Wir suchen die lineare Relation bzgl.
    $F$
  - Damit erhalten wir die folgenden lin. Relationen für
    $F$ (mit Wkeit 1!)
    1. $⟨ α_{13}, F (x) ⟩ = ⟨ α_{7, 15, 23, 31}, x ⟩$
    2. $⟨ α_{5, 15}, F (x) ⟩ = ⟨ α_{7}, x ⟩$
    3. $⟨ α_{15, 21}, F (x) ⟩ = ⟨ α_{23, 31}, x ⟩$
    4. $⟨ α_{23, 29}, F (x) ⟩ = ⟨ α_{3} 1, x ⟩ \oplus 1$
  - Somit lässt sich ein Angriff ausfuhren

VL05 Differentielle Kryptoanalyse

Einführung:
- Sei die folgendeChiffre gegeben:
  
  $c = P (S (m \oplus k^{0})) \oplus k^{1}$
- Man hat zwei Paare
  $(m_{1}, c_{1})$ und
  $(m_{2}, c_{1})$
- Man betrachtet die Differenzen und versucht dadurch Infos über den Schlüssel.
- Durch Die Linearität von
  $P$ gilt für jeden Teilschlüssel:
  
  $(m_{1})_{i} \oplus (k^{0})_{i} \in D^{i} ((Δ (m_{1}, m_{2}))_{i}, (P^{- 1} (Δ (c_{1}, c_{2})))_{i})$
- man findet den richtigen Schlüssüel, in dem man alle Plaintextpaare durchgeht. Der richtige Teilschlüssel befindet sich in allen Teilmengen.
Bei mehreren Runden spielt man mit W'Keiten.
- Man versucht die Rundensücshlüsseln von hinten nach vorne zu raten.
- Um den Angriff besser zu verstehen, kann man ihn als einen Angriff gegen die SBox betrachten. Wenn man bei der Untersuchung der Paartext-Schlüsseltext-Paare sicherstellen sollte, dass manche Input-Differenen mit einer hohen Wahrscheinlichkeit zu bestimmten Output-Differenzen führt, dann könnte man dies ausnutzen, um den Schlüssel zu extrahieren, in dem man den Ciphertext c mit dem am ehesten vorkommenden Outputs vergleicht. Man eältrh eine Liste von potenziellen Schlüsselnkandidaten. Dies tut man nur für die letzte vorletzte Runde (
  $Δ^{o, r}$ und
  $Δ^{o, r + 1}$ )
Wie verhindert man linearer und differenzieller Kryptoanalyse?
- Linearitäts- bzw. Differenzentabellen der S-Boxen.
- Bei paralleler Ausführung der S-Boxen verringern sich die Wkeiten
  – Es müssen also immer möglichst viele S-Boxen aktiv sein (Muss die Permutation P umsetzen)
- Mit Anzahl der Runden verringern sich die Wkeiten ebenfalls.

VL06-VL07 Algebraische Kryptoanalyse

angreifer kennt ein plaintext-ciphertext-paar
Goal: Lösung des Gleichungssystems
$E (m, x) = c$ mit unbekanntem
$x = (x_{1}, . . ., x_{l}) \in F_{2}^{l}$
- Eine andere Darstellung der Lösung:
  1. Wir stellen ein bekanntes Paar in einem Gleichungssystem
  2. Die Gleichung besteht aus den folgenden Projektionen aud das i-te Komponent:
    $E_{i} : F_{2}^{n} \times F_{2}^{l} ⟶ F_{2}; (m, k) \mapsto E (m, k)_{i}$
  3. Das folgende Gleichungssytem sieht wie folgt aus:
    
    $E_{1} (m, x) \oplus c_{1} = 0 ⋮ E_{n} (m, x) \oplus c_{n} = 0$
  4. Wir beschreiben die Boolischen Funktionen als Polynome und suchen deren gemeinsamen Nullstellen. Dies ist eine NP-schwere Aufgabe.
  5. Um das Problem zu vereinfachen, linearisieren wir das Gleichungssystem, durch den Ersatz von Monomen durch Unbekannte. Somit haben wir eine Laufzeit von
    $O (n^{3})$ , wo
    $n$ die Anzahl der Variablen ist. In unserem Fall ist es
    $O (l^{3 d})$
Mathe: ??? (Sehr verwirrend)
- Die Auswertefunktion ???
- Sei
  $F \in F (F_{2}^{l}, F_{2})$ eine Boolesche Funktion. Dann ist der Grad von
  $F$ der Grad des Polynoms
  $f$ mit
  $Eval (f) = F$ , dass nur aus einfachen Monomen besteht.
- Affinität:
  $f$ ist affin
  $\Leftrightarrow Grad (f) \leq 1$
- Ringe
- Einfache Monome
- Ideale
- Basen
- Varietät von
  $I$
- irreduzible Polynome
Schutz gegen algebraische Krypto:
1. Hoher algebraischer Grad von
  $f$
2. Dicht besetzte Polynome
Gröbner-Basen sind ein anderes Tool, das ebenfalls zur Vereinfachung der Lösbarkeit von Polynomsystemen durch ihre Umformulierung dient.
1. Buchberger-Algorithmus zum Finden einer Gröbnerbasis.
2. Laufzeit ist von gewählter Monomenordnung aabhngig
  $\approx$ subexponentiell.
3. Mithilfe eines Umkehralgorithmus lässt sich ein Verfahren mit einer Hintertür erstellen.
4. Die Basis ist schwer zu finden, aber sie existiert. Es ist einfacher bei Polynom-basierten asymmetrischen-Verfahren, Eine Hintertür damit zu erstellen.
Interpolationsattacke (Lagrange-Interpolationsformel)
- Sei
  $K$ ein Körper und
  $F : K ⟶ K$ ein Polynom vom Grad
  $t - 1$ . Dann lässt sich
  $F$ aus
  $t$ Paaren
  $(x_{i}, F (x_{i}))$ rekonstruieren.
  
  $F (x) = \sum_{i = 1}^{t} F (x_{i}) \prod_{j = 1 j \neq i}^{t} \frac{x - x_{j}}{x_{i} - x_{j}}$
- Damit lassen sich alle Texte entsüschlsselt, ohne den Suchlüssel zu kennen.
- Satz 7.4: Jedes Polynom kann man mithilfe einer linearen Abbildung in ein anderes Polynom umrechnen, was das gleiche Polynom ebenfalls darstellt. Es ist zu umständlig alloe mglichen linearen Abbildungen durchzugehen, um nachzuschauen, ob man das Polynom in ein viel einfacheres Polynom umrechnen lassen kann. Somit könnte man ein Polynom als ein viel komplexeres Polynom darstellen.
- linear unabhängigen Zeilenvektoren???
Zum Schluss ist es am Wichtigsten sich daran zu erinnern, dass diese Art von Angriffen sich sehr gut gegen Krypto-Verfahren eignet, deren Funktionen sich mit einem niedrigen algebraischen Grad darstellen lassen.

VL08-VL09 Stromchiffren 1: LFSR und Periodenlänge

Linear Feedback Shift Register: Definition
- Baustein vieler Blockchiffren
- Takt: Bits an den Stellen
  $a_{i} = 1$ werden abgenommen und addiert
  – alle Bits werden um eine Stelle nach rechts geschoben
  – Ergebnis wird links ins Register eingespielt
- Erste Eigenschaften:
  - Für Initialzustand
    $(0, . . ., 0)$ ist die erzeugte Folge
    $00 . . .$ .
  - Für LFSR mit
    $a_{0} \neq 0$ und Initialzustand
    $(k_{0}, . . ., k_{n - 1}) \neq (0, . . ., 0)$ gilt
    
    $(k_{t - n}, . . ., k_{t - 1}) \neq (0, . . ., 0) für alle t \geq n$
  - Erzeugter Schlüsselstrom hat eine Periode
    $\leq 2^{n} - 1$
  - Jede Bitfolge mit Periode N wird von einem LFSR erzeugt Registerlänge
    $N$ , Rückkopplung
    $(a_{0} = 1, a 1 = 0, . . ., a_{N - 1} = 0)$
Ein LFSR dient als Grundbaustein für sichere PRNG und ist alleine nicht sicher. Da ein Angriff auf einander folgende Blöcke relativ einfach ist.
Grundbaustein:
- Parallele LFSRs können taktweise als eingabe für eine Hashfunktion zur Erstellung eines neuen Schlüssels angewandt werden.
- Sollte ein PRNG benötigt werden, dann laufen die LFSR außer takt.
Wichtige Themen in dieser VL:
1. Ein LFSR ist weniger sicher, wenn er keine maximale Periode hat; wie bestimmt man,ob er diese also hat?
  - Zuerst beschreibt man LFSRs durch Polynome, um das Problem formal zu betrachten.
  - ???
  - Körper? Hauptidealringe? Polynomnullstellen? Rückkopplungskoeffizienten? Ein charaktarestisches Polynom eines LFSRs? Sind alle charakteristische Polynome irreduzibel?
  - ???
  - Goal? How do the Sätze relate to one another
  - Satz 9.1 ???
  - Satz 9.2 ???
  - Satz 9.8 Sei
    $f$ das charakteristische Polynom eines LFSR. Weiter sei
    $f$ irreduzibel,
    $Grad (f) = n$ und
    $α$ eine Nullstelle von
    $f$ . Dann existiert zu jeder vom LFSR erzeugten Folge
    $(k_{t})_{t}$ ein
    $θ \in F_{(2^{n})}$ mit
    $k_{t} = Tr (θ α^{t})$ für alle
    $t \in N$ . ???
2. Was sind die Eigenschaften von unserer Hashing-Funktion
  $F$ ?
  - Wird in VL11 behandelt
??? Lots missing

VL10 Stromchiffren 2: Berlekamp-Messay-Algorithmus

Nicht prüfungsrelevant

Wiki

VL11 Stromchiffren 3: Korrelationsattacken

Erinnerung: Wir benutzen m LFSRs und wenden
$f : F_{2}^{m} ⟶ F_{2}$ an.
Förderungen für
$f$ :
1. $f$ ist gleichverteilt.
  - LFSRs mit max. Periode haben sehr gute statische Eigenschaften ähnlich viele Nullen wie Einsen.
  - Ist
    $f$ gleichverteilt, hat auch
    $k_{0} . k_{1}, . . .$ diese Eigenschaft.
2. Der Schlüsselstrom muss eine große Periode haben.
Mögliche Angriffe gegen LFSRs:
1. Korrelationsangriffe
2. Algebraische Angriffe
Periodizität dieser Konstruktion:
- maximal, wenn alle
  $m$ LFSRs eine teilerfremde länge haben, und alle eine maximale Periode haben.
Korrelationsangriffe
- Schlüsselexhaustion benötigt
  $2^{n_{1}} . . . 2^{n_{m}}$ Schritte
  $n_{1}, . . ., n_{m}$ seien die Längen der LFSRs
  $1, . . ., m$
- Dann ist folgender Angriff möglich (known plaintext):
  
  d.h. Schlüsselstrom
  $k_{i}, . . ., k_{i + t - 1}$ sei bekannt
- ???
- Trade-offs??

VL12 Stromchiffren 4: Algebraische Angriffe

Man kann eine Stromchiffre algebraisch darstellen:

$L_{1} = (\begin{matrix} 0 & 1 & 0 & . . . & 0 \\ 0 & 0 & 1 & . . . & 0 \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ \\ 0 & 0 & 0 & . . . & 1 \\ a_{0}^{j} & a_{1}^{j} & a_{2}^{j} & . . . & a_{n - 1}^{j} \end{matrix})$

$k_{t} = f (π_{n_{1}} \circ L_{1}^{t} (k_{0}^{1}, . . ., k_{n_{1} - 1}^{m}), . . ., π_{n}^{m} \circ L_{m}^{t} (k_{0}^{m}, . . ., k_{n^{m} - 1}))$
Mathe:
- Annihalator ???
- Algebraische Immunität ???
Courtois-Meier 2003: Für alle
$f : F_{2}^{m} ⟶ F_{2}$ ist
$AI (f) \leq ⌈ m / 2 ⌉$ . (DIE GANZE VL DREHT SICH UM DIEEN SATZ!! WAS SAGT ES???)
Was ist unser Ziel in dieser VL? Was haben wir gemacht? Was ist die Schwäche? Was ist die Schwachstelle?
???
Get a better understanding of the attack

VL13 Effiziente Berechnung kryptographischer Gütekriterien

Wie lassen sich kryptographische Gütekriterien eff. bestimmen?
1. Grad einer boolschen Funktion
  $f : F_{2}^{n} ⟶ F_{2}$
2. Approximation von
  $f$ durch lineare Funktion
3. Verteilung von
  $f$ (d.h.
  $Pr (f (x) = 0)$ ).
4. Weitere kryptographische Gütekriterien:
- (Korrelationsimmunität, differenzielle Attacke, Avalanche-Kriterium)
Algebraische Normalform
- Beispiel. Betrachte
  $f (x_{1}, x_{2}) = x_{1} \cdot x_{2} \oplus 1$ . Durch Auswertung erhält man die Wertetabelle von f: f(0,0) = 1,f(0,1) = 1,f(1,0) = 1 und f(1,1) = 0.
- Grad von dem Polynom eines SBoxes mit der Normalform bestimmen, zur Messung der algebraischen Immunität.
Approximation durch lineare Funktionen
- Man nutzt die Fouriertransformierte, um die Übereinstimmung von
  $f$ und der lin. Abb.
  $x \mapsto ⟨ α, x ⟩$ zu messen.
Der Satz von Parseval ???
Bentfunktion:
- a bent function is a special type of Boolean function which is maximally non-linear
- Sie hat alles, was sich eine/e KryptografIn ünschen wwürde…Avalanche Kriterium, Anti-linear, aber nun ist sie nicht balanciert… Also kann man die Bentfunktion nicht als SBox benutzen.
Avalanche-Kriterium: Sei
$f : F_{2}^{n} ⟶ F_{2}^{m}$ .
- Bei Änderung eines Eingabebits sollen sich 50% der Ausgabebitsändern
- Bentfunktion erfullen das Avalanche-Kriterium
??? Vieles fehlt