Brevet et sécurité informatique :

les liaisons dangereuses ?

François LetellierINRIA / ObjectWeb

francois.letellier@inria.fr

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

francois.letellier@inria.fr

Journées Académiques MicrosoftParis, 26 avril 2005