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:**
- [x] Gedächtnisprotokoll strukturell zeigen
- [x] Themengebiete und relevante Begriffe (ohne Beschreibung)
- [x] 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:** <[e-mail]>

---

## <mark>Visuellisierung der Vorlesungsthemen</mark>
Mindmap von dem gesamten Stoff:

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

---
---

## <mark>Gedächtnisprotokolle</mark>

### Protokoll \#1
Das Gedächtnis Protokoll eines Mitstudierenden, der mit Stromchiffren angefangen hat.
1. Stromchiffren:
- Die verschiedenen Eigenschaften
- Wie ist sowas aufgebaut?
- Was macht f besonders?
- 3 Varianten von stromchiffren: otp, lfsr und counter Mode.
2. OTP
3. Was ist "Perfect Security"?
4. Lineare & algebraische kryptoanalyse
- Was brauche ich?
- Was mache ich und warum?
5. Die Gütekriterien
6. Differentielle Kryptoanalyse kam nicht vor

### Protokoll \#2
<ins>Gerne euren eigenen einfügen</ins>

---
---

## <mark>Externe nutzvolle Literatur</mark>

1. ALGEBRAIC ATTACKS ON CERTAIN STREAM CIPHERS: https://madoc.bib.uni-mannheim.de/1352/1/Armknecht.pdf
2. Correlation Attacks on Wikipedia: https://en.wikipedia.org/wiki/Correlation_attack
3. Paper Correlation Attack on LFSRs: https://eprint.iacr.org/2018/522.pdf
4. Wikipedia Article on Differential Cryptoanalysis: https://en.wikipedia.org/wiki/Differential_cryptanalysis
5. Very basic Article on GeeksForGeeks about differential and linear Cryptoanalysis: https://www.geeksforgeeks.org/differential-and-linear-cryptanalysis/
6. An explanation of algebraic Cryptanalysis https://www.esat.kuleuven.be/cosic/blog/algebraic-cryptanalysis/
7. Paper on Algebraic Cryptanalysis using Gröbner bases: https://tuprints.ulb.tu-darmstadt.de/1060/1/Andrey.Pyshkin_Dissertation.pdf
8. Die gesamte 12. VL: https://www.semanticscholar.org/paper/Algebraic-Attacks-on-Stream-Ciphers-with-Linear-Courtois-Meier/526fe83e0eb8aec7eda4ab84311f20c0dc807e42
9. 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
---
---

## <mark>Themengebiete</mark>
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.

### <ins>Einführung</ins>

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

### <ins>Informations- und Komplexitätstheorie</ins>
1. Perfekte Sicherheit
- Shannon
2. Beweisbare Sicherheit
- Pseudo-random Number Generator (PRNG)
3. 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

### <ins>Blockchiffren: Modes of Operation</ins>
1. 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
2. Betriebsarten:
- Elektronic Code Book (ECB)
- Cipher Block Chaining (CBC)
- Counter Mode

### <ins>Lineare Kryptoanalyse</ins>
1. Definition:
- Verdeckte Linearität
- Nichtlinearität
- Potential
- Rundenanzahl
- Erfolgswahrscheinlichkeit
2. Die Rolle der Permutation bei linearen Kryptoanalyse
3. Beispielangriff:
- FEAL-4

### <ins>Differenzielle Kryptoanalyse</ins>
1. Definition:
- Ein- und Ausgabediff. in einem known-plaintext Angriff
- Schlüsselkandidaten
- 1-Runden-Charakteristiken
- Anzahl benötigter Paare
2. 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."

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

### <ins>Stromchiffren 1: LFSR und Periodenlänge</ins>

1. Ein LFSR dient als PRNG in einem Counter Mode
2. 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
3. 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."

### <ins>Stromchiffren 2: Berlekamp-Messay-Algorithmus</ins>
**NICHT PRÜFUNGSRELEVANT**

### <ins> Stromchiffren 3: Korrelationsattacken</ins>

1. m LFSRs und f : F₂^m -> F₂
2. 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
3. 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

### <ins>Stromchiffren 4: Algebraische Angriffe</ins>
1. Schlüsselstrom als Gleichungssystem
2. Zusammenhang mit Grad
3. Annihalator
4. Algebraic Immunity
5. Courtois-Meier (Die ganze VL ist dafür da, um diesen Satz zu beweisen)

### <ins> Effiziente Berechnung kryptographischer Gütekriterien</ins>

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

---
---

## <mark>Wichtige Definitionen</mark>

### <ins>VL01 Einführung</ins>
- **Verschlüsselungsverfahren:** Ein Verschlüsselungsverfahren ist definiert als (P, K, C, E, D), wo P die Menge aller <ins>Plaintexte</ins>, K die Menge aller möglichen <ins>Schlüsseln</ins>, C die Menge aller möglichen <ins>Ciphertexte</ins> sind. Außerdem sind D und E jeweils die <ins>Entschlüsselungs- und die Verschlüsselungsfunktion</ins> unseres Verfahrens.

- **Das Kerchoffsche Prinzip:** Sei unser Verschlüsselungsverfahren öffentlich. In so einem Fall ist die <ins>Sicherheit</ins> unseres Systems <ins>allein von Geheimhaltung des eingesetzten Schlüssels abhängig</ins>.

- **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^n^ Versuche benötigt sind.
- Heute 128-Bit benötigt
- Mögliche Angriffsszenarien (die wir betrachten):
- <ins>ciphertext-only:</ins> Angreifer kennt nur den Ciphertext Sekunden.
- <ins>known plaintext:</ins> Angreifer kennt einige Plaintext-Ciphertext-Paare
- <ins>chosen-plaintext:</ins> Angreifer kann zu frei wählbaren Plaintexten Ciphertexte berechnen lassen (adaptive chosen-plaintext)
- <ins>chosen-ciphertext:</ins> Angreifer kann zu frei wählbaren Ciphertexten Plaintexte berechnen lassen (adaptive chosen-ciphertext)
- <ins>chosen-text:</ins> Sowohl Plain-, als auch Ciphertext sind frei wählbar

### <ins>VL02 Informations- und Komplexitätstheorie</ins>

- **Sicherheitsbegriffe:**
- <ins>Perfekt:</ins> Sicher bei Angreifern mit unbeschränkten Ressourcen
- <ins>Beweisbar:</ins> Reduktion auf bekannte schwere Probleme
- <ins>Praktisch:</ins> 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 \mathcal{P}$ und $c \in \mathcal{C}$ gilt $\text{Pr}(m|c) = \text{Pr}(m)$.
Mit anderen Worten: $m$ zu erraten ist mit oder ohne Wissen des Ciphertextes $c$ gleich schwer. Ciphertext liefert keine Information über Plaintext.
- <ins>Satz von Shannon zur perfekten Sicherheit (Shannon 1949):</ins> Ein Verschlüsselungsverfahren mit $|\mathcal{P}| = |\mathcal{C}| \geq |\mathcal{K}|$ und $\text{Pr}(m) > 0$ für alle $m \in \mathcal{P}$ ist genau dann perfekt sicher, wenn gilt:
1. die Schlüssel sind gleichverteilt,
2. für alle $m \in \mathcal{P}$ und $c \in \mathcal{C}$ ex. genau ein $k \in \mathcal{K}$ mit $E(m,k) = c$.
<ins>Beispiel:</ins> 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=NP$, dann gibt es keine sichere Krypto
- <ins>Beispiel (PRNG):</ins> Unter vorraussetzung $P\neq NP$
- **Praktische Sicherheit:** Sicher gegenüber allen bekannten Angriffen.

### <ins>VL03 Blockchiffren, Modes of Operation</ins>

- <ins>Konstruktionsprinzipien nach Shannon 1948:</ins>
- 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
### <ins>VL04 Lineare Kryptoanalyse</ins>
- Lineare Blockchiffren sind unsicher -> man sucht lineare Zusammäennhge zwischen m, k, und c.
- Mit einer linearen Relation $(\alpha, \beta, \gamma)$ 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; \langle \alpha, m_i \rangle \oplus \langle \gamma, c_i \rangle=0\}|$
- Ist $t>N/2$, setze $\langle \gamma,k_i\rangle =0$, sonst $\langle \gamma,k_i\rangle =1$
- Man greift die SBox an und versucht die Linearität des einzelnen SBoxes zu untersuchen.
- das Potential $\lambda_{\alpha, \beta, \gamma}$ ist ein Wert zwischen 0 und 1 und dessen Stärke beschreibt die Zuneigung einer Funktion zu einer linearen Abbildung, die sich mit $\alpha$, $\beta$, und $\gamma$ definieren lässt.
- Wie lassen sich SBoxen innerhalb einer Runde kombinieren?
- Sei $p_{\alpha, \beta, \gamma}$ die Wahrscheinlichkeit der Übereinstimmung einer linearen Relation mit einem SBox. Diese lassen wir al $1/2 + \epsilon$ definieren.
- Das Kombinieren mehrerer SBoxen lässt sich wie folgt zeigen:
$$ p_{\alpha, \beta} = 1/2 + 2^7 \prod^8_{i=1} \epsilon_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 \epsilon_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
- $\text{Wkeit}\approx \tfrac{1}{\sqrt{2 \pi}} \int ^{\sqrt{N \lambda}}_{- \infty}e^{t^2/2}dt$ mit $\lambda = (2p-1)^2$ (Potenzial), $p \approx 1/2$ und $N<<2^n$.
- Für Erfolgswkeit 97.7% werden $N \approx 4/\lambda$ 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. $\langle \alpha_{13},F(x)\rangle =\langle \alpha_{7,15,23,31},x\rangle$
2. $\langle \alpha_{5,15},F(x)\rangle=\langle \alpha_7,x \rangle$
3. $\langle \alpha_{15,21},F(x)\rangle = \langle \alpha_{23,31},x \rangle$
4. $\langle \alpha_{23,29},F(x)\rangle =\langle \alpha_31,x\rangle \oplus 1$
- Somit lässt sich ein Angriff ausfuhren
### <ins>VL05 Differentielle Kryptoanalyse</ins>
- 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((\Delta (m_1, m_2))_i , (P^{-1} (\Delta (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 ($\Delta^{o,r}$ und $\Delta^{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.

### <ins>VL06-VL07 Algebraische Kryptoanalyse</ins>
- angreifer kennt ein plaintext-ciphertext-paar
- Goal: Lösung des Gleichungssystems $E(m, x)=c$ mit unbekanntem $x=(x_1, ..., x_l) \in \mathbb{F}^l_2$
- 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: \mathbb{F}^n_2 \times \mathbb{F}^l_2 \longrightarrow \mathbb{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 \\ \vdots \\ 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 $\mathcal{O}(n^3)$, wo $n$ die Anzahl der Variablen ist. In unserem Fall ist es $\mathcal{O}(l^{3d})$
- Mathe: ????? (Sehr verwirrend)
- Die Auswertefunktion ???
- Sei $F \in \mathcal{F}(\mathbb{F}^l_2, \mathbb{F}_2)$ eine Boolesche Funktion. Dann ist der Grad von $F$ der Grad des Polynoms $f$ mit $\text{Eval}(f) = F$, dass nur aus einfachen Monomen besteht.
- Affinität: $f$ ist affin $\Leftrightarrow \text{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 \longrightarrow K$ ein Polynom vom Grad $t-1$. Dann lässt sich $F$ aus $t$ Paaren $(x_i, F (x_i))$ rekonstruieren.
$$ F(x) = \sum^t_{i=1} F(x_i) \prod^t_{j = 1 \\ j \neq i} \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.

### <ins>VL08-VL09 Stromchiffren 1: LFSR und Periodenlänge</ins>
- 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) \text{ 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, a1 = 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, $\text{Grad}(f) = n$ und $\alpha$ eine Nullstelle von $f$. Dann existiert zu jeder vom LFSR erzeugten Folge $(k_t)_t$ ein $\theta \in \mathbb{F}_{(2^n)}$ mit $k_t = \text{Tr}(\theta \alpha^t)$ für alle $t \in \mathbb{N}$. ?????
2. Was sind die Eigenschaften von unserer Hashing-Funktion $F$?
- Wird in VL11 behandelt
- ?????? Lots missing

### <ins>VL10 Stromchiffren 2: Berlekamp-Messay-Algorithmus</ins>
**Nicht prüfungsrelevant**

[Wiki](https://en.wikipedia.org/wiki/Berlekamp–Massey_algorithm "Wikipedia Artikel")

### <ins>VL11 Stromchiffren 3: Korrelationsattacken</ins>
- Erinnerung: Wir benutzen m LFSRs und wenden $f: \mathbb{F}^m_2 \longrightarrow \mathbb{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??

### <ins>VL12 Stromchiffren 4: Algebraische Angriffe</ins>
- Man kann eine Stromchiffre algebraisch darstellen:
$$ L_1 =
\begin{pmatrix}
0 & 1 & 0 & ... & 0 \\
0 & 0 & 1 & ... & 0 \\
\vdots & \vdots & \vdots & \ddots & \vdots\\
0 & 0 & 0 & ... & 1 \\
a^j_0 & a^j_1 & a^j_2 & ... & a^j_{n-1}
\end{pmatrix} $$

$$ k_t = f(\pi_{n_1} \circ L^t_1(k_0^1,...,k_{n_1-1}^m),...,\pi_n^m \circ L^t_m(k_0^m,...,k_{n^m-1}))$$

- Mathe:
- Annihalator ?????
- Algebraische Immunität ?????
- Courtois-Meier 2003: Für alle $f : \mathbb{F}^m_2 \longrightarrow \mathbb{F}_2$ ist $\text{AI}(f) \leq \lceil m/2 \rceil$. (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

### <ins>VL13 Effiziente Berechnung kryptographischer Gütekriterien</ins>

- Wie lassen sich kryptographische Gütekriterien eff. bestimmen?
1. Grad einer boolschen Funktion $f : \mathbb{F}^n_2 \longrightarrow \mathbb{F}_2$
2. Approximation von $f$ durch lineare Funktion
3. Verteilung von $f$ (d.h. $\text{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 \langle \alpha, x \rangle$ 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 : \mathbb{F}^n_2 \longrightarrow \mathbb{F}^m_2$ .
- Bei Änderung eines Eingabebits sollen sich 50% der Ausgabebitsändern
- Bentfunktion erfullen das Avalanche-Kriterium
- ??????? Vieles fehlt