Message Authentification Code

Cours/Sécurité/Cryptographie/Intégrité/Message Authentification Code

Un MAC, Message authentification code est constitué d'une paire :

$S: \{0, 1\}^s \times \{0, 1\}^n \rightarrow \{0, 1\}^h$ qui signe en produisant un tag (en utilisant une clé $k$ un message $m$)
$V: \{0, 1\}^s \times \{0, 1\}^n \times \{0, 1\}^h \rightarrow \{0, 1\}$ qui vérifie (en utilisant une clé $k$, un message $m$ et son tag potentiel)
$V(k, m, S(k, m)) = 1$

Un MAC est un hash muni d'un clé de chiffrement.

Usage

On utilise le pattern encrypt then MAC pour transmettre le message : le message chiffré est concaténé au MAC du message crypté :

$$ E(k_1, m) \ ||\ \text{MAC}(k_2, E(k, m)) $$

L'utilisation de deux clés différentes est importante. Elles sont souvent dérivée d'une clé primaire $k$.

MAC sécurisé

Un MAC est sécurisé si un adversaire efficace ne peut gagner le jeu suivant, nommé existential forgery against a chosen message attack, qu'avec un avantage négligeable :

le testeur choisit uniformément une clé $k$
l'adversaire choisit q messages $m_1$ et $m_{q}$ à donner au testeur
le testeur renvoie à l'adversaire les $q$ messages signés $S(k, m_1), \dots S(k, m_q)$
l'adversaire répond un couple $(m, t)$ où $m \notin \{m_1, \dots, m_q\}$
l'adversaire gagne si $V(k, m, t) = 1$

    
     testeur                            adversaire
    ---------        m1, ..., mq       ------------
    |   k   | <----------------------- |          |  
    |       |  S(k,m1), ..., S(k,mq)   |          |
    |       | -----------------------> |          |
    |       |           (m, t)         |          |
    |       | <----------------------- |          |
    ---------                          ------------

Ce jeu simule le fait qu'un attaquant peut influencer la teneur de messages envoyés (en comptant sur un reply lors d'un envoie de mail par exemple) et ne peut forger à son tour un MAC valide.

Attaque

Remarquez qu'un MAC peut toujours être attaqué avec une probabilité au moins négligeable. Pour cela, il suffit de générer tous les tag possibles, il y en a $2^h$, pour obtenir une probabilité de succès de $1/2^h$. Ceci impose que la taille du tag doit être supérieure à $\mathcal{O}(\log_2(n))$ pour que l'adversaire ne puisse avoir une attaque brute force avec un gain non négligeable.

MAC pour message de taille fixe

MAC à taille fixe

Si $F: \{0, 1\}^s \times \{0, 1\}^n \rightarrow \{0, 1\}^n$ est une PRF, alors :

$S(k, m) = F(k, m)$
$V(k, m, t) = (F(k, m) = t)$

Est un MAC sécurisé pour tout message de taille $n$.

preuve

Soit $F$ une PRF, $(S, V)$, le MAC qui lui est associé et $A$ un algorithme efficace permettant de gagner au jeu existential forgery against a chosen message attack contre $(S, V)$ avec une probabilité $\epsilon(n)$.

Soit $H$ une fonction réellement aléatoire et $(S^\star, V^\star)$, le MAC qui lui est associé. L'algorithme $A$ ne peut gagner au jeu qu'avec une probabilité inférieure à $1/2^n$ puisque $H$ est uniformément répartie.

On peut maintenant créer un algorithme efficace $B$ jouant au jeu de la distinguabilité pour la PRF F :

    testeur ND                                     adversaire
    -----------                             ----------------------
 b  |         |             m               |              ------|
--->|  k, H   |<----------------------------|--------------|    ||
    |         |  F(k, m) si b=1 sinon H(m)  |              |    ||
    |         |-----------------------------|------------->|    ||
    |         |                             | m'   (m', t) | A  ||
    |         |<----------------------------|---  <--------|    ||
    |         | F(k, m') si b=1 sinon H(m') | r            ------|    
    |         |-----------------------------|--->                | rép(b)=(r=t)
    |         |                             |                    |-------------->   
    -----------                             ----------------------

Cet adversaire est efficace puisque A l'est et on a les probabilités :

$Pr[B(F(k,\cdot), 1) = 1] = \epsilon(n)$
$Pr[B(F(k,\cdot), 0) = 1] \leq 1/2^n$

Son avantage est donc $\epsilon(n) - 1/2^n$. Or $F$ est une PRF cet avantage ne peut être que négligeable : $\epsilon(n)$ est négligeable.

MAC à taille variable

L'idée est de découper le message en paquets de taille identique et d'appliquer itérativement des MAC à taille fixe. Il faut bien sur encoder tout le message et pas juste une partie, sinon il est facile pour un attaquant de forger un nouveau message ayant même tag qu'un message précédent

Utiliser une fonction de hash

HMAC

Soient :

$M: \{0, 1\}^s \times \{0, 1\}^n \rightarrow \{0, 1\}^n$ un MAC à taille fixe
$H: \{0, 1\}^\star \rightarrow \{0, 1\}^n$ une fonction de hash cryptographique

Alors :

$S(k, m) = M(k, H(m))$
$V(k, m, t) = (S(k, m) = t)$

Est un MAC sécurisé pour tout message.

preuve

TBD

One-time MAC

Cette technique est utilisée pour assurer l'intégrité des messages chacha20 (voir partie AEAD).

TBD utilisé pour le AEAD de chacha20 avec poly1305

Ces macs sont très simple à mettre en œuvre, mais ils sont, comme le code de Vernam très sensibles à la clé : il ne faut pas la réutiliser.

Ils sont basés sur les fonctions de hash universelles, dont nous n'allons pas plus parler ici. Pour plus d'info :

Universal hash function

Comme le message $m$ est une suite de 0 et de 1, on peut très bien le considérer comme un nombre. On va se placer dans le corps $\mathbb{Z}/p\mathbb{Z}$, avec $p$ premier.

Le one-time MAC que l'on considère est :

$$ MAC((a, b), m) = a\cdot m + b \mod p $$

Si $p$ possède $|p|$ bits, le $MAC$ est définit sur $\{0, 1\}^{2|p|} \times \{0, 1\}^\star \rightarrow \{0, 1\}^{|p|}$.

Posséder $(m, c)$ avec $c = a\cdot m + b \mod p$ ne donne pas d'informations sur (a, b). Il y a $p$ paires possibles puisqu'une fois $a$ choisi, $b = c- a\cdot m \mod p$.

Supposons que Mallory choisisse la paire $(a^\star, c- a^\star\cdot m \mod p)$ et remplace le message $m$ par $m'$. Il enverra le couple $(m', c')$ avec $c' = a^\star\cdot m' + (c- a^\star\cdot m) \mod p = a^\star(m'-m) + c \mod p$.

Lorsque Bob va décoder le message il voudra vérifier que :

$$ am'+b \mod p = a^\star(m'-m) + c \mod p $$

et donc que :

$$ \begin{array}{lcl} am'+b \mod p &=& a^\star(m'-m) + am+b \mod p\\ a(m'-m) \mod p &=& a^\star(m'-m) \mod p\\ a \mod p &=& a^\star \mod p\\ \end{array} $$

Il n'y a donc qu'une probabilité de $1/p$ que cela arrive. Si la taille de $p$ est supérieure à 128b, c'est sécurisé.

Il ne faut cependant pas réutiliser la clé !

Si on envoie deux messages :

$(m, c)$ avec $c=a\cdot m + b \mod p$
$(m', c')$ avec $c'=a\cdot m' + b \mod p$

Mallory possède deux équations à deux inconnues, ce qui lui permet de déterminer $a$ et $b$.

Enfin, en l'état, il faut que $m \leq p$ ce qui donne une taille de MAC égale à $m$, ce qui est non acceptable. La solution communément utilisée est de compresser $m$. Plusieurs méthodes sont possibles, la plus simple est de découper $m$ en bouts $m_i$ de taille de la clé et d'effectuer :

$$ c = \sum_i a_i \cdot m_i + b \mod p $$

exemple tiré de ce texte

Faire grossir un MAC à taille fixe

Cette technique est utilisée pour assurer l'intégrité des messages AES (voir partie AEAD).

Cela semble la manière la plus naturelle et cependant c'est la plus risquée. Pour garantir la sécurité du MAC, il faut en effet utiliser 2 clés de chiffrement :

$k_1 = F(k, 0)$
$k_2 = F(k, 1)$

Et itérer sur des tailles fixe de message

on découpe le message en d messages $m_i$
$t_0 = 0$
$t_i = F(k_1, t_{i-1} \oplus m_i)$
si le dernier message est plus petit que $n$ on concatène avec 10000 avant de le chiffrer en $t_l$
en fin on applique la seconde clé pour rendre le MAC final : $F(k_2,t_l)$.

Attention

Il Faut cependant faire très attention à ce que l'on fait

Place du $\oplus$

Faire un XOR de tous les bouts de messages puis appliquer un MAC à taille fixe n'est pas ok non plus car il suffit d'ajouter deux block identiques pour avoir le même XOR
faire un MAC sur chaque bout puis un XOR est aussi pas bon puisque l'ordre des paquets n'est pas important dans cette construction : on peut forger un nouveau message ayant même tag en inversant deux bout de messages

Padding

Attention à la forme du Padding si le padding est une constante, on peut forger un autre message :

$mi \ ||\ 0000$ = même hash que $m_{i+1} \ ||\ 000$ avec $m_{i+1} = m_i \ ||\ 0$

On peut par exemple prendre un padding valant :

1000000...
la taille du message nnnnnn

Utilisation de deux clés

Si on ne prend pas de seconde clé, ce n'est pas sécurisé :

$(m \ ||\ t \oplus m, t)$ est un nouveau message si $t=F(k, m)$

$t_1 = F(k, m)$
$t_2 = F(k, t \oplus t \oplus m) = F(k, m) = t$