2002_attack_pkcs_rsa.pdf

(128 KB) Pobierz
Attaque a texte chiffr´ choisi contre les protocoles
`
e
bas´s sur PKCS#1
e
Thomas Baign`res
e
2002, Winter Semester
`
TABLE DES MATIERES
1
Table des mati`res
e
1 Introduction
2 RSA : algorithme de chiffrement ` cl´ publique
a e
2.1 Historique minimaliste . . . . . . . . . . . . . . . . . . .
2.2 La g´n´ration des cl´s, le chiffrement et le d´chiffrement
e e
e
e
2.3 Quelques pr´cisions . . . . . . . . . . . . . . . . . . . . .
e
2.4 Le d´chiffrement . . . . . . . . . . . . . . . . . . . . . .
e
2.5 En bref . . . . . . . . . . . . . . . . . . . . . . . . . . .
3 Description de PKCS#1
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
2
2
2
2
3
3
3
4
4 L’attaque ` texte chiffr´ choisi contre PKCS#1 : Premier contact 4
a
e
4.1 G´n´ralit´s sur l’attaque . . . . . . . . . . . . . . . . . . . . . . .
e e
e
4
4.2 L’id´e fondamentale de l’attaque . . . . . . . . . . . . . . . . . .
e
5
4.3 Le plan de l’attaque. . . . . . . . . . . . . . . . . . . . . . . . . .
5
5 L’attaque en d´tails
e
5.1 L’algorithme d´compos´ . . . . . . . . . . . . . . . . . . . . . . .
e
e
5.2 Explications concernant le pas 2 . . . . . . . . . . . . . . . . . .
5.3 Explications concernant le pas 3 . . . . . . . . . . . . . . . . . .
6 Les
6.1
6.2
6.3
probl`mes rencontr´s, ´l´ments de
e
e ee
Concernant le troisi`me pas . . . . . .
e
Solution sans r´initialisation . . . . . .
e
Toutes les bonnes choses ont une fin .
solution
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
6
6
7
8
9
9
10
11
12
12
12
12
13
13
7 Description de l’impl´mentation
e
7.1 Les deux modes de fonctionnement . .
7.2 Les commandes et leur fonctionnement
7.3 Les autres r´pertoires . . . . . . . . .
e
7.4 Principe de d´velopement . . . . . . .
e
8 Conclusion
1 INTRODUCTION
2
1
Introduction
Ce rapport a ´t´ r´alis´ dans le cadre d’un projet de semestre au labora-
ee e e
toire de cryptographie et de s´curit´ (LASEC) de l’EPFL. Il ´tudie l’attaque a
e
e
e
`
texte chiffr´ choisi r´alis´e en 1998 par Daniel Bleichenbacher contre le standard
e
e e
PKCS#1.
Dans un premier temps je rappelerai le fonctionnement de RSA, puis du stan-
dard PKCS#1. Je d´crirai ensuite l’attaque, les probl`mes auxquels j’ai ´t´
e
e
ee
confront´s et les solutions que j’ai essay´es d’apporter. Pour terminer j’expose-
e
e
rai la m´thode que j’ai employ´e pour effectuer une r´alisation de l’attaque.
e
e
e
2
2.1
RSA : algorithme de chiffrement ` cl´ pu-
a e
blique
Historique minimaliste
RSA est un algorithme de chiffrement a cl´ publique. Il a ´t´ baptis´ d’apr`s
` e
ee
e
e
le nom de ses inventeurs : Ron Rivest, Adi Shamir et Leonard Adleman. Sa
s´curit´ est assur´e par le fait qu’il est difficile de d´composer de tr`s grands
e
e
e
e
e
nombres en facteurs premiers.
2.2
La g´n´ration des cl´s, le chiffrement et le d´chiffrement
e e
e
e
On choisi deux nombres premiers
p
et
q.
On calcule leur produit, que l’on
appellera modulus de RSA :
n
=
p
·
q
On choisi ensuite une cl´ de chiffrement al´atoire
e
de telle mani`re que
e
et
e
e
e
1
ϕ(n)
= (p
−
1)(q
−
1) soient premiers entre eux.
On utilise ensuite l’algorithme d’Euclide pour calculer la cl´ de d´chiffrement
d
e
e
telle que :
d
≡
e
−1
(mod (p
−
1)(q
−
1))
On peut constater que
d
et
n
sont aussi premiers entre eux. Le nombre
e
sera la
cl´ publique de RSA, et
d
sera la cl´ priv´e. Les nombres
p
et
q
ne seront plus
e
e
e
utilis´s mais ne doivent en aucun cas ˆtre r´v´l´s.
e
e
e ee
Soit
m
le message a chiffrer. Ce message
m
devra ˆtre plus petit que
n.
Le
`
e
chiffrement se fait de la mani`re suivante :
e
c
=
m
e
mod
n
Le d´chiffrement s’effectue a l’aide de la cl´ priv´e :
e
`
e
e
m
=
c
d
mod
n
On adoptera dans la suite de ce texte les notations suivantes :
- Pour le chifrement :
C(m)
=
c.
- Pour le d´chiffrement :
D(c)
=
m.
e
1
ϕ(n)
est appel´ l’indicateur d’Euler de
n
e
`
´
2 RSA : ALGORITHME DE CHIFFREMENT A CLE PUBLIQUE
3
2.3
Quelques pr´cisions
e
Les deux nombres premiers
p
et
q
sont de tr`s grande taille, de l’ordre de
e
100 a 200 chiffres (et plus encore). C’est a dire que l’on choisira pour
p
et
q
des
`
`
nombres de 512 bits. En les multipliant on obtient ainsi un nombre de 1024 bits
pour n. Pour les g´n´rer on utilise des algorithmes probabilistes. On commence
e e
par g´n´rer un nombre de fa¸on al´atoire et on v´rifie a l’aide d’un test proba-
e e
c
e
e
`
biliste (comme celui de Miller-Rabin) s’il est premier. Le resultat d’un tel test
donne g´n´ralement la borne sup´rieure de la probabilit´ que ce nombre ne soit
e e
e
e
pas premier.
En pratique, le choix de
e
n’est pas laiss´ au hasard. PKCS#1 recommande les
e
16
nombres 3 et 2 + 1 = 65537. Les repr´sentations binaires de ces deux derniers
e
nombres ne pr´sentent que deux 1, le calcul de leurs puissances en est grande-
e
ment facilit´.
e
L’indicateur d’Euler de
n, ϕ(n),
est le nombre d’entiers inf´rieurs a n, premiers
e
`
avec n.
ϕ(n)
= #{i,
i < n|
gcd(i,
n)
= 1}
Finalement, pour g´n´rer la cl´ priv´e
d
de l’algorithme, on utilise l’algorithme
e e
e
e
d’Euclide ´tendu.
e
2.4
Le d´chiffrement
e
c
d
≡
(m
e
)
d
≡
m
ed
(mod
n)
Si l’on effectue les op´rations suivantes modn, on obtient :
e
Comme
d
≡
e
−1
(mod (p
−
1)(q
−
1)) alors
ed
≡
1 (mod (p
−
1)(q
−
1)) ce qui
revient a dire qu’il existe une constante
k
telle que
ed
= 1 +
k
·
((p
−
1)(q
−
1)).
`
Donc :
c
d
≡
m
k(p−1)(q−1)+1
≡
m·m
k(p−1)(q−1)
≡
m·(m
(p−1)(q−1)
)
k
≡
m·(m
ϕ(n)
)
k
Or, d’apr`s le petit th´or`me de Fermat, comme
pgcd(m, n)
= 1 on a :
e
e e
ϕ(n)
m
≡
1 (mod
n).
On obtient finalement :
c
d
≡
m
·
(1)
k
≡
m
(mod
n)
(mod
n)
2.5
En bref
Modulus :
n
=
p
·
q
avec
p
et
q
deux nombres premiers qui doivent rester secrets
e
premier avec
ϕ(n)
= (p
−
1)(q
−
1)
Cl´ priv´e :
e
e
d
=
e
−1
mod((p
−
1)(q
−
1))
Chiffrement :
c
=
m
e
D´chiffrement :
e
m
=
c
d
(mod
n)
(mod
n)
Cl´ publique :
e
3 DESCRIPTION DE PKCS#1
4
3
Description de PKCS#1
Soit
n
le modulus,
e
la cl´ publique de RSA, soit
d
la cl´ priv´e correspon-
e
e
e
dante. On notera
k
la longueur en bytes de
n.
On a donc :
2
8(k−1)
≤
n <
2
8k
Le bloc utilis´ pour les chiffrements conformes a PKCS#1 a la forme
e
`
2
suivante :
k bytes
00
02
padding string 00
data block
1 byte 1 byte
k-3-|D| bytes
1 byte
|D| bytes
La longueur du bloc est la mˆme que celle de la cl´
n.
e
e
D sera le bloc de donn´es que l’on veux chiffrer. Le Padding String (P
S)
est
e
e
c
e
form´ de
k
−
3
− |D|
bytes non nuls, engendr´s de fa¸on pseudo-al´atoire. La
e
longueur de
P S
doit ˆtre d’au moins 8 bytes, autrement dit,
|D|
ne doit pas
e
d´passer
k
−
11 bytes. Une fois le bloc constitu´, on le chiffre a l’aide de la cl´
e
e
`
e
publique de RSA.
Le serveur PKCS#1 recoit le cryptogramme et le d´chiffre avec sa cl´ priv´e. Il
e
e
e
v´rifie ensuite que le texte clair obtenu est bien conforme a PKCS#1.
e
`
Un bloc
EB
de
k
bytes :
EB
=
EB
1
||.
. .||EB
k
est conforme a PKCS#1 s’il est de la forme du bloc pr´c´demment d´crit. En
`
e e
e
particulier,
EB
doit satisfaire les conditions suivantes :
-
EB
1
=
0x00
-
EB
2
=
0x02
-
EB
3
jusqu’`
EB
10
sont diff´rents de
0x00
a
e
- Au moins un des bytes
EB
11
a
EB
k
est
0x00.
Il permet de rep´rer le
`
e
d´but du message.
e
Par extension, un texte chiffr´ sera dit conforme si le texte clair correspondant
e
est conforme a PKCS#1.
`
4
4.1
L’attaque ` texte chiffr´ choisi contre PKCS#1 :
a
e
Premier contact
G´n´ralit´s sur l’attaque
e e
e
Dans une attaque a texte chiffr´ choisi, l’ennemi choisi un texte chiffr´, l’en-
`
e
e
voie a la victime et recoit en retour le texte chiffr´ correspondant ou une partie
`
e
2
Il
existe deux autres forme de blocs r´serv´s pour les signatures digitales
e
e

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin