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🟩

La caratteristica bella è che data la chiave questo è facilmente invertibile, anche se $f$ potrebbe non esserlo. Infatti la seguente funzione inverte in modo facile

$$ \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**:

Suppose they are linear, aka we can write $S_{i}(x) = A_{i}x \mod 2$. If this is happens, then it’s just shuffling and xors, and the whole cipher would be linear because composition of linear functions is linear. If the whole cipher is linear then something like

$$ 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.

Suppose DES is a ideal PRF (ideal secure cipher!?):

$$ DES:\pi_{1},\dots \pi_{56} \times \left\{ 0, 1 \right\}^{64} \to \left\{ 0, 1 \right\}^{64} $$

Th: $\forall m, c$ there is at most one key $k$ such that $c = DES(k, m)$ with probability $\geq 1 - \frac{1}{256} \approx 99.5\%$. Proof:

$$ \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}$.)

Considero tre chiavi e considero

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

Is a 1 byte S-box, a 256 byte table, so it is easily computable.

$$ \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

A $PRF$ defined over $(K, X, Y)$ (key, input, output space) is a function

$$ 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

$PRP$ defined over $K, X$ is a

$$ 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}$

We define

$$ 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