Misty1

algorithme de chiffrement par bloc

Misty1 (pour «Mitsubishi Improved Security Technology») a été créé en 1995 par Mitsuru Matsui pour Mitsubishi Electric[2].

Misty1
Description de l'image Misty1 alg.png.
Résumé
Concepteur(s) Mitsuru Matsui
Première publication 1995
Dérivé de Aucun
Chiffrement(s) basé(s) sur cet algorithme Camellia, MISTY2, KASUMI
Caractéristiques
Taille(s) du bloc 64 bits
Longueur(s) de la clé 128 bits
Structure réseau de Feistel
Nombre de tours 8 tours

Meilleure cryptanalyse

Une attaque complète avec recouvrement total de la clef en 263,9999 chiffrés choisis et en temps 279 ou en 264 chiffrés choisis et en temps 269.5 opérations[1]

Misty1 est un algorithme de chiffrement symétrique par blocs de 64 bits avec une clé de 128 bits et un nombre variable de tours, basé sur un réseau de Feistel. Misty1 est conçu pour résister à la cryptanalyse différentielle et à la cryptanalyse linéaire, et pour être très rapide dans ses mises en œuvre matérielles et logicielles. Il est recommandé d'utiliser Misty1 avec huit tours pour un bon compromis vitesse/sécurité.

Description de l'algorithme

modifier

L'algorithme peut être divisé en deux parties, à savoir la gestion de la clé et le chiffrement/déchiffrement à proprement parler.

Terminologie

modifier

Les opérateurs suivants sont utilisés pour décrire l'algorithme :

Gestion de la clé

modifier

L'expansion de la clé est réalisé par l'algorithme suivant :

pour i = 0, etc., 7 faire
EK[i] = K[i*2]*256 + K[i*2+1]
finpour pour i = 0, etc., 7 faire
EK[i+ 8] = FI(EK[i], EK[(i+1)%8])
EK[i+16] = EK[i+8] & 0x1ff
EK[i+24] = EK[i+8] >> 9 finpour

K est la clé secrète de 128 bits et chaque octet de K est noté K[i].

EK est la clé étendue et chaque élément de EK représente deux octets et est noté EK[i].

K[0 .. 15] est copié dans EK[0 .. 7] puis l'extension de la clé est produite à partir de EK[0 .. 7] en utilisant la fonction FI (décrite dans la section suivante) et est stocké dans EK[8 .. 15].

Le chiffrement

modifier

Cette partie décrit les deux fonctions utilisée pour le chiffrement : FO et FL.

La fonction FO utilise (comme l'expansion de la clé ci-dessus) la sous-routine FI. La sous-routine FI utilise deux boîtes-S (S-BOXES) à savoir S7 et S9.

La fonction FO

modifier

La fonction FO prend deux paramètres. Le premier est une entrée de 32 bits nommée FO_IN, l'autre est un index d'EK noté k. FO renvoie un buffer de 32 bits de données nommé FO_OUT (ceci est dû à sa structure de schéma de Feistel sur 64 bits).

fonction FO(FO_IN, k)
variables t0, t1 (entiers de 16 bits)
début
t0 = FO_IN >> 16
t1 = FO_IN & 0xffff
t0 = t0 ^ EK[k]
t0 = FI(t0, EK[(k+5)%8+8])
t0 = t0 ^ t1
t1 = t1 ^ EK[(k+2)%8]
t1 = FI(t1, EK[(k+1)%8+8])
t1 = t1 ^ t0
t0 = t0 ^ EK[(k+7)%8]
t0 = FI(t0, EK[(k+3)%8+8])
t0 = t0 ^ t1
t1 = t1 ^ EK[(k+4)%8]
FO_OUT = (t1<<16) | t0
retourner FO_OUT
fin

La fonction FI

modifier

La fonction FI prend deux paramètres. Le premier est une entrée de 16 bits nommée FI_IN, l'autre est une partie d'EK de 16 bits, à savoir FI_KEY. FI renvoie un buffer de 16 bits, FI_OUT. La fonction FI effectue une substitution d'octet non linéaire par boîte-S.

fonction FI(FI_IN, FI_KEY)
variable d9 (entier de 9 bits)
variable d7 (entier de 7 bits)
début
d9 = FI_IN >> 7
d7 = FI_IN & 0x7f
d9 = S9[d9] ^ d7
d7 = S7[d7] ^ d9
(d7 = d7 & 0x7f)
d7 = d7 ^ (FI_KEY >> 9)
d9 = d9 ^ (FI_KEY & 0x1ff)
d9 = S9[d9] ^ d7
FI_OUT = (d7<<9) | d9
retourner FI_OUT
fin

Voici la description des tables S7 et S9 en notation hexadécimale :

S7 0 1 2 3 4 5 6 7 8 9 a b c d e f
00: 1b 32 33 5a 3b 10 17 54 5b 1a 72 73 6b 2c 66 49
10: 1f 24 13 6c 37 2e 3f 4a 5d 0f 40 56 25 51 1c 04
20: 0b 46 20 0d 7b 35 44 42 2b 1e 41 14 4b 79 15 6f
30: 0e 55 09 36 74 0c 67 53 28 0a 7e 38 02 07 60 29
40: 19 12 65 2f 30 39 08 68 5f 78 2a 4c 64 45 75 3d
50: 59 48 03 57 7c 4f 62 3c 1d 21 5e 27 6a 70 4d 3a
60: 01 6d 6e 63 18 77 23 05 26 76 00 31 2d 7a 7f 61
70: 50 22 11 06 47 16 52 4e 71 3e 69 43 34 5c 58 7d


S9 0 1 2 3 4 5 6 7 8 9 a b c d e f
000: 1c3 0cb 153 19f 1e3 0e9 0fb 035 181 0b9 117 1eb 133 009 02d 0d3
010: 0c7 14a 037 07e 0eb 164 193 1d8 0a3 11e 055 02c 01d 1a2 163 118
020: 14b 152 1d2 00f 02b 030 13a 0e5 111 138 18e 063 0e3 0c8 1f4 01b
030: 001 09d 0f8 1a0 16d 1f3 01c 146 07d 0d1 082 1ea 183 12d 0f4 19e
040: 1d3 0dd 1e2 128 1e0 0ec 059 091 011 12f 026 0dc 0b0 18c 10f 1f7
050: 0e7 16c 0b6 0f9 0d8 151 101 14c 103 0b8 154 12b 1ae 017 071 00c
060: 047 058 07f 1a4 134 129 084 15d 19d 1b2 1a3 048 07c 051 1ca 023
070: 13d 1a7 165 03b 042 0da 192 0ce 0c1 06b 09f 1f1 12c 184 0fa 196
080: 1e1 169 17d 031 180 10a 094 1da 186 13e 11c 060 175 1cf 067 119
090: 065 068 099 150 008 007 17c 0b7 024 019 0de 127 0db 0e4 1a9 052
0a0: 109 090 19c 1c1 028 1b3 135 16a 176 0df 1e5 188 0c5 16e 1de 1b1
0b0: 0c3 1df 036 0ee 1ee 0f0 093 049 09a 1b6 069 081 125 00b 05e 0b4
0c0: 149 1c7 174 03e 13b 1b7 08e 1c6 0ae 010 095 1ef 04e 0f2 1fd 085
0d0: 0fd 0f6 0a0 16f 083 08a 156 09b 13c 107 167 098 1d0 1e9 003 1fe
0e0: 0bd 122 089 0d2 18f 012 033 06a 142 0ed 170 11b 0e2 14f 158 131
0f0: 147 05d 113 1 cd 079 161 1a5 179 09e 1b4 0cc 022 132 01a 0e8 004
100: 187 1ed 197 039 1bf 1d7 027 18b 0c6 09c 0d0 14e 06c 034 1f2 06e
110: 0ca 025 0ba 191 0fe 013 106 02f 1ad 172 1db 0c0 10b 1d6 0f5 1ec
120: 10d 076 114 1ab 075 10c 1e4 159 054 11f 04b 0c4 1be 0f7 029 0a4
130: 00e 1f0 077 04d 17a 086 08b 0b3 171 0bf 10e 104 097 15b 160 168
140: 0d7 0bb 066 1ce 0fc 092 1c5 06f 016 04a 0a1 139 0af 0f1 190 00a
150: 1aa 143 17b 056 18d 166 0d4 1fb 14d 194 19a 087 1f8 123 0a7 1b8
160: 141 03c 1f9 140 02a 155 11a 1a1 198 0d5 126 1af 061 12e 157 1dc
170: 072 18a 0aa 096 115 0ef 045 07b 08d 145 053 05f 178 0b2 02e 020
180: 1d5 03f 1c9 1e7 1ac 044 038 014 0b1 16b 0ab 0b5 05a 182 1c8 1d4
190: 018 177 064 0cf 06d 100 199 130 15a 005 120 1bb 1bd 0e0 04f 0d6
1a0: 13f 1c4 12a 015 006 0ff 19b 0a6 043 088 050 15f 1e8 121 073 17e
1b0: 0bc 0c2 0c9 173 189 1f5 074 1cc 1e6 1a8 195 01f 041 00d 1ba 032
1c0: 03d 1d1 080 0a8 057 1b9 162 148 0d9 105 062 07a 021 1ff 112 108
1d0: 1c0 0a9 11d 1b0 1a6 0 cd 0f3 05c 102 05b 1d9 144 1f6 0ad 0a5 03a
1e0: 1cb 136 17f 046 0e1 01e 1dd 0e6 137 1fa 185 08c 08f 040 1b5 0be
1f0: 078 000 0ac 110 15e 124 002 1bc 0a2 0ea 070 1fc 116 15c 04c 1c2

La fonction FL

modifier

La fonction FL prend deux paramètres. Le premier est une entrée de 32 bits nommée FL_IN, l'autre est un index d'EK noté k. FL renvoie un buffer de 32 bits de données nommé FL_OUT.

fonction FL(FL_IN, k)
variables d0, d1 (entiers de 16 bits)
début
d0 = FL_IN >> 16
d1 = FL_IN & 0xffff
si (k est pair) alors
d1 = d1 ^ (d0 & EK[k/2])
d0 = d0 ^ (d1 | EK[(k/2+6)%8+8])
sinon
d1 = d1 ^ (d0 & EK[((k-1)/2+2)%8+8])
d0 = d0 ^ (d1 | EK[((k-1)/2+4)%8])
finsi
FL_OUT = (d0<<16) | d1
retourner FL_OUT
fin

Quand l'algorithme est utilisé pour le déchiffrement, la fonction FLINV est utilisée à la place de FL.

fonction FLINV (FL_IN, k)
variables d0, d1 (entiers de 16 bits)
début
d0 = FL_IN >> 16
d1 = FL_IN & 0xffff
si (k est pair) alors
d0 = d0 ^ (d1 | EK[(k/2+6)%8+8])
d1 = d1 ^ (d0 & EK[k/2])
sinon
d0 = d0 ^ (d1 | EK[((k-1)/2+4)%8])
d1 = d1 ^ (d0 & EK[((k-1)/2+2)%8+8])
finsi
FL_OUT = (d0<<16) | d1
retourner FL_OUT
fin

Description du chiffrement/déchiffrement

modifier

On utilise en général un chiffrement/déchiffrement en 8 tours. Un tour consiste en un appel à la fonction FO, les tours paires incluent en plus un appel à FL ou FLINV. Après le tour final un appel à FL ou FLINV est effectué.

Voici les descriptions détaillées des tours pour le chiffrement :

Un texte clair P de 64 bits est divisé en D0 (les 32 bits de poids fort) et D1 (les 32 bits de poids faible).

 début
// tour 0
D0 = FL(D0, 0);
D1 = FL(D1, 1);
D1 = D1 ^ FO(D0, 0);
// tour 1
D0 = D0 ^ FO(D1, 1);
// tour 2
D0 = FL(D0, 2);
D1 = FL(D1, 3);
D1 = D1 ^ FO(D0, 2);
// tour 3
D0 = D0 ^ FO(D1, 3);
// tour 4
D0 = FL(D0, 4);
D1 = FL(D1, 5);
D1 = D1 ^ FO(D0, 4);
// tour 5
D0 = D0 ^ FO(D1, 5);
// tour 6
D0 = FL(D0, 6);
D1 = FL(D1, 7);
D1 = D1 ^ FO(D0, 6);
// tour 7
D0 = D0 ^ FO(D1, 7);
// final
D0 = FL(D0, 8);
D1 = FL(D1, 9);
fin

Le texte chiffré C de 64 bits est construit à partir de D0 et D1 de la manière suivante :

  C = (D1<<32) | D0;

Lors du déchiffrement, l'ordre des tours est inversé :

 début
D0 = C & 0xffffffff;
D1 = C >> 32;
D0 = FLINV(D0, 8);
D1 = FLINV(D1, 9);
D0 = D0 ^ FO(D1, 7);
D1 = D1 ^ FO(D0, 6);
D0 = FLINV(D0, 6);
D1 = FLINV(D1, 7);
D0 = D0 ^ FO(D1, 5);
D1 = D1 ^ FO(D0, 4);
D0 = FLINV(D0, 4);
D1 = FLINV(D1, 5);
D0 = D0 ^ FO(D1, 3);
D1 = D1 ^ FO(D0, 2);
D0 = FLINV(D0, 2);
D1 = FLINV(D1, 3);
D0 = D0 ^ FO(D1, 1);
D1 = D1 ^ FO(D0, 0);
D0 = FLINV(D0, 0);
D1 = FLINV(D1, 1);
P = (D0<<32) | D1;
fin

Notes et références

modifier
  1. Bar-On et Keller 2016.
  2. Matsui 1997, Publication dans une conférence. Les premières traces sont dans un (en) rapport technique.

Annexes

modifier

Liens externes

modifier

Bibliographie

modifier