# 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](src/ex1/file.crypt) 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.
<div align="center">
<img src="./img/feistel.png">
</div>
##### 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 :
<div align="center">
<img src="./img/xtea.png">
</div>
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 :
```c
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.
```bash
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é](./src/ex2/key1.k), et ce [fichier
crypté](./src/ex2/fichier.crypt) sur une architecture little-endian.
4. Écrire une version de tea en mode CBC :
```bash
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.