Malléabilité (cryptographie)

La malléabilité est une propriété que peuvent posséder des protocoles cryptographiques^[1]. 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[modifier | modifier le code]

Chiffrement par flot[modifier | modifier le code]

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[modifier | modifier le code]

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é[modifier | modifier le code]

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^[2].

Exemples d’utilisation de la malléabilité en cryptographie[modifier | modifier le code]

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^[3].

Notes et références[modifier | modifier le code]

(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).

Références[modifier | modifier le code]

↑ Dolev et Naor 2000.
↑ Libert et al. 2014.
↑ Système de vote Belenios

Annexes[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

[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[modifier | modifier le code]

Portail de la cryptologie

[DolevNaor2000-1] Dolev et Naor 2000.

[LibertPetersJoyeYung2014-2] Libert et al. 2014.

[3] Système de vote Belenios

[1]

[2]

[3]

v · m Mesures de sécurité cryptographique
Cryptographie	Preuve de sécurité Sécurité inconditionnelle Niveaux d'attaques IND-CPA Principe de Kerckhoffs Malléabilité Sécurité calculatoire Confusion et diffusion
Cryptanalyse de base	Biais statistique Corrélation Dictionnaire Force brute Fréquence Indice de coïncidence Interpolation Mot probable Paramètre de sécurité
Cryptanalyse par canal auxiliaire	Acoustique Consommation Émanations EM Faute Sondage Temporel
Cryptanalyse ciblée	Clé apparentée Clé faible EFF Enigma Glissement Intégrale Linéaire / Différentielle / Différentielle impossible / Différentielle-linéaire / Boomerang Modes opératoires Modulo n Quadratique Rectangle Rencontre au milieu Vigenère χ²
Systèmes asymétriques	Clé apparentée Clé faible Homme au milieu Sécurité sémantique
Fonctions de hachage	Effet avalanche Linéaire / Différentielle Paradoxe des anniversaires Pseudo-collision
Autres	Anonymat Confidentialité Intégrité Sécurité par l'obscurité