Sécurité des systèmes informatiques
L’identification
Olivier Markowitch
L’identification
Mécanisme permettant à un vérificateur de s’assurer
interactivement de l’identité d’un prouveur
L’identification ne peut se résoudre uniquement au
moyen de codes d’authentification de messages (MAC)
Applications : Contrôle d’accès, logging ...
1
Propriétés
Le vérificateur Bob ne peut réutiliser les informations
reçues du prouveur, Alice, pour impersonnaliser cette
dernière auprès de Charles (un vérificateur tiers)
La preuve de l’identité ne doit donc pas être transfé-
rable
La probabilité qu’Oscar puisse se faire passer pour
Alice auprès de Bob doit être négligeable
2
Identification faible
Identification basée sur :
– les mots de passe, éventuellement associés :
– à S/Key
– au schéma de Lamport
– un secret partagé
3
Identification forte
L’identification forte est aussi appelée challenge-
response
Le prouveur prouve sa connaissance d’un secret au
vérificateur sans pour autant le révéler
A chaque session d’identification, le vérificateur pose
une question différente (un challenge) au prouveur, à
laquelle ce dernier répond grâce à la connaissance
de son secret (response)
4
Identification forte (suite)
Challenge-response basé sur :
– le chiffrement symétrique
(identification unilatérale ou mutuelle)
– les fonctions à sens unique avec clés
(exemple : SKID3)
– le chiffrement asymétrique
(exemple Needham-Schroeder)
5
Protocole sans apport d’information
Résolution sur mesure du problème d’identification au
cours d’un protocole de preuve interactive
Un protocole de preuve interactive peut être consis-
tant (complete) et significatif (sound), le protocole est
alors appelé preuve de connaissance
Un protocole de preuve de connaissance peut respec-
ter la propriété d’apport nul de connaissance (zero-
knowledge property), le protocole est alors dit simu-
lable
6
En pratique
Protocoles d’identification de :
– Fiat-Shamir (basé sur le problème de la factorisa-
tion)
– Guillou-Quisquater (basé sur le problème RSA)
– Schnorr (basé sur le problème du logarithme dis-
cret)
7
Fiat-Shamir : les prémices
Une autorité :
– choisit deux premiers secrets et (RSA)
– calcule la valeur publique
Chaque prouveur :
– choisit un secret tel que est pre-
mier avec
– calcule la valeur publique
8
Fiat-Shamir : l’identification
1. le prouveur choisit un nombre aléatoire dans
l’intervalle , calcule
, et
envoie au vérificateur
2. le vérificateur choisit un bit aléatoire et l’envoie
au prouveur
3. le prouveur calcule et l’envoie
au vérificateur
4. si et si alors le véri-
ficateur accepte l’identification
Ces étapes sont réalisées
fois de suite
9
Fiat-Shamir : consistant
Le prouveur envoie :
La vérification :
10
Fiat-Shamir : significatif
Si un opposant arrive à s’identifier, de manière ré-
pétée, avec une probabilité non négligeable alors ce
n’est pas en devinant . Il arrive donc à construire des
réponses ayant « la bonne forme ».
Supposons que cet opposant construise, lors de deux
identifications, deux réponses, et , à deux ques-
tions distinctes, et , en utilisant le
même dans la construction de la réponse.
Nous avons : et , et donc ½ le
¾
secret.
11
Fiat-Shamir : simulable
Le simulateur choisit aléatoirement un et calcule :
– pour répondre à la question
, et
– pour répondre à la question
.
Nous avons ainsi une simulation basée sur une connais-
sance préalable des questions (des challenges).
12
Fiat-Shamir : exemple
Soit
.
Soient et donc
.
1. Soient ,
: 56
2. Soit
:1
3.
: 35
4.
et
13
Guillou-Quisquater : les prémices
Une autorité :
– choisit deux premiers secrets et
– calcule la valeur publique
– choisit le paramètres de sécurité public
: un pre-
mier de 40 bits
– calcule secret tel que
– calcule sur base de l’identité du prouveur :
– transmet au prouveur
14
Guillou-Quisquater : l’identification
1. le prouveur choisit aléatoirement
,
calcule et envoie et
au vérificateur
2. le vérificateur calcule
, choi-
sit un nombre aléatoire
et envoie
au prouveur
3. le prouveur calcule et envoie
au vérificateur
4. si , le vérificateur accepte
l’identification
15
Guillou-Quisquater : consistant
Notons
Le vérificateur vérifie :
16
Quillou-Quisquater : significatif
Un opposant qui arrive à s’identifier avec une proba-
bilité non négligeable construit des réponses ayant
« la bonne forme ». Supposont que cet opposant pro-
duise deux réponses distinctes et correctes, et ,
aux questions distinctes et , et ce sur base du
même . Nous avons alors :
½
½
¾
¾
½ ¾
¾½ (avec ½
¾)
Calculons ½ ¾ ½
(car ½ ¾ et premier)
´ ½ ¾ µ
¾
½
Notons ½ donc : ½¾
Soit ½ et calculons ¾½
Nous obtenons : ½
¾
½
Et donc :
¾
½
17
Guillou-Quisquater : simulable
Le simulateur connaît , et
. Il choisit aléatoirement
et calcule :
Nous avons ainsi une simulation basée sur une connais-
sance préalable des questions (des challenges).
18
Guillou-Quisquater : exemple
Soient
,
et
.
Nous avons
(
) et
1. Soient ,
: 11
2. Soit
: 13
3.
: 44
4.
et
19
Schnorr : les prémices
Une autorité choisit :
– un grand premier public d’au-moins 512 bits
– un grand facteur premier public de (d’au-
moins 140 bits)
– un élement public d’ordre
– un paramètre public de sécurité
tel que
Chaque prouveur choisit aléatoirement un secret
, calcule
et transmet à
l’autorité
L’autorité calcule alors
où est
une fonction publique qui permet à quiconque de s’as-
surer que a bien été construit par l’autorité
L’autorité produit le certificat
20
Schnorr : l’identification
1. le prouveur choisit aléatoirement
,
calcule et envoie son certificat
et au vérificateur
2. le vérificateur s’assure que le certificat est valide,
puis choisit aléatoirement et l’envoie
au prouveur
3. le prouveur calcule et en-
voie au vérificateur
4. si , le vérificateur accepte
l’identification
21
Schnorr : consistant
Le vérificateur vérifie :
22
Schnorr : significatif
Un opposant qui arrive à s’identifier avec une proba-
bilité non négligeable construit donc des réponses
ayant « la bonne forme ». Supposont que cet oppo-
sant produise deux réponses distinctes et correctes,
et , aux questions distinctes et , et ce sur
base du même .
Nous avons alors :
½ ½ ¾ ¾
½ ¾ ¾ ½
Comme et est un premier , nous
avons et donc :
23
Schnorr : simulable
Le simulateur connaît , et . Il choisit aléatoirement
et calcule :
Nous avons ainsi une simulation basée sur une connais-
sance préalable des questions (des challenges).
24
Schnorr : exemple
Soient ,
, un générateur de ,
, et
Soit un élément de d’ordre :
½
Nous avons
1. Soient et
:8
2. Soit
:4
3.
:4
4.
25