Padding optimal pour le chiffrement et
la signature

Pour le chiffrement à clef publique, la notion de base reste la sécurité sémantique selon des attaques à chiffrés choisis . De la même façon, pour la signature, l’exigence est désormais la sécurité contre les falsifications existentielles face aux attaques à messages choisis [61]. Cependant, la sécurité forte ne suffit pas, elle doit, de surcroît, être obtenue de manière efficace selon plusieurs critères : le temps de calcul, la taille du chiffré/de la signature, et la taille du code. Les deux premiers critères cités sont courants. En effet, il existe dans la littérature des paddings rapides pour le chiffrement [10, 94] et pour la signature [11]. Concernant la bande passante, dans le chapitre précédent, nous avons proposé un padding optimal qui évite la redondance dans le chiffrement. De nombreux schémas de signature avec « reconstitution de message » (message recovery en anglais) [92, 86, 11] peuvent améliorer la bande de passante sans pour autant atteindre les solutions optimales en raison de la présence d’aléa et de redondance. Une exception à remarquer, fruit d’une idée récente de Katz et Wang, atteint une bonne réduction de sécurité en utilisant la construction FDH (« Full-Domain Hash » [11]) avec un seul bit additionnel dépendant du texte clair [71]. Pour le troisième critère, i.e. la taille du code, Coron et. al [36] ont introduit la notion de padding universel : la taille du code est réduite grâce à l’utilisation d’un padding commun pour le chiffrement et la signature. Ils ont proposé une variante de PSS, appelée PSS-ES pour la construction du padding universel. D’autres solutions, dont celle de Komano et Ohta [76], ont ensuite été proposées. Cependant, dans toutes ces constructions, le chiffrement contient de la redondance et la signature est probabiliste. 

Redondance et aléa 

Comme présenté dans le chapitre précédent, afin d’atteindre la sécurité sémantique, un chiffrement doit être probabiliste. De plus, les redondances sont souvent ajoutées aux chiffrés pour une preuve de connaissance du texte clair ou « plaintext awareness » . Nous avons également prouvé que la redondance pouvait être évitée, au moins dans le modèle de l’oracle aléatoire et dans celui du chiffrement idéal. De la même façon, afin d’obtenir la sécurité contre les falsifications, une certaine redondance doit être introduite dans le couple (message, signature) ou dans une chaîne unique en cas de reconstitution de message : sans la clef de signature, il est difficile de créer un couple (message, signature) qui satisfasse la redondance. La plupart des schémas de signature sont, de plus, probabilistes bien que ceci ne soit pas une condition nécessaire (la signature FDH est déterministe, cependant, la réduction n’est pas efficace).

Padding universel 

Il convient de noter que le padding universel est applicable en même temps au chiffrement et à la signature, avec les mêmes clefs d’utilisateur : la clef publique est utilisée pour le chiffrement et pour la vérification ; la clef privée, pour le déchiffrement et pour la signature. Même si ceci n’est pas obligatoire, dans la suite, nous considérons ce cas qui est le pire. En effet, dans le modèle de sécurité, nous considérons les attaquants (contre la sécurité sémantique ou la falsification existentielle) ayant accès au déchiffrement et à la signature. L’oracle de déchiffrement pourra donc les aider à forger des signatures, puisque la même clef est utilisée, et réciproquement au sujet de la sécurité du chiffrement. 

Modèle de sécurité pour la signature

 Les schémas de signature sont les versions électroniques des signatures manuscrites pour les documents numériques : la signature d’un utilisateur sur un message m est une chaîne qui dépend de m et de ses données publiques et secrètes. N’importe qui peut vérifier la validité de la signature en n’utilisant que des données publiques. Nous rappelons brièvement les principales notions de sécurité pour la signature [61]. Un schéma de signature S = (K, S, V) est défini par trois algorithmes : – L’algorithme de génération de clef K : sur l’entrée 1k, où k est le paramètre de sécurité, l’algorithme probabiliste K génère un couple clef publique, clef secrète (pk,sk). On appelle k le paramètre de sécurité. Les tailles des clefs ainsi que les autres paramètres dans le schéma dépendent de ce paramètre. – L’algorithme de signature S : étant donné un message m (dans l’espace des textes clairs M) et un couple de clef publique-clef secrète (pk,sk), S produit une signature σ. L’algorithme de signature peut être probabiliste. – L’algorithme de vérification V : étant donné une signature σ, un (ou une partie, éventuellement vide du) message m, et une clef publique pk, V vérifie si σ est une signature valide et finalement, extrait le message m. En règle générale, l’algorithme de vérification n’a pas à être probabiliste 

Infalsifiabilité 

L’objectif de l’attaquant est de produire un nouveau couple (message, signature) valide. Cette production s’appelle la falsifiabilité existentielle. La sécurité contre ce type d’attaque est l’infalsifiabilité existentielle (dénotée EUF). En ce qui concerne le moyen d’attaque, on considère habituellement les attaques adaptatives à messages choisis (dénotée CMA). Dans ce modèle, l’attaquant peut demander au signataire de signer n’importe quel message et adapter ses questions aux réponses obtenues. A la fin, l’attaquant retourne un couple (m, σ), avec m n’ayant jamais été soumis à l’oracle de signature. L’attaquant gagne si σ est une signature valide du message m. L’objectif est de résister aux falsifications existentielles selon des attaques adaptatives à messages choisis (EUF/CMA), i.e. la probabilité de succès de tout attaquant A en un temps raisonnable est négligeable. Cette probabilité de succès est définie comme suit : Succeuf/cma S (A) = Pr  (pk,sk) ← K(1k),(m, σ) ← ASsk (pk) : V(pk, m, σ)=1  . 

Signature et chiffrement 

Nous cherchons à construire un padding unifié qui peut être utilisé en même temps et avec une même primitive pour le chiffrement et pour la signature. L’attaquant a pour objectif soit de construire une falsification existentielle (i.e. casser EUF) contre le schéma de signature, soit de casser la sécurité sémantique du schéma de chiffrement (i.e. casser IND). Pour y parvenir, il dispose de l’accès adaptatif aux oracles de signature et de déchiffrement. Il s’agit d’une combinaison des attaques contre le chiffrement et contre la signature, d’où la notation de l’attaque CMA + CCA. 

Permutations sans griffe 

Dans [71], Katz et Wang ont prouvé que, en utilisant des permutations à trappe induites par des permutations sans griffe (claw-free permutations en anglais), on peut obtenir une variante de FDH (en y ajoutant un bit supplémentaire) avec une réduction fine. Nous utilisons également cette technique pour notre construction. L’hypothèse de l’existence des permutations sans griffe semble être raisonnable. En effet, toute permutation à sensunique aléatoirement auto-réductible peut être considérée comme une permutations sans griffe [42] et la quasi-totalité des exemples connus de permutations à sens-unique à trappe sont aléatoirement auto-réductibles. Définition 46 (Permutations sans griffe) Une famille de permutations sans griffe est un ensemble d’algorithmes {Gen; fi; gi|i ∈ I}, tels que : – Gen retourne un indice aléatoire i et une trappe td. – fi, gi sont des permutations sur le même domaine Di. – il existe un algorithme d’échantillonnage efficace qui, pour chaque indice i, retourne une valeur aléatoire x ∈ Di.