DEAL – 128 chiffre de bit par blocs

 

Lars R. Knudsen

Le 21 février 1998

 

La traduction de l'anglais : Kochetkov N. N

Octobre 1998

 

L'annotation

 

Nous proposons un nouveau chiffre par blocs, DEAL, fondé sur DES (DEA). Le montant du bloc DEAL – 128 bits, le montant de la clé peut être 128 192 ou 256 bits. Le chiffre proposé par nous a quelques avantages devant d'autres schémas : en remerciant большему au montant des blocs, le problème «les attaques d'après le chiffre-texte choisi» devient moins essentiel, mais la vitesse шифрования correspond à la vitesse triple DES. Nous supposons que le plus réaliste (ou le moins non réaliste) l'attaque contre n'importe quelle version DEAL’а est une recherche exhaustive des clés. Nous avons proposé ANSI au (institut) d'insérer DEAL dans le standard ANSI X9.52. En plus nous proposons DEAL, comme le candidat sur le standard NIST AES.

 

1 Introduction

DES (ou DEA) [15] – le chiffre par blocs avec le montant du bloc de 64 bits et 64 clé de bit, dans qui sont effectifs 56 bits. C'est itératif 16 цикловой le chiffre, dans lui le chiffre-texte est calculé par voie de l'application itérative цикловой les fonctions vers le texte ouvert. DES a un soi-disant Fejstelevu la structure : dans chaque cycle la moitié du bloc est manquée dans la fonction non linéaire, sa sortie XOR’ится avec une autre moitié, après quoi les deux moitiés sont permutées.

Pour les applications modernes le montant de la clé DES est devenu trop petit. Винер [20] a montré que construire l'installation spécialisée, capable de produire la recherche exhaustive de la clé DES en moyenne tout en 3.5 heures, coûtera environ 1 million US $. En plus, récemment était montré que des attaques de programme la clé par le montant de 56 bits n'accorde pas la protection considérable – la clé DES était trouvée par voie de la recherche exhaustive les moyens répandu selon Internet’у.

À vrai dire, au problème du montant insuffisant de la clé indiquaient déjà presque à la fois après la publication DES [6]. C'est pourquoi, souvent DES est utilisé selon le schéma triple шифрования, appelé triple DES’ом (Triple-DES), où le texte ouvert est chiffré trois fois sur trois clés indépendantes. Dans une autre variante appelée deuxclé triple DES’ом, le texte ouvert est chiffré d'abord par la clé К1, puis est déchiffré par la clé К2 et, enfin, est chiffré de nouveau par la clé К1 [18]. Cependant, le montant du bloc à 64 bits fait ces schémas vulnérable vers l'attaque d'après le chiffre-texte choisi, qui est fondée sur ce fait que pour le plus grand nombre des modes avec DES [16] après зашифрования 233 blocs peut attendre les blocs identiques du chiffre-texte, cela donne la fuite de l'information sur le texte ouvert [5, 9, 13]. En plus, triple DES avec trois clés indépendantes est vulnérable vers l'attaque selon la clé dépendante (?) [7], le temps de l'exécution de qui environ même, comme le temps de la recherche exhaustive de la clé à simple DES.

La commission X9.F.1 de l'Institut National Américain des Standards (ANSI) travaille sur l'acceptation de l'ensemble des régimes triple шифрования DES [21]. Un de ces régimes – avec la liaison en retour d'après le chiffre-texte (Triple DES Cipher Block Chaining – TCBC), où le bloc pour la liaison en retour est le bloc du chiffre-texte après 3 зашифрований, – s'appelle aussi extérieur (outer-) CBC le régime. Cependant, ce régime est vulnérable vers l'attaque d'après le chiffre-texte choisi. C'est pourquoi, il est proposé d'utiliser triple DES en régime avec la liaison en retour d'après le chiffre-texte avec l'interaction, s'appelle aussi intérieur (inner-) CBC le régime, où la liaison en retour se réalise après chacun зашифрования simple DES’ом. Bien que ce régime soit moins vulnérable vers l'attaque d'après le chiffre-texte choisi, l'attaque effective selon l'ouverture de la clé peut être passée en un temps beaucoup plus petit, que l'on pourrait attendre pour le schéma avec triple шифрованием [1].

Coupersmith, Jonson et Matyas [5, 4] proposent pour triple DES’а le régime CBC avec OFB Masking (CBCM). Wagner [5] a passé криптоанализ de la proposition précédant l'élaboration donnée, où chacune de deux valeurs initiales peut accepter seulement 220 significations. Le régime CBCM n'est pas vulnérable vers l'attaque d'après le chiffre-texte choisi, et le niveau de la sécurité est supposé 280. L'inconvénient du schéma proposé que pour зашифрования du bloc du texte ouvert par le montant de 64 bits est utilisé 4 зашифрования DES sur trois diverses clés. Auparavant Biham et Knudsen ont montré que DES en régime CBCM est vulnérable vers l'attaque d'après le chiffre-texte choisi, dans qui on utilise 265 blocs du chiffre-texte choisi et la complexité de qui par temps – 258 [2].

Nous proposons r-tsiklovoj Fejstelev le chiffre utilisant DES en la qualité цикловой les fonctions. Il se trouve finalement le chiffre avec le montant du bloc de 128 bits et r · à 64 bits цикловых des clés reçues selon l'algorithme de l'horaire des clés. L'horaire des clés est élaborée ainsi que le montant de la clé peut accepter une de trois diverses significations : 128 192 ou 256 bits. Nous recommandons de mettre à premier deux montants de la clé r = 6, mais au montant de la clé de 256 bits r = 8. Plus bas nous expliquerons, pourquoi nous recommandons r ≥ 6. Si les bits du contrôle четности de chaque octet de la clé ne sont pas utilisés à шифровании, comme cela se passe à DES, les montants agissant des clés diminuent jusqu'à 112, 168 et 224 bits en conséquence. La recherche exhaustive de la clé est encore tout à fait impossible (voir, par exemple, la discussion des montants des clés à [3]). En plus, pour l'attaque fructueuse d'après le chiffre-texte choisi il est nécessaire d'introduire de l'ordre de 264 blocs du chiffre-texte. La vitesse du chiffre proposé par nous même, comme chez triple DES’а, si utiliser 6 зашифрований pour la clôture de deux blocs du texte ouvert selon 64 bits, de plus, on peut l'appliquer avec l'utilisation des moyens existant DES.

L'Institut national des Standards et la Technologie (NIST) a annoncé récemment l'intention de standardiser un nouvel algorithme шифрования, Advanced Encryption Standart, comme le remplacement DES [14]. La demande NIST de ce qu'avant qu'AES sera prêt, passera quelques années, et qu'ils ont l'intention de reconnaître «le DES-algorithme Triple, une fois lui est acceptée par le standard ANSI» [14], fait l'initiative ANSI même plus important.

 

2 DEAL

DEAL (Data Encryption Algorithm with Larger blocks – Algoritm Shifrovanija Dannyh avec les blocs Agrandis) est 128 chiffre de bit par blocs avec les montants de la clé 128, 192 et 256 bits qu'ensuite sera désigné ici DEAL-128, DEAL-192 et DEAL-256 en conséquence. Toutes les versions peuvent être utilisées dans chacun de quatre régimes standard DES’a [16]. Nous commencerons par la description du travail DEAL en régime ECB. Qu'avec = EVES () signifie chiffré DES la signification 64 de bit Mais sur la clé à, et qu'Y = ЕAZ (X) signifie зашифрование DEAL 128 de bit X sur la clé Z. Le texte ouvert Р se divise en blocs Pi selon 128 bits chacun, P = P1, P2, …, Pn. L'horaire des clés accepte la clé Vers et rend r des clés DES RKi, où i = 1, …, r, comme est décrit plus bas. Nous désignerons XL et XR de parties gauches et droites Х en conséquence. Le Chiffre-texte est calculé comme il suit. Nous mettrons, et nous calculerons pour j = 1, …, r

(1)

.

(2)

Nous mettrons. Sur fig. 1 on montre un cycle DEAL. Pour DEAL-128 et DEAL-192 nous proposons d'utiliser 6 cycles, i.e. r = 6. Cependant, comme nous verrons plus bas, de cela peut être insuffisamment pour DEAL-256, il est proposé d'utiliser ici 8 cycles, r = 8. Il Semble que la version avec le montant de la clé de 256 bits est utilisée seulement quand il faut particulièrement fort зашифрование.


Nous remarquerons que le dernier cycle DEAL de la moitié du bloc par endroits changent. La raison dans le suivant : la partie droite du chiffre-texte Сi n'est pas chiffrée dans le dernier cycle I-ÈME зашифрования, et seulement une gauche partie de l'entrée i + 1-er зашифрования (qui est égal) est chiffrée sur le dernier cycle. Т l'île la partie droite Ci resterait non перезашифрованной deux cycles. Cela peut donner le champ d'activité aux malfaiteurs, d'autant plus que le chiffre comprend de tout de 6 ou 8 cycles. Nous remarquerons que la propriété analogue est et chez DES en régime CBC. Cela à vrai dire, ressemblait plus difficilement utiliser, en effet, chez DES 16 cycles. Nous permettrons de marquer que l'échange pour places des gauches parties droites sur le dernier cycle n'influence pas la résistance du chiffre par blocs en régime ECB.

Le travail du régime CBC est décrit plus en détail à [16]. Donc, nous désignerons les blocs du texte ouvert selon 128 bits P1, P2, …, Pn et С1, С2, …, Сn – les blocs leur correspondant du chiffre-texte. Alors :

,

С0 – la signification initiale.

À DES le réarrangement initial IP premier est appliqué au texte ouvert, et est analogue devant la sortie le chiffre-texte est manqué par inverse vers elle IP-1. Il est possible d'augmenter la vitesse DEAL, si enlever d'utilisé DES ceux-ci les réarrangements initiaux et finaux. Il est facile de montrer que pour la réception de la réalisation correcte DEAL’а IP doit être mise aux deux parties du texte ouvert devant зашифрованием, mais IP-1 – vers les deux parties du chiffre-texte.

Sur l'entrée de l'horaire des clés est donné s des clés DES, К1, …, Ks, pour s = 2, 3, 4, chacun selon 64 bits (y compris 8 bits de contrôle, les bats principaux de chaque octet), sur la sortie réussit r des clés DES, i. Nous utilisons la méthode totale, appliqué vers tous trois montants de la clé. Premièrement nous élargissons s des clés jusqu'à r des clés, par voie de la répétition et XOR’ения avec une nouvelle constante pour chaque nouvelle répétition. Nous chiffrons la liste élargie des clés DES’ом en régime CBC avec la clé fixée et la signification nulle initiale. Des blocs reçus du chiffre-texte sont formés connecte RKi. Ensuite nous amenons les définitions exactes de chacun des horaires des clés, ici Vers = 0х1234 5678 90ab cdefx (le nombre hexadécimal) – la clé fixée DES.

À DEAL-128 connecte sont générés comme il suit :

,

,

,

,

,

,

– 64 nombre entière de bit, dans qui i – le 1-er bit (l'indexation va avec 0) est établi, mais autre sont nettoyés. Par exemple, peut être présenté comme hexadécimal “0х8000 0000 0000 0000х”.

 

À DEAL-192 connecte sont générés comme il suit :

,

,

,

,

,

.

Ces versions de l'horaire des clés demandent 6 horaires des clés DES et 6 зашифрований DES sur la clé fixée. Connecte il faut générer seulement une fois, si de ceux-ci par la suite garder.

 

À DEAL-256 connecte sont générés comme il suit :

,

,

,

,

,

,

,

.

Cette version de l'horaire des clés demande 8 horaires des clés DES et 8 зашифрований DES sur la clé fixée. Connecte il faut générer seulement une fois, si de ceux-ci par la suite garder.

 

Nous remarquerons que pour toutes les versions de l'horaire des clés 64 valeurs de bit RKi sont utilisés comme les clés DES, c'est pourquoi les bits du contrôle четности RKi ne sont pas utilisés dans l'I-ÈME cycle. Cependant, tout 64 bits RKi, comme de la sortie шифрования sur la clé Vers, sont utilisés à la génération du suivant подключа.

Les principes de l'élaboration de l'horaire des clés, premièrement, comprennent que connecte dépendaient du plus grand nombre des bits de la clé principale, mais ne demandaient pas de plus beaucoup de travail, deuxièmement, à l'introduction s les clés principales par le montant selon 64 bits, chacuns s successif подключей doivent avoir l'entropie s ∙ 56 bits, et, enfin, il n'y avoir pas être faibles clés évidemment dépendantes et ne doit pas rester la propriété дополнительности (?). Nous remarquerons que les derniers deux problèmes assistent et à DES, et – tout trois – à triple DES. Nous avons remarqué que si les clés principales par le montant selon 64 bits chacun, peut se trouver une paire des clés générant les multitudes identiques подключей. Cependant, le nombre de telles clés est tellement pas grand, paraît-il, que ne présente pas la menace DEAL’у, appliqué pour шифрования.

Les déplacements sont introduits pour la prévention de l'apparition des faibles clés. S'ils n'étaient pas, il y avait des clés, pour lesquelles tout connecte étaient égaux. Par exemple, pour DEAL-128 les clés K1 = K2 = DK (0) généreraient 6 подключей avec la signification 0. Les déplacements et шифрование sur la clé fixée préviennent l'apparition des clés faibles et dépendantes et la propriété дополнительности.

Nous remarquerons que si le bit du contrôle четности est utilisé dans chaque octet de la clé principale, les montants agissant des clés proposées font 112 168 et 224 bits, en conséquence.

La structure décrite ci-dessus DEAL pourrait être et l'autre – est quelques variantes possibles. Au lieu de Fejstelevoj de la structure on peut utiliser la structure MISTY pour la première fois décrite à [12], elle permet dans une plus grande mesure распараллелить les calculs (dans l'exécution de matériel). Cependant, cette structure est élaborée beaucoup plus tard et pas encore est profondément analysée ainsi. Une autre variante – utiliser DEAL en régime «DES-X» [8], à qui la clé supplémentaire XOR’ится avec en clair et avec le chiffre-texte. Ou, au lieu de l'utilisation DES, comme цикловой les fonctions, on peut utiliser DES-X. Le manque des dernières deux propositions de ce que demander générer le plus grand nombre подключей, et, donc, l'horaire des clés DEAL sera plus complexe.

 

2.1 Résistance DEAL’а

Que l'on peut dire sur la résistance DEAL’а en tout ? Avant tout, nous remarquerons que pour DEAL l'attaque simple meet-in-the-middle (rencontrer selon le milieu), analogue à une telle attaque sur double DES [6, 19], recherchera les clés au cours de l'ordre 2168 зашифрований pour six et 2224 зашифрований pour huit cycles DEAL en conséquence, indépendamment de l'horaire des clés. C'est pourquoi, il est proposé à DEAL-256 de produire au moins 8 cycles зашифрования. Pour DEAL-128 la recherche exhaustive de la clé occupera le temps de l'ordre de 2112 зашифрований.

Patarin à [17] a montré que pour distinguer 5 ou 6 цикловой Fejstelev de n bits le chiffre avec accidentel цикловой par la fonction d'est véritable du réarrangement accidentel de 2n bits, il faut connaître au moins 22n / de 3 textes ouverts et les chiffres-textes leur correspondant. Ensuite il suppose qu'est demandé 2n la vapeur. Si trouver que DES modèle le réarrangement accidentel [1], cela, selon la supposition Patarin’а, il faut de l'ordre de 264 зашифрований pour distinguer DEAL du réarrangement accidentel; est telle la complexité de l'attaque d'après le chiffre-texte choisi. Le plus rapide des attaques connues par la présence de la clé sur DEAL (avec six cycles), qui nous comprenons, – l'attaque totale sur 6 цикловые Fejstelevy les chiffres [10], dans l'application vers DEAL, elle demande de l'ordre de 2121 зашифрований DES, en utilisant de l'ordre de 270 textes choisis ouverts, pour n'importe quelle horaire des clés. Nous définirons par la suite la différence entre deux successions du bats, comme побитное XOR.

L'affirmation 1 : il Y a une attaque sur шестицикловый DEAL avec les indépendants цикловыми par les clés, qui demande de l'ordre de 2121 зашифрований DES, en utilisant de l'ordre de 270 textes choisis ouverts.

La preuve : nous Examinerons 5 цикловую la version et une paire des textes ouverts avec la différence α ≠ 0 dans les parties droites et de gauches parties égales. Nous supposerons que les chiffres-textes après 5 cycles ont la différence α dans de gauches parties et les parties égales droites. Cela signifie qu'aux deux зашифрованиях sur les entrées DES (à цикловой les fonctions DEAL) étaient les significations identiques sur le premier et sur les cinquièmes cycles. Ensuite, la différence sur les entrées DES sur deuxième et sur les quatrièmes cycles était α. Mais il faut d'ici que les sorties DES en troisième cycle sont égales, donc et les entrées DES sur le troisième cycle sont égales aussi. Cela conduit à la contradiction, car cela signifie que les sorties DES sur deuxième et sur les quatrièmes cycles sont égales qu'est impossible, car nous avons supposé qu'ils ne sont pas égaux. Ainsi la supposition que la différence entre les chiffres-textes après 5 cycles est égale α en gauches et 0 dans les parties droites, non exactement. En d'autres termes, nous avons défini 5 цикловой la différentielle avec la probabilité nulle. Cela peut être utilisé pour l'attaque sur DEAL.

L'attaque se passe comme il suit. Nous choisirons 264 textes ouverts avec de gauches et diverses parties fixées droites, nous les désignerons à i = 1, …, 264. Nous désignerons les chiffres-textes leur correspondant. Nous calculerons et trouveront les coïncidences à i  ≠ j. On Peut attendre de l'ordre de 263 telles coïncidences :. Nous mettrons. Pour toutes de telles paires coïncidant et pour toutes les significations de la clé dans le sixième cycle nous déchiffrerons un cycle des chiffres-textes. Si les différences après 5 cycles sont égales α et 0, la signification supposée de la clé non exactement. Nous remarquerons qu'à la signification juste de la clé telles différences après 5 cycles ne peuvent pas apparaître, mais à incorrect ils apparaîtront avec la probabilité 2-64 pour chaque paire analysée. Ainsi avec 263 vapeurs de l'ordre de la moitié des clés seront rejetés. À la répétition de l'attaque de 56 fois resteront possible seulement quelque de la signification de la clé dans le sixième cycle. À total, l'attaque demande 56 ∙ 264 ≈ 270 textes choisis ouverts, (256 + 255 + 254 + … + 2 + 1) ∙ 264 ≈ 257 ∙ 264 = 2121 зашифрований DES et 264 mots ярь =ш.аааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааа □

L'attaque décrite ci-dessus mise vers DEAL-192 est plus rapide, que la recherche exhaustive de la clé, bien que les conditions très non réaliste. Si attaquant on réussira à trouver 264 ou plus vapeurs ouvert et les chiffres-textes, l'attaque d'après le chiffre-texte choisi peut entrer dans le jeu, et il faut dans tous les cas le chiffre avec un grand montant du bloc. L'attaque la plus étudiée sur DEAL-128 – la recherche exhaustive de la clé – demande le temps de l'ordre de 2112 зашифрований. Nous n'avons pas trouvé l'attaque sur DEAL avec восемью par les cycles le meilleur, que la recherche décrite ci-dessus exhaustive de la clé «meet-in-the-middle». Peut être, il y a des attaques plus rapides, par exemple, la généralisation réussie de l'attaque citée ci-dessus sur 6 cycles, mais un tel plan de l'attaque demanderont la quantité irréelle de textes choisis ouverts et le volume irréel de la mémoire.

L'attaque contre 6 cycles explique nos recommandations – utiliser pour DEAL r ≥ 6. À r ≤ 5 il est possible d'indiquer les différentielles avec la probabilité nulle. Cela signifie que pour certaines différences dans les vapeurs du texte ouvert, les autres différences sont impossibles dans les vapeurs correspondantes du chiffre-texte. Avant tout, une telle propriété est absente près de certains chiffres modernes par blocs, ensuite, telles différentielles peuvent être utilisées dans les attaques selon l'ouverture de la clé avec la complexité de l'ordre de 288 pour DEAL seulement avec les 5-ème cycles [10]. (Nous Remarquerons qu'une telle attaque – seulement la limite supérieure du niveau de la sécurité).

À la fin de ce paragraphe nous ferons le bilan aux particularités DEAL.

·         DEAL a le montant du bloc de 128 bits et le montant de la clé 128, 192 ou 256 bits (le montant agissant, en conséquence, – 112 168 ou 224 bits,).

· l'        Attaque d'après le chiffre-texte choisi demande de l'ordre de 264 blocs du chiffre-texte.

·         Il n'y a pas d'attaques connues probables.

·         DEAL avec six cycles a la vitesse analogue à la vitesse triple DES.

·         DEAL peut être utilisé dans les modes standard.

·         DEAL on peut réaliser sur trouvant de matériel et de programme la garantie DES.

·         Il n'y a pas d'évidemment faibles clés et on élimine la propriété дополнительности.

Enfin, nous permettrons de remarquer qu'en raison de l'horaire assez complexe des clés, DEAL utiliser non raisonnablement dans les fonctions accidentelles.

 

3 Conclusion

Nous avons décrit le chiffre par blocs, DEAL, avec le montant du bloc de 128 bits et le montant de la clé 128, 192 ou 256 bits, comme l'alternative aux régimes existant triples шифрования. DEAL peut être utilisé à tout de quatre, élaboré pour DES, les régimes standard шифрования. Pour premier deux montants de la clé le schéma chiffre deux blocs selon 64 bits, en utilisant six зашифрований DES, ainsi sa productivité est égale à la productivité triple DES. La productivité DEAL avec восемью par les cycles (et le montant de la clé de 256 bits) est égale DES en régime CBCM. Grâce à de grands montants du bloc et la clé, la recherche exhaustive de la clé et l'attaque d'après le chiffre-texte choisi sont irréalisable. En plus, on évite les faibles DES et triple DES. Il n'y a pas d'évidemment faibles clés, il ne restait pas les propriétés дополнительности, et le succès des attaques selon la clé dépendante est très peu probable. Nous recommandions ANSI d'accepter DEAL, comme la partie [21]. En outre nous proposons DEAL, comme le candidat possible sur Advanced Encryption Standard [14].

 

4 Reconnaissances

L'auteur est reconnaissant Don Coupersmith’y, Bart Preneel’y, Vincent Rijmen’y et Matthew Robshaw’y de la multitude de commentaires considérables.

 

Les références

Voir l'original de l'article en anglais, le paragraphe References.

 

 



[1] nous Remarquerons que bien que l'attaque la plus étudiée sur DES – l'attaque linéaire Matsui [11] – demande la connaissance seulement"243 textes ouverts, elle demande que tous ces ouvert et les chiffres-textes soient on savent que ne peut pas être supposé dans l'application DES vers DEAL.

Яндекс цитирования

Subscribe Subscribe.Ru
The Family Tree of Family