Brevet et sécurité informatique :
les liaisons dangereuses ?
François LetellierINRIA / ObjectWeb
Journées Académiques MicrosoftParis, 26 avril 2005
Plan de la présentation
Contexte Procédé d’authentification breveté Possibilités d’attaque sur le procédé Apport du brevet à la sécurité
1er centre de recherche publique en informatique en Europe
double tutelle : ministères en charge de la recherche / en charge de l'industrie
3000 personnes, 6 UR
Consortium international> 50 sociétés, >1.500 individuels
Co-fondé, hébergé par l’INRIA, FT R&D, Bull Neutralité et but non lucratif : création de middleware Large offre couvrant différents besoins de
l’entreprise: >80 projets, 30 solutions Conformité aux standards ouverts (W3C, OMG,
OSGi, …)
e-businesse-government
etc
Network
Algorithmes Cryptographiques Brevetés
One Time Pad : brevet US 1,310,719 (Gilbert Vernam, 1917) RSA : brevet US 4,405,829 (Rivest, Shamir, and Adleman)
MIT sept 83 , domaine public sept. 2000(lecture conseillée: http://www.cyberlaw.com/rsa.html)
Europe : rappel de la législation actuelle Et future ?
Brevet européen EP 0 810 506 B1« Procédé et dispositif d’identification sécurisée entre deux terminaux »
Notre sujet d’étude :EP 0 810 506 B1
Un brevet européen dûment délivré par l’Office Européen des Brevets (23 avril 2003)
La présente étude a été réalisée exclusivement à partir du document public
Brevet exploité commercialement – notamment pour de l’authentification forte en contexte bancaire
EP 0 810 506 B1 : une Invention Mise en Œuvre par Ordinateur
Serveur banalClient banal
Canal de transmission banalAlgorithmecryptographique
Support personnalisé banal (CD, diskette)
Code Secret
Utilisateur
[0032] « qui ne nécessite pas de modifier la structure déjà existante des micro-ordinateurs personnels utilisés […] et qui fait appel à un support d’authentification connu »[0034] « aucun matériel additionnel spécifique n’est utile »[0083] Diskette 3"1/4 -- [0073] Réseau Internet
Seul le logiciel est innovant nous étudions (une version) de l’algorithme cryptographique
Authentification parDéfi / Réponse
Fiabilité améliorée si : Le défi (donc la réponse) change à chaque fois La réponse n’est pas calculable : secrets aléatoires
AliceBob
Oscar
Défi: Quel est le nom de jeune fille de votre mère ?
Réponse:« Smith »
Réponse:« Wilde »
Non répudiation
« Je suis Bob »
Défi : Nom de jeune fille de votre mère ?
« Je suis Bob »
Mécanisme Défi / Réponse deEP 0 810 506 B1 : Préparation
Matrice serveur(aléatoire)
0 1 2 3
A X G B
F O M T
N A U S
K Q E X
0
1
2
3
Fonction de décalage
Code Secret
(203)
0 1 2 3
A B M N
E O S Q
G U K X
F X A T
0
1
2
3
Matrice client(décalée)
UtilisateurEtape préparatoire:Transmission des secrets
Transmission sécurisée
Transm
ission sécurisée
Mécanisme Défi / Réponse deEP 0 810 506 B1 : Authentification
Matrice serveur
0 1 2 3
A X G B
F O M T
N A U S
K Q E X
0
1
2
3
Fonctionde décalage
Code Secret
(203)
0 1 2 3
A B M N
E O S Q
G U K X
F X A T
0
1
2
3
Matrice client
Défi : (x=0, y=2)
Coordonnées décalées :(X=3, Y=0)
Réponse : « N »=?
Authentification ou rejet
Alice
Bob
Fonction de décalage[0058], [0133]
A X G B
F O M T
N A U S
K Q E X
G A X
A S N
E K Q
A B M N
E O S Q
G U K X
F X A T
B
U
X
F O M T
Décalage paramétrique ligne
Code Secret
(203)
A
E
G
F
B
O
U
X
M
S
K
A
N
Q
X
T
Décalage paramétrique colonne
Apport du brevet EP 0 810 506 B1
Recommandation : matrices 255x255 cars alpha-num, codes de 7 à 20 cars alpha-num, un défi = plusieurs couples de coordonnées
Selon le texte du brevet : [0053] « [le] code de décalage n’existe ni sur le
support d’authentification, ni sur le serveur, et ne transite jamais sur le réseau »
[0143] « les conditions nécessaires à un pirate pour se connecter au serveur en usurpant l’identité d’un utilisateur autorisé sont tellement démesurées que le risque s’approche de zéro »
Système d’authentification bancaire sécurisé
Code Secret
Réseau Internet
La matrice utilisateur ne nécessite pas d’être
protégée car elle est décalée
Le code n’est écrit nulle part
Banque « Alice »
Bob
La matrice serveur est dans un environnement
protégé
Le réseau n’est pas sécurisé : le code ne transite jamais dessus, les
défis ne sont pas rejoués
J’utilise un procédé breveté:
Je pense être tranquille !Algorithme
cryptographique
2 - Oscar copiela matrice
1 - Oscar sniffe des couples défi/réponse
Oscar connaît l’algorithme : il est
breveté(principe de Kerckhoffs)
Attaque de l’algorithme
Oscar peut-il usurper l’identité
de Bob ?
?
Contraintes pour une authentification probante
Pour tout défi, un seul (ou un petit nombre de) code(s) doit permettre de fournir la bonne réponse avec une matrice permutée donnée La population de la matrice doit être homogène Plus la matrice est grande, plus les défis doivent
être long ( O (w2) )
Une attaque est possible Après interception d’un nombre suffisant de
défis/réponses Force brute
Attaque en force brute Fonction de décalage :
Code de longueur l : c = c [0].c [1].c [2] … c [l] Matrice décalée M carrée dimension w Position défi colonne, ligne : (x, y)
Réponse V = M[X, Y] Avec:
X = (x + c [y mod l]) mod w Y = (y + c [X mod l]) mod w
Une dizaine d’opérations d’arithmétique entière pour chaque élément du défi
PC actuel : 10.000 MIPS (?) – entre 1M et 10M codes/seconde – codes jusqu’à 11 chiffres décimaux en 1 journée
Principe d’une attaque heuristique
Matrice décalée connue :
Défis interceptés : (x=0, y=2) (1,2) (3,1) (3,0) Réponses interceptées : « N A T B »
On suppose connue la longueur du code (l=3)
Chaque couple défi / réponse élémentaire va donner des hypothèses partielles sur le code
0 1 2 3A B M N
E O S Q
G U K X
F X A T
0
1
2
3
Principe d’une attaque heuristique (2)
(x=0, y=2) -> « N » « N » est en position (X=3, Y=0)
3 = (0 + c [2 mod 3]) mod 4 = c [2] mod 40 = (2 + c [3 mod 3]) mod 4 = (2 + c [0]) mod 4
c [2] = 3c [0] = 2
0 1 2 3A B M N
E O S Q
G U K X
F X A T
0
1
2
3
X = (x + c [y mod l]) mod wY = (y + c [X mod l]) mod w
0 1 2 3A B M N
E O S Q
G U K X
F X A T
0
1
2
3
Principe d’une attaque heuristique (3)
(x=1, y=2) -> « A » « A » est en positions (X=0, Y=0)
(X=2, Y=3) 0 = (1 + c [2 mod 3]) mod 4 = (1 +c [2]) mod 4
0 = (2 + c [0 mod 3]) mod 4 = (2 + c [0]) mod 4ou 2 = (1 + c [2 mod 3]) mod 4 = (1 +c [2]) mod 4
3 = (2 + c [2 mod 3]) mod 4 = (2 + c [2]) mod 4
c [2] = 3, c [0] = 2 (on n’apprend rien)ou c [2] = 1
X = (x + c [y mod l]) mod wY = (y + c [X mod l]) mod w
0 1 2 3A B M N
E O S Q
G U K X
F X A T
0
1
2
3
Principe d’une attaque heuristique (4)
(x=3, y=1) -> « T » « T » est en position (X=3, Y=3)
3 = (3 + c [1 mod 3]) mod 4 = (3 +c [1]) mod 43 = (1 + c [3 mod 3]) mod 4 = (1 + c [0]) mod 4
c [1] = 0, c [0] = 2 Le code est 2 0 3 X = (x + c [y mod l]) mod w
Y = (y + c [X mod l]) mod w
Attaque heuristique (5)
Complexité de l’attaque : au pire de l’ordre de O ((w2/p)l/2)
Matrice 256 x 256, p=256 val possibles / case Codes sur 4 positions x 8 bits (~10 chiffres
déc.) En moyenne, chaque position défi/réponse
aboutit à w2 / p hypothèses (ici 256) L’attaque a été simulée avec un
démonstrateur : moins d’une minute (en PERL !) avec les hypothèses ci-dessus
EP 0 810 506 B1 en signature [0153]
A X G B
F O M T
N A U S
K Q E X
A B M N
E O S Q
G U K X
F X A T
Code Secret
(203)« S A U N A »
(2,1) (0,0) (1,2) (3,0) (2, 3)
Codage par substitution Choix aléatoire des cases parmi celles
contenant les caractères du message à signer
« S A U N A »
AliceBob
Attaques de EP 0 810 506 B1 en signature
Sans vol de matrice décalée Attaque à texte clair choisi évidente
On obtient directement une partie du contenu de la matrice serveur
Attaque statistique à texte chiffré connu Possible avec corpus suffisant (épuisement de la matrice)
Altérations possibles du texte + signature
Avec vol de matrice décalée Toute attaque réussi révèle de l’information sur le code (cf
défi / réponse)
Peut-on améliorerEP 0 810 506 B1 ? « Brûler » les cases correspondant aux défis déjà
posés ; les modifier aléatoirement [0062] Affaiblit la capacité à la non répudiation
Choix des paramètres (?)
Moyens non prévus dans le brevet Sécurisation du canal de transmission (SSL) Inscription de la matrice sur un support impossible à lire
sauf à travers un calculateur (carte à puce)
Le brevet revendique de permettre de s’en dispenser Ils rendent le recours au procédé breveté inutile
Caution du brevet : attention ! Le brevet EP 0 810 506 B1 n’est pas inintéressant, mais il
propose une méthode qui n’est pas suffisante à garantir les propriétés revendiquées
Un système reposant sur ce brevet peut atteindre un haut niveau de sécurité, mais à condition de s’appuyer sur d’autres moyens de protection des transmission et/ou des secrets
Les détenteurs des droits sur EP 0 810 506 B1 pourraient entraver l’exploitation d’une version améliorée, ou tirer profit des perfectionnement clefs apportés par d’autres
La caution du brevet risque d’endormir la vigilance d’exploitants d’inventions mises en œuvre par ordinateur
Quid d’éventuels litiges passés où la non répudiation aurait été invoquée ?
Brevet = innovation ?
L’absence de travaux antérieurs signifie-t-elle invention, ou fausse bonne idée ?
Le nombre de brevets déposés est-elle une bonne mesure de l’innovation ?
Le processus de révision par l’OEB n’a pas mis en lumière les faiblesses du procédé
La révision paritaire (milieu de la recherche, logiciel open-source), en particulier dans les domaines sensibles, reste la seule option raisonnable
Quelles limites au champ du brevetable ?
Esprit de la convention européenne sur le brevet (art. 52c) qui exclut le logiciel du champ du brevetable => encourage la révision paritaire et dissuade le brevetage de pseudo-science ?
Toute l’étude a été menée sans manipuler une seule fois un appareil matériel (même si un démonstrateur a été réalisé) !
Un bon critère d’appréciation du côté « logiciel » d’un brevet ?
Merci pour votre attentionMerci à Microsoft
Questions ?
François LetellierINRIA / ObjectWeb
Journées Académiques MicrosoftParis, 26 avril 2005