Note: Descriptions are shown in the official language in which they were submitted.
CA 02480896 2004-09-29
WO 03/085881 PCT/FR03/01032
1
Procédé de sécurisation d'une entité électronique à accès crypté
L'invention se rapporte à un. procédé de sécurisation d'une entité
électronique à accès crypté, telle que par exemple une carte à microcircuit,
le
perfectionnement visant plus particulièrement à détecter les attaques connues
sous l'abréviation DFA (Differential Fault Analysis, en anglais). L'invention
vise
particulièrement à sécuriser des algorithmes connus tels que l'AES ou le DES.
Certaines entités électroniques à accès crypté, notamment les cartes à
microcircuit, sont vulnérables à des attaques dites DFA consistant à perturber
le
déroulement de l'algorithme cryptographique de façon à changer la valeur d'un
résultat intermédiaire, à traiter la différence obtenue entre le message
chiffré
normalement et le message chiffré avec erreur et à en déduire des informations
sur la clé secrète de l'entité électronique. Les erreurs sont très faciles à
produire
sur une carte à microcircuit, en intervenant sur l'environnement extérieur,
par
exemple en provoquant un pic de tension, en soumettant la carte à un éclair
lumineux (notamment à l'aide d'un faisceau laser), en faisant varier
brutalement
la fréquence de l'horloge extérieure, etc...
Parmi les algorithmes les plus utilisés, on peut citer le DES (Data
Encryption Standard, en anglais) et surtout I'AES (Advanced Encryption
Standard, en anglais). On rappelle que les deux algorithmes AES et DES ont en
commun d'appliquer à un message d'entrée une succession de groupes
d'opérations dits "rounds" sous le contrôle d'une série de sous-clés
respectives,
successivement élaborées à partir d'une clé initiale secrète, spécifique de
l'entité
électronique considérée. C'est cette clé initiale (notée K ci-après) que le
fraudeur
tente de reconstituer. Une partie de l'algorithme est consacrée à
l'élaboration des
sous-clés en mettant en oeuvre un processus d'extension de clé par une
fonction
F, non linéaire dans le cas de l'AES. La fonction est appliquée à ladite clé
initiale,
puis à nouveau au résultat de l'application de ladite fonction et ainsi de
suite. Les
sous-clés sont élaborées à partir de cette succession de résultats
intermédiaires
issus de la clé initiale K.
Jusqu'à présent, les attaques de type DFA sont considérées comme
inexploitables en pratique vis-à-vis de l'algorithme de type AES. Cependant,
des
études à l'origine de l'invention ont permis de mettre en évidence qu'une
triple
CA 02480896 2011-06-30
2
attaque du type DFA, en synchronisme avec certaines applications de la
fonction
F et le début du dernier "round", permet de retrouver tous les octets de la
dernière sous-clé dans le cas où ladite clé d'entrée K est codée sur 128 bits,
ce
qui est actuellement le cas pour la plupart des systèmes où l'algorithme AES
est
utilisé. La connaissance de ces informations permet de retrouver la clé
d'entrée.
L'invention offre une parade simple et efficace à ce type d'attaque.
L'invention concerne un procédé de sécurisation d'une entité électronique à
accès
crypté, exécutant un algorithme cryptographique consistant à appliquer à un
message d'entrée une succession de groupes d'opérations faisant intervenir une
série de sous-clés respectives, successivement élaborées par un processus
itératif
mis en oeuvre à partir d'une clé initiale, le procédé comprenant une mise en
oeuvre
d'étapes dudit processus itératif de façon à obtenir un résultat d'une étape
intermédiaire, comprenant une mémorisation dans ladite entité éléctronique du
résultat de ladite étape intermédiaire, une répétition d'au moins une partie
des
étapes dudit processus itératif jusqu'à un recalcul d'un résultat
correspondant à
celui qui a été mémorisé à l'étape de mémorisation, une comparaison de la
valeur
dudit résultat mémorisé à la valeur du résultat recalculé correspondant et une
interdiction d'une diffusion d'un message crypté résultant d'une mise en
oeuvre
dudit algorithme si ces deux valeurs sont différentes.
L'invention concerne également une entité électronique autonome exécutant
un algorithme cryptographique consistant à appliquer à un message d'entrée une
succession de groupes d'opérations faisant intervenir une série de sous-clés
respectives, successivement élaborées par un processus itératif mis en oeuvre
à
partir d'une clé initiale, l'entité électronique comprenant des moyens pour
effectuer
une mise en oeuvre dudit processus itératif de façon à obtenir un résultat
d'une
étape intermédiaire, comprenant des moyens pour effectuer une mémorisation
dans ladite entité électronique du résultat de ladite étape intermédiaire, des
moyens pour effectuer une répétition d'au moins une partie des étapes dudit
processus itératif jusqu'à un recalcul d'un résultat correspondant à celui
CA 02480896 2011-06-30
2a
qui a été mémorisé par les moyens pour effectuer une mémorisation, des moyens
pour effectuer une comparaison de la valeur dudit résultat mémorisé à la
valeur du
résultat recalculé correspondant et des moyens pour effectuer une interdiction
d'une diffusion d'un message crypté résultant d'une mise en oeuvre dudit
algorithme si ces deux valeurs sont différentes.
En effet, si une erreur, due à une attaque DFA, intervient pendant le
processus itératif d'élaboration des sous-clés, alors le résultat mémorisé et
le
résultat recalculé correspondant sont forcément différents car il est
impossible
de reproduire deux fois de suite la même "erreur" dans la pratique.
lo Par exemple, un résultat mémorisé, dit résultat intermédiaire, peut être
l'une des étapes du processus dit de diversification de clé consistant à
appliquer
une fonction F non linéaire au résultat de l'étape analogue précédente. On
peut
aussi mémoriser l'une des sous-clés et recalculer cette sous-clé à partir
d'une
étape antérieure dudit processus itératif. Par exemple, on mémorise la
dernière
sous-clé.
L'invention sera mieux comprise et d'autres avantages de celle-ci
apparaîtront plus clairement à la lumière de la description qui va suivre,
donnée
uniquement à titre d'exemple et faite en référence aux dessins annexés dans
lesquels :
CA 02480896 2004-09-29
WO 03/085881 PCT/FR03/01032
3
- la figure 1 est un schéma d'une entité électronique telle qu'une carte à
microcircuit, susceptible de mettre en oeuvre le procédé de l'invention ;
- la figure 2 est un organigramme illustrant l'algorithme dit AES ;
- la figure 3 est un organigramme illustrant la mise en oeuvre de l'invention
à titre de complément dans l'exécution de I'AES ; et
- la figure 4 est un organigramme illustrant l'algorithme DES auquel
l'invention peut aussi s'appliquer.
Sur la figure 1, on a représenté une entité électronique 11, formant ici une
carte à microcircuit avec ses composants essentiels, à savoir un ensemble de
plages de contact 12, métalliques, permettant de connecter le microcircuit 13
contenu dans la carte à un lecteur de carte, serveur ou analogue avec lequel
ladite carte à microcircuit va pouvoir échanger des informations après une
phase
d'authentification mettant en oeuvre un algorithme connu à clé secrète, par
exemple l'algorithme AES ou l'algorithme DES. Classiquement, le microcircuit
13
se décompose en un microprocesseur 14, dont certains accès sont connectés
aux plages de contact, et une mémoire M couplée au microprocesseur. Lorsque
la carte est couplée à une unité extérieure pour remplir une fonction donnée
(transaction financière, accès à un service téléphonique ou télématique,
contrôle
d'accès, etc...), une phase d'authentification est mise en oeuvre dans la
carte.
Ce processus est programmé dans le microcircuit 13 et une partie de la mémoire
M lui est dédiée.
Par exemple, la phase d'authentification met en oeuvre un algorithme AES
dont le fonctionnement va être rappelé en référence à la figure 2.
L'algorithme
AES s'opère à partir d'un message d'entrée ME transmis en clair par l'unité
extérieure à laquelle l'entité électronique se trouve couplée. L'entité 11
possède
aussi une clé secrète K, mémorisée, et l'algorithme consiste à transformer le
message ME jusqu'à obtenir un message chiffré MC à la suite d'un certain
nombre de transformations opérées avec intervention d'un certain nombre de
sous-clés K0, KI, K2, ..., Kn_1, Kn. D'autre part, une fonction non linéaire F
est
programmée dans l'entité électronique pour s'appliquer successivement, d'abord
à la clé K, puis au résultat RI la transformation de la clé K par la fonction
F, puis
au résultat R2 de la transformation du résultat RI par la même fonction F et
ainsi
de suite. Les différentes sous-clés Ko ... Kn sont extraites de ce processus
CA 02480896 2004-09-29
WO 03/085881 PCT/FR03/01032
4
d'extension de la clé K par la fonction F. Plus précisément, on sait que la
clé K
peut être un mot de 128 bits, 192 bits ou 256 bits. Le message d'entrée ME est
un mot de 128 bits. Toutes les combinaisons sont possibles et l'homme du
métier choisit la combinaison qui représente le meilleur compromis, compte
tenu
du contexte, entre la rapidité d'exécution et le niveau de sécurité requis.
Actuellement cependant, la plupart des algorithmes AES effectivement mis en
oeuvre font appel à une clé K de 128 bits. Les sous-clés Ko ... Kn doivent
être au
format du message d'entrée. C'est pourquoi, chaque sous-clé est créée à partir
d'un ou deux résultats successifs élaborés au cours du processus d'extension
de
clé par la fonction F. Dans l'exemple décrit, la clé K est codée sur 192 bits.
Par
conséquent, la sous-clé Ko est extraite des deux premiers tiers de la clé K,
la
sous-clé KI est extraite de l'autre tiers de la clé K et du premiers tiers du
résultat
intermédiaire RI de la première transformation de cette clé par la fonction F,
la
sous-clé K2 est extraite des deux derniers tiers du résultat intermédiaire RI,
et
ainsi de suite jusqu'à l'élaboration de la dernière sous-clé Kn.
Du côté du traitement du message d'entrée, les opérations sont les
suivantes. Ledit message d'entrée ME est combiné à la sous-clé Ko par une
fonction ou exclusif 16. Après quoi, le résultat est soumis à un groupe
d'opérations (appelé ici ROUND 1) avec intervention de la sous-clé KI. Puis,
le
résultat est soumis à nouveau à un groupe d'opérations dit ROUND 2 avec
intervention de la sous-clé K2, jusqu'à ROUND,_,, dit dernier ROUND, avec
intervention de la sous-clé Kn_1. Tous les "ROUNDS", de 1 à n-1, sont composés
de quatre transformations. Un ROUND,,, dit ROUND final avec intervention de la
sous-clé Kn comporte seulement trois transformations. Le résultat de ce round
final est un message chiffré MC qui est renvoyé vers l'extérieur.
A la base de l'invention, on a mis en évidence que, si on est capable de
provoquer des perturbations comme indiqué à des moments précis du
déroulement de l'algorithme AES décrit ci-dessus, on peut retrouver tous les
octets d'une sous-clé et plus particulièrement selon l'exemple, de la dernière
sous-clé Kn de la façon suivante :
- si on provoque la perturbation au moment de l'application de la dernière
fonction F, on arrive à retrouver des informations sur l'avant-dernière
extension
CA 02480896 2004-09-29
WO 03/085881 PCT/FR03/01032
de la clé par la fonction F, à savoir les quatre derniers octets de l'avant-
dernier
résultat Rn,-i .
- si on parvient aussi à produire une perturbation au moment de
l'exécution de l'avant-dernière extension par la fonction F, on peut retrouver
les
5 quatre octets voisins de Rm_1.
- si on provoque une perturbation sur le début du dernier round
(ROUNDn_1), on arrive à retrouver 8 octets de la dernière extension de clé par
la
fonction F, c'est-à-dire Rm. Ces octets appartiennent à la sous-clé K.
- en traitant les résultats précédents, on arrive encore à retrouver six
octets de plus répartis dans la dernière extension de clé R. par la fonction
F.
Ces octets appartiennent aussi à la sous-clé Kn.
Pour retrouver les deux derniers octets de la sous-clé K, il est
envisageable d'étudier toutes les possibilités jusqu'à retrouver ces deux
derniers
octets. Par conséquent, si la clé K avait été codée sur 128 bits, elle aurait
pu être
retrouvée à coup sûr par la seule mise en oeuvre de l'attaque décrite ci-
dessus.
On rappelle que dans la majorité des algorithmes AES mis en oeuvre
actuellement, la clé K est effectivement codée sur 128 bits et il n'y a pas de
différence entre les résultats intermédiaires RI, R2 ... Rm et les sous-clés
KI, K2
... Kn (dans ce cas, n = m) puisque chaque sous-clé est constituée de la
totalité
d'un résultat intermédiaire R; correspondant. Dans l'exemple décrit cependant,
la
clé K a été codée sur 192 bits et l'attaque qui a été décrite dans ses grandes
lignes ci-dessus ne permet pas de retrouver la clé puisque le résultat Rm
n'est
pas entièrement connu. On ne peut donc pas "remonter" jusqu'à la clé K à
partir
de ce résultat incomplètement connu. Cependant, on a affaibli considérablement
la sécurité puisqu'on dispose d'informations partielles sur la clé, ce qui
rend plus
efficaces d'autres attaques (par exemple du type DPA) connues en soi.
Quoi qu'il en soit, la parade à ce type d'attaque consiste à mémoriser un
résultat intermédiaire R;, par exemple Rm, ou une sous-clé, par exemple ici la
dernière sous-clé Kn, à refaire au moins une partie des étapes d'élaboration
de la
succession desdites sous-clés, c'est-à-dire essentiellement le processus
d'extension de clé par la fonction F, jusqu'au recalcul d'un résultat
correspondant
à celui qui a été mémorisé. A partir de ce moment, on dispose de deux valeurs
(de résultat intermédiaire ou de sous-clé) qui doivent être identiques si
l'entité
CA 02480896 2004-09-29
WO 03/085881 PCT/FR03/01032
6
électronique n'a été soumise à aucune attaque du type DFA. Il suffit de
comparer
la valeur du résultat ou sous-clé mémorisé à la valeur du résultat ou sous-clé
recalculé correspondant et interdire la diffusion du message crypté MC issu du
ROUND final si ces deux valeurs sont différentes. C'est ce qu'illustre la
figure 3
où l'algorithme AES est complété (selon un mode de réalisation) en refaisant
la
totalité des étapes d'élaboration de la succession desdites sous-clés et plus
particulièrement du processus d'extension de la clé K. Selon cet exemple,
l'algorithme AES décrit en référence à la figure 2 est exécuté une première
fois,
le résultat est un message crypté MC. La dernière sous-clé Kn est mémorisée.
Ensuite, on refait tout le processus d'extension de clé par la fonction F à
partir de
la clé K secrète de l'entité. Ceci aboutit à déterminer une nouvelle valeur de
Kn.
La valeur précédemment mémorisée et la nouvelle valeur sont comparées (test
d'égalité). Si les deux valeurs sont égales, on autorise la sortie du message
MC.
Si les deux valeurs ne coïncident pas, la valeur MC n'est pas retransmise à
l'extérieur et on peut émettre un message d'erreur.
Dans l'exemple qui vient d'être décrit, on refait la totalité du processus
d'extension de clé jusqu'à obtenir le nouveau calcul de la dernière sous-clé
K.
Comme on l'a vu plus haut, on peut mémoriser un résultat intermédiaire R; ou
sous-clé, quelconque et refaire au moins une partie des étapes d'élaboration
de
la succession des sous-clés jusqu'au recalcul d'un résultat intermédiaire ou
sous-clé correspondant à celui qui a été mémorisé. D'une façon générale, on a
avantage, si on ne refait pas la totalité du cycle d'extension de clé par la
fonction
F, à refaire au moins une partie finale des étapes d'élaboration de la
succession
desdites sous-clés, c'est-à-dire plus particulièrement une partie finale du
processus d'extension de clé par la fonction F, jusqu'à obtenir un second
calcul
du dernier résultat intermédiaire Rn, ou de la dernière sous-clé.
Si on ne refait pas l'intégralité du processus itératif d'extension de clé (à
partir de la clé K), il faut évidemment mémoriser le résultat intermédiaire
(ou la
sous-clé) d'où on repart.
L'invention n'est pas limitée à la sécurisation de l'algorithme AES. A titre
d'exemple, l'algorithme DES, également connu, est décrit à la figure 4.
Brièvement, dans cet algorithme, le processus d'extension de la clé K est le
suivant. La clé K (64 bits) est soumise à une permutation P1 sur les bits et
CA 02480896 2004-09-29
WO 03/085881 PCT/FR03/01032
7
réduite à 56 bits. Le résultat est un mot 20 partagé en deux parties de 28
bits.
Chacune d'elles est soumise à une permutation R (rotation circulaire sur les
bits)
de 1 ou 2 bits selon les cas. Les deux résultats sont rassemblés pour former
un
nouveau mot 21 de 56 bits soumis à une nouvelle permutation P2 et concaténé
à 48 bits pour donner une sous-clé K1. Par ailleurs, le mot 21 de 56 bits est
traité
de façon à subir deux rotations circulaires R pour aboutir à un nouveau mot
22, à
nouveau soumis à la permutation P2 pour engendrer une sous-clé K2 et ainsi de
suite jusqu'à K16. Par ailleurs, le message d'entrée ME de 64 bits subit les
transformations suivantes. Il est d'abord soumis à une permutation P3 sur les
bits et le résultat est soumis à des fonctions constituant le ROUND 1 faisant
intervenir la sous-clé K1. On met ensuite en oeuvre d'autres rounds successifs
faisant intervenir d'autres sous-clés correspondantes (jusqu'à la sous-clé
K16) et
le résultat du dernier round est soumis à une permutation inverse P3". Le
résultat
de cette permutation inverse est le message chiffré MC destiné à être renvoyé.
On conçoit que la structure générale de l'algorithme DES qui vient d'être
rappelée ci-dessus se prête bien à la mise en oeuvre de l'invention. Il suffit
par
exemple de mémoriser la sous-clé KI 6 et de refaire tout ou partie du
processus
de diversification de la clé K composé de la permutation P1 et des rotations
R.
Le test peut même être réalisé sur la valeur du dernier résultat intermédiaire
(mot 36) avant la dernière permutation P2. Dans ce cas, c'est ce dernier
résultat
qui est mémorisé et non pas la sous-clé K16.
Bien entendu, l'invention concerne aussi toute entité électronique,
notamment toute carte à microcircuit, comportant des moyens de mise en oeuvre
du procédé décrit ci-dessus.
