Chiffrer un message de taille fixe
On va analyser ici les conditions théoriques pour pouvoir chiffrer un message de taille donnée. Cette partie sera ensuite utilisé dans la suite pour chiffrer un message de taille quelconque.
Reprenons le schéma général :
k k
| |
v v
------- -------
| | | |
m --> | E | --> c --> | D | --> m
| | | |
------- -------
Avec :
- $E : \{0, 1\}^s \times \{0, 1\}^t \rightarrow \{0, 1\}^t$
- $D : \{0, 1\}^s \times \{0, 1\}^t \rightarrow \{0, 1\}^t$
Tel que : $D(k, E(k, m)) = m$ pour tout $m \in \{0, 1\}^t$
Pour tout $k \in \{0, 1\}^k$ on a :
- $f_k(x) = E(k, x)$ était une permutation de $\{0, 1\}^t$
- $f^{-1}_k(x) = D(k, x)$
Pour que ce genre de fonctions soient valides pour un usage cryptographique, il faut qu'elles soient sémantiquement sécurisées.
PRP
Définition
Soit $F: \{0, 1\}^s \times \{0, 1\}^t \rightarrow \{0, 1\}^t$ une fonction telle que :
- $F(k,\cdot)$ doit être une permutation de $\{0, 1\}^t$ pour tout $k \in \{0, 1\}^s$
- $F$ doit être implémentable par algorithme efficace.
$F$ est dite être une fonction pseudo-aléatoire sécurisée (secure PRF, pseudo random function) si tout algorithme efficace ne peut avoir qu'un avantage négligeable au jeu de la reconnaissance entre :
- une fonction $F(k, \cdot)$ pour $k$ uniformément choisie,
- une fonction $f$ uniformément choisie parmi toutes les fonctions de $\{0, 1\}^t$ dans $\{0, 1\}^t$.
Si de plus $F$ est une permutation, elle est appelée permutation pseudo-aléatoire sécurisée (secure PRP, pseudo random permutation) si tout algorithme efficace ne peut avoir qu'un avantage négligeable au jeu de la reconnaissance entre :
- une fonction $F(k, \cdot)$ pour $k$ uniformément choisie,
- une permutation $f$ uniformément choisie parmi toutes les permutations de $\{0, 1\}^t$ dans $\{0, 1\}^t$.
Une PRP est un cas particulier de PRF, mais si $n$ est grand, elle est indistinguable d'une fonction quelconque avec un avantage non négligeable :
Proposition
Une PRP ne peut être distinguée d'une fonction PRF qu'avec un avantage non négligeable par un algorithme efficace.
preuve
preuve
On considère le jeu de la reconnaissance où un algorithme efficace cherche à distinguer une fonction $F(k, \cdot)$ pour un $k$ uniformément choisi d'une fonction $f$ uniformément choisie parmi toutes les permutations de $\{0, 1\}^t$ dans $\{0, 1\}^t$.
La seule façon de distinguer une permutation d'une simple fonction est de chercher des points fixes : s'il existe $x\neq y$ tel que $f(x) = f(y)$, $f$ n'est pas une permutation. Comme les fonctions sont tirées aléatoirement, vérifier si $N$ éléments ont des images différentes a la même probabilité que savoir si $N$ éléments tirés aléatoirement sont différents. En reprenant la démonstration du paradoxe des anniversaires, cette probabilité vaut :
Le nombre de tirages $N$ est plus petit que la complexité de l'algorithme et comme celui-ci est efficace il est borné par $K\cdot n^d$ avec $d$ et $K$ deux constantes, et $n$, le paramètre de sécurité, supérieur à $t$. De là $N << 2^t$ et :
Le meilleur avantage possible que peut avoir un adversaire efficace au jeu de la reconnaissance est donc $1-\bar{p}(N, 2^t) \leq \frac{t^d}{2^t}$, qui est négligeable.
La proposition précédente fait des PRP des candidats idéaux pour pour nos méthodes de chiffrement, ce sont des bijections mais vues de l'extérieur (ie d'un adversaire) elles sont indistinguables de simples fonctions. Leur existence n'est cependant pas prouvée... Elles sont équivalentes à l'existence de fonctions à sens unique.
Les fonctions à sens unique sont une représentation de la difficulté computationnelle et sont à la base de nombreuse méthodes en cryptographie :
définition
Une fonction $F : \{0, 1\}^n \rightarrow \{0, 1\}^n$ est à sens unique si :
- il existe un algorithme efficace pour calculer $F(x)$ quelque soit $x$
- Que pour tout algorithme $G$, $Pr[F(G(F(x))) = F(x)]$ soit négligeable.
La définition stipule que $F$ soit difficile à inverser en moyenne et pas seulement dans le pire des cas comme en théorie de la complexité classique. De là, si une telle fonction existe :
- il n'existerait pas d'algorithme polynomial produisant la fonction $G(F(x)) = y$ tel que $F(y) = F(x)$
- mais il serait facile de vérifier si $F(y) = F(x)$
Et donc $P \neq NP$.
Comme on pense très fort à l'existence de problèmes dont la résolution nécessite plus qu'un algorithme polynomial pour être résolu, donc que $P \neq NP$, on croit très fort que les PRG et PRF existent.
TBD rappeler qu'on a vu ça en algorithmie.
Design du chiffrement par flux
Le chiffrement le plus générique. Il utilise habituellement d'autre méthodes de chiffrement comme composant.
En pratique
Comme l'existence d'une PRP n'étant pas prouvée, il faut prendre toute proposition de chiffrement avec pincette. Il n'est pas improbable que l'on découvre des failles de sécurité et qu'il faille changer de méthode de chiffrement (c'est arrivé et ça arrivera encore) ou qu'il faille augmenter la taille de la clé pour maintenir la confidentialité que ce soit par le développement de nouveaux ordinateur de nouvelles attaques (c'est arrivé et ça arrivera encore).
S'il faut retenir une chose c'est :
Utilisez des bibliothèques de chiffrement développés par des professionnels reconnus comme openssl.
Nécessité de la non linéarité
Pour éviter une attaque classique, nommée cryptanalyse linéaire, tous les PRP vont avoir à la fois des transformations linéaires $\oplus$, décalage ou circulation de bits ainsi que des choses non linéaire, souvent encapsulé dans des matrices de transformation appelées S-box. Il faut bien sûr que ces opérations soient choisies avec soin pour éviter tout biais, la moindre linéarité cachée pouvant être facilement utilisée comme attaque.
Le chiffrement DES, proposé par la NSA, proposait des S-box obscures qui ont toujours laissé des doutes quant à la sincérité de ses non-linéarités.
La cryptanalyse linéaire va chercher des corrélations linéaires entre le message $m$, le chiffre $c$ et la clé $k$, c'est à dire si :
Si $\epsilon$ est non négligeable, on peut en déduire un algorithme qui va exécuter $1/\epsilon$ fois cette relation et trouver avec une grande probabilité cette corrélation, et donc l'information nécessaire à sa cryptanalyse.
TBD calcul probabilité avec une binomiale $Pr[B(n, p) \geq 1]$.
Chaque méthode de chiffrement intègre ainsi en son sein des transformations non linéaires permettant de casser ce genre d'attaque.