Sécurité dispositif vote électronique

crypgirl a écrit :

Bonjour,

J'ai un dossier à faire dans le cadre de mes études et j'aimerai un peu d'aide
en ce qui concerne certaines questions de cryptologie (n'étant pas calée dans la
matière).

Il s'agirait de savoir comment (de manière logique) peut-on sceller une urne
électronique, ainsi que l'authentification des électeurs afin de garder leur
anonymat, par mot de passe.

la question n'a pas de sens puisque la problématique principale
du vote est liée à l'intégrité du déroulement du scrutin

et pour qu'il y ait intégrité du scrutin il faut que les gens
puissent effectuer un contrôle
et pour que ce contrôle puisse s'effectuer il ne peut y avoir
d'électronique de crypto ou tout autre dispositif à la con
obscur

en plus la valeur ajoutée d'un tel dispositif est vraiment
plus que négligeable l'on gagne quoi 1 h
pour les gens pressés il existe les sondages

et en plus j'aime bien le côté grande messe républicaine
je sais je suis un vieux con
qui ne voudrait pas avoir à voter depuis son ordinateur
à la maison

remy

Voilà, j'espère que certains pourront m'aider!

Merci d'avance!

According to crypgirl <crypgirl@domain-xyz.in>:

Il s'agirait de savoir comment (de manière logique) peut-on sceller
une urne électronique, ainsi que l'authentification des électeurs afin
de garder leur anonymat, par mot de passe.

C'est une vaste question.

Tout d'abord, regardons quelles propriétés on veut pour un "vote".
Notons bien qu'il y a beaucoup de types de votes. Habituellement, on
pense aux élections "politiques", genre municipales ou présidentielles,
mais il y a d'autres votes, beaucoup plus nombreux (CA d'entreprises,
élections de délégués syndicaux, assemblées générales d'actionnaires,
assemblées de copropriétaires, bureaux d'associations...). Suivant les
cas, certaines des propriétés sont voulues, ou pas.

Donc, on distingue les propriétés suivantes :

-- Il y a une "liste électorale" qui est une définition de qui peut
voter. Cela suppose que les participants sont authentifiés d'une manière
ou d'une autre. Dans un vote "politique", il y a une vraie liste avec
inscription préalable, et contrôle d'une pièce d'identité par des
opérateurs sous contrôle (i.e. sous le regard des assesseurs). On
assortit en général cette condition d'une deuxième, à savoir qu'un
votant donné ne peut voter qu'une seule fois par élection.
Électroniquement, un mot de passe, un certificat, etc... peuvent faire
l'affaire.

-- On veut pouvoir savoir a posteriori qui est venu voter parmi les
inscrits. Suivant le type de vote, cette information peut être
considérée comme publique, voire nécessitant une preuve.

-- Le "poids" de chaque votant est défini préalablement. Il y a des
votes à choix multiples (on choisit "oui" ou "non", ou alors on choisit
un candidat parmi une dizaine) et d'autres types de votes (par exemple,
un vote par assentiment où on choisit un ou plusieurs candidats dans une
liste). Le votant peut peser plus ou moins (dans un vote politique dans
une démocratie égalitaire, toutes les voix ont le même poids, mais dans
une assemblée d'actionnaires, le poids dépend du nombre d'actions
détenues).

-- Si le vote est à bulletin secret, alors on souhaite l'anonymat.
C'est-à-dire qu'on veut empêcher le fait de lier un vote à un votant. Ce
n'est pas contradictoire avec l'authentification des votants : on veut
savoir qui a voté, mais pas ce que chacun a voté. En revanche, ça pose
des problèmes pour les votes à "poids". Par exemple, s'il y a cinq
actionnaires de poids 5, 13, 17, 23 et 32%, respectivement, alors il
n'est pas difficile de reconstituer qui a voté quoi simplement en
regardant le résultat. Dans un vote politique, on utilise un isoloir
qui a une fonction double :
** L'isoloir protège l'électeur, qui peut choisir pour qui il vote
sans subir de pression extérieure.
** L'isoloir protège _contre_ l'électeur, qui ne peut pas montrer
pour qui il vote. Cela dissuade l'électeur de vendre son vote,
puisque l'acheteur n'aurait pas de moyen de vérifier que
l'électeur a rempli sa part du marché.
Dans l'analyse des protocoles de vote électronique, il est important
de se rappeler de cette double fonction.

-- On veut un système vérifiable, où chaque acteur (notamment les
votants) peut vérifier au moins une partie du déroulement du protocole.
Dans un vote politique, chaque électeur peut venir observer les choses
dans le bureau de vote, il peut rester planté là toute la journée, et il
peut participer au dépouillement. Un votant ne peut pas physiquement
surveiller un vote national dans son intégralité, mais il peut s'assurer
que sa partie "locale" se déroule bien.


Donc, une fois qu'on a posé tout ça, on se dit : pourrait-on remplacer
certaines des étapes de vérification "physique" (isoloir, pièce
d'identité, bureau de vote où on va passer la journée) par des protocoles
cryptographiques finauds ?

La recherche sur le sujet a dégagé, grosso-modo, deux familles de
protocoles : les réseaux de mix, et le chiffrement homomorphique.


Un "mix", c'est une entité, une sorte de boîte noire, qui prend en
entrée une série de messages et le reproduit en sortie dans un ordre
aléatoire. Le mix "honnête" fait ça avec du vrai aléa (enfin, quelque
chose d'imprédictible) et ne prend aucune note sur ce qu'il a fait. Cet
aléa ne prend son sens que si on couple ça avec du chiffrement à clé
publique. Autrement dit, le mix a une clé publique, et on lui envoie des
messages chiffrés avec cette clé publique. Le mix déchiffre les
messages, et les ressort en vrac (c'est-à-dire selon un ordre aléatoire
tiré uniformément). De l'extérieur, à cause du chiffrement, on ne peut
pas savoir quel message de sortie correspond à quel message d'entrée
(ceci suppose que le chiffrement à clé publique est randomisé, ce qui
est le cas de tout chiffrement à clé publique qui se respecte).

Le mix assure l'anonymat. Mais uniquement s'il est honnête. Pour
résoudre les problèmes de corruption du mix, on en cascade plusieurs :
la sortie d'un mix est envoyée dans un autre mix. Ainsi, il suffit d'un
seul mix honnête sur la série pour que la non-traçabilité du vote soit
assurée. Cela suppose que chaque mix a sa clé publique, et que le vote
soit encapsulé dans plusieurs couches de chiffrement : le vote est
chiffré avec la clé publique du dernier mix ; ce vote chiffré est
surchiffré avec la clé publique de l'avant-dernier mix ; ce vote
surchiffré est surchiffré à nouveau avec la clé publique du mix
précédent, etc... Chaque mix enlève la couche de chiffrement qui le
concerne.

Les autres propriétés sont plus difficiles à assurer. Par exemple, si on
veut que le votant puisse vérifier que son vote a été pris en compte, on
peut prévoir que chaque votant peut ajouter une "marque" qui lui est
propre (et dont il garde le secret), marque qui se retrouve dans le vote
déchiffré final et qui lui permet de voir que son vote à lui est arrivé
au bout du processus. Mais cette marque permet au votant de facilement
vendre son vote (il peut s'entendre sur la marque utilisée avec
l'acheteur, et l'acheteur peut vérifier que la marque se retrouve en
sortie, et voir à quel vote elle est attachée). Pour obtenir les
propriétés voulues, il faut sortir une armada d'outils cryptographiques
qui sont un peu techniques à décrire et à implémenter (chercher
"non-interactive zero-knowledge proof").


Le chiffrement homomorphe est un autre moyen de faire ce gros mélange
anonymisant de votes. Un chiffrement homomorphe est un protocole de
chiffrement à clé publique où on peut, sans connaissance de la clé
privée, faire des calculs avec les messages chiffrés.

Prenons le cas de l'algorithme de chiffrement El-Gamal. Ça se présente
comme ça :

Il y a un nombre premier p, gros, connu, et un nombre premier q qui
est également connu, et qui divise p-1. p fait au moins 1024 bits, q
au moins 160 bits. Il y a un entier g modulo p qui est générateur
du sous-groupe multiplicatif d'ordre q (autrement dit, 1 < g < p et
g^q = 1 mod p). p, q et g sont des paramètres publics qui peuvent être
partagés par tous les utilisateurs de l'algorithme (ce sont les mêmes
que pour l'algorithme de signature électronique DSS).

Une clé privée est un entier x non nul modulo q (autrement dit, un
entier quelconque entre 1 et q-1). La clé publique correspondante
est y = g^x mod p. Retrouver la clé privée à partir d'une clé publique
revient à résoudre le problème dit du "logarithme discret", qui est
un problème difficile ; avec p et q ayant au moins les tailles indiquées
plus haut, c'est un problème intordable.

El-Gamal permet de chiffrer des entiers modulo p. Autrement dit, on
chiffre des messages qu'on peut représenter par des nombres entiers
entre 1 et p-1. Soit m un tel message.

L'émetteur choisit un entier k aléatoire entre 1 et q-1, et il
calcule a = g^k mod p et b = m*(y^k) mod p. La paire (a,b) est
le message chiffré. Pour le déchiffrement, on utilise x : on
calcule b / (a^x) mod p. Comme a^x = (g^k)^x = g^(k*x) = (g^x)^k = y^k,
les y^k se neutralisent mutuellement, et on retrouve m.

Maintenant, l'homomorphisme. Supposons qu'on ait deux messages
chiffrés (a,b) et (a',b'), selon ces équations:
a = g^k mod p
b = m * (y^k) mod p
a' = g^(k') mod p
b' = m' * (y^(k')) mod p
(i.e. chiffrements de m et m' selon la même clé publique y ; notons
que chaque chiffrement a son propre "k" aléatoire.)
On peut calculer ceci :
a'' = a*a' mod p
b'' = b*b' mod p
Ce calcul peut se faire avec les chiffrés seuls, sans connaissance de
la clé privée. Or, on constate que cela donne :
a'' = (g^k) * (g^k') = g^(k+k') mod p
b'' = m * (y^k) * m' * (y^k') = (m*m') * (y^(k+k')) mod p
donc (a'',b'') est un chiffrement valide du message m'' = m*m'.

Du coup, on peut multiplier entre eux deux messages chiffrés, et obtenir
le résultat tout autant chiffré, sans connaître la clé privée.

Dans un système de vote, ça devient ceci. Supposons un vote binaire, par
exemple un référendum. Au démarrage, on choisit deux entiers e et f, qui
representent "oui" et "non". Chaque votant fait un chiffrement de e ou
de f. Les votes chiffrés sont publiés. Chacun peut faire la combinaison
expliquée ci-dessus ; du coup, s'il y a u votants "oui" et v votants
"non", on obtient au final le chiffrement par El-Gamal de l'entier
(e^u)*(f^v) mod p. On confie alors cet entier à une "autorité" qui en
fait le déchiffrement. Enfin, on recherche les valeurs de u et v par
recherche exhaustive (même avec des millions de votants, un PC de base
s'en tirera en au pire quelques heures). Cette autorité, c'est l'entité
qui détient la clé privée x. Comme cette clé permet de déchiffrer tous
les votes, on souhaite contrôler fortement l'utilisation de x, donc on
va faire un déchiffrement de groupe : x est fractionné entre plusieurs
entités, qui se réunissent (selon une cérémonie qui peut être
visuellement très chargée, avec des costumes rigolos) pour faire le
déchiffrement. Là encore, divers outils techniques cryptographiques
permettent d'organiser cette opération.

L'aspect homomorphique permet de faire la somme "dans le brouillard",
c'est-à-dire en ne manipulant que des messages chiffrés. Comme on ne
déchiffre, à la fin, que le produit final, on a l'anonymat recherché.
Chaque votant peut vérifier que son vote est bien là au final. Chaque
votant peut _de plus_ refaire lui-même le produit et vérifier que le
déchiffrement par l'autorité est correct. Pour empêcher le votant de
vendre son vote, il faut de plus s'assurer qu'il ne connaît pas le "k"
aléatoire qu'il a choisi pour chiffrer son vote, ce qui là encore
nécessite quelques outils bien sentis et bien techniques.

Ici j'ai présenté le cas d'El-Gamal ; il y a d'autres algorithmes de
chiffrement homomorphiques, donc le chiffrement de Paillier, qui a
l'avantage de permettre de calculer la somme, et non plus le produit, de
messages chiffrés (ça simplifie la phase finale, celle qui prend jusqu'à
quelques heures sur un PC dans le cas d'El-Gamal).



Pour finir, je dois rajouter ceci : rien de tout cela ne concerne les
"machines à voter" qui commencent à se répandre dans les élections
nationales. Ces machines ne sont que des calculatrices blindées ; elle
remplacent simplement le dépouillement manuel. La sécurité du
dépouillement manuel est assurée par les scrutateurs, qui ouvrent grand
leurs yeux et vérifient que tout se passe bien. Dans la machine de vote,
il y a blindage, détecteurs et scellés (un peu comme dans les terminaux
de paiement), et procédures complexes d'initialisation et entretien
(avec des scrutateurs...). Permettre au gens de voter depuis chez eux,
c'est supprimer le rôle de l'isoloir, ce qui est gênant. Les votes
politiques s'en accomodent tant que ça ne concerne que peu de personnes
(typiquement, pour les expatriés qui votent par correspondance) mais ça
ne résiste pas à une généralisation trop poussée. Il y a là un problème
à résoudre pour lequel la cryptographie n'aide pas.


--Thomas Pornin

Thomas Pornin wrote:

C'est une vaste question.

Excellente lecture (bien que très technique - j'ai décidément du mal
après tant d'années à ne plus faire de maths) ; quelques petites
questions cependant:
(1) on peut si je pige bien avec l'exemple d'El-Gamal avoir une autorité
attaquée (ie. compromise) dans la mesure où on peut la véfifier après
coup dans tous les cas ?
(2) l'anonymat par mix est voué à l'échec si les mix sont tous compromis
? (ce qui n'est pas difficile, à priori - nombre limité d'autorités au
niveau national)
(3) la vérification individuelle _ET_ le non-commerce des votes _ET_ la
compromission possible des autorités au milieu est-elle contournable
avec un système "non-interactive zero-knowledge proof" cité ?

Et la question subsdidiaire: dans le cadre d'un vote "important" [ie.
suffisamment pour envisager des attaques internes et donc avoir
notamment des autorités corrompues], y a-t-il jamais eu un seul exemple
théorique qui tient la route (sans intervention d'un élément matériel,
comme le fameux masque jetable "visuel" qui était assez amusant mais
probablement pas très facile à mettre en oeuvre dans un vrai vote) ?

Enfin, sur la remarque de remy plus haut, je suis tout aussi d'accord,
même si c'est un problème ortogonal (la confiance dans le vote et la
fiabilité effective du vote), même si si le premier peut être mis en
cause par l'absence manifeste du second.

(mes 15c¤)

According to Xavier Roche <xroche@free.fr.NOSPAM.invalid>:

(1) on peut si je pige bien avec l'exemple d'El-Gamal avoir une autorité
attaquée (ie. compromise) dans la mesure où on peut la véfifier après
coup dans tous les cas ?

La connaissance de la clé privée permet de lever l'anonymat des votes.
Donc on ne _veut pas_ que cette clé puisse être retrouvée par un
attaquant. Le rôle de l'autorité est double : on veut qu'elle déchiffre
le résultat du vote (et il est vérifiable après coup qu'elle a fait ce
travail correctement), mais on veut aussi qu'elle ne déchiffre rien
d'autre (et ça, ce n'est pas vérifiable a posteriori...).

La séparation de la clé privée entre plusieurs entités, avec un protocole
de partage de secret, permet de rendre l'occurrence de la corruption
de l'autorité peu probable (il faudrait corrompre toutes les entités qui
détiennent une partie du secret).

(2) l'anonymat par mix est voué à l'échec si les mix sont tous compromis
? (ce qui n'est pas difficile, à priori - nombre limité d'autorités au
niveau national)

Dans un cas pratique de vote "important", une entité qui détient une
part de clé privée, ou un mix, c'est une boîte fermée et blindée (et
chère). Un peu comme une carte à puce, mais en plus gros (comprendre :
si la carte à puce est un vélo, ici on parle d'un tank). La corruption
d'une telle boîte, ça revient à corrompre les fabricants, et l'activité
des fabricants est sévèrement contrôlée (notamment par des tonnes de
paperasse, des revues de code et matériel par des tiers, des inspections
surprise et des procédures d'initialisation formelles avec des
"cérémonies des clés"). Ce sont d'ailleurs toutes ces procédures qui
expliquent le coût unitaire de ce genre de matériel.

(L'acronyme courant est HSM = Hardware Security Module.)

Sur un échelon national, on pourrait avoir plusieurs dizaines ou
centaines de ces matériels, produits par des constructeurs distincts.

Au fond, il suffit d'avoir un niveau de sécurité suffisant pour que les
autres attaques soient moins chères. Admettons, par exemple, qu'un
groupe mafieux cherche à faire élire son pion Président de la
République. Une attaque possible est d'enlever la mère / l'épouse / les
enfants du candidat démocratiquement élu. Faire ça discrètement et
efficacement, c'est compliqué donc cher, mais pas théoriquement
infaisable. Du coup, il n'est pas nécessaire de blinder le système de
vote plus que ça. (Ceci est une variation sur le thème : une porte
blindée n'a pas à être plus blindée que le mur dans lequel elle est
encastrée.)

Et la question subsdidiaire: dans le cadre d'un vote "important" [ie.
suffisamment pour envisager des attaques internes et donc avoir
notamment des autorités corrompues], y a-t-il jamais eu un seul exemple
théorique qui tient la route (sans intervention d'un élément matériel,
comme le fameux masque jetable "visuel" qui était assez amusant mais
probablement pas très facile à mettre en oeuvre dans un vrai vote) ?

Le votant est un élément matériel. Et il manipule du matériel, que ce
soit un ordinateur, une machine à voter ou un bulletin. Tout le problème
d'un protocole de vote est bien d'arriver à combiner ces éléments
matériels entre eux pour arriver à une procédure de vote qui fontionne
et fournit un résultat, et dont la fiabilité est ressentie comme
suffisante par les participants.

Les protocoles cryptographiques gèrent une partie du bouzin. Mais ils ne
font que transporter le problème : un protocole cryptographique
travaille sur des 0 et de 1 ; tôt ou tard, il faut bien transposer ces 0
et 1 dans le monde "physique". Et certaines propriétés de sécurité ne
peuvent être obtenues que dans le monde physique (ce qu'apporte
l'isoloir, par exemple : cryptographie ou pas, quand un votant utilise
son ordinateur perso chez lui, on ne peut pas garantir qu'il n'y a pas
un gros bras derrière lui qui surveille ce qu'il tape sur son clavier).
Scientifiquement, les parties actuellement gérées par la cryptographie
sont intéressantes.


--Thomas Pornin

Thomas Pornin a écrit :

Les protocoles cryptographiques gèrent une partie du bouzin. Mais ils ne
font que transporter le problème : un protocole cryptographique
travaille sur des 0 et de 1 ; tôt ou tard, il faut bien transposer ces 0
et 1 dans le monde "physique".

complètement d'accord et même si l'on me sort un protocole
qui garantisse l'anonymat
qui permette d'associer un votant à un vote
sans divulguer son vote


je resterai sceptique
même si l'on me sort une bonne cinquantaine de fabricant
de machines différentes avec des bureaux de certification accrédités
des coffres forts dans toutes les mairies pour entreposer les machines
entre 2 scrutins


tout cela ne sera pour moi que des éléments en plus qui fragiliseront
l'édifice et donc le scrutin

pourquoi vouloir détourner le contrôle du vote
pourquoi vouloir abandonner
un pan de la république à des machines

quel en est l'intérêt ? cela coûte si cher que cela une boite en
plastique transparente mis dans l'école primaire du coin

sinon il existe beaucoup plus simple je propose le vote à l'applaudimètre

comme cela ils l'auront leur machine




remy

Thomas Pornin a écrit :

C'est une vaste question.

et une vaste réponse - du très grand T.P.
merci pour ces excellents points.

Sylvain.

remy wrote:

et en plus j'aime bien le côté grande messe républicaine
je sais je suis un vieux con
qui ne voudrait pas avoir à voter depuis son ordinateur
à la maison

Le vote à la maison rajoute un problème. En plus des certitudes précédentes
(validité, anonymat), se rajoute le choix du votant.

En allant dans un isoloir, le votant vote pour qui il veut. Même si
quelqu'un lui a donné des consignes de votes, il peut faire ce qu'il veut
au moment de mettre son bulletin dans l'enveloppe. c'est une chose que tu
ne peux pas garantir pour un vote à la maison.

--
Stéphane

Pour me répondre, traduire gratuit en anglais et virer le .invalid.
http://stef.carpentier.free.fr/

Le Mon, 08 Dec 2008 16:40:58 +0100, remy a écrit :

Thomas Pornin a écrit :

Les protocoles cryptographiques gèrent une partie du bouzin. Mais ils
ne font que transporter le problème : un protocole cryptographique
travaille sur des 0 et de 1 ; tôt ou tard, il faut bien transposer ces
0 et 1 dans le monde "physique".

complètement d'accord et même si l'on me sort un protocole qui
garantisse l'anonymat
qui permette d'associer un votant à un vote sans divulguer son vote


je resterai sceptique

Tout dépend de l'"atmosphère" dans laquelle ce protocole fait son
apparition ...

Par atmosphère j'entends la manière donc les spécifications et
l'implémentation est faite : si ça se passe à la sauce IETF avec
implémentation ouverte, ça me semble jouable.

Thomas a fait un excellent exposé technique d'une solution basée sur un
algo de cryptage homomorphe ... qui rempli le besoin mais ça règle pas
tout.

En bref : Niveau informatique, on sait faire le bousin mais çà introduit
un certain nombre de questions comme la sécurité de l'ordinateur du
votant et j'en passe ...

a +.

--
Jérôme Benoit aka fraggle
La Météo du Net - http://grenouille.com
OpenPGP Key ID : 9FE9161D
Key fingerprint : 9CA4 0249 AF57 A35B 34B3 AC15 FAA0 CB50 9FE9 161D

Jérôme Benoit <jerome.benoit@grenouille.com> écrivait :

En bref : Niveau informatique, on sait faire le bousin mais çà introduit
un certain nombre de questions comme la sécurité de l'ordinateur du
votant et j'en passe ...

De plus seules les gens compétents en crypto seront surs du
fonctionnement. Ça amène donc à une possibilité d'intimidation pour les
votes. Si des gros bras débarquent chez toi te demandant avec insistance
de voter pour untel, et que tu n'es pas sûr à 100% qu'ils ne pourront
pas savoir pour qui tu as voté, que fais-tu ?



--
Le travail n'est pas une bonne chose. Si ça l'était,
les riches l'auraient accaparé