Le Surchiffrement vous en pensez quoi

According to Pierre Vandevenne <pierre@datarescue.com>:

En fait, et à ma connaissance toujours, pas prouvé pour la majorité des
algos symétriques. T. Pornin en sait probablement beaucoup plus sur le
sujet.

C'est malin de m'invoquer comme ça. Maintenant je me sens obligé de
répondre.


Pour la très grande majorité des algorithmes de chiffrement par blocs,
il n'est en effet pas prouvé que ces algorithmes ne sont pas des groupes
(mais c'est quand même fortement soupçonné -- disons que tomber sur une
structure de groupe serait bien étonnant, puisque rien n'a été fait
pour).

Pour un algorithme de chiffrement, je note E_K(x) = y la fonction de
chiffrement, avec K la clé, x le bloc clair et y le bloc chiffré. Quand
on parle de groupe, on parle en fait de sous-groupe du groupe des
permutations. Si on note T l'ensemble des blocs dans lesquels vivent
x et y (les blocs de 64 bits dans le cas de DES), alors E_K est une
permutation de T : chaque x est envoyé sur un y, et c'est bijectif,
c'est-à-dire que pour chaque y dans T on peut trouver un x (ça, ça veut
juste dire qu'on peut "déchiffrer" n'importe quel bloc).

Si on considère deux clés K et K', alors on peut définir le
surchiffrement comme la fonction E_K'(E_K(x)) = z : on chiffre avec
K, et on chiffre le résultat avec K'. Ce surchiffrement est une autre
permutation. Dire que l'algorithme "est un groupe" revient à dire que
pour toutes les paires de clés K et K', il existe une clé K'' telle que
E_K'(E_K(x)) = E_K''(x) pour tous les blocs x. Autrement dit, chiffrer
avec K puis avec K' revient à chiffrer avec K''. Dans ces conditions, le
surchiffrement n'apporte rien.

Maintenant, si le fait d'être un groupe implique que le surchiffrement
est inutile, ça ne veut pas dire que le surchiffrement est utile dès
que l'algorithme ne définit pas un groupe. Ce qu'on peut dire en
revanche, c'est que le surchiffrement n'affaiblit pas _si les clés
sont bien indépendantes_. C'est facile à prouver par l'absurde :

Supposons un instant que l'attaquant a une machine qui lui permet
de casser facilement du double-DES : si on lui donne E_K'(E_K(x))
pour un certain nombre de valeurs de x, la machine renvoie K et K' en
quelques secondes. Supposons maintenant que l'attaquant veut casser du
simple-DES : il a des E_K(x) pour un certain nombre de valeurs de x, il
veut retrouver K. Alors, il n'a qu'à choisir un K' aléatoire, calculer
E_K'(E_K(x)) pour tous ses x, et fourguer le tout à sa machine. La
machine lui renvoie K et K'. K', il s'en balance, puisqu'il l'a choisie,
mais K, voilà qui l'intéresse.

Autrement dit, une machine capable de casser du double-DES peut casser
du simple-DES aussi facilement. Donc double-DES n'est pas moins solide
que simple-DES. Que DES soit un groupe ou pas.


Tout ceci, bien sûr, repose sur l'idée que le surchiffrement est fait
avec une deuxième choisie aléatoirement et indépendamment. Si les clés K
et K' sont liées, tout cela saute allègrement. Le cas du XOR l'illustre
assez clairement : (x XOR K) XOR K' = x XOR (K XOR K'). Autrement dit,
chiffrer avec K puis avec K' revient à chiffrer avec K'' = K XOR K'.
Si K et K' sont choisies indépendamment, aléatoirement et uniformément
sur l'espace des clés, c'est aussi le cas de K'', et tout va bien. En
revanche, si on choisit K' comme étant, par exemple, l'inverse bit-à-bit
de K, on obtient K'' comme étant constituée uniquement de bits à 1, ce
qui fait une seule clé possible, ce qui est hautement attaquable par
recherche exhaustive.

Ce genre de chose peut marcher aussi avec des clés liés entre elles
(sans être identiques) et des algorithmes différents. Un algorithme de
chiffrement est une grosse tambouille où on fait rentrer la clé. Si on
prend le résultat et qu'on réinjecte ensuite plus ou moins indirectement
la même clé, on prend le risque de "démêler" une partie du boulot fait
par le premier chiffrement. Même si ce n'est pas le cas, il est très
difficile d'établir une certitude à ce sujet. Ce n'est donc pas un
bon design, puisque le principe de la cryptographie, c'est quand même
d'avoir des garanties de sécurité quantifiables a priori.


Par ailleurs, il existe des attaques génériques qui montrent que, quoi
qu'il advienne, le double chiffrement avec deux clés indépendantes
n'apporte pas le gain en résistance qu'on pourrait espérer. C'est le cas
du double-DES : on a 112 bits de clés (effectifs), mais ça s'attaque
en moins de 2^112 essais. De même, le triple-DES (168 bits de clés
effectifs) s'attaque en temps 2^112 et espace 2^56, donc bien en-dessous
de 2^168 (ça reste complètement infaisable, donc ne paniquez pas braves
gens : triple-DES, c'est sûr pour le moment).


Comme enfin le double ou triple chiffrement, ça veut dire 2 à 3 fois
plus de travail pour le calcul, on peut dire que ces manipulations ne
sont pas recommandées. Le cas de triple-DES n'est justifié que par un
soucis de compatibilité ascendante (avec les bonnes clés, un triple-DES
en mode "EDE" est compatible avec un simple-DES).


--Thomas Pornin

On Thu, 13 May 2004, Thomas Pornin wrote:

[snip]

Pour compléter cette longue tirade savante de Thomas, on pourra encore
mentionner le théorème de Maurer-Massey:

Une chaine de $n$ ciphers (qui utilisent des clefs statistiquement
indépendentes, c'est important !) est au moins aussi difficile à casser
que le premier cipher de la chaine.


A+

Pascal


--
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
* Pascal Junod <pascal.junod@epfl.ch> http://crypto.junod.info *
* Security and Cryptography Laboratory (LASEC) *
* Swiss Federal Institute of Technology (EPFL), CH-1015 Lausanne *
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Ce qu'on peut dire en
revanche, c'est que le surchiffrement n'affaiblit pas _si les clés
sont bien indépendantes_. C'est facile à prouver par l'absurde :

Supposons un instant que l'attaquant a une machine qui lui permet
de casser facilement du double-DES : si on lui donne E_K'(E_K(x))
pour un certain nombre de valeurs de x, la machine renvoie K et K' en
quelques secondes. Supposons maintenant que l'attaquant veut casser du
simple-DES : il a des E_K(x) pour un certain nombre de valeurs de x, il
veut retrouver K. Alors, il n'a qu'à choisir un K' aléatoire, calculer
E_K'(E_K(x)) pour tous ses x, et fourguer le tout à sa machine. La
machine lui renvoie K et K'. K', il s'en balance, puisqu'il l'a choisie,
mais K, voilà qui l'intéresse.

Autrement dit, une machine capable de casser du double-DES peut casser
du simple-DES aussi facilement. Donc double-DES n'est pas moins solide
que simple-DES. Que DES soit un groupe ou pas.
Je ne saisi pas bien le raisonnement.

Notons P la proposition suivante : "le double-DES n'est pas moins solide que
simple-DES". P est ce que l'on souhaite démontrer par le résonnement par
l'absurde. Il faut donc considérer la proposition contraire à P, notons la Q
: "le double-DES est moins solide que simple-DES" et montrer que cette
considération améne une contradiction. Mais à quel moment du raisonnement à
ton supposer Q ? On a seulement supposé "un instant que l'attaquant a une
machine qui lui permet de casser facilement du double-DES". En quoi le fait
de disposer d'une telle machine revient t il à considérer que le double-DES
est moins solide que simple-DES ?

Merci d'avance de m'aider à y voir plus clair.

Nicolas.

pornin@nerim.net (Thomas Pornin) wrote in news:c7vanp$22ir$1
@biggoron.nerim.net:

According to Pierre Vandevenne <pierre@datarescue.com>:

En fait, et à ma connaissance toujours, pas prouvé pour la majorité des
algos symétriques. T. Pornin en sait probablement beaucoup plus sur le
sujet.

C'est malin de m'invoquer comme ça. Maintenant je me sens obligé de
répondre.

Je pense que personne ne le regrette! Merci encore un fois.

According to Nicolas Delors <nospam@nospam.com>:

Je ne saisis pas bien le raisonnement.

En plus simple alors : avec une machine à casser du double-DES, je
construit une machine qui casse du simple-DES qui marche aussi bien.
Donc simple-DES ne peut pas être plus résistant que double-DES : toute
attaque qui marche sur double-DES fonctionne aussi, avec le même coût,
sur simple-DES.

Évidemment, cela n'exclue pas que simple-DES soit plus facile à attaquer
que le double-DES, mais ce n'est pas la question.


C'est un raisonnement par l'absurde si on le note ainsi : je veux
montrer la proposition P qui dit "le double-DES est au moins aussi
solide que le simple-DES". Par l'absurde, je suppose non-P, c'est-à-dire
que "le double-DES est strictement plus facile à casser que le
simple-DES". Je construit alors une machine à casser du simple-DES,
machine qui est aussi rapide que la machine à casser du double-DES,
strictement plus rapide que la meilleure machine à casser du simple-DES.
C'est une contradiction, donc non-P est absurde. Donc P est vraie.


--Thomas Pornin

"Thomas Pornin" <pornin@nerim.net> a écrit dans le message de news:
c7vanp$22ir$1@biggoron.nerim.net...

According to Pierre Vandevenne <pierre@datarescue.com>:

En fait, et à ma connaissance toujours, pas prouvé pour la majorité des
algos symétriques. T. Pornin en sait probablement beaucoup plus sur le
sujet.

C'est malin de m'invoquer comme ça. Maintenant je me sens obligé de
répondre.


Pour la très grande majorité des algorithmes de chiffrement par blocs,
il n'est en effet pas prouvé que ces algorithmes ne sont pas des groupes
(mais c'est quand même fortement soupçonné -- disons que tomber sur une
structure de groupe serait bien étonnant, puisque rien n'a été fait
pour).

Pour un algorithme de chiffrement, je note E_K(x) = y la fonction de
chiffrement, avec K la clé, x le bloc clair et y le bloc chiffré. Quand
on parle de groupe, on parle en fait de sous-groupe du groupe des
permutations.

Excellent et magistral exposé. Je me permettrai d'ajouter mon petit grain de
sel.

Si, pour un algorithme de chiffrement, on peut affirmer qu'en prenant au
hasard deux blocs, l'un jouant le rôle d'un bloc clair, l'autre d'un bloc
chiffré, et que par une méthode exhaustive, on puisse vérifier toutes les
clefs qui pourraient correspondre à ce ou ces chiffrements, et qu'on puisse
vérifier que le nombre correspond à une distribution de Poisson, pourrait-on
dire dans ce cas qu'il n'y a pas lieu de craindre des sous-groupes néfastes?
Vous me direz qu'il n'est pas possible de réaliser cette recherche
exhaustive avec les algorithmes par bloc bien connus.

Pourtant, avec l'algorithme SED, il est parfaitement
possible de
simuler le comportement de l'algorithme à 127 bits par un algorithme SED du
même type avec des blocs de 17 bits. En effet, il existe deux polynômes
primitifs pouvant engendrer des ensembles de corps finis caractéristique
deux. Il s'agit de 1+P^5+P^17 et 1+P^6+P^17. La recherche exhaustive
s'effectue dans ce cas sur 131071 éléments et donne une statistique valable.

Des calculs de ce type ont permis d'établir une parfaite correspondance
entre les valeurs théoriques et les résultats expérimentaux. En fait, j'ai
recherché pour ces 131071 éléments, les valeurs des rapports entre les
exponentiations discrètes générées par les deux polynômes primitifs. Dans le
tableau ci-après, on donne les valeurs théoriques, l'écart quadratique et
les valeurs expérimentales pour une distribution de Poisson où la moyenne
égale à 1. Dans le cas présent, il y a 131071 cas à envisager pouvant donner
131071 valeurs différentes du rapport en question. Certaines valeurs sont
inexistantes (i=0), d'autres se présentent une ou plusieurs fois (i=1,
2,..... 16)

Valeurs théoriques Écart quadratique Valeurs expérimentales
(2 exp 17-1) * P(i) (où * = sigma) +/- écart_quadratique
(131071/2.71828)

i = 0 48218.34 * = 219.59 48455 + 1.08 *
i = 1 48218.34 * = 219 .59 48055 - 0.74 *
i = 2 24109.17 * = 155.27 23927 - 1.17 *
i = 3 8036.39 * = 89.64 8047 + 0.12 *
i = 4 2009.09 * = 44.82 2068 + 1.31*
i = 5 401.81 * = 20.04 448 + 2.30 *
i = 6 66.96 * = 8.18 67 + 0.00 *
i = 7 9.56 * = 3.0 9 +0.14 *
i = 8 1.19 0
i = 9 0.13 1
i = 10 0.01 0
i = 11 0.00 1
i = 12..15 0.00 0
i = 16 0.00 1


Note: On pouvait également établir les statistiques pour n=7 à la place
de 17, ce qui a été fait, mais les résultats ne sont pas aussi sympathiques
car les nombres sont trop petits pour effectuer une statistique valable.

Question de surchiffrement, pour ma part, je pense que le choix de blocs
de 128 bits est largement suffisant. C'est une puissance de 2 et largement
suffisante pour décourager toute recherche exhaustive. Vouloir prévoir des
valeurs supérieures, c'est un peu avancer l'idée que les chiffrements ne
donneraient pas toutes les garanties voulues.

Etant absent prochainement de mon domicile, vos commentaires sont les
bien venus à mon adresse emilemusyck@skynet.be

Précisons toutefois (histoire de pinailler un peu), que les deux précédents
raisonnements font l'hypothèse que le temps d'opération de N chiffrements
simple-DES soit négligeable par rapport au temps que prendrait la machine
pour casser du double-DES. N est égale au nombre de textes chiffrés ou
couples de textes clairs/chiffrés nécessaires au fonctionnement de la
machine. Cette hypothèse semble toutefois parfaitement raisonnable.

On peut également généraliser la conclusion ("le double-DES est au moins
aussi solide que le simple-DES") à toute cascade d'algorithmes de
chiffrement utilisant des clés statistiquement indépendantes. Ainsi en
utilisant un raisonnement similaire, on peut énoncer le théorème suivant :
"une cascade d'algorithmes de chiffrement est au moins aussi sûre que le
plus solide des algorithmes de chiffrement de cette cascade" [1] . Ce
théorème conforte la maxime "la sécurité est une chaîne dont la résistance
est celle de son maillon le plus faible". On fait cependant dans ce cas
l'hypothèse très peu réaliste que l'attaquant n'a aucune information d'ordre
statistique sur le texte en clair qu'il souhaite obtenir. A ce propos,
Maurer et Massey donne un contre exemple du théorème dans une publication
[2] (accessible à tous). Le théorème n'est ainsi valide qu'au regard de
_pures_ attaques à textes clairs connus, à textes clairs choisis ou à textes
chiffrés choisis [3]. Il n'est donc pas valide pour une attaque à textes
chiffrés connus où l'attaquant n'a pas d'autre choix que d'exploiter le
caractère statistique du texte en clair [3].

Il est ainsi plutôt préférable de retenir le théorème de Maurer-Massey (cité
par Pascal Junod dans un précédent post) : "une cascade d'algorithmes de
chiffrement est au moins aussi sûre que le premier algorithme de cette
cascade" (moyennant une hypothèse tout à fait raisonnable similaire à celle
dont je faisais mention en début de post - cf. [2]).

Un corrollaire intéressant à ce théorème est : "Une cascade d'algorithmes de
chiffrement permutables est au moins aussi sûre que le plus solide des
algorithmes de chiffrement de cette cascade" (sans restriction, aucune, sur
le type d'attaque de l'opposant). Il est intéressant dans le sens où il peut
conduire à des applications pratiques dont la preuve de sécurité sera
clairement établie. Par exemple, on peut mettre en cascade l'algorithme du
masque jetable (ou exclusif entre le clair et la clé à usage unique) où à
chaque étage de la cascade on emploiera une clé générée par un générateur de
nombres aléatoires de conception différente. On pourra par exemple
construire une cascade à deux étages utilisant chacun un générateur dont la
sécurité est basée pour l'un sur la difficulté de factoriser des grands
nombres et pour l'autre sur le problème des logarithmes discrets. Ainsi, la
cascade restera sûre même si les mathématiciens font une avancée majeure
concernant l'un de ces deux problèmes.

Enfin pour conclure ce (trop) long post, le surchiffrement s'il est employé
devra toujours relevé d'un choix établi par un cryptographe et non par un
développeur devant réaliser une application, fût-elle très sensible.

Olivier.

[1] Even & Goldreich - On the power of cascade ciphers - 1985
[2] Maurer & Massey - Cascade ciphers : the importance of being first - 1993
[3] Description des types d'attaques courantes :
+ Textes chiffrés connus : l'attaquant n'a connaissance que des messages
chiffrés.
+ Textes clairs connus : l'attaquant a en sa disposition différents
couples de textes clairs et de textes chiffrés correspondant.
+ Textes clairs choisis : l'attaquant a la possibilité d'obtenir les
textes chiffrés correspondant aux textes clairs qu'il aura lui même choisis.
Cela est possible par exemple s'il a temporairement accès à la machine qui
chiffre.
+ Textes chiffrés choisis : l'attaquant a la possibilité d'obtenir les
textes clairs correspondant aux textes chiffrés qu'il aura lui même choisis.

On Sun, 16 May 2004, Olivier Delors wrote:

[snip]

Il est ainsi plutôt préférable de retenir le théorème de Maurer-Massey (cité
par Pascal Junod dans un précédent post) : "une cascade d'algorithmes de
chiffrement est au moins aussi sûre que le premier algorithme de cette
cascade" (moyennant une hypothèse tout à fait raisonnable similaire à celle
dont je faisais mention en début de post - cf. [2]).

Un corrollaire intéressant à ce théorème est : "Une cascade d'algorithmes de
chiffrement permutables est au moins aussi sûre que le plus solide des
algorithmes de chiffrement de cette cascade" (sans restriction, aucune, sur
le type d'attaque de l'opposant).

Pas correct. Ce "corollaire" est seulement valable si les ciphers sont
commutatifs... (ca serait le cas de stream ciphers, mais pour les blocks
ciphers, ca ne marche quasiment jamais).

clairement établie. Par exemple, on peut mettre en cascade l'algorithme du
masque jetable (ou exclusif entre le clair et la clé à usage unique) où à
chaque étage de la cascade on emploiera une clé générée par un générateur de
nombres aléatoires de conception différente. On pourra par exemple
construire une cascade à deux étages utilisant chacun un générateur dont la
sécurité est basée pour l'un sur la difficulté de factoriser des grands
nombres et pour l'autre sur le problème des logarithmes discrets. Ainsi, la
cascade restera sûre même si les mathématiciens font une avancée majeure
concernant l'un de ces deux problèmes.

Ouille ! Le masque jetable est censé utiliser un aléa "pur", afin que la
"securité parfaite" tienne, et pas un alea produit par un générateur basé
sur un problème difficile... Et qui te dit que les deux problèmes
sus-mentionnés ne sont pas liés (soyons fous !) d'une manière ou d'une
autre ?!

A+

Pascal

--
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
* Pascal Junod <pascal.junod@epfl.ch> http://crypto.junod.info *
* Security and Cryptography Laboratory (LASEC) *
* Swiss Federal Institute of Technology (EPFL), CH-1015 Lausanne *
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Un corrollaire intéressant à ce théorème est : "Une cascade d'algorithmes
de

chiffrement permutables est au moins aussi sûre que le plus solide des
algorithmes de chiffrement de cette cascade" (sans restriction, aucune,
sur

le type d'attaque de l'opposant).
Pas correct. Ce "corollaire" est seulement valable si les ciphers sont

commutatifs... (ca serait le cas de stream ciphers, mais pour les blocks
ciphers, ca ne marche quasiment jamais).
C'est ce que je voulais dire par "algorithmes de chiffrement _permutables_".

Mais c'est vrai que le terme était peut-être mal choisi et que cà aurait
mérité d'être d'avantage explicité.

Olivier.

On Mon, 17 May 2004, Olivier Delors wrote:

Pas correct. Ce "corollaire" est seulement valable si les ciphers sont
commutatifs... (ca serait le cas de stream ciphers, mais pour les blocks
ciphers, ca ne marche quasiment jamais).

C'est ce que je voulais dire par "algorithmes de chiffrement _permutables_".
Mais c'est vrai que le terme était peut-être mal choisi et que cà aurait
mérité d'être d'avantage explicité.

Désolé, le "permutable" m'avait échappé... :-|

A+

Pascal

--
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
* Pascal Junod <pascal.junod@epfl.ch> http://crypto.junod.info *
* Security and Cryptography Laboratory (LASEC) *
* Swiss Federal Institute of Technology (EPFL), CH-1015 Lausanne *
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~