forked from monnerat/BUT2FI_R4.B.10
194 lines
6.0 KiB
Markdown
194 lines
6.0 KiB
Markdown
# 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.
|
|
|
|
|