Faiblesse de préparation des clefs de SAFER+


J. Kelsey, B. Schneier, D. Wagner
Seconde conférence de l'AES, avril 1999.


 

 RÉSUMÉ


Nous analysons la mise au point de la clef du chiffrement par bloc SAFER+, en particulier la faible diffusion des composants de la clef au travers du chiffrement lors de l'utilisation de SAFER+ avec des clefs de 256 bits. Nous développons alors une attaque « par le milieu » de SAFER+ 256 bits qui requiert 12 x 2
24 octets de mémoire, 3 paires de textes clair/chiffrés et un travail à peu près équivalent à 2240 chiffrements SAFER+. Nous avons aussi développé une attaque à clef corrélées de SAFER+ 256 bits qui requiert 2 x 232 textes clair choisis sous deux clefs avec une relation XOR choisie et un travail approximativement équivalent à 2200 chiffrements SAFER+.

Nous considérons un nombre d'autres propriétés liées aux clefs, comme les clefs équivalents, les clefs faibles et semi-faibles du type DES, et les caractéristiques différentielles et linéaires dépendantes de la clef. Nous montrons alors pourquoi nous n'avons pas trouvé ces propriétés, et offrons quelques arguments expliquant pourquoi ces propriétés n'existent probablement pas.

Enfin, nous proposons une amélioration de la mise au point des clefs de SAFER+ 256 bits qui la défend contre nos attaques, sans avoir d'effet de faiblesse sur le chiffrement et sa résistance aux autres types d'attaques.
 

 1   Introduction


Dans ce document, nous discutons la mise au point des clefs de SAFER+ [MKK98], l'un des quinze candidats à l'AES. SAFER+, comme les autres candidats de l'AES, est en fait trois chiffrements distincts; un premier avec des clefs de 128 bits, un second avec des clefs de 192 bits et enfin un troisième avec des clefs de 256 bits. Pour simplifier ce document, nous allons appeler ces chiffrements SAFER+/128, SAFER+/192 et SAFER+/256. Certains candidats, comme CAST-256 [Ada98] et E2 [NTT98] utilisent essentiellement la même structure de clefs et de chiffrement pour les trois versions, et complètent les clefs de moins de 256 bits (ou plus) avant de réaliser la grosse préparation de clef. D'autres candidats à l'AES, comme SAFER+, Rijndael [DR98] et Twofish [SKW+98] modifient le chiffrement en fonction de la taille de la clef (SAFER+ et Rijndael modifient la fonction de chiffrement ce qui le rend plus lent pour des clefs plus longues; Twofish modifie la préparation de la clef, afin que le chiffrement et le déchiffrement se réalisé à une même vitesse quelle que soit la taille de la clef). Dans SAFER+, les clefs de 128 bits sont utilisées avec 8 rondes, les clefs de 192 bits avec 12 rondes et les clefs de 256 bits avec 16 rondes.
  Nous avons fait les découvertes suivantes:

  • Nous avons découverte que dans SAFER+/192 et SAFER+/256, la préparation de la clef n'est pas très performante pour impliquer rapidement toute la clef dans le processus de chiffrement. SAFER+/192 requiert 5 rondes sur 12 pour que toute la clef soit impliquée dans le processus, SAFER+/256 requiert 9 rondes sur 16. Ceci contraste avec SAFER+/128 où chaque ronde est affectée par chaque bit de la clef.
  • A cause de cette lente diffusion de clef, nous avons été capables de trouver une attaque « par le milieu » sur SAFER+/256. Cette attaque représente un travail d'environ 2240 chiffrements SAFER+/256 et requiert environ 12 x 224 octets de mémoire.
  • Toujours à cause de cette diffusion lente, nous avons pu trouver une attaque par clefs corrélées sur SAFER+/256. Cette attaque ne demande que très peu de mémoire, 3 x 232 textes en clair choisis chiffrés avec deux clefs différentes choisies avec une relation XOR, et un travail d'environ 2200 chiffrements SAFER+/256.
  • Nous n'avons pas pu trouver de clefs équivalentes ou de paires de clefs équivalentes. Nous serions en fait très surpris de découvrir une paire de clefs équivalentes pour SAFER+.
  • Nous n'avons pas pu trouver de clefs presque-faibles. Toutefois, nous n'avons aucun avis tranché sur l'existence ou pas de ces clefs.
  • Nous n'avons pas trouvé de moyen de réaliser d'attaques par glissement [Wag95, BW99] ou d'attaques par clefs liées [Bih94, KSW96, KSW97] à cause des divergences de clefs.
    line

    1.1  Application pratique de nos découvertes

Aussi bien notre attaque par le milieu que notre attaque par clef corrélée illustrent les violations substantielles des déclarations de sécurité de SAFER+/256. Un chiffrement par bloc avec des clefs de 256 bits doit fournir une sécurité de 256 bits; ainsi, un attaquant devra réaliser environ 2255 chiffrements d'essai sous différentes clefs, en moyenne, pour la récupérer.
  Aucune de nos attaques n'est réalisable pour l'instant, à cause des énormes quantités de calculs à réaliser. Toutefois, il y a peu de raisons d'utiliser une clef de 256 bits si elle n'offre pas d'amélioration de la sécurité par rapport à une clef de 192 bits. C'est particulièrement vrai pour SAFER+ où SAFER+/192 est presque 1,3 fois plus rapide que SAFER+/256.
  Ne pas réussir à trouver certaines propriétés variées dans la mise au point des clefs implique de bonnes choses pour le chiffrement. Les clefs faibles, semi-faibles, équivalentes, presque-faibles ou toute combinaison de ces propriétés induirait des problèmes de sécurité dans certaines applications. Par exemple, si SAFER+/256 avait des paires de clefs équivalentes, il ne pourrait pas être utilisé comme fonction de hachage.

line

1.2  Guide pour le reste de ce document

Le reste de ce document est organisé comme suit. Nous donnons d'abord un brève description du chiffrement SAFER+ et de sa préparation de clef. Puis, nous décrivons notre attaque par le milieu, et notre attaque par clef liées. Enfin nous proposons une correction de SAFER+/192 et de SAFER+/256 et terminons par quelques questions ouvertes. Dans l'appendice nous décrivons quelques propriétés additionnelles de la mise au point des clefs dans SAFER+.
 

 2   SAFER+ et sa préparation de clefs


SAFER+ est défini dans [MKK98]. Le chiffrement, qui fait partie de la famille de chiffrements SAFER définie depuis quelques années [Mas94], consiste en une série de rondes identiques (avec seulement des clefs de rondes différentes) et une transformation en sortie. Chaque ronde est une couche Table-S et une couche de mélange.

line

2.1  Le chiffrement

La couche Table-S traite chacun des seize octets en entrée de manière indépendante: un octet de sous-clef est combiné avec un octet en entrée, puis une Table-S à 8 bits est appliquée, puis un autre octet de la clef est combiné dans l'octet. Ceci est réalisé en parallèle pour tous les 16 octets du bloc en cours de chiffrement. SAFER+ utilise deux transformations d'octet différentes:

equation

Ceci est plus détaillé que ce dont nous avons besoin pour la majeure part de notre analyse. Pour une description plus précise, consultez [MKK98].
  La couche de mélange implique l'ajout de deux octets ensemble dans une structure complexe basée sur la structure PHT:

equation

L'effet ultime de cette couche de mélange est expliqué par une matrice M présente dans [MKK98]. Notez que la matrice M n'est pas auto-inverse, ce qui implique une asymétrie entre le chiffrement et le déchiffrement.
  La transformation en sortie finale est simplement une couche d'ajout et de XOR des éléments de la clef. Notez que la transformation finale n'est pas une couche totalement non-linéaire dans le chiffrement, ce qui contribue aussi à l'asymétrie du chiffrement. Cela n'a que peu d'impact sur nos attaques, décrites ci-dessous.

2.2  La préparation de la clef

La préparation de la clef étend la clef de 16, 24 ou 32 octets vers des sous-clefs de 272, 400 et 528 octets respectivement. Chaque ronde utilise 32 octets de sous-clef; la transformation finale utilise 16 octets de sous-clef. La première clef est d'abord étendue d'un octet, soit 17, 25 ou 33 octets de clef; cet octet est le XOR de tous les autres octets. Nous appelons cette clef étendue ek[0..n]. La préparation de la clef utilise aussi des « biais de clefs », un jeu d'octets constantes que nous appelons kb[0..m-1].

equation

  Il y a deux attributs importants dans cette préparation de clef:

  1. Chaque ronde utilise 256 bits (32 octets) de sous-clef; mais ne dérive ses sous-clefs qu'à partir de 132 bits seulement (17 octets) de la clef étendue.
  2. Des rondes successives réutilisent la majeure part des mêmes matériaux de clef, ce qui fait qu'une paire de rondes successives utilise 512 bits (64 octets) de sous-clefs, mais qui ne dérivent que de 148 bits (19 octets) de la clef étendue.

Ces deux propriétés rendent nos deux attaques possibles contre SAFER+/256.

equation
Table 1: utilisation des octets de la clef dans SAFER+
 

Octets de clef étendue:
ronde

SAFER+/128
SAFER+/192
SAFER+/256

0

0-16

0-16

0-16

1

2-16, 0-1

2-18

2-18

2

4-16, 0-3

4-20

4-20

3

6-16, 0-5

6-22

6-22

4

8-16, 0-7

8-24

8-24

5

10-16, 0-9

10-24, 0-1

10-26

6

12-16, 0-11

12-24, 0-3

12-28

7

14-16, 0-13

14-24, 0-5

14-30

8/OX

16, 0-14

16-24, 0-7

16-32

9

-

18-24, 0-9

18-32, 0-1

10

-

20-24, 0-11

20-32, 0-3

11

-

22-24, 0-13

22-32, 0-5

12/OX

-

24, 0-14

24-32, 0-7

13

-

-

26-32, 0-9

14

-

-

28-32, 0-11

15

-

-

30-32, 0-13

OX

-

-

32, 0-14

equation

2.3  Diffusion de la clef

Une chose utile à observer pour tout chiffrement, c'est à quelle vitesse la clef influe sur l'état interne du chiffrement. Un mélange efficace des bits de la clef dans le processus de chiffrement minimise l'avantage qu'un attaquant peut tirer de la détermination de quelques bits de la clef, et de l'attaque qu'il réalisera à partir de son estimation.
  Dans SAFER+, une étude de la diffusion de la clef expose une faiblesse dans la conception du chiffrement. Dans SAFER+/128, chaque bit de la clef est utilisé dans la première ronde, et dans chaque ronde qui suit. C'est une propriété excellente pour un chiffrement: un attaquant ne peut pas déshabiller une seule ronde sans connaître tous les bits de la clef. On pourrait s'attendre à rencontrer la même propriété dans SAFER+/192 et SAFER+/256. En fait, il faut 5 rondes sur 12 pour que tous les octets de la clef soient impliqués dans le chiffrement avec SAFER+/192 et 9 rondes sur 16 pour la même chose avec SAFER+/256.
  Pour en comprendre l'impact, considérez la table 2, qui montre pour une clef de 256 bits, combien d'octets composant la clef doivent être devinés afin d'avoir une connaissance complète de la sortie de chaque ronde (en devinant à partir du haut) ou d'entrée (en devinant à partir du bas).
  Ces deux tables illustrent l'échec de la préparation de clef de SAFER+ à gérer des clefs de plus de 128 bits. Cet échec dans le cas des 256 bits conduit directement à nos attaques, et c'est cette propriété dans ces tables qui nous a initialement amenés à analyser la préparation de clef de SAFER+.
 

 3   Attaque par le milieu de SAFER+/256


Une attaque par le milieu peut être réalisée sur un chiffrement lorsque l'on peut deviner une partie de la clef à partir du côté texte en clair et du côté texte chiffré, et calculer la même valeur interne pour les deux côtés. Dans ce cas, nous essayons chaque valeur de clef partielle possible, en calculant la valeur intermédiaire et en la plaçant dans une liste ordonnée pour le texte en clair. Puis nous faisons la même chose à partir du texte chiffré, en plaçant les résultats dans la même liste ordonnée. Nous recherchons alors des correspondances. Des valeurs intermédiaires qui correspondent indiquent une estimation correcte; si les valeurs intermédiaires sont assez grandes, alors elles correspondent, et la probabilité que l'estimation du coté texte clair et du côté texte chiffré correspondent est très élevée.
  Pour voir comment notre attaque par le milieu sur SAFER+ est menée, nous devons d'abord utiliser une variante de la table 2. La table 4 décrit l'attaque.

equation
Table 2: estimation partielle contre SAFER+/256
Ronde
Estimation par le haut
Estimation par le bas
Bits

0

17

-

136

1

19

-

152

2

21

-

168

3

23

-

184

4

25

-

200

5

27

-

216

6

29

-

232

7

31

-

248

8

-

-

-

9

-

30

240

10

-

28

224

11

-

26

208

12

-

24

192

13

-

22

176

14

-

20

160

15

-

18

144

OX

-

16

128

equation
Table 3: attaque par estimation partielle contre SAFER+/192

Ronde

Estimation par le haut

Estimation par le bas

Bits

0

17

-

136

1

19

-

152

2

21

-

168

3

23

-

184

4

-

-

-

5

-

-

-

6

-

-

-

7

-

-

-

8

-

24

192

9

-

22

176

10

-

20

160

11

-

18

144

OX

-

16

128

equation
Table 4: attaque par le milieu de SAFER+/256

Ronde

Estimation
par le haut

Estimation
par le bas

Commentaires

0

17

-

1

19

-

2

21

-

3

23

-

4

25

-

5

27

-

6

29

-

7

-

-

Savons tout sauf 2 octets de la couche PHT

8

-

-

Savons tout sauf 2 octets de sortie de la couche PHT ci-dessus

9

-

30

10

-

28

11

-

26

12

-

24

13

-

22

14

-

20

15

-

18

OX

-

26

equation

  Dans l'attaque, nous considérons une paire de texte clair/chiffré provenant de la clef que nous voulons récupérer. A partir du côté clair, nous calculons les 229 x 8 = 2232 valeurs possibles des octets de la clef étendue utilisés dans les sept premières rondes. Ceci nous donne les valeurs de tous les octets sauf deux de l'entrée de la couche PHT dans la ronde 7. Une étude rapide de la matrice de transition qui décrit la couche PHT de SAFER+ nous apprend une propriété intéressante: bien que chaque octet de la sortie soit inconnu lorsque un octet unique de l'entrée est inconnu, il est possible de calculer des expressions dans les octets de sortie provenant du PHT qui ne sont pas affectés par les deux octets d'entrée inconnus. A ce stade de l'attaque, nous utilisons ces expressions pour notre état de chiffrement intermédiaire, et les plaçons dans la liste ordonnée.
  Pour le côté chiffré, nous calculons les 230x8 = 2240 valeurs possibles des octets de la clef étendue utilisés dans la transformation de sortie et les 7 dernières rondes. Ceci nous donne tous les octets sauf deux de la sortie de la couche PHT à la ronde 7. Nous pouvons calculer les mêmes expressions à partir de ces octets comme ci-dessus, et nous les plaçons aussi dans la liste ordonnée.
  Le résultat est une attaque par le milieu qui demande au moins 2240 chiffrements et autant de mémoire; c'est une quantité énorme de mémoire. Toutefois, nous pouvons améliorer cela en remarquant que nous avons deviné la plupart des octets identiques de chaque côté. A chaque fois qu'un octet de clef étendue apparaît des deux côtés, nous le devinons puis nous tentons l'attaque par le milieu. Nous faisons donc ce qui suit:

  1. Deviner les octets de clef 0..14, 18..28 soit une recherche de 26 octets, ou 208 bits.
  2. En utilisant le résultat précédent, essayer toutes les valeurs possibles des octets de clef étendue 15..17. Utiliser ces octets pour chiffrer vers l'avant à partir de la sortie 6 et ainsi calculer un ensemble d'octets dérivés de la sortie de la ronde 7 qui ne dépendant pas des octets étendus 29..30, et qui seront aussi calculables à partir du bas. Générer une liste des 224 entrées à 12 octets, ordonnée.
  3. En utilisant le résultat de la recherche à l'étape (1), essayer toutes les valeurs possibles des octets de clef étendue 29..32. Calculer le même ensemble d'octets comme à l'étape (2). Pour chaque ensemble d'octets intermédiaires calculés, regarder dans la liste ordonnée s'il y a une correspondance.
  4. Si une ou plusieurs correspondances sont trouvées, nous tentons les estimations approchées à partir des côtés clair et chiffré, sur les deux paires de texte clair/chiffré. Si nous obtenons des valeurs correspondantes pour les trois, nous avons très probablement obtenu les bonnes valeurs de la clef.

    3.1  Calcul des valeurs intermédiaires

La capacité à calculer les valeurs intermédiaires est ce qui rend l'attaque possible. Ici nous expliquons plus clairement comment ces valeurs sont calculées.
  Considérons la matrice de transition qui décrit la couche PHT à chaque ronde. Soit x1..16 les octets en entrée de la couche PHT et y1..16 les octets en sortie de la couche PHT. Nous connaissons x1..14 et y3..16. Quels valeurs intermédiaires pouvons nous calculer à partir de ces octets?

equation

où z3 et z4 sont les valeurs qui ne dépendent que des octets x1..14, et qui sont connus. Nous ne pouvons pas encore calculer ces valeurs pour y3 ou y4 juste à partir des valeurs x connues, puisque x15,x16 sont inconnus. Toutefois l'expression

equation

est connue, puisqu'elle ne dépend que de x1..14. En ne connaissant que y3..16, nous pouvons toujours calculer cette valeur interne. Il y a 12 expressions indépendantes de ce type que nous pouvons utiliser, qui sont toutes de la forme a0yi - a1yj. Cela nous donne une condition de filtrage de 96 bits, donc les estimations incorrectes ne devraient provoquer de fausses alarmes qu'avec une probabilité de seulement 2-96.

3.2  Détection des recherches correctes de clefs

Comme décrit ci-dessus, pour chaque recherche de 208 bits, nous calculons 232 valeurs intermédiaires de 12 octets à partir du texte chiffré, et 224 valeurs idoines à partir du texte clair. Il y a donc 256 paires de valeurs, chacune ayant 2-96 pour probabilité de correspondre. Nous estimons qu'environ 2-40 de nos estimations 208 bits auront une valeur correspondante, donc 2168 recherches demanderont plus de travail.
  Pour gérer les valeurs correspondantes, nous utilisons trois paires de texte clair/chiffré. Pour toute recherche 208 bits, si nous trouvons une paire d'entrées correspondantes pour une pair clair/chiffré, nous essayons le suivant. Si ce dernier nous donne aussi une paire correspondante, nous essayons le troisième. Si les trois correspondent, il est très probable que nous avons les bonnes valeurs de clef.
  En pratique, cela n'a aucun effet remarquable sur le temps requis par l'attaque (en comparaison d'un travail de 2240, 2168 x 232 est négligeable).

3.3  Travail total impliqué

Pour calculer le total de travail impliqué, nous calculons simplement la quantité de travail réalisée en moyenne par recherche 208 bits. Il devrait être évident que les rares occurrences de fausses positives (correspondances dans nos 12 octets intermédiaires qui n'indiquent pas une estimation correcte de clef) ont un effet insignifiant sur ce total. Pour chaque recherche 208 bits, nous faisons:

  1. Chiffrement vers l'avant de 224 valeurs différentes, chacune pour essentiellement une moitié de la fonction de chiffrement SAFER+/256, et construction d'une liste ordonnée contenant les résultats intermédiaires, ce qui demande environ 24 x 224 ± 229 échanges en mémoire (ce qui est moins que les 224 demi-chiffrements SAFER+/256, et qui peut être encore optimisé avec l'utilisation d'une table de hachage plutôt qu'une liste ordonnée).
  2. Déchiffrement vers l'arrière de 232 valeurs différentes, chacune pour essentiellement une moitié de la fonction de chiffrement SAFER+/256, et vérifier si chaque valeur intermédiaire ne se trouve pas dans la table produite ci-dessus, ce qui demande environ 24 opérations de comparaison (ce qui est moins que les 232 demi-chiffrements SAFER+/256, et qui peut être encore optimisé avec l'utilisation d'une table de hachage plutôt qu'une liste ordonnée).

  Ainsi, les besoins totaux pour cette attaque sont les suivants:

  • Un travail équivalent à 2208 x 232 = 2240 chiffrements SAFER+/256.
  • Une quantité de mémoire d'environ 12 x 224 octets.
  • Trois textes connus en clair et leurs formes chiffrées correspondantes.
     

 4   Attaque par clefs liées de SAFER+/256


Les attaques par clefs liées ont été longuement discutées dans [WH87, Bih94, KSW96, KSW97]. Une attaque par clefs liées est une attaque où les chiffrements sont demandés en fonction de deux clefs ou plus, qui ont une relation entre elles choisie par l'attaquant. En observant les textes chiffrés produits, l'attaquant est capable d'apprendre de l'information sur les clefs utilisées.
  Lorsque nous avons vu la préparation des clefs de SAFER+/256 pour la première fois, nous pensions déjà qu'une attaque par clefs liées serait possible, à cause de la mauvaise diffusion de la clef. La meilleure attaque à clefs liées que nous avons trouvée est aussi simple que cela:

  1. Changer quelques octets de la clef étendue qui sont utilisé dans les premières rondes, et qui ne sont pas utilisés à nouveau avant un bon moment dans le processus de chiffrement. Utiliser ces changements pour déterminer

    equation

    K est la clef originale et K* est la clef altérée.

  2. Choisir une différence

    equation

    pour approcher la différence dans K avec une probabilité assez importante.

  3. Lorsque nous avons la bonne paire, nous obtiendrons les mêmes valeurs après plusieurs rondes de chiffrement de X avec la clef K, et du chiffrement de X* avec la clef K*. Nous devinons les derniers octets des dernières quelques rondes pour le tester.

  La table 5 souligne les octets de la clef utilisés à chaque ronde dans la couche non-linéaire de SAFER+/256.

equation
Table 5: comment les octets de la clef sont utilisés (et devinés) dans SAFER+/256

Ronde

Estimation
par le haut

Estimation
par le bas

0

-

0-16

1

-

2-18

2

-

4-20

3

-

6-22

4

-

8-24

5

-

10-26

6

-

12-28

7

-

14-30

8

-

16-32

9

30

18-32, 0-1

10

28

20-32, 0-3

11

26

22-32, 0-5

12

24

24-32, 0-7

13

22

26-32, 0-9

14

20

28-32, 0-11

15

18

30-32, 0-13

OX

16

32, 0-14

equation

  A partir de cela, nous pouvons voir deux faits qui seront utilisés ci-dessous pour construire une attaque par clefs liées sur SAFER+/256:

  1. Les octets de clef étendue 2 et 3, après avoir été utilisés aux rondes 0 et 1, ne sont pas utilisés à nouveau avant la ronde 10.
  2. Nous pouvons apprendre la sortie de la ronde 11 en devinant 24 octets (192 bits) du matériel de la clef étendue.

    4.1  Aperçu de l'attaque

Dans l'attaque, nous ne commençons pas sans connaître K, mais nous choisissons une relation XOR entre K et K*, une clef liée. Nous sommes alors capables de demander une séquence de textes clair choisis sous ces deux clefs. Nous utilisons les relations entre les textes chiffrés résultant pour obtenir la clef originale, K. Notre objectif est de modifier la clef, et trouver un moyen quelconque de faire un changement par décalage dans le texte en clair chiffré sous la clef modifiée. Nous tenterons alors plusieurs paires de texte clair (3 x 232) sous ces deux clefs différentes; la plupart de ces paires émergeront après une ou deux rondes de chiffrement, mais dans un petit nombre de paires, que nous appelons bonnes paires, les changements apparaissent dès la sortie de la ronde 0 sous une certaine forme, qui annule les différences de clefs dans la couche non-linéaire de la ronde 1, et qui n'apparaissent pas à nouveau avant la couche non-linéaire de la ronde 10. Ceci nous permet de deviner assez du matériel de la clef pour voir la sortie de la ronde 11. A partir de là, nous sommes capables de distinguer les bonnes paires des mauvaises lorsque nous avons deviné la bonne valeur pour cette partie de la clef. Détecter les bonnes paires est ainsi comment nous déterminons qu'une estimation partielle de clef est correcte.
  Nous allons modifier les octets 2 et 3 de la clef (en comptant à partir de zéro). Dans la première ronde, nous choisissons des paires à chiffrer sous chaque clef qui, dans certaines paires, nous donneront une différence de sortie de (0, 0, 128, 0, 128, 128, 0, ..., 0). Ces paires amènent une différence d'entrée dans la seconde ronde de (128, 128, 0, 0, ..., 0). Les octets modifiés de la clef auront alors la probabilité approchée 2-8 d'annuler ce changement, afin que la sortie de la seconde ronde ait une différence nulle entre les chiffrements avec les deux clefs. Lorsque cela survient, nous pouvons alors deviner les derniers 192 bits du matériel de la clef utilisée, et déchiffrer à partir de la sortie de la ronde 11. Ceci nous permet de comparer les même 12 octets de résultat intermédiaire comme nous l'avons fait dans l'attaque par le milieu, ci-dessus. Si ces octets sont identiques pour les paires de texte considérées, cela signifie qu'il est très probable qu'il s'agisse d'une bonne paire (probabilité de 2-96 pour les mauvaises paires, et 1 pour les bonnes paires). Ceci fonctionne car les octets de clef changées, une fois utilisés, ne sont pas utilisés à nouveau avant la ronde 10 (en comptant à partir de zéro).
  Le travail impliqué dans l'attaque est l'estimation partielle (192 bits) pour chacun des 256 paires de texte candidats chiffrés sous les deux clefs liées, plus une petite quantité supplémentaire de travail dont nous avons besoin pour éliminer les fausses alarmes. Au lieu de cela, nous utilisons notre estimation partielle pour déterminer quelles paires peuvent être les bonnes si l'estimation est correcte. Nous réalisons ainsi 2200 déchiffrements d'essai partiels SAFER+/256 pour l'attaque. C'est approximativement la même quantité de travail que 2199 chiffrements complets SAFER+/256. Nous déchiffrons par essai des paires de blocs, afin que notre total de travail soit approximativement équivalent à 2200 chiffrements SAFER+.
  Nous travaillons donc approximativement pour 2200 chiffrements SAFER+/256, et nous avons besoin de 3 x 232 textes clair choisis sous deux clefs liées, et nous apprenons 192 bits de la clef étendue. Le reste du matériel de la clef peut être appris après avec une recherche de 64 bits.

4.2  Choisir la différence de clef

La différence de clef est (0, 0, c, 128, 0, 0, ..., 0), où les différences sont indiquées en termes d'octets, et c est une différence d'un octet autre que 0 ou 128 (à peu près la moitié des valeurs possibles de c doivent fonctionner pour cette attaque). Nous devons choisir c afin que pour au moins une paire d'octet u nous ayons la propriété telle que

equation

exp[x] = 45x mod 256. La couche non-linéaire de la ronde 0 aura les différences suivantes (au niveau des octets) dans ses octets de sous-clef:

equation

La couche non-linéaire de la ronde 1 aura les différences suivantes (au niveau des octets) dans ses octets de sous-clef:

equation

4.3  Choisir les paires de texte clair

En analysant la matrice qui décrit la couche de mélange, nous avons pu trouver la différentielle suivante:

equation

Nous avons aussi été capables de voir qu'avec une paire de texte en clair avec la différence (128, 128, 0, 0, ..., 0) entrant dans la ronde 1, notre différence de clef choisie a une probabilité de s'annuler contre la différence des textes en clair, ce qui signifie que les 8 rondes qui suivent sont identiques dans les deux textes.
  Ceci laisse la question d'obtenir des paires de texte clair qui donnent la différence désirée en sortie à partir de la ronde 0. Ceci est en fait assez facile à obtenir. Nous avons besoin de paires de texte clair P, P' telles que

equation

où (u, v) satisfait

equation

(w, x) satisfait

equation

et (y, z) satisfait

equation

pour chaque valeur possible de xk1, xk4 et xk5 pour les indices

equation

Nous attendons ainsi 3 x 232 paires de texte clair.
  Notez qu'en ayant i prenant toutes les valeurs possibles, dans la sortie de la ronde 0, l'octet 7 prend toutes les valeurs possibles. Après la couche de mélange, ceci force l'octet 0 de l'entrée à prendre toutes les valeurs possibles. Puisque nous savons que pour au moins une valeur de u nous avons:

equation

equation

Nous savons que pour au moins l'une de ces valeurs, si la différence en entrée est (128,128,0,0,...,0) alors il s'agira d'une bonne paire.

4.4  Extraction de la clef

Nous avons maintenant 3 x 232 paires chiffrées sous les deux clefs liées. Pour extraire la clef, nous devons deviner assez de matériel de la clef pour apprendre la sortie de la ronde 11, 192 bits. Nous devons alors réaliser un déchiffrement partiel de toute paire de texte qui peut former une bonne paire, afin de les trouver.
  Au lieu de faire des déchiffrements d'essai sur tous les 3 x 232 paires de texte, nous utilisons une information sur la clef que nous avons déjà obtenue. Les octets 1, 4 et 5 de la clef étendue doivent être devinés avant d'obtenir la sortie de la ronde 11. Chacun de ces octet ne laissera que 3 x 256 paires de texte comme paires possibles, à cause de la manière de sélection des textes.

equation
Table 6: différentielle tronquée utilisée dans l'attaque de clefs liées

Part du chiffrement

Différentielle tronquée
en sortie

Commentaires

Entrée

(0,?,c,128,?,?,0,0,...,0)

Première addition
de clef

(0,?,0,0,?,?,0,0,...,0)

S'annule dans les octets 2,3 avec
la probabilité = 1.

Table-S

(0,-c,0,0,128,128,0,0,...,0)

Événements critiques aux octets 1, 4, 5.

Seconde addition
de clef

(0,0,128,0,128,128,0,0,...,0)

S'annule à l'octet 1.

Mélange

(128,128,0,0,...,0)

Probabilité 1.

Première addition
de clef

(?,0,0,...,0)

Événement critique à l'octet 0,
s'annule avec prob. = 1 à l'octet 1.

Table-S

(128,0,0,...,0)

Seconde addition
de clef

(0,0,...,0)

S'annule à l'octet 1.

equation

Pour chaque estimation de 192 bits des dernières rondes du matériel de la clef, nous faisons:

  1. Sélectionner un jeu de 256 paires qui (à cause de la manière dont nous choisissons les textes) est garanti d'avoir au moins une bonne paire (c'est un jeu de paires avec les paires (u, v), (w, x) et (y, z) sélectionnées avec l'estimation initiale, avec j=0 et avec i prenant toutes les valeurs entre 0 et 255 incluses).
  2. Déchiffrer partiellement les 256 paires et calculer les mêmes 12 expressions que nous avions utilisées dans l'attaque par le milieu, ci-dessus (cela donne une valeur de 12 octets qui sera identique s'il s'agit de la bonne paire).
  3. Si nous obtenons une correspondance entre les 12 octets de valeurs dans les deux textes pour toute paire, essayer le jeu des 256 paires avec j=1 et j=2. Si elles correspondant toutes, alors nous avons une forte probabilité d'avoir une bonne paire, et notre estimation des 192 bits de la clef est correcte.
     

 5   Correction des préparations de clef de SAFER+/192 et SAFER+/256


Ayant démontré les faiblesses des préparations de clef de SAFER+/192 et SAFER+/256, nous avons voulu corriger ces faiblesses. Le problème avec SAFER+ et sa préparation de clef c'est qu'il faut trop de rondes à l'algorithme pour impliquer toute la clef dans le chiffrement. Nos deux attaques exploitent d'ailleurs cette faiblesse.
  Les trois chiffrements SAFER+ utilisent 32 octets de clef par ronde. Les plus grandes clefs que ces chiffrements auront à traiter sont de 32 octets. Intuitivement alors, obtenir une bonne diffusion de la clef devrait être une tâche facile. Ci-dessous, nous proposons un changement à SAFER+/256 et SAFER+/192. Ceci nous donne donc deux nouvelles préparations de clef en ligne avec SAFER+/128, et les trois chiffrements auront donc pour propriété que chaque ronde est affectée par chaque bit de la clef.
  Soit ski,j l'octet de sous-clef j utilisé à la ronde i, xki l'octet i de la clef étendue (la clef avec un octet de parité ajouté à sa fin) et f(x,i,j) représentant la rotation de bits et l'addition avec un mot biaisé à appliquer à l'octet de clef étendue et sur lequel ski,j est basé. Notez que f(x,i,j) n'a pas été modifiée.
  Nous avons donc la formule:

equation

pour les clefs de 256 bits, et

equation

pour les clefs de 192 bits.
  Les tables 7 et 8 montrent les octets de la clef étendue qui sont utilisés pour chaque position d'octet de chaque deux octets de sous-clef à chaque ronde. La rotation d'octets et de l'utilisation de biais de clefs n'est pas modifiée, nous sélectionnons simplement les octets de clef étendue à être utilisés, et dans un ordre différent que les préparations originelles de SAFER+. Dans les tables, la première colonne de chiffres représente la ronde, qui est numérotée de 0 à 15 pour SAFER+/256 et de 0 à 11 pour SAFER+/192. Le reste des colonnes montre, pour chaque position d'octet, quel octet de clef étendue doit être utilisé.
  Pour les deux nouveaux types de préparation de clef, nous avons les propriétés suivantes:

  1. Pour deviner une sous-clef, quelle que soit la ronde, un attaquant doit deviner la totalité de la clef. Ceci élimine les attaques qui fonctionnent pas l'estimation d'une partie de la clef sur plusieurs rondes.
  2. Aucune de nos attaques ne fonctionne contre cette nouvelle préparation de clef.
  3. Tout changement de la clef modifie au moins un octet du matériel de clef utilisé à chaque ronde.
  4. Comme nous le discutons dans l'appendice, SAFER+ ne semble pas avoir de clefs faibles, semi-faibles ou équivalentes. Cela semble également vrai pour notre préparation de clef proposée.
  5. Chaque octet de clef étendue est combiné avec deux autres à différents moments de la préparation de la clef.
  6. Avec des clefs de 192 bits, la préparation proposée utilise chaque octet de la clef étendue au moins une fois dans chaque ronde. Avec des clefs de 256 bits, la préparation proposée utilise chaque octet de clef étendue dans au moins 15 rondes.
  7. Avec des clefs de 256 bits, aucun octet de clef étendue n'est utilisé deux fois au sein d'une même ronde.
  8. Les octets de clef étendue ne sont jamais utilisés avec eux-mêmes dans la couche de substitution d'octet non-linéaire.
  9. Les deux préparations proposées ont quelques octets qui se retrouvent entre les couches non-linéaires de rondes successives, afin que quelques octets puisse avoir deux valeurs dérivées du même octet de clef étendue ajouté en succession (la préparation originelle de SAFER+ dispose aussi de cette propriété). Ceci ne semble pas affaiblir le chiffrement d'aucune manière.
  10. Des paires d'octets de la clef étendue sont utilisés ensemble dans la couche non-linéaire de la fonction de ronde de SAFER+ dans beaucoup de rondes successives, aussi bien dans la préparation originelle que dans celle que nous proposons. Toutefois, dans notre préparation, et dans le cas des 256 bits, chaque octet de clef étendue est utilisé avec un seul et autre octet de clef étendue dans tout autre ronde, et il est utilisé avec le même octet de clef dans plusieurs rondes successives. Ainsi, dans notre préparation proposée pour 256 bits, l'octet de clef étendue 15 est utilisé avec l'octet 31 aux rondes 0-7 et avec l'octet de clef étendue 32 aux rondes 9-15. Ceci ne semble pas affaiblir le chiffrement dans son ensemble.

  Notez que ces préparations modifiées sont très proches de l'esprit des préparations originelles, et ne demandent qu'une petite modification de programmation. En fait, elles appliquent le même principe que la préparation de SAFER+/128 où la totalité de la clef affecte chaque ronde. Il y a des raisons de penser qu'un tel changement permettrait à SAFER+ de passer à la seconde étape de l'AES. En conservant la même convention que celle recommandée par Lars Knudsen à la préparation de clef de SAFER [Knu95a] nous suggérons d'appeler ces versions modifiées SAFER+/192-SK et SAFER+/256-SK.
 

 6   Questions ouvertes


Ces résultats amènent une série de questions sur la conception de la préparation de clefs de SAFER+:

  1. Est-ce que nos attaques par le milieu et à clefs liées sont les meilleures attaques de leur type? Est-ce que des attaques similaires peuvent être réalisées contre SAFER+/192?
  2. Est-ce qu'une variante de notre attaque à clefs liées peuvent être utilisées pour trouver des collisions plus facilement lorsque SAFER+/192 et SAFER+/156 sont utilisés comme fonctions de hachage?
  3. Est-ce que d'autres attaques sont possibles en exploitant la mauvaise diffusion de la clef dans SAFER+/192 et SAFER+/256?
  4. Est-ce que des attaques sont possibles contre notre proposition de préparations?
  5. Est-ce qu'il y a encore des propriétés intéressantes à découvrir?

  Nous espérons que SAFER+ recevra plus d'études afin de répondre à ces questions.

equation
Table 7: utilisation des octets de clef étendue dans SAFER+/256-SK

00

00
16

01
17

02
18

03
19

04
20

05
21

06
22

07
23

08
24

09
25

10
26

11
27

12
28

13
29

14
30

15
31

01

02
18

03
19

04
20

05
21

06
22

07
23

08
24

09
25

10
26

11
27

12
28

13
29

14
30

15
31

16
32

17
00

02

04
20

05
21

06
22

07
23

08
24

09
25

10
26

11
27

12
28

13
29

14
30

15
31

16
32

17
00

18
01

19
02

03

06
22

07
23

08
24

09
25

10
26

11
27

12
28

13
29

14
30

15
31

16
32

17
00

18
01

19
02

20
03

21
04

04

08
24

09
25

10
26

11
27

12
28

13
29

14
30

15
31

16
32

17
00

18
01

19
02

20
03

21
04

22
05

23
06

05

10
26

11
27

12
28

13
29

14
30

15
31

16
32

17
00

18
01

19
02

20
03

21
04

22
05

23
06

24
07

25
08

06

12
28

13
29

14
30

15
31

16
32

17
00

18
01

19
02

20
03

21
04

22
05

23
06

24
07

25
08

26
09

27
10

07

14
30

15
31

16
32

17
00

18
01

19
02

20
03

21
04

22
05

23
06

24
07

25
08

26
09

27
10

28
11

29
12

08

16
32

17
00

18
01

19
02

20
03

21
04

22
05

23
06

24
07

25
08

26
09

27
10

28
11

29
12

30
13

31
14

09

18
01

19
02

20
03

21
04

22
05

23
06

24
07

25
08

26
09

27
10

28
11

29
12

30
13

31
14

32
15

00
16

10

20
03

21
04

22
05

23
06

24
07

25
08

26
09

27
10

28
11

29
12

30
13

31
14

32
15

00
16

01
17

02
18

11

22
05

23
06

24
07

25
08

26
09

27
10

28
11

29
12

30
13

31
14

32
15

00
16

01
17

02
18

03
19

04
20

12

24
07

25
08

26
09

27
10

28
11

29
12

30
13

31
14

32
15

00
16

01
17

02
18

03
19

04
20

05
21

06
22

13

26
09

27
10

28
11

29
12

30
13

31
14

32
15

00
16

01
17

02
18

03
19

04
20

05
21

06
22

07
23

08
24

14

28
11

29
12

30
13

31
14

32
15

00
16

01
17

02
18

03
19

04
20

05
21

06
22

07
23

08
24

09
25

10
26

15

30
13

31
14

32
15

00
16

01
17

02
18

03
19

04
20

05
21

06
22

07
23

08
24

09
25

10
26

11
27

12
28

OX

32

00

01

02

03

04

05

06

07

08

09

10

11

12

13

14


 

 7   Remerciements


Les auteurs souhaitent remercier Jim Massey et les consultants anonymes pour l'information utilisée dans ce document.

Références

[Ada98] C. Adams, "The CAST-256 Encryption Algorithm" NIST AES Proposal, Jun 98.

[Bih94] E. Biham, "New Types of Cryptanalytic Attacks Using Related Keys" Journal of Cryptology, v. 7, n. 4, 1994, pp. 229-246.

[BPS90] L. Brown, J. Pieprzyk, and J. Se berry, "LOKI: A Cryptographic Primitive for Authentication and Secrecy Applications" Advances in Cryptology - AUSCRYPT '90 Proceedings, Springer-Verlag, 1990, pp. 229-236.

[BS93] E. Biham and A. Shamir, Differential Cryptanalysis of the Data Encryption Standard, Springer-Verlag, 1993.

[BW99] A. Biryukov and D. Wagner, "Slide attacks" Fast Software Encryption, 6th International Workshop Proceedings, Springer-Verlag, à paraître.

[DR98] J. Daemen and V. Rijmen, "AES Proposal: Rijndael" NIST AES Proposal, Jun 98.

[HKM95] C. Harpes, G. Kramer, and J. Massey, "A Generalization of Linear Cryptanalysis and the Applicability of Matsui's Piling-up Lemma" Advances in Cryptology - EUROCRYPT '95 Proceedings, Springer-Verlag, 1995, pp. 24-38.

[HM97] C. Harpes and J. Massey, "Partitioning Cryptanalysis" Fast Software Encryption, 4th International Workshop Proceedings, Springer-Verlag, 1997, pp. 13-27.

[Knu93] L.R. Knudsen, "Cryptanalysis of LOKI" Advances in Cryptology - ASIACRYPT '91, Springer-Verlag, 1993, pp. 22-35.

[Knu95a] L.R. Knudsen, "A Key-Schedule Weakness in SAFER K-64" Advances in Cryptology - CRYPTO '95 Proceedings, Springer-Verlag, 1995, pp. 274-286.

[Knu95b] L.R. Knudsen, "Truncated and Higher Order Differentials" Fast Software Encryption, 2nd International Workshop Proceedings, Springer-Verlag, 1995, pp. 196-211.

[Knu95c] L.R. Knudsen, "New Potentially 'Weak' Keys for DES and LOKI" Advances in Cryptology - EUROCRYPT '94 Proceedings, Springer-Verlag, 1995, pp. 419-424.

[KSW96] J. Kelsey, B. Schneier, and D. Wagner, "Key-Schedule Cryptanalysis of IDEA, G-DES, GOST, SAFER, and Triple-DES" Advances in Cryptology - CRYPTO '96 Proceedings, Springer-Verlag, 1996, pp. 237-251.

[KSW97] J. Kelsey, B. Schneier, and D. Wagner, "Related-Key Cryptanalysis of 3-WAY, Biham-DES, CAST, DES-X, NewDES, RC2, and TEA" Information and Communications Security, First International Conference Proceedings, Springer-Verlag, 1997, pp. 203-207.

[Mas94] J.L. Massey, "SAFER K-64: A Byte-Oriented Block-Ciphering Algorithm" Fast Software Encryption, Cambridge Security Workshop Proceedings, Springer- Verlag, 1994, pp. 1-17.

[Mat94] M. Matsui, "Linear Cryptanalysis Method for DES Cipher" Advances in Cryptology - EUROCRYPT '93 Proceedings, Springer-Verlag, 1994, pp. 386-397.

[MKK98] J. Massey, G. Khachatrian, and M. Kuregian, "Nomination of SAFER+ as Candidate Algorithm for the Advanced Encryption Standard (AES)", NIST AES Proposal, 1998.

[NBS77] National Bureau of Standards, NBS FIPS PUB 46, "Data Encryption Standard" National Bureau of Standards, U.S. Department of Commerce, Jan 1977.

[NTT98] Nippon Telephone and Telegraph, "Specication of E2 - a 128-bit Block Cipher" NIST AES Proposal, Jun 98.

[SKW+98] B. Schneier, J. Kelsey, D. Whiting, D. Wagner, C. Hall, and N. Ferguson, "Twofish: A 128-Bit Block Cipher" NIST AES Proposal, Jun 98.

[Wag95] D. Wagner, \Cryptanalysis of S-1" sci.crypt Usenet posting, 27 Aug 1995.

[WH87] R. Winternitz and M. Hellman, "Chosen key Attacks on a Block Cipher" Cryptologia, v. 11, n. 1, Jan 1987, pp. 16-20.

equation
Table 8: utilisation des octets de clef étendue dans notre préparation proposée

00

00
16

01
17

02
18

03
19

04
20

05
21

06
22

07
23

08
24

09
00

10
01

11
02

12
03

13
04

14
05

15
06

01

02
18

03
19

04
20

05
21

06
22

07
23

08
24

09
00

10
01

11
02

12
03

13
04

14
05

15
06

16
07

17
08

02

04
20

05
21

06
22

07
23

08
24

09
00

10
01

11
02

12
03

13
04

14
05

15
06

16
07

17
08

18
09

19
10

03

06
22

07
23

08
24

09
00

10
01

11
02

12
03

13
04

14
05

15
06

16
07

17
08

18
09

19
10

20
11

21
12

04

08
24

09
00

10
01

11
02

12
03

13
04

14
05

15
06

16
07

17
08

18
09

19
10

20
11

21
12

22
13

23
14

05

10
01

11
02

12
03

13
04

14
05

15
06

16
07

17
08

18
09

19
10

20
11

21
12

22
13

23
14

24
15

25
16

06

12
03

13
04

14
05

15
06

16
07

17
08

18
09

19
10

20
11

21
12

22
13

23
14

24
15

00
16

01
17

02
18

07

14
05

15
06

16
07

17
08

18
09

19
10

20
11

21
12

22
13

23
14

24
15

00
16

01
17

02
18

03
19

04
20

08

16
07

17
08

18
09

19
10

20
11

21
12

22
13

23
14

24
15

00
16

01
17

02
18

03
19

04
20

05
21

06
22

09

18
09

19
10

20
11

21
12

22
13

23
14

24
15

00
16

01
17

02
18

03
19

04
20

05
21

06
22

07
23

08
24

10

20
03

21
04

22
05

23
06

24
07

25
08

26
09

27
10

28
11

29
12

30
13

31
14

32
15

00
16

01
17

02
18

11

22
13

23
14

24
15

00
16

01
17

02
18

03
19

04
20

05
21

06
22

07
23

08
24

09
00

10
01

11
02

12
03

OX

24

00

01

02

03

04

05

06

07

08

09

10

11

12

13

14

 

 Annexe A: propriétés additionnelles

 

A.1  Sous-clefs de rondes et attaques par "glissement"

Dans certains chiffrements, il est possible à une séquence de sous-clefs de se répéter quelque part pendant le chiffrement. Par exemple, on pourrait voir la même sous-clef être utilisée toutes les deux rondes dans le chiffrement. Ceci permet une attaque où l'on choisit les textes en clair afin d'obtenir un texte X1 tel qu'il soit le résultat des deux premières rondes de chiffrement du texte X0. Si c'est le cas, alors Y1 = E(X1) est le résultat de deux rondes de chiffrement en plus que Y0 = E(Y0). Ceci permet une attaque directe afin de récupérer les sous-clefs des deux premières et deux dernières rondes. Cela s'appelle une attaque par "glissement" [Wag95, BW99].
  Dans SAFER+, le biais de sous-clef semble l'empêcher. Il n'y a pas de moyen apparent pour que les sous-clefs se répètent, que ce soit dans le cas d'une clef unique, ou bien dans une attaque à clefs liées du style Biham [Bih94].

A.2  Clefs faibles et semi-faibles du type DES, clefs équivalentes et propriétés de symétrie

Dans le DES, il existe quelques clefs qui sont auto-inverses; chiffrer tout texte deux fois sous une telle clef redonne le texte d'entrée original. Nous sommes incapables de prouver leur non-existence, mais nous avons la forte intuition qu'il n'existe pas de clefs faibles dans SAFER+.
  La raison est que les processus de chiffrement et de déchiffrement, bien que similaires, ne sont pas identiques. Ceci signifie qu'en utilisant une même sous-clef pour déchiffrer puis déchiffrer ne donne pas de clef inverse. La matrice de transition qui décrit la couche de mélange est très différente de son inverse; il n'y a aucun moyen de changer quelques octets utilisés de manière à annuler l'effet de cette matrice de transition. Ainsi, s'il y a des clefs auto-inverses, elles ne peuvent être construites simplement en choisissant des clefs dont la ronde 0 est l'inverse de la ronde 15, la ronde 1 l'inverse de la ronde 14, etc. Nous serions très surpris de découvrir des paires faibles ou semi-faibles dans SAFER+.
  Dans le DES [NBS77] il y a aussi des clefs semi-faibles; ce sont des paires où le chiffrement sous certaines clefs peut être déchiffré avec une autre clef d'une autre paire. Pour les raisons indiquées ci-dessus, nous ne pensons pas que SAFER+ ait des paires de clefs semi-faibles.
  DES a aussi des clefs quasi-faibles; ce sont des paires de clefs pour lesquels beaucoup plus de textes clairs ont des formes chiffrées identiques que prévu. D'un certain sens, une paire de clefs quasi-faibles représente un choix de deux permutations "voisines". Nous n'avons pas trouvé de paires de clefs quasi-faibles dans SAFER+, et nous ne savons pas si elles existent. Toutefois, il ne semble pas y avoir d'opportunité pour construire des clefs quasi-faibles dans SAFER+ comme elles sont construites dans [Knu95c] puisque tout changement de la clef de SAFER+ provoque des différences non-nulles à chaque fois qu'une partie modifiée de la clef est utilisée.
  Dans certains chiffrements, il y a des clefs équivalentes; des paires de clefs qui produisent un même résultat chiffré. Par exemple, LOKI-89 [BPS90] est connu pour avoir des classes de clefs équivalentes [Knu93]. Nous n'avons pas été capables de trouver un moyen pour construire des clefs équivalentes dans SAFER+. En fait, cela semble très difficile à réaliser sous SAFER+. Tout changement de la clef est utilisé dans plusieurs rondes, et il est très difficile d'imaginer deux clefs dont les changements s'annuleraient pendant plus d'une ou deux rondes. Nous serions très surpris de trouver des clefs équivalentes dans SAFER+.

A.3  Tables-S dépendantes des clef et caractéristiques

SAFER+ est typiquement décrit comme un chiffrement à Tables-S fixes et dont les matériaux de clef sont combinés avant et après les Tables-S. Toutefois, il est possible de décrire SAFER+ de manière alternative, avec seize Tables-S dépendantes de la clef à chaque ronde. Dans ce cas, les matériaux de la clef sont directement combinés pendant la transformation de sortie.
  Une Table-S dépendante de la clef peut être produite en choisissant deux octets de clef,
k0,k1 et une Table-S fixe, exp[] ou log[]. Nous définissons alors:

equation

  La raison pour considérer ces Tables-S comme dépendantes de la clef est qu'il y a beaucoup de propriétés de la Table-S combinée qui ne sont pas présentes dans les Tables-S exp[] ou log[]. Actuellement, nous n'avons pas d'analyse basée sur cette observation. Nous ne serions pas surpris de voir quelques choix de k0,k1 pour lesquels la Table-S résultante serait non habituellement faible vis-à-vis des attaques différentielles [BS93], linéaires [Mat94], linéaires généralisées [HKM95] ou de partition [HM97]. Puisque une succession de trois octets de clef définissent environ seize Tables-S dépendantes de la clef malgré tout, nous serions très surpris de voir des clefs qui donnent de très mauvaises propriétés linéaires, différentielles ou autres pendant tout le chiffrement, à cause de la manière dont la couche de mélange étale les caractéristiques linéaires ou différentielles rapidement. Toutefois, nous pourrions voir quelques clefs qui nous donneraient des mauvaises propriétés linéaires, différentielles et autres pendant un petit nombre de rondes consécutives du chiffrement.
  Un autre problème possible serait l'existence possible de quelques octets de clef étendue quadruples (
w, x, y, z) tels qu'une permutation d'un octet défini par w, x soit identique à une permutation formée par y, z aux mêmes positions. Si cela survient, alors échanger y, z pour w, x n'aurait pas d'effet pendant quelques rondes dans notre préparation de clef proposée (en supposant que le quadruple ne fonctionne que pour une seule permutation définie, soit celle qui commence par un XOR soit celle qui commence par une addition, et considérant SAFER+/256-SK, le changement n'aurait d'effet que pendant 4 des premières 8 rondes du chiffrement, au coût d'un changement radical dans les dernières 8 rondes suivantes). Cela ne semble pas poser de menace pratique au chiffrement.



 Traduction


Si vous trouvez une faute ou une coquille dans cette traduction, veuillez
me le signaler.