Chiffrements par blocs
DES |
Introduction
L'algorithme DES, Data Encryption Standard, a été créé dans les laboratoires de la
firme IBM Corp. C'est un chiffrement qui transforme des blocs de 64 bits avec une clé secrète
de 56 bits au moyen de permutations et de substitutions. Le DES est considéré comme étant
raisonnablement sécuritaire, officiellement défini dans la publication FIPS 46-3 et il est public.
La clé est en fait constituée de 64 bits, dont 56 bits sont générés
aléatoirement et utilisés dans l'algorithme. Les huit autres bits peuvent être utilisés
pour la détection d'erreurs (dans une transmission par exemple). Chacun des huit bits est utilisé
comme bit de parité des sept groupes de 8 bits.
Comme blowfish, le DES est un chiffrement Feistel. Il utilise les transformations de substitution et de transposition
(chiffrement par produit). Il est aussi appelé Data Encryption Algorithm (DEA).
Algorithme
Pour être chiffré, un bloc subit tout d'abord une permutation initiale, puis un algorithme
complexe est appliqué en fonction de la clé (calcul médian), et enfin le bloc subit
une permutation finale. Cette dernière permutation est l'inverse de la permutation initiale. De cette
façon, l'algorithme de chiffrement et de déchiffrement est le même.
Le calcul médian dépendant de la clé peut être défini comme étant deux
fonctions : une première appelée la fonction de chiffrement et une fonction de programmation de la
clé.
Chiffrement
Programmation de la clé
La fonction de programmation du bloc de 48 bits en fonction de la clé est appelée à chaque
round avec en entrée, un nombre entier "n" entre 1 et 16 et le bloc de 64 bits de la clé.
La sortie est le bloc clé "K" de 48 bits, ce bloc étant une sélection de bits de
la clé après des permutations.
Kn = PC(n,CLÉ)
PC = programmation de la clé
Permuation initiale
Les 64 bits du bloc en entrée dans l'algorithme DES subissent la permutation initiale.
Bloc en entrée |
|
Bloc en sortie
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
24 |
25 |
26 |
27 |
28 |
29 |
30 |
31 |
32 |
33 |
34 |
35 |
36 |
37 |
38 |
39 |
40 |
41 |
42 |
43 |
44 |
45 |
46 |
47 |
48 |
49 |
50 |
51 |
52 |
53 |
54 |
55 |
56 |
57 |
58 |
59 |
60 |
61 |
62 |
63 |
64 |
|
|
P.I. |
58 |
50 |
42 |
34 |
26 |
18 |
10 |
2 |
60 |
52 |
44 |
36 |
28 |
20 |
12 |
4 |
62 |
54 |
46 |
38 |
30 |
22 |
14 |
6 |
64 |
56 |
48 |
40 |
32 |
24 |
16 |
8 |
57 |
49 |
41 |
33 |
25 |
17 |
9 |
1 |
59 |
51 |
43 |
35 |
27 |
19 |
11 |
3 |
61 |
53 |
45 |
37 |
29 |
21 |
13 |
5 |
63 |
55 |
47 |
39 |
31 |
23 |
15 |
7 |
|
|
Ainsi, le premier bit du bloc résultant de la permutation initiale est le 58ème
bit du bloc en entrée, le deuxième bit est le 50ème bit et ainsi de suite.
Calcul médian
Le calcul médian peut se résumer comme étant une fonction contenant 16 itérations identiques.
Cette fonction traite deux blocs à la fois : un bloc de 32 bits, les données, et l'autre de 48 bits,
la clé. Le résultat donne un bloc de 32 bits.
Le bloc de donnée de 64 bits est préalablement divisé en deux blocs de 32 bits, "L"
et "R" (pour "Left" et "Right"), après être passé dans la permutation
initiale. Ainsi, "L" contient les bits pairs et "R" contient les bits impairs.
Les 48 bits du bloc "K" (pour "Key") sont choisis à partir de la clé initiale
de 64 bits. La sortie de L'R' après l'itération est définie par :
L' = R
R' = L XOR f(R,K)
L'R' = [R][L + f(R,K)]
L'entrée à la première itération du chiffrement est le bloc ayant subit la permutation
initiale. À la fin, le bloc L'R' restant après la seizième itération devient le bloc
de pré-sortie (avant la permutation finale). À chaque itération, un bloc "K" différent
de 48 bits est choisi à partir de la clé de 64 bits.
Pour "n" variant de 1 à 16, on a
Ln = Rn-1
Rn = Ln-1 XOR f(Rn-1,Kn)
La fonction de chiffrement "f"
f reçoit le bloc "R" et le bloc "K" en entrée.
La fonction E prend un bloc de 32 bits en entrée et donne un bloc de 48 bits en sortie. Les 48 bits, représentés
en huit blocs de 6 bits chacun, sont obtenus en sélectionnant les bits du bloc en entrée selon le
tableau suivant.
32 |
1 |
2 |
3 |
4 |
5 |
4 |
5 |
6 |
7 |
8 |
9 |
8 |
9 |
10 |
11 |
12 |
13 |
12 |
13 |
14 |
15 |
16 |
17 |
16 |
17 |
18 |
19 |
20 |
21 |
20 |
21 |
22 |
23 |
24 |
25 |
24 |
25 |
26 |
27 |
28 |
29 |
28 |
29 |
30 |
31 |
32 |
1 |
|
Ainsi les trois premiers bits du bloc sortant sont le 32ème,
le 1er et le 2ème bit du bloc en entrée. Chacune des huit fonctions de sélection,
les S-Boxes, prend un bloc de 6 bits comme entrée et donne un bloc de 4 bits en sortie. La première
fonction de sélection "S1" est représentée par la table suivante
S1 |
Ligne No. |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
|
|
|
|
14 |
4 |
13 |
1 |
2 |
15 |
11 |
8 |
3 |
10 |
6 |
12 |
5 |
9 |
0 |
7 |
0 |
15 |
7 |
4 |
14 |
2 |
13 |
1 |
10 |
6 |
12 |
11 |
9 |
5 |
3 |
8 |
4 |
1 |
14 |
8 |
13 |
6 |
2 |
11 |
15 |
12 |
9 |
7 |
3 |
10 |
5 |
0 |
15 |
12 |
8 |
2 |
4 |
9 |
1 |
7 |
5 |
11 |
3 |
14 |
10 |
0 |
6 |
13 |
|
|
Le bloc en entrée de 8 bits "B" est traité comme suit : le premier bit et le dernier bit
du bloc unis représentent un nombre compris entre 0 et 3 en base 2, appelé Bi, alors que les 4 bits
restants du milieu représentent un nombre compris entre 0 et 15 en base 2, appelé "Bj".
Par exemple, si le bloc "B" est "011011" :
Bi = 01 = 1 en base 10
Bj = 1101 = 13 en base 10
Ainsi, Bi étant le numéro de la ligne de S1 et Bj étant le numéro de sa colonne, le
bloc de 4 bits de sortie sera "5" en base 10 , donc "0101" en base 2.
Les 8 fonctions de sélection S1, S2, S3, ..., S8 traitent chacune un des 8 blocs. Ces 8 blocs sont consolidés
pour former qu'un seul bloc de 32 bits, lequel sera l'entrée pour une dernière permutation dans la
fonction f.
La permutation "P" sur le bloc de 32 bits est représentée par la table suivante :
16 |
7 |
20 |
21 |
29 |
12 |
28 |
17 |
1 |
15 |
23 |
26 |
5 |
18 |
31 |
10 |
2 |
8 |
24 |
14 |
32 |
27 |
3 |
9 |
19 |
13 |
30 |
6 |
22 |
11 |
4 |
25 |
|
Le résultat est un bloc de 32 bits.
À la suite des 16 rounds, le bloc de pré-sortie est L16R16.
Permutation finale
Le contenu du bloc de pré-sortie, est permuté une dernière fois. Cette permutation correspond
à l'inverse de la permutation initiale.
40 |
8 |
48 |
16 |
56 |
24 |
64 |
32 |
39 |
7 |
47 |
15 |
55 |
23 |
63 |
31 |
38 |
6 |
46 |
14 |
54 |
22 |
62 |
30 |
37 |
5 |
45 |
13 |
53 |
21 |
61 |
29 |
36 |
4 |
44 |
12 |
52 |
20 |
60 |
28 |
35 |
3 |
43 |
11 |
51 |
19 |
59 |
27 |
34 |
2 |
42 |
10 |
50 |
18 |
58 |
26 |
33 |
1 |
41 |
9 |
49 |
17 |
57 |
25 |
|
Ainsi, le premier bit du bloc final est le 40ème
bit du bloc précédent, le deuxième bit égale le 8ème bit, etc..
Déchiffrement
La permutation finale est l'inverse de la permutation initiale. On applique exactement le même algorithme,
mais à l'inverse, en tenant bien compte que chaque itération du déchiffrement traite les mêmes
paires de blocs utilisées dans le chiffrement.
Rn-1 = Ln
Ln-1 = Rn XOR f(Ln,Kn)
Maintenant R16L16 et le bloc d'entrée dans la fonction de déchiffrement, et
R0L0 est le bloc de pré-sortie, avant la permutation finale. Ainsi le bloc relatif
à la clé K16 est utilisé dans la première itération et K1 dans la dernière.
Considérations
La recherche de failles a mis en relief la possibilité qu'il pourrait exister des relations linéaires
ou quasi linéaires entre le texte clair et le texte chiffré du DES. Si cette possibilité se
révélait vrai, le DES serait extrêmement vulnérable face aux attaques relatives aux
relations linéaires.
|
|
|
Chiffrements par blocs
DES |
Identification Significative:
DES, utilisant des sBox va être facile à repérer,
soit dans la section DATA soit dans la section TEXT:
SBox1 byte 14,4,13,1,2,15,11,8,3,10,6,12,5,9,0,7
byte 0,15,7,4,14,2,13,1,10,6,12,11,9,5,3,8
byte 4,1,14,8,13,6,2,11,15,12,9,7,3,10,5,0
byte 15,12,8,2,4,9,1,7,5,11,3,14,10,0,6,13
SBox2 byte 15,1,8,14,6,11,3,4,9,7,2,13,12,0,5,10
byte 3,13,4,7,15,2,8,14,12,0,1,10,6,9,11,5
byte 0,14,7,11,10,4,13,1,5,8,12,6,9,3,2,15...
|
Coté Cracking...
newDES |
Introduction
En résumé, newDES utilise une clé qui est encryptée puis utilisée
pour traiter le Plain Text. A l'inverse la séquence de déchiffrement réutilisera la clé,
la décryptera, avant de passer au traitement du Cipher Text dans la même routine que précedement.
Le principe de newDES est identique au Data Encryption Standard mais est plus simple
à implanter. A la différence de DES, il n'utilise pas de SBox, mais un rotor.
push offset Key
call newDES_SetEncryptKey
push offset plaintext
push offset ciphertext
call newDES_Crypt |
push offset Key
call newDES_SetDecryptKey
push offset ciphertext
push offset plaintext
call newDES_Crypt |
A la place des blocs du DES, on trouve un rotor qui , invisible sous Wdasm, aura ce look
sous IDA
004010CE db 20h,89h,EFh,BCh,66h,7Dh,DDh,48h,D4h,44h,51h,25h
db 56h,EDh,93h,95h,46h,E5h,11h,7Ch,73h,CFh,21h,14h
db 7Ah,8Fh,19h,D7h,33h,B7h,8Ah,8Eh,92h,D3h,6Eh,ADh...
soit " 32 137 239 188 102 125 221 72 212 68 81 37 86 237 147 149" en décimal.
Une petite recherche rapide sur le net en utilisant cette chaîne permet d'identifier
immédiatement le mode de chiffrement newDES.
Chiffrement
NewDES_Crypt_Decrypt
pushad
xor ebx, ebx
xor ecx, ecx
mov esi, ptrIn
mov edi, ptrOut
mov eax, dword ptr [esi]
mov edx, dword ptr [esi+4]
mov dword ptr [edi], eax
mov dword ptr [edi+4], edx
mov esi, offset NewDES_internal_Key
mov ebp, 8
@@:
mov eax, dword ptr [edi]
mov edx, dword ptr [edi+4]
xor eax, dword ptr [esi]
mov cl, al ;cl = B0^K
mov bl, ah ;bl = B1^K
xor dl, byte ptr [NewDES_rotor+ecx]
xor dh, byte ptr [NewDES_rotor+ebx]
ror eax, 16
ror edx, 16
mov cl, al ;cl = B2^K
mov bl, ah ;bl = B3^K
xor dl, byte ptr [NewDES_rotor+ecx]
xor dh, byte ptr [NewDES_rotor+ebx]
mov eax, dword ptr [edi]
ror edx, 16
ror eax, 8
mov dword ptr [edi+4], edx
add esi, 4
xor dh, dl ;dh = B5^B4
xor dl, byte ptr [esi] ;dl = B4^K
mov cl, dh
mov bl, dl
xor ah, byte ptr [NewDES_rotor+ecx]
xor al, byte ptr [NewDES_rotor+ebx]
ror edx, 16
ror eax, 16
xor dx, word ptr [esi+1]
mov cl, dh
mov bl, dl
xor ah, byte ptr [NewDES_rotor+ecx]
xor al, byte ptr [NewDES_rotor+ebx]
add esi, 3
ror eax, 8
dec ebp
mov dword ptr [edi], eax
jnz @B
mov eax, dword ptr [edi]
mov edx, dword ptr [edi+4]
xor eax, dword ptr [esi]
mov cl, al ;cl = B0^K
mov bl, ah ;bl = B1^K
xor dl, byte ptr [NewDES_rotor+ecx]
xor dh, byte ptr [NewDES_rotor+ebx]
ror eax, 16
ror edx, 16
mov cl, al ;cl = B2^K
mov bl, ah ;bl = B3^K
xor dl, byte ptr [NewDES_rotor+ecx]
xor dh, byte ptr [NewDES_rotor+ebx]
ror edx, 16
mov dword ptr [edi+4], edx
popad
ret
|
Chiffrements par blocs
RijnDael |
Introduction
Le chiffrement a une longueur de bloc variable, une longueur de clé variable et un nombre de rounds variables.
Par contre, Rijndael version "AES" est restreint à des longueurs de blocs de 128, 192
et 256 bits avec une clé fixée à 128 bits.
Algorithme
Comme la plupart des chiffrements par blocs modernes, le chiffrement s'effectue en deux parties : une procédure
d'expansion de la clé et la fonction principale de chiffrement.
Chiffrement
La fonction de chiffrement se divise en trois : une transformation initiale avec la clé (l'étape
"Add Round Key", bloc XOR clé), une série de rounds puis une transformation finale.
Le nombre de rounds s'établit en fonction de la taille des blocs et de la clé :
· |
9 rounds si la taille des blocs et de la clé sont de 128 bits, |
· |
11 rounds si la taille des blocs ou de la clé est de 192 bits (maximum), |
· |
13 rounds si la taille des blocs ou de la clé est de 256 bits. |
Dans un round, quatre transformations sont appliquées au bloc à chiffrer.
La première étape est appelée "Byte Sub". Chaque octet des sous-blocs est
alors substitué selon une S-Box. Cette opération augmente la non-linéarité des
données.
Ensuite, l'étape "Shift Row" décale les bits des sous-blocs. La taille des sous-blocs
dépend de la taille des blocs. Par exemple, pour des blocs de 128 bits, les sous-blocs ont une taille de
16 bits :
1 |
5 |
9 |
13 |
2 |
6 |
10 |
14 |
3 |
7 |
11 |
15 |
4 |
8 |
12 |
16 |
|
|
|
1 |
5 |
9 |
13 |
14 |
2 |
6 |
10 |
11 |
15 |
3 |
7 |
8 |
12 |
8 |
4 |
|
|
Cette étape augmente la diffusion des données dans le round.
En troisième lieu, l'étape appelée "Mix Column" est appliquée. L'opération
utilisée est la multiplication d'une matrice aux sous-blocs de 16 bits, toujours dans le cas d'un bloc de
128 bits. La matrice est représentée par
1 |
5 |
9 |
13 |
2 |
6 |
10 |
14 |
3 |
7 |
11 |
15 |
4 |
8 |
12 |
16 |
|
Cette étape augmente la diffusion des données entre les rounds. À
noter que les octets utilisés dans la multiplication sont traités comme des polynômes plutôt
que des nombres.
L'étape finale est appelée "Add Round Key". Cette étape est simplement l'addition
des sous-clés aux sous-blocs correspondants.
Déchifffement
Le déchiffrement est l'inverse du chiffrement.
Identification Significative
SBox
99, 124, 119, 123, 242, 107, 111, 197, 48, 1, 103, 43, 254, 215, 171,
118, 202, 130, 201, 125, 250, 89, 71, 240, 173, 212, 162, 175, 156, 164,
114, 192, 183, 253, 147, 38, 54, 63, 247, 204, 52, 165, 229, 241, 113...
|
|