Dans ce tp, om implémente l'algorithme de chiffrement symétrique par Bloc TEA. On l'utilisera pour créer une fonction de hachage cryptographique (calcul d'empreinte). On calculera des empreintes MD5, SHA1 et SHA256 en utilisant openssl.

Rappel de cours

TEA

Tiny Encryption Algorithm est un algorithme de chiffrement symétrique par bloc. les algorithmes de chiffrement sysmétrique par bloc crypte/decrypte des blocs entiers, en utilisant la même clé secrète (symétrique). TEA est un exemple simple de tels algorithmes (DES, AES, Blowfish) facile à implanter. La plupart de ces algorithmes utilise ce que l'on appelle un réseau de Feistel.

Réseau de Feistel

Désignons par \(K\) la clé (un mot binaire). On décompose le bloc à crypter en 2 moitiés $$(L_0,R_0)$$ On lui applique une transformation de la forme $$(L_0,R_0) \rightarrow (L_1,R_1) \mbox{ où } \left\{ \begin{matrix} L_1 & = & R_0 \\ R_1 & = & L_0 + f(R_0,K) \end{matrix}\right.$$

• La loi \( + \) doit simplement être "réversible" (une loi de groupe). Dans la pratique, il s'agit souvent d'un xor, mais pour TEA, il s'agit de l'addition binaire.
• La fonction \(f\) n'a pas besoin d'être inversible pour que la transformation précédente soit réversible. Pourquoi ? Comment fait-on ?
• Le chiffrement consiste alors à itérer la transformation (appelée round) un certain nombre de fois.

TEA

TEA crypte des blocs de 8 octets, en utilisant une clé de 16 octets.

Un cycle (2 rounds, itéré 32 fois) de TEA est donné par le réseau suivant :

En vert, il s'agit de l'addition binaire sur 32 bits, en rouge le xor.

• la clé est décomposée 4 sous-clés \(K[0],K[1],K[2],K[3]\).
• chaque round utilise un multiple de \(\delta = (\sqrt(5)-1)*2^{31}\) pour rendre les rounds non symétriques.

Voici un exemple de code correspondant :

void encrypt (uint32_t* v, uint32_t* k) {
    uint32_t v0=v[0], v1=v[1], sum=0, i;           /* set up */
    uint32_t delta=0x9e3779b9;                     /* a key schedule constant */
    uint32_t k0=k[0], k1=k[1], k2=k[2], k3=k[3];   /* cache key */
    for (i=0; i < 32; i++) {                       /* basic cycle start */
        sum += delta;
        v0 += ((v1<<4) + k0) ^ (v1 + sum) ^ ((v1>>5) + k1);
        v1 += ((v0<<4) + k2) ^ (v0 + sum) ^ ((v0>>5) + k3);
    }                                              /* end cycle */
    v[0]=v0; v[1]=v1;
}

Padding (bourrage)

Lorsque l'on cherche à crypter un fichier, sa taille n'est pas toujours un multiple de la longueur des blocs chiffrés par l'algortihme. Il existe diffèrentes techniques dites de padding. Nous utiliserons celle-ci :

• Si le dernier bloc à chiffer du fichier n'est pas entier, on écrit dans son dernier octet le nombre d'octets manquants. Les octets précédents peuvent être zéroifiés, ou remplis aléatoirement.
• Si le dernier bloc est entier, on rajoute tout un bloc pour qu'il n'y est pas d'ambiguité.

Voici un exemple avec des blocs de taille 8 octets. Le fichier en entrée est

ascii : hello word!
hex : 68 65 6c 6c 6f 20 77 6f 72 6c 64 21

Le dernier bloc est

ascii : ord!
hex : 72 6c 64 21 00 00 00 04

On ajoute des zéros (ou des octets aléatoires), et le dernier est le nombre d'octets ajoutés (ici, 4). Si le dernier bloc est complet, on rajoute tout un bloc.

hex : 00 00 00 00 00 00 00 00 08

Votre travail

1. Ecrire une fonction qui decrypte un bloc.
2. Ecrire une commande tea qui permet de (dé)chiffrer un fichier.

   tea -e|-d filekey file1 file2
   

   • filekey est le fichier ou est stocké la clé. Vous pouvez en générer en utilisant le pseudo fichier /dev/urandom, et la commande dd.
   • l'option -ecrypte. file1 est alors le fichier à crypter, file2 le fichier crypté.
   • l'option -ddecrypte. file1 est alors le fichier crypté, file2 le fichier decrypté.
3. Testez avec cette clé, et ce fichier crypté.

Fonctions de hachage cryptographque

Une fonction de hachage cryptographique qui permet de "résumer" une fichier, message en calculant une empreinte. Une telle fonction, mathématiquement, peut-être formalisée par $$\begin{matrix} \{0,1\}^{*} & \rightarrow & \{0,1\}^n \\ m &\rightarrow & f(m) \end{matrix}$$

\(n\) est la taille de l'empreinte. Elle vaut 128 pour MD5 et SHA-1.

Grâce à TEA, on va construire une telle fonction pour avec \(n=64\). Voici le principe.

• Le message ou fichier est décomposé en bloc de 24 bits (on bourrera le dernier bloc suivant le pricincipe déjà vu en ajoutant des octets avec la valeur du nombre d'octets ajoutés).
• Chaque bloc est vu comme un bloc suivi d'une clé de TEA \(x,k\) (bloc \(x\) de 8 octets, clé \(k\) de 16 octets). On calcule $$hash = tea(x,k) \oplus x$$.
• On combine le hash du bloc courant avec le hash du bloc précédent à l'aide d'un xor. Le hash finale est l'empreinte.

Votre travail

1. Implantez le fonction prédente. Testez-là. Vérifiez que pour un message "assez proche", l'empreinte est "vraiment" différente.
2. Récupérez les fichiers fichier1 et fichier2. Décompressez-les, et regardez leur contenu.
3. Calculer leur empreinte MD5 avec openssl. Conclusion ?
4. Même question avec SHA1 et SHA256.