Utilizzano blocchi per cifra invece che stream generators. $n$ bits in input and $m$ bits in output generally a key is expanded into multiple keys, one for each rounds, and applied to a round function that iterates on the $m$.

• DES 56 bit
• 3DES 56*3 bit di chiave
• AES che può andare a 128, 196 o 256 Solitamente i stream ciphers studiati in OTP and Stream Ciphers sono più veloci.

Cipher	Speed MB/sec
RC4	126
Salsa20	643
Sosemanuk	727
AES	13
3DES	109

Data Encryption Standard

- 1974 da IBM su commissione di NSA (Horst Feistel designed Lucifer at IBM in early 1970) - 1976 DES is federal standard with key-len 56 bits and block-len 64 bits.

in quel periodo era solamente fatta dalla intelligence, non c’era bisogno di comunicazioni per il pubblico in quel periodo.

• 1977 - 1998 questo era lo standard per gli stati uniti.
• best studied cipher in the world!
• Oggi insicuro, esiste una sua variante 3DES che è più sicura, ma comunque rotto
• 1997 DES broken by brute force.
• 2000 AES replaces DES.

C’è una step di **creazione delle chiavi

Feistel network

##### Definizione Feistel 🟩 Definiamo una funzione di Feistel $f(L^{i - 1}, R^{i - 1}, K^{i}) \to L^{i}, R^{i}$ la seguente:

Uno state $u^{i}$ è diviso in due parti, che vengono cifrati in questo modo: $$

\begin{cases} L^{i} = R^{i - 1}\ R^{i} = L^{i - 1} \oplus f^{i}(R^{i - 1}, K^{i}) \end{cases} $$ Dove $f$ è una funzione invertibile, se si ha la chiave.

Invertibilità di Feistel🟩

$$ \begin{cases} L^{i - 1} = R^{i} \oplus f^{i}(L^{i}, K^{i})\\ R^{i - 1} = L^{i} \end{cases} $$

Si può verificare in modo facile che funziona questo.

The $f$ functions are only used in inverse order. AES does not use those.

Theoretical result: Suppose we have a $f: K \times \left\{ 0, 1 \right\}^{n} \to \left\{ 0, 1 \right\}^{n}$ then a 3-round Feistel using the same $f$ at each step $F: K^{3}\times \left\{ 0, 1 \right\}^{2n} \to \left\{ 0, 1 \right\}^{2n}$ is a secure $PRP$ so the security is dependent on the $f$ function, which makes sense to use this function.

Funzionamento DES🟩

Quindi

1. mapping iniziale $IP$ che crea $L^{0}R^{0}$
2. rounds di Feistel
3. Poi output

La decryption è simmetrica con la conoscenza della chiave.

$f$ function in DES🟨

Dove $A$ è il 32 bit plain-text e $J$ è la chiave di $48$ bits.

Le funzioni $S$ sono tra le più importanti per la sicurezza, perché resistono a certi tipi di attacchi conosciuti (che se riesco metto in questi appunti qui sotto). Sono in pratica una mappa di 4 bit e 2 bit a un 4 bit: functions $S: \left\{ 0, 1 \right\}^{6} \to \left\{ 0, 1 \right\}^{4}$. These tables are built following some design principles: **Not linear**: $$ DES(k, m_{1}) \oplus DES(k, m_{2}) = B \begin{bmatrix} m_{1} \\ k \end{bmatrix}\oplus B \begin{bmatrix} m_{2} \\ k \end{bmatrix}= B\begin{bmatrix} m_{1} \oplus m_{2} \\ k \oplus k \end{bmatrix} $$

Another theoretical result is that if DES is linear most of the time, it would be possible to break it.

Attacchi a DES🟩

Gli attacchi maggiori (alcuni lo vengono anche come servizio commerciale) è semplicemente bruteforce perché la chiave di 56 bit usata non è che sia molto utile. (In un giorno te o rompe). Gli attacchi con known plaintext esistono, ma usano un insieme di dati non feasible. di $2^{40}$ coppie di plaintext-ciphertext.

Unicità della chiave🟩-

È notabile osservare che è probabile sia in DES che AES che è molto probabile che sia unica la chiave usata per cifrare quello. Questa nota è utile per dire che se trovi quella chiave, probabilmente ti funziona anche per altre comunicazioni che utilizzano roba simile.

$$ DES:\pi_{1},\dots \pi_{56} \times \left\{ 0, 1 \right\}^{64} \to \left\{ 0, 1 \right\}^{64} $$$$ \mathbb{P} \left[ \exists k' \neq k : c = DES(k, m) = DES(k', m) \right] \leq \sum_{k' \in \left\{ 0, 1 \right\}^{56}} \mathbb{P}\left[ DES(k, m) = DES(k', m) \right] = 2^{56}\frac{1}{2^{64}} = \frac{1}{256} $$

Which means that the probability of having a key different from $k$ such that the encryption is the same is $1 / 256$.

If you do the same math for two messages we have $1 - 1 / 2^{71}$. Same thing is true for AES. This means that having one or two input pairs is enough for finding the real key.

Altre versioni di DES

Attacco a 2-DES🟩

Vorremmo trovare una coppia di chiavi $k_{1}, k_{2}$ tale che per cui $E(k_{2}, m) = D(k_{1}, c)$ ed è possibile con un meet in the middle, che dovrebbe diminuire lo spazio di ricerca. Conseguenza: Mi basta un $< 2^{63}$ e space $2^{56}$ non un $2^{112}$ per rompere la chiave con questo attacco. Per questo motivo uso un 3-DES che non permette di fare questo. Ma per essere possibile questo attacco ha bisogno della coppia $M, C$ reale. Usato su 3DES abbiamo $2^{118}$ ma da una parte abbiamo il doppio.

DESX (non impo)

Wikipedia, this is not standardized, but should resist more against meet in the middle attacks. Ha key len of $184$. (Best attach is $2^{120}$.)

$$ k_{1} \oplus E(k_{2}, m\oplus k_{3}) $$

In parole semplici ho due chiavi in più che uso per fare un xor prima di mandarlo in #Data Encryption standard normale. La cosa da notare è che non cresce la complessità di quanto ci si aspetta.

3-DES

In modo semplice per renderlo più sicuro è il 3-DES in pratica DES applicato 3 volte, con chiave lunga il triplo, quindi più resistente a brute-force.

$$ 3E(k_{1},k_{2},k_{3}, m) = E(k_{1}, D(k_{2}, E(k_{3}, m))) $$

We add a decryption because we can implement $DES$ if we want. 3 times slower. Keysize is $2^{168}$. But attach in time $2^{118}$ is present, so 3DES is usually considered secure.

Advanced Encryption Standard

It’s a substitution permutation network.

Note storiche di AES

Da un punto di vista storico è stata una competizione internazionale 1997 che poi è stata standardizzata nel 2000. Una conferenza per questo (in particolare al seconda) è stata fatta a Roma, cosa che era curiosa, solitamente non si faceva così). È stato scelto in base a

1. Sicurezza
2. Costo implementazione
3. Velocità hardware e software. (DES troppo lento e insicuro) Alla fine è un algoritmo molto parallelizzabile.

Generazione della chiave🟨-

La lunghezza della chiave decide il numero di rounds, rispettivamente 10, 12, 14. In base al fatto che usiamo 128, 192, o 256. Vedere 4.6 di (Stinson 2005). Per l’algoritmo. La cosa è che avremo una chiave di 16 bytes in output per il numero di rounds.

Funzionamento del cifrario🟩-

Definiamo le operazioni (inizio con 16 bytes (blocco da 128 bits)) SubBytes (byte-by-byte substitution using an S-box) ShiftRows (a permutation, which cyclically shifts the last three rows in the State) MixColumns (substitution that uses Galois Fields, GF(2^8) arithmetic) Add Round key (bit-by-bit XOR with an expanded key

Suboperations:

$$ \forall i,j : A_{k+1}[i, j] = S[A_{k}[i,j]] $$

Con $k$ lo step.

Mix Column is a linear transformation done independently (like $\oplus$ xor operations and similar).

Code-size vs performance

Those tables can be compressed with a code that produces that. This has trade-offs for code-size and performance, but it can be allowed to be easily stored and implemented in embedded systems (like 8-bit wrist watches).

Modes of operation

Electronic Code Book (ECB)

Il problema principale di questo metodo naïve è il fatto che posso vedere s e blocchi hanno avuto stesso input, perché non dipendono dalla posizione.

Questo non è semantically secure secondo note in OTP and Stream Ciphers#Semantic security (!)

Deterministic Counter (DETCTR)

In pratica creo stream di bytes a blocchi per cifrare

Th: questo cipher è semanticamente sicuro se la funzione $F$ usata è sicura. Ossia ha un buone garanzie teoriche se esiste e trovo tale $F$.

Cipher Block Chaining (CBC)

Lo conosci.

Una nota importante è che si può fare una analisi teorica, e sapere dopo quanti riusi di chiave è necessario cambiarla, al fine di mantenere garanzie di sicurezza.

Se si guarda le slides possiamo avere un risultato, che è circa di $2^{48}$ blocchi per CBC. Si può fare la stessa analisi per #Data Encryption Standard (per DES è di circa $2^{12}$ (se ho più di $2^{48}$ blocchi))

NOTA: CBC non è sicuro con un chosen plaintext se ho la capacità di predire gli IV Come:

1. Scelgo come mio chosen-plaintext $0$ così ho in pratica la versione criptata di $IV$.
2. Poi mando $m_{0} = IV \oplus IV_{2}$ e $m_{1} \neq m_{0}$ , se $c(m_{0})$ è uguale al primo, allora ho indovinato il messaggio. Questo chiaramente dà advantage 1 e rompe la definizione di semantic security.

Diventa sicuro solamente se $IV$ è abbastanza randomico.

Una possibilità è usare un IV creato dalla cifrazione di un Nonce, così sei abbastanza sicuro che IV sia sicuro.

Counter Mode (CTR)

molto simile al counter mode per #Electronic Code Book (ECB) però ora abbiamo IV. Anche in questo caso possiamo usare una nonce based version. Per nonce-CTR abbiamo un $2^{64}$ di usage blocks (solitamente più sicuro, e anche più veloce, quindi verrà più utilizzato).

Substitution-Permutation Networks (not required for exam)

2 componenti principali

Abbiamo un box di sostituzione e un box di permutazione. La stringa iniziale viene divisa in molti blocchi di lunghezza $m$, e in totale avrà lunghezza $lm$. Con padding finale possibile. C’è un algoritmo abbastanza generale per questo genere di cifrari, che è il 4.1 in (Stinson 2005). la cosa carina è che queste funzioni alla fine sono molto semplici da implementare, sia in hardware e software. Non so bene su security garantuess

Key generation and rounds

In un unico round, viene encryptato molte volte (un round è fra 10-20 cicli di criptazione) si chiamano iterated ciphers, e dalla chiave iniziale vengono generate 16 chiavi, una per ogni round. Questo lo chiamiamo round function e la funzione che genera le chiavi per ogni round sono key schedule.

Pseudo random function

Main definition

$$ F: K \times X \to Y $$

That has an efficient algorithm to evaluate this function. We say that this is random because we are considering three spaces of random variables (so the output should be a probability distribution over possible values!?)

Pseudo random permutation

Solamente una pseudorandom-function tale per cui inizio e fine sono le stesse, quindi è bigettiva

$$ E: K \times X \to X $$

Such that

• $E$ is easy to evaluate
• $E$ is one-to-one
• $E$ is easily invertible, a function $D: K \times X \to X$ that is invertible knowing the key.

Secure Pseudo random functions

Consider the set of all functions to $X \to Y$ as $Funs\left[ X, Y \right]$ of size $Y^{X}$. Consider $S_{F} = \left\{ F(k, \cdot) \text{ s.t. } k \in K \right\} \subseteq Funs\left[ X, Y \right]$, which has the size of the $K$ keyspace

We say that PRF is secure if a random function in $Funs\left[ X, Y \right]$ is not distinguishable (with statistical tests or similar) from $S_{F}$. This is the similar idea from previous definitions of security (advantage with statistical tests, semantic security OTP and Stream Ciphers#Security necessities for PRNGs), if this is true it means an adversary has not knowledge of the original.

Formal definition of secure PRF

We define experiments in a way similar for semantic security. $b \in \left\{ 0, 1 \right\}^{}$ we say that if $b=0$ then a PRF is sent. if $b= 1$ is sent a truly random function from $Funs$. We say that this is secure if the adversary doesn’t have any advantage.

Same thing for $PRP$.

PRF -> PRG

Let’s take a valid $PRF$ $F: K \times \left\{ 0,1 \right\}^{n} \to \left\{ 0, 1 \right\}^{n}$we want to show that we can generate a $G: K \to \left\{ 0, 1 \right\}^{nt}$

$$ G(k) = F(k, 0) \mid \dots \mid F(k, t) $$

This is easily parallelizable. Output of the generation of the truly random function is indistinguishable from output of pseudo-random thanks to security.

References

[1] Stinson “Cryptography: Theory and Practice, Third Edition” CRC Press 2005