BUT2FI_R4.B.10/td_tp/tp1

TP1

• Registre à décalage à rétroaction linéaire (lfsr),
• Chiffrement par bloc symmétrique (XTEA), fonction de hachage.

EX1

Le but est d'implanter un registre à décalage linéaire, sur un octet.

À chaque étape, le registre (un octet) (b_7,b_6,b_5,b_4,b_3,b_2,b_1,b_0) est décalé à gauche, et le bit b_0 est remplacé par un bit, calculé par une fonction linéaire f.

Vous disposez d'un fichier crypté avec un lfsr, en faisant un XOR de chacun des octets avec les valeurs successives du registre. L'état initial du registre était 0xa7, et la fonction utilisée

	f(b_7,b_6,b_5,b_4,b_3,b_2,b_1,b_0) = b_7\oplus b_6\oplus b_5\oplus b_4\oplus b_3\oplus b_1

Retrouver le fichier initial.

Vous pouvez utiliser la fonction interne __builtin_parity de gcc.

Ex2

eXtended 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). XTEA 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)
 \, 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.

XTEA

XTEA (cf cours) crypte des blocs de 8 octets, en utilisant une clé de 16 octets.

Un cycle (2 rounds, itéré 32 fois) de XTEA 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[2], uint32_t const key[4]) 
{
	unsigned int i;
	uint32_t v0=v[0], v1=v[1], sum=0, delta=0x9E3779B9;
	for (i=0; i < 32; i++) {
		v0 += (((v1 << 4) ^ (v1 >> 5)) + v1) ^ (sum + key[sum & 3]);
		sum += delta;
		v1 += (((v0 << 4) ^ (v0 >> 5)) + v0) ^ (sum + key[(sum>>11) & 3]);
	}
	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 xtea qui permet de (dé)chiffrer un fichier.

   xtea -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 -e crypte. file1 est alors le fichier à crypter, file2 le fichier crypté.
   • l'option -d decrypte. file1 est alors le fichier crypté, file2 le fichier decrypté.

3. Testez avec cette clé, et ce fichier crypté sur une architecture little-endian.

4. Écrire une version de tea en mode CBC :

   xtea_cbc -e|-d iv filekey file1 file2
   

   iv est le vecteur d'initialisation (8 octets) donné sur la ligne de commande.

   Rappel : en mode CBC, le bloc à chiffrer subit un XOR avec le chiffré du bloc précédent. Le vecteur d'initialisation sert pour le premier bloc.

Ex3: une fonction de hachage cryptographique avec XTEA

Une fonction de hachage cryptographique permet de "résumer" un 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 par exemple pour MD5 et SHA-1.

Grâce à XTEA, on va construire une telle fonction pour avec n=64.

Voici le principe.

• Le message ou fichier est décomposé en bloc de 24 octets (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 XTEA x,k (bloc x de 8 octets, clé k de 16 octets). On calcule hash = xtea(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.