Attaques sur les signatures RSA

Comme nous l'avons vu au chapitre 2, l'algorithme RSA permet de réaliser un schéma de signature électronique. Nous avons vu aussi que de nombreuses attaques sont apparues sur les algorithmes de signature basés sur RSA. Ces attaques ne mettent pas en cause l'algorithme RSA lui-même, mais plutôt son utilisation incorrecte. On a vu que si on n'applique aucun format particulier au message $M$, on était directement exposé à une attaque par forge existentielle ou par masquage.

Deux méthodes permettent couramment de se prémunir contre de telles attaques. La première consiste à hacher le message avant de le signer et la deuxième consiste à ajouter de la redondance au message. Ces deux méthodes peuvent se révéler également vulnérables. Ainsi, De Jonge et Chaum ont décrit dans [37] la première attaque sur un schéma de signature avec redondance. Desmedt et Odlyzko décrivent dans [38] une attaque contre le cryptosystème RSA qui peut s'appliquer au cas des signatures avec fonction de hachage. Les résultats de De Jonge et Chaum ont été étendus par Girault et Misarsky dans [50] au cas des redondances modulaires puis par Misarsky dans [66] au cas où les redondances sont séparées en plusieurs parties, en utilisant l'algorithme de réduction de réseau LLL [61]. Nous référons le lecteur à la thèse de Misarsky [68] qui décrit ces attaques en détail.

Dans ce chapitre, après avoir rappelé les différents modèles d'attaque contre un schéma de signature, on étudie les principales attaques connues s'appliquant spécifiquement aux signatures RSA. Nous montrons également qu'il est possible d'étendre l'attaque de Girault et Misarsky au cas de redondances de taille plus grande; cette attaque sera présentée à la conférence Crypto 2001 [16].

Les différents modèles d'attaque

Comme dans le cas du chiffrement, le modèle d'attaque dépend à la fois de l'objectif de l'attaquant et des ressources dont il dispose.

Lorsque l'objectif de l'attaquant est de forger la signature d'un message, sans pouvoir nécessairement le choisir à l'avance, on parle de forge existentielle. C'est le niveau de succès le plus faible. Lorsque l'attaquant veut forger la signature d'un message choisi à l'avance, il s'agit d'une forge sélective. Lorsque l'attaquant veut de plus être capable de signer n'importe quel message, on parlera de forge universelle. Enfin, le cassage total correspond au cas où l'attaquant retrouve la clef privée du signeur. C'est le niveau de succès le plus fort.

Les ressources les plus faibles de l'attaquant correspondent au cas où il ne connaît que la clef publique du signeur; on parle dans ce cas d'attaque à clé publique seule. Lors d'une attaque à signature connue, l'attaquant connaît la signature de certains messages choisis par le signeur. Enfin, lors d'une attaque à message choisi adaptative, l'attaquant peut obtenir la signature de messages de son choix. C'est l'attaque la plus puissante.

Le modèle de sécurité le plus fort correspond donc au cas où il est impossible pour un attaquant de réaliser une forge existentielle lors d'une attaque à message choisie adaptative. Autrement dit, l'attaquant ne peut pas produire lui-même une signature valide d'un message, même inintelligible, et ceci même après avoir obtenu la signature d'autres messages de son choix.

Attaque de Desmedt et Odlyzko

Il est possible d'adapter l'attaque de Desmedt et Odlyzko décrite dans le chapitre consacré à RSA au cas des schémas de signature avec redondance ou utilisant une fonction de hachage. Cette variante est décrite par Misarsky dans [67]. L'attaque s'applique au cas où le message à signer est relativement petit.

Soit $m$ le message à signer et $\mu(m)$ la fonction de hachage ou de redondance associée. On veut obtenir $\mu(m)^d \mod N$ sans connaître la clef privée $d$.

1. On commence par factoriser l'entier $\mu(m)$ en produit de petits premiers.

2. On obtient les racines $e$-èmes des petits facteurs premiers en combinant les signatures de messages dont les facteurs premiers sont aussi petits.

3. On obtient finalement la signature de $m$ en multipliant les racines $e$-èmes des petits facteurs premiers.

La complexité de l'attaque dépend de la taille de $\mu(m)$, et pas de la taille du module $N$. L'attaque ne s'applique que dans le cas où l'entier $\mu(m)$ est de petite taille, car dans le cas contraire, la probabilité qu'il se décompose en produit de petits facteurs premiers est trop faible. On évite cette attaque en choisissant $\mu(m)$ de la taille du module $N$.

Attaques sur les signatures RSA avec redondance

Une fonction de redondance $R$ est une fonction inversible prenant en entrée un message $m$ et renvoyant en sortie une chaîne de bits, telle qu'il est facile de calculer $R^{-1}$. On définit la taille de la redondance comme la taille en bits de $R(m)$ moins la taille du message $m$.

Pour signer un message $m$, on calcule:

$$s=R(m)^d \mod N$$

Pour vérifier la signature $s$, le vérifieur obtient

$$R(m)=s^e \mod N$$

retrouve le message $m$ et vérifie que $R(m)$ respecte la redondance.

Dans la suite de ce chapitre, on considère plus particulièrement les signatures RSA avec redondance fixée. Pour signer un message $m$, le signeur concatène à $m$ un block fixé $P$:

$$R(m)=P\Vert m$$

et la signature s'obtient en calculant:

$$s=(P\Vert m)^d \mod N$$

où $d$ est l'exposant privé et $N$ le module.

Plus généralement, on considère les signatures RSA à redondance affine, donnée par:

$$R(m)=\omega \cdot m+a \left\{ \begin{array}{l} w \mbox{~est la redondance multiplicative} \\ a \mbox{~est la redondance additive} \\ \end{array} \right.$$ (5.1)

Une redondance fixée à gauche $P\Vert m$ correspond à $\omega=1$ et $a=P \cdot 2^{\ell}$, tandis qu'une redondance fixée à droite $m\Vert P$ s'obtient avec $\omega=2^{\ell}$ et $a=P$.

L'attaque de De Jonge et Chaum

L'attaque de De Jonge et Chaum [37] s'applique lorsqu'une fonction de redondance affine est utilisée:

$$R(m)=\omega \cdot m+a$$

L'attaque est basée sur l'utilisation de l'algorithme d'Euclide.

Si la redondance additive $a$ est nulle, alors l'attaque s'applique quelle que soit la valeur de $\omega$, à condition que la taille de la redondance soit inférieure à la moitié de la taille du module $N$:

$$\vert$$redondance$$\vert \prec \frac{1}{2} \vert N\vert$$

Si la redondance multiplicative est égale à $1$, alors l'attaque s'applique quelle que soit la valeur de $a$, à condition que la taille de la redondance soit inférieure au tiers de la taille du module:

$$\vert$$redondance$$\vert \prec \frac{1}{3} \vert N\vert$$

La figure 5.3.1 montre un exemple de signature RSA à redondance affine pouvant être forgée par cette méthode.

L'attaque de Girault et Misarksy

L'attaque précédente a été étendue par Girault et Misarsky [50], en utilisant un algorithme dû à Okamoto et Shiraishi [70], qui est une extension de l'algorithme d'Euclide. L'attaque de Girault et Misarsky améliore l'efficacité de l'attaque de De Jonge et Chaum sur une fonction de redondance affine. De plus, l'attaque s'applique aussi lorsqu'une redondance modulaire est utilisée:

$$R(m)=\omega_1 \cdot m+ \omega_2 \cdot \phi(m)+a$$ (5.2)

où $\omega_1, \omega_2$ sont les redondances multiplicatives, $a$ est la redondance additive et $\phi(m)$ est la redondance modulaire, avec

$$\phi(m)=m \mod m_r$$

où $m_r$ est une constante.

Lorsque $R(m)$ est une fonction affine de $m$, c'est à dire lorsque $\omega_2=0$, l'attaque s'applique quels que soient $\omega_1$ et $a$, à condition que la taille de la redondance soit inférieure à la moitié de la taille du module $N$:

$$\vert$$redondance$$\vert \prec \frac{1}{2} \vert N\vert$$

Cette attaque est illustrée à la figure 5.3.2.

Dans le cas général, pour une fonction $R(m)$ donnée par (5.2), l'attaque s'applique à condition que la taille de la redondance soit inférieure à la moitié de la taille du module moins la taille de la redondance modulaire:

$$\vert$$redondance$$\vert \prec \frac{1}{2} \vert N\vert-\vert$$redondance modulaire$$\vert$$

L'attaque de Misarsky

L'attaque de Misarsky [66] étend l'attaque précédente au cas où le message $m$ et la redondance modulaire sont séparés en plusieurs parties, qui n'ont pas nécessairement la même taille:

$$R(m)=\sum\limits_{i=1}^{k_1} m_i \cdot \omega_i + \sum\limits_{j=1}^{k_2} \phi(m)_j \omega_{k_1+j}+a$$

où $w_1,w_2,\ldots$ sont les différentes redondances multiplicatives, $m_i$ sont les différentes parties du messages $m$, $\phi(m)_j$ les différentes parties de la redondance modulaire $\phi(m)$, et $a$ la redondance additive. L'attaque de Misarsky utilise l'algorithme de réduction de réseau LLL [61].

Extension de l'attaque de Girault et Misarsky

Description de l'attaque

Dans ce paragraphe, on étend l'attaque de Girault et Misarsky contre les signatures RSA à redondance affine,

$$R(m)=\omega \cdot m+a$$

pour des tailles de redondance allant jusqu'aux deux-tiers de la taille du module, comme cela est illustré à la figure 5.4.1.

$$\vert$$redondance$$\vert \prec \frac{2}{3} \vert N\vert$$

Comme l'attaque de Girault et Misarsky, notre attaque est une attaque multiplicative s'appliquant quels que soient $\omega$ et $a$ et de complexité polynomiale.

Une attaque multiplicative est une attaque dans laquelle la fonction de redondance d'un message peut s'exprimer comme combinaison multiplicative des fonctions de redondance d'autres messages. Par exemple, l'attaque de Girault et Misarsky permet de trouver trois messages $m_1$, $m_2$ et $m_3$ tels que:

$$R(m_1) \cdot R(m_2)=R(m_3) \mod N$$

Ensuite, à partir des signatures de $m_2$ et $m_3$ on peut obtenir la signature de $m_1$ avec:

$$R(m_1)^d=\frac{R(m_3)^d}{R(m_2)^d} \mod N$$

De plus, l'attaque de Girault et Misarsky est sélective, c'est à dire que le message $m_1$ peut être entièrement déterminé par l'attaquant.

Dans notre attaque, on cherche quatre messages distincts $m_1$, $m_2$, $m_3$ et $m_4$, tous de taille inférieure à un tiers de la taille du module $N$, tels que

$$R(m_1) \cdot R(m_2)= R(m_3) \cdot R(m_4) \mod N$$

Notre attaque sera seulement existentielle: on ne sera pas capable de déterminer à l'avance l'un des messages $m_1$, $m_2$, $m_3$ ou $m_4$. On obtient:

$$(\omega \cdot m_1+a) \cdot (\omega \cdot m_2+a)=(\omega \cdot m_3+a) \cdot (\omega \cdot m_4+a) \mod N$$

En notant $P=a/\omega \mod N$, on obtient:

$$(P+m_1) \cdot (P+m_2)=(P+m_3) \cdot (P+m_4) \mod N$$

et en notant:

$$\begin{array}{rclcrcl} t & = & m_3 & ~~~~~~ & y & = & m_2-m_... ... =& m_1-m_3 & ~~~~~~ & z & = & m_4-m_1-m_2+m_3 \\ \end{array}$$ (5.3)

on obtient

$$\left((P+t)+x \right) \cdot \left((P+t)+y\right)=(P+t) \cdot \left((P+t)+x+y+z\right) \mod N$$

ce qui se simplifie en:

$$x \cdot y=(P+t) \cdot z \mod N$$ (5.4)

Il faut donc trouver quatre entiers $x$, $y$, $z$ et $t$, tous de taille inférieure au tiers de la taille de $N$, qui doivent satisfaire l'équation (5.4).

D'abord, on obtient deux entiers strictement positifs $z$ et $u$ tels que:

$$P \cdot z=u \mod N$$     avec $$\left\{ \begin{array}{l} -N^\frac{1}{3} < z < N^\frac{1}{3} \\ 0<u < 2 \cdot N^\frac{2}{3} \\ \end{array} \right.$$

Cela revient à trouver une bonne approximation de la fraction $P/N$, et peut se faire en développant $P/N$ en fraction continue, c'est à dire en appliquant l'algorithme d'Euclide étendu à $P$ et $N$. On obtient une solution telle que $\vert z\vert<Z$ et $0<u<U$ si $Z \cdot U > N$, ce qui est le cas ici avec $Z=N^\frac{1}{3}$ et $U=2 \cdot N^\frac{2}{3}$.

Ensuite on sélectionne un entier $y$ tel que $N^{\frac{1}{3}} \leq y \leq 2 \cdot N^\frac{1}{3}$ et PGCD$(y,z)=1$. On calcule ensuite l'entier positif $t<y$ tel que:

$$t \cdot z=-u \mod y$$

ce qui est possible car PGCD$(y,z)=1$. Ensuite on définit l'entier $x$ tel que

$$x=\frac{u+t \cdot z}{y} \leq 4 N^\frac{1}{3}$$

et on obtient

$$P \cdot z=u=x \cdot y - t \cdot z \mod N$$

ce qui donne l'équation (5.4), avec $x$, $y$, $z$ et $t$ qui sont des entiers positifs tous inférieurs à $4 \cdot N^\frac{1}{3}$. A partir de $x$, $y$, $z$ et $t$, on obtient en utilisant (5.3) quatre messages $m_1$, $m_2$, $m_3$ et $m_4$ de taille un tiers de la taille du module $N$, tels que:

$$R(m_1) \cdot R(m_2)= R(m_3) \cdot R(m_4) \mod N$$

et on peut exprimer la signature de $m_1$ en fonction de la signature de $m_2$, $m_3$ et $m_4$.

On a donc réalisé une attaque à message choisi: l'attaquant demande la signature des messages $m_2$, $m_3$ et $m_4$, pour être ensuite capable d'exhiber la signature de $m_1$, qui n'a jamais été signé par le signeur légitime. La complexité de notre attaque est polynomiale en la taille du module $N$.

Application pratique

Dans ce paragraphe, on donne un exemple de signature forgée en utilisant un module de $1024$ bits proposé par les laboratoires RSA, dont la factorisation est encore inconnue. On prend $\omega=1$ et $a=2^{1023}-2^{352}$.

$N=$	RSA-309
$=$	bdd14965	645e9e42	e7f658c6	fc3e4c73	c69dc246	451c714e	b182305b	0fd6ed47
	d84bc9a6	10172fb5	6dae2f89	fa40e7c9	521ec3f9	7ea12ff7	c3248181	ceba33b5
	5212378b	579ae662	7bcc0821	30955234	e5b26a3e	425bc125	4326173d	5f4e25a6
	d2e172fe	62d81ced	2c9f362b	982f3065	0881ce46	b7d52f14	885eecf9	03076ca5
$R(m_1)=$	7fffffff	ffffffff	ffffffff	ffffffff	ffffffff	ffffffff	ffffffff	ffffffff
	ffffffff	ffffffff	ffffffff	ffffffff	ffffffff	ffffffff	ffffffff	ffffffff
	ffffffff	ffffffff	ffffffff	ffffffff	ffffffff	00415df4	ca4219b6	ea5fa8e4
	e2eabcfc	61348b80	e7ccbac7	3d1f5cc7	249e1519	9412886a	f76220c6	d1409cd6
$R(m_2)=$	7fffffff	ffffffff	ffffffff	ffffffff	ffffffff	ffffffff	ffffffff	ffffffff
	ffffffff	ffffffff	ffffffff	ffffffff	ffffffff	ffffffff	ffffffff	ffffffff
	ffffffff	ffffffff	ffffffff	ffffffff	ffffffff	00127f44	f753253a	a0348be7
	826e893f	693032db	c2194dbb	3b81e1c2	630b66d3	1448a3f4	7fd2d34f	b28aefd6
$R(m_3)=$	7fffffff	ffffffff	ffffffff	ffffffff	ffffffff	ffffffff	ffffffff	ffffffff
	ffffffff	ffffffff	ffffffff	ffffffff	ffffffff	ffffffff	ffffffff	ffffffff
	ffffffff	ffffffff	ffffffff	ffffffff	ffffffff	00781bd4	e0c918a7	308fcff7
	8f64044c	a35b4937	36cd37d7	93f281b5	fdd0a951	52a0479b	57dd73b2	25b6df85
$R(m_4)=$	7fffffff	ffffffff	ffffffff	ffffffff	ffffffff	ffffffff	ffffffff	ffffffff
	ffffffff	ffffffff	ffffffff	ffffffff	ffffffff	ffffffff	ffffffff	ffffffff
	ffffffff	ffffffff	ffffffff	ffffffff	ffffffff	000919fd	86e5afce	7fc11c94
	0e0827c8	03be05bb	71f8de48	c61d6d5f	0feb036d	a1ff2f8b	5f596108	3d142538

On vérifie que

$$R(m_1) \cdot R(m_2)= R(m_3) \cdot R(m_4) \mod N$$

où les messages $m_1$, $m_2$, $m_3$ et $m_4$ sont de taille un tiers de la taille du module.

Conclusion

Nous avons rappelé les principales attaques connues sur les signatures RSA, et nous avons montré comment étendre l'attaque de Girault et Misarsky sur les signatures RSA à redondance affine: nous avons décrit une attaque à message choisi pour des tailles de redondance allant jusqu'aux deux-tiers de la taille du module. Un problème intéressant consiste à essayer d'étendre cette attaque à des tailles de redondance encore plus grande, par exemple pour une redondance de taille les trois-quarts de la taille du module.

Parmi les attaques que nous avons rappelées, la plus puissante est sans doute l'attaque de Desmedt-Odlyzko, puisqu'elle ne suppose rien sur la fonction de redondance utilisée. La seule contrainte est que la taille de la fonction $\mu(m)$ soit suffisamment petite, bien inférieure à la taille de $N$, pour que $\mu(m)$ puisse se décomposer en produit de petits facteurs premiers avec forte probabilité. Nous verrons dans le prochain chapitre comment étendre l'attaque de Desmedt-Odlyzko à certains schémas de signature RSA pour lesquels la fonction $\mu(m)$ est de la taille de $N$.