Malléabilité (cryptographie)

La malléabilité est une propriété que peuvent posséder des protocoles cryptographiques. Un cryptosystème est dit malléable s’il est possible de transformer un chiffré d’un message m en un chiffré pour un message f(m) pour une fonction f connue sans connaître le message originel m ni obtenir d’information sur lui.

Cette propriété n’est pas toujours désirable, puisqu’elle peut permettre à un attaquant de modifier le contenus de messages. Pour l'illustration, mettons qu’une banque chiffre une transaction de la forme (150,00€, #44), pour signifier « virement de 150,00€ pour le compte #44». Un attaquant sans connaître le message pourrait appliquer la fonction $(x,y)\mapsto (100\cdot x,133)$, ce qui dans notre cas donnerait la transaction (15 000,00€, #133), qui correspond à la transaction de 15 000,00€ pour un compte cible: #133.

En revanche cette propriété permet aussi de débloquer des fonctionnalités, comme le chiffrement homomorphe, qui permet d’exécuter des calculs sur des données chiffrés sans les connaître.

Exemple de systèmes malléables

Chiffrement par flot

En cryptographie symétrique, les chiffrements par flot, qui sont conçus en prenant le ou exclusif du clair et d’un flot de bits pseudo-aléatoire (sur le principe du masque jetable) est un exemple de chiffrement malléable.

Plus formellement, on peut voir la fonction de chiffrement comme: Enc(m,k) = m ⊕ G(k) pour G un générateur de nombres pseudo-aléatoires et ⊕ désignant l’opérateur du ou exclusif. Ainsi, étant donné un second message t, un attaquant peut appliquer sur le chiffré la fonction m ⟼ m ⊕ t comme suit : Enc(m,k) ⊕ t = m ⊕ t ⊕ G(k) = Enc(m ⊕ t, k).

Chiffrement ElGamal

Dans le cadre de la cryptographie asymétrique, le cryptosystème d'ElGamal est un autre exemple de chiffrement malléable.

On rappelle que pour chiffrer un message m sous la clé publique h par ElGamal, on commence par tirer un aléa r, et on calcule ${\mathsf {Enc}}(m,pk)=(g^{r},m\cdot h^{r})$.

Ainsi si on veut appliquer au chiffrement la fonction x ⟼ 2·x, il suffit de calculer $(x,y)\mapsto (x,2\cdot y)$, ce qui nous donne pour le message $(g^{r},m\cdot h^{r})$ le résultat $(g^{r},2\cdot m\cdot h^{r})={\mathsf {Enc}}(2\cdot m,pk)$.

Pallier la malléabilité

Si la malléabilité n’est pas désirable, la cryptographie fournit néanmoins des solutions, comme la méthodologie Chiffrer puis MAC (en) dans le cadre du chiffrement symétrique, qui consiste à attacher au message un code d’authentification de message qui va garantir l’intégrité du chiffré. Le principe étant que si un attaquant est capable de modifier le chiffré par une fonction f, il sera difficile pour lui de reconstruire un MAC pour le chiffré de f(m).

Similairement, une signature numérique ou une preuve à divulgation nulle de connaissance peut être attachée au message pour arriver au même résultat en cryptographie à clef publique.

Exemples d’utilisation de la malléabilité en cryptographie

On peut remarquer que la malléabilité du chiffrement ElGamal que nous avons vu peut se généraliser et faire du chiffrement un homomorphisme multiplicatif. Similairement, une variante d'ElGamal peut donner un morphisme additif. En prenant un sous-groupe $\langle i\rangle$ où le logarithme discret est facile, on peut ainsi chiffrer m comme étant ${\mathsf {Enc}}(m,pk)=(g^{r},i^{m}\cdot h^{r})$, effectuer le déchiffrement classique, et calculer le logarithme discret de $i^{m}$, c’est-à-dire m. Cette variante est utilisée par exemple dans le système de vote Belenios.

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Malleability (cryptography) » (voir la liste des auteurs).

Annexes

Bibliographie

• [Dolev et Naor 2000] (en) Danny Dolev et Moni Naor, « Nonmalleable cryptography », SIAM Journal on Computing,‎ 2000 (DOI 10.1137/S0036144503429856)
• [Libert et al. 2014] (en) Benoît Libert, Thomas Peters, Marc Joye et Moti Yung, « Non-Malleability from Malleability: Simulation-Sound Quasi-Adaptive NIZK Proofs and CCA2-Secure Encryption from Homomorphic Signatures », Eurocrypt,‎ 2014 (lire en ligne)

Articles connexes

• Chiffrement homomorphe
• Calcul multipartite sécurisé