Vote électronique / demexp

Entries feed - Comments feed

Last entries

Tue 14 May 2013

  • David Mentré

High-level requirements for re-demexp

I recently spoke about the three main points to work on if one would start some re-engineering work on demexp. The first point was to start from some High-Level requirements. I have started to write those High-Level requirements. Let me know if you have comments or questions, either directly at dmentre@linux-france.org or through this post's comments.

Sat 04 May 2013

  • David Mentré

Re-engineering demexp

demexpA long long time ago, I worked on demexp, a specific software made to support the Democratic Experience, a direct democracy initiative. demexp is programmed in OCaml language. The software contains both a server and a client. The client user interface is programmed with Gtk+. I also tried to make a web interface, without much success. The whole software is made in literate programming style. After several years of development, I was bored and stopped working on it. The software project never had a lot of momentum. The Democratic Experience political project is still alive, without much activity as far as I know.

After those years, one (at least me ;-) ) could wonder what failed in the project and how it could be improved, from a software engineering point of view. I see three main points to work on if one wanted to re-engineer demexp.

1. Start from a well-defined high-level specification. When we started demexp, we did not know exactly what kind of software we wanted. We discovered a new territory. Nowadays, I think we could have a much clearer picture of the requirements. As for any software, starting from clear requirements is mandatory. :-) So we should start from a set of high-level requirements, from which derive some low-level requirements for the software.

2. Design a modular architecture. I made demexp as a big monolithic software. The server part contained the network interface, the question and response database, the security model, the delegation system, etc. The client was containing a User Interface as well as code to authenticate the user and access the server. I now think I should have started from a much modular architecture, with several small programs, each one of them focused on a part of the system. Having several programs would force me to have clear interfaces between them, thus imposing a cleaner architecture. And if the task of developing all those programs is too big, at least I could focus on a sub-part of them to have a system with less functionalities, but at least working.

3. Use formal methods to verify some properties. Using formal method is not strictly required, but, well, it interests me :-) and I think formal methods could bring benefits to such a software. For example to prove that some properties of the system, e.g. the security model is correctly designed and implemented.

Moreover, I see some additional points to review in the original demexp design:

  1. Drop the literate programming approach. It is too costly to maintain (it is heart-braking to remove some code, but its even more difficult to remove some documentation). Some well defined documentation for the tricky parts or the global overview of the system would be enough I think.
  2. Traceability. From high-level specification to low-level one, down to code and its tests or proofs. As for safety critical software, maintaining traceability would bring a cleaner view of the system and it would help code reviews (one can dream! ;-) ) and show the software meets its goals.
  3. Focus on smaller goals. The overall objectives of demexp were very ambitious and thus difficult to reach. One should probably start from less ambitious goals, but try to make useful software in small steps.

Regarding the use of OCaml language, is was probably part of the raison why we never gain much contributions. But OCaml is so nice to use! I would probably keep that part... or not. I currently some other interesting and somewhat confidential languages to look at. :)

Wed 21 Jul 2010

  • David Mentré

A small idea to securely store votes in a voting machine

I recently reviewed the French requirements for (electronic) voting machines. Amongst the 114 requirements, two of them seem a bit difficult to satisfy simultaneously:

Requirement 65: If a voting machine should be stoped during a vote, no indication of the choice made by the voter should be visible.

and

Requirement 69: If a voting machine should be stoped during a vote, it should be possible to recover vote information by vote pool members without any modification, while still following requirement 65.

Thus those two requirements simultaneously request that votes should be recovered in case of crashes but at the same time it should not be possible to read them!

In the following I propose a design to fulfil those two requirements. The main idea of this design is to have two separate kind of machines:

  1. the voting machines themselves, used in the voting booth,
  2. and a centralised controller, used to initialise voting machines, read final votes and when needed re-initialise a voting machine.

Moreover, within voting machines, the recorded votes are stored in a writeable and removable media (like a Flash memory) but they are encrypted. The encryption material should be kept in volatile memory, i.e. in RAM, so that in case of power failure it is lost, making impossible to read the recorded votes on the writeable media. When the voting machine (or a new voting machine) is restarted after a failure, the encryption material is reloaded from the centralised controller, allowing to store new votes next to the previous ones. At the end of the voting period, the votes are read and tallied by the central controller, which has access to the encryption material.

More specifically, here is how a typical vote would be done:

  1. The centralised controller is started and it generates the encryption/decryption material for each voting machine;
  2. Each voting machine is connected to the centralised controller and receives the encryption/decryption material, that is stored in RAM;
  3. The voting machines are then put in their voting booth and set into voting mode (i.e. they accept and store votes);
  4. After also being put in voting mode, the centralised controller can no longer generate new encryption/decryption material;
  5. When each vote on a voting machine is made, it is encrypted and stored on the flash memory of the machine;
  6. If a voting machine crashes, it is connected to the centralised controller and the encryption/decryption material is reloaded, so the voting machine can continue to store votes after the previous one;
  7. At the end of the voting period, all the Flash memories of voting machines are removed and put into the centralised controller. The centralised controller decrypts the votes (it has the encryption/decryption material) and tallies the votes.

As encryption procedure, one could use a One Time Pad but, as there are in practice difficult to generate correctly, we could use instead a stream cipher to generate a "random" stream that would be XORed with the information to store, like AES in counter mode. In the latter case, only the encryption/decryption key would be transferred from the centralised controller to the voting machine and stored in RAM.

The requirement 69 also mandates that vote information should be recovered without any modification. This could be easily done by adding a cryptographic signature on the whole set of recorded votes on the removable media, using as signing key the same material as encryption/decryption material.

The main advantage of this design is its simplicity. If a One Time Pad is used in a voting machines, there is no need to use complex cryptographic code in the voting machines. A simple XOR operation can be used. And even if an AES block is used, it is relatively simple to use. The complex generation of random numbers needed for the generation of encryption/decryption material is only done in the centralised controller.

Another advantage is that votes stored on the removable media can be re-read in case a re-counting is needed, provided that the encryption/decryption material of the centralised controller is securely stored somewhere at the end of the voting period.

One weak point of this approach is during the transfer of the encryption/decryption material from the centralised controller to the voting machines, where the encryption/decryption material could be intercepted by an attacker. A solution would be to authorise this transfer only after proper authentication of a voting authority, limiting the ability to intercept it.

What do you think of this design? Do you see any major weak point or security defect?

Fri 16 Jul 2010

  • David Mentré

A modification proposal to Frédéric Connes' voting protocol

A recently presented the very interesting electronic voting protocol of Frédéric Connes. This protocol has some issues, most notably that is does not work for the first voter and an attack is possible, knowing the paper receipt of previous voters. https://bentobako.org/david/blog/admin/post.php?id=75&upd=1# I would like to present a modification proposal on Connes' protocol. The main idea of this proposal is to let memorize by the voting machine a pool of random numbers, use them for the first voter so that they will be correctly associated to the choice of future voters. That way, the main property of the protocol is kept, even for the first voter:

  • All vote choices on a receipt are associated to a valid vote;
  • All votes are available on the web site and can be checked.

Moreover, one should notice that if this approach is applied not only for the first voter but for latter voters, this approach could be a counter-measure against the attack that try to guess votes, knowing the paper receipt of voters.

Of course, this proposal is just an idea and a detailed analysis would be necessary to see if it really brings additional security. The probably most difficult point is that the initial pool should be empty at the end of the vote, i.e. all random numbers printed on a paper receipt should be used as a choice by other voters. Otherwise it might be possible to guess some votes. And pre-generating and storing some random numbers add some security issues that must taken into account.

Proposal details

Here is an hopefully more detailed presentation of the proposal. We assume an election amongst three people, A, B and C.

During the vote initialisation phase, three series of 10 random numbers are generated, IA1..IA10, IB1..IB10, IC1..IC10. Each one of these random number is associated to a state. Three states are possible:

  • Unused;
  • Assigned-to-vote-choice;
  • Assigned-to-other-choice.

Initially, all random numbers have state Unused.

When a new voter votes, supposing that he/her wants to vote for option A:

  • For option A, a number is chosen:
    • Either a new random number (which is stored to be reused by further voters);
    • Or either a previously generated number in IA1..IA10 in the state Assigned-to-other-choice. This number is put into the state Assigned-to-vote-choice;
  • For each option B and C, a number is chosen:
    • Either a previously used and stored number for votes B and C;
    • Or either a previously generated number in IB1..IB10 and IC1..IC10 and with the state Assigned-to-vote-choice;
    • Or either a previously generated number in IB1..IB10 and IC1..IC10 and with the state Unused. The state is put to state Assigned-to-other-choice.

Then the receipt is given to the voter as usual and the chosen option and associated number is stored for final counting.

For an initial voter, it is always possible to have random number, either a new one for his/her option A and a previously generated one for options B and C. As those two numbers are associated to state Assigned-to-other-choice, at one point in the future another voter is going to select those numbers and use it as his/her vote option, thus publishing it on the final web site and making the receipt of the initial voter perfectly valid.

In the above algorithm, the probability of selection between the different options might be not equal. The size 10 of the initial pool is chosen so that the probability of having the pool empty at the end of the vote is high. This remains to be verified.

It now remains to make a detailed presentation and analysis of the protocol and to implement it.

Thu 15 Jul 2010

  • David Mentré

An interesting new electronic voting protocol by Frédéric Connes

I recently stumbled on this presentation at SSTIC 2010 on the Security of voting systems. Beyond the usual presentation on the lack of security in current electronic voting systems, Frédéric Connes presents an interesting new electronic voting protocol.

This protocol has been firstly draft in a first paper in 2008 and then in an updated second French paper for SSTIC 2010. The French slides of the SSTIC 2010 presentation are also available.

Very roughly, the main idea of this protocol is to associate a randomly generated number to each new vote. For example, if in a election amongst three people A, B, and C I vote for A, a random number 23482 is generated and associated to my vote A. Just after leaving the voting both, I also receive a paper receipt where my choice is displayed ("A 23482"). To keep the anonymity of my vote, for other options B and C a number is also printed, number chosen so that it corresponds to the choice of a previous voter. At the end of the vote, the results are published on a web site. Everybody can verify that his/her vote is correctly taken into account by checking that the random number is correctly displayed with the correct choice. One can also verify other options on the receipt. And one can also recount the tally the displayed votes and verify the election result.

This protocol ensures the good properties of a voting protocol:

  • My vote is anonymous because there is no way to associate my identity to the random number;
  • I have no way to prove that I vote for a given person because all the votes on the receipt are valid and displayed on the web site;
  • The whole vote can be audited because everybody can check that the content of his receipt is correctly displayed on the web site and recount the whole vote.

This protocol is relatively simple to understand, with no complex cryptography and with simple procedures. Of course, this protocol is far from being perfect and its author present some weak points and counter-measures:

  • the random number should be really chosen at random. The author presents two procedures to ensure this randomness. One of them is to let both the voter and the voting machine participate in the generation of the random number, but this seems very complicated to me;
  • For the first voters, there is no or few previous random numbers for the choices different that his/her choice. The author propose to generate false votes for the first voter. This has strong implication, most notably that the vote of the first voter is not really taken into account;
  • It is possible to guess the vote by knowing the receipt of one or more voters before a given voter. The author proposes the ability to generate a "completely anonymous" receipt, where the random number generated for the vote is not displayed on the receipt. This breaks the nice property to check the receipt content on the final web site;
  • The receipt should signed to ensure its integrity, so one can go into a Court to defend ones vote in case an error is detected. This signing procedure complicates a lot the voting procedure.

Another issue that the author does not mention:

  • What happens if all voters vote for the same option? Are their vote still guaranteed to be anonymous?

Overall, this voting protocol is currently not perfect but it offers very interesting ideas and properties. Probably the most interesting of it is that the protocol is "Software independent" as defined by Ronald Rivest, meaning that the correct working of the vote procedure does not need a correct software, any (or most) errors in the software can be detected.

A lot of work would be needed on this protocol:

  • An attack tree to find the possible attacks and way to counter them;
  • A probability analysis of the protocol, especially in the attack scenario where an attacker knows one or more paper receipt;
  • A detailed description of the voting procedure, giving the rationale of each step and giving actions to take in case of errors (one or more receipt is not valid, the voter does not like the random number, etc.);
  • A formal description of all the properties and invariants of the protocol.

I would like to thank Frédéric Connes for his very stimulating paper. :-)

Thu 01 Apr 2010

  • David Mentré
  • 2

Pourquoi je quitte l'expérience démocratique

demexp On m'a récemment contacté à propos de l'expérience démocratique. J'avais déjà annoncé que je quittais le projet mais j'ai fini par élaborer une réponse plus précise. Il me semble intéressant de la rendre publique, non pas pour étaler mes états d'âmes mais comme une réflexion a posteriori sur un engagement et sur un projet de logiciel Libre qui n'a pas marché (et accessoirement pour l'« histoire » du projet ;-).

Si on retourne en 2003, je venais surtout pour l'aspect informatique du projet. Faire un logiciel de débat et de vote électronique original, c'était intéressant et très motivant. Mais après plusieurs années de développement je n'ai toujours pas un logiciel utilisable et je me suis retrouvé tout seul à le faire (ou quasiment). La lassitude a fait le reste du travail. ;-)

Par ailleurs, certains choix technologiques ont limité le développement du projet (client lourd en Gtk+, pas d'interface web), même si cela était dû à des contraintes quand j'ai commencé (Ocsigen n'existait pas à l'époque). Pour d'autres choix comme utiliser le langage OCaml, ça a très certainement limité l'arrivée de nouveaux développeurs. Mais je n'en aurais pas fait autant dans des langages plus classiques comme PHP ou Python. D'ailleurs d'autres ont proposé des morceaux de logiciel, en repartant de zéro comme Jean-Marc Fauché ou Lyu Abe. Mais ces propositions ne m'ont jamais emballé.

Plus sur le fond, je m'interroge pas mal sur le sens du projet. La démocratie ne se limite pas au vote, le débat et la formation des citoyens sont tout aussi important. Après quelques années, j'ai eu l'impression qu'on se concentrait uniquement sur l'aspect vote et pas assez sur les autres aspects. Pour le dire autrement, c'était peut-être plus important de faire un serveur de listes de diffusion, un service web pour synthétiser les débats et puis finalement voter en Condorcet avec du papier et du crayon que de faire un logiciel de vote électronique. On avait dit qu'on ferait des « soirées Condorcet » dans un bar, pour mettre en œuvre de manière concrète et ludique les idées du projet : cela ne s'est jamais fait.

Pour le logiciel, je suis parti sans réellement de spécifications, quasiment par le codage. Ce n'est pas comme ça que l'on fait un bon logiciel. ;-) Évidemment, quand on a démarré, on ne savait pas trop où on allait. Maintenant je pense que j'aurais des idées plus claires.

Informatiquement parlant, l'amplitude du projet est très vaste. Cela va des bases de données aux interfaces graphiques en passant par la cryptographie ou le réseau. C'est très stimulant sur le plan intellectuel, on apprend pleins de choses mais on n'est pas forcément bon partout.

Sur un plan plus pratique et citoyen, le vote électronique est très polémique (voir par exemple ordinateurs-de-vote.org). Je suis moi même contre les machines de votes actuelles[1] ! Il est quasiment impossible de faire un logiciel de vote aussi transparent qu'une urne en plexiglas. La recherche dans le domaine des protocoles de vote avance mais il faudra encore probablement de nombreuses années avant d'avoir quelque chose d'utilisable. Et ce sera très vraisemblablement plus compliqué qu'un bulletin dans une urne.

Sur le plan plus humain, on a démarré à quatre sur le projet, puis à trois au cœur. J'ai trouvé sur le long terme que j'étais un peu seul à faire la gestion de tâches informatiques (mise à jour du serveur, répondre sur les listes, le développement, etc.), malgré le soutien de mes deux compères. Ils ont beau être les pères de l'idée, j'ai trouvé que leur implication n'y était plus.

Enfin et surtout, après plusieurs années, j'ai envie de m'attaquer à d'autres défis, dans des domaines totalement différent et cela ne se fera pas sans dégager du temps libre. J'ai donc arrếté mon implication dans des projets non « productifs ».

Voilà, c'est probablement trop long et un peu confus, mais c'est dur de résumer plusieurs années de projet en quelques mots.

Je considère toujours que la thématique du projet, la réflexion sur la démocratie et le rôle du politique, est cruciale. Peut-être juste que l'angle n'était pas le bon, je ne sais pas. Apparemment, d'autres on des idées similaires et très intéressantes.

Et l'expérience a été pour moi enrichissante. Je ne regrette rien ! :-)

Notes

[1] Vous avez dit schizophrène ? ;-)

Mon 13 Jul 2009

  • David Mentré
  • 3

Mini news : micro-blogging et demexp

En premier lieu, désolé pour le manque de billets la semaine dernière, mais il est parfois nécessaire de faire une pause de temps en temps.

Première mini-news : micro-blogging

Logo Identi.ca J'ai cédé aux appels de Jean-Philippe, Thomas ou Fabien sur le micro-blogging en finissant par ouvrir un compte sur le service de micro-blogging libre identi.ca. Mon identifiant (très original) : dmentre. Pourquoi choisir identi.ca plutôt que Twitter ? Parce que identi.ca fonctionne sur une plate-forme libre avec le logiciel Laconica et que les billets sont publiés sous une licence libre (CC-BY-SA 3.0). Bon, à mon avis, c'est encore une source de perte de temps sans réel utilité, mais j'affirme de plus en plus mon côté geek. :-)

Deuxième mini-news : demexp et les RMLL

RMLL 2009 J'ai fait un saut au 10e Rencontres Mondiales du Logiciel Libre (les reumeuleuleu pour les intimes) à Nantes cette année et malgré le peu de temps que j'ai pu y passer, Fred a trouvé le moyen de me faire participer à un débat radiophonique sur le vote électronique. Et pourtant, ce n'est pas faute de dire que demexp m'intéresse de moins en moins ! :-) Si vous avez 50 minutes à perdre, n'hésitez pas à me donner votre avis. J'ai l'impression qu'on est super confus au début (forcément, aucune préparation !) mais qu'après ça s'arrange un peu. Enfin j'espère. ;-) Pour ceux qui suivent les aventures du vote électronique, pas grande originalité dans les propos. Sinon, les RMLL, c'est super sympa pour voir les potes exilés aux quatre coins de l'hexagone. :)

Le logiciel de vote epoll pour les élections au CNRS réalisé par le troisième intervenant, Olivier Thauvin (alias nanardon), est lui aussi disponible. Il a des spécifications plus classiques (par rapport à demexp ;-) mais il y a apparemment un gros effort pour garantir les bonnes propriétés du vote en respectant notamment les recommandations de la CNIL. Les présentations d'Olivier donnent une description plus complète d'epoll.

Troisième mini-news : nouvelle version du demexp de Jean-Marc Fauché

Jean-Marc a publié il y a plus de deux semaines une nouvelle version de son demexp développé en Python avec web2py. Elle est enfin accessible en ligne à l'URL http://bentobako.org:8000/Demexp. Cette version apporte un système de délégation d'un vote.

Thu 28 May 2009

  • David Mentré

Une nouvelle application demexp en web avec web2py

Le projet d'expérience démocratique est un projet de démocratie directe à grande échelle. Il a démarré il y a quelques années déjà mais il a du mal à décoller, en particulier par manque d'un logiciel adapté. En effet le projet nécessite un logiciel de vote électronique en ligne ayant des caractéristiques bien particulière comme le vote Condorcet, une délégation possible du vote, à tout moment possibilité de changer un vote, etc. J'avais écris un serveur et un client lourd (en OCaml) pour remplir ce rôle mais les développements ont stagné pour diverses raisons : manque de motivation de ma part, trop de choses encore à faire, client lourd trop compliqué à déployer et à maintenir, langage OCaml peu connu donc je suis le seul développeur sur le projet, etc.

Hors, très récemment, une nouvelle application est apparue, programmé par Jean-Marc Fauché : une implémentation des idées de demexp en technologie web. Plutôt que de partir de mon code, Jean-Marc redémarre de zéro en langage Python, en utilisant le framework web2py.

Les caractéristiques de web2py sont intéressantes :

  • un déploiement aisé des applications : on peut télécharger une application dans un serveur existant ou récupérer une application existante à partir d'un serveur ;
  • on peut développer l'application en ligne : base de données, modèles et vues (même si à mon avis ce n'est pas forcément très utile pour de grosses applications) ;
  • les rapports d'erreurs (exceptions) sont accessibles en ligne, par l'interface d'administration ;
  • le déploiement est hyper-simple : unzip web2py_src.zip && python web2py/web2py.py ;
  • web2py est organisé autour de l'architecture modèle-vue-contrôleur et incite à utiliser ce modèle ;
  • le système de template utilise le langage Python plutôt qu'un autre langage ad hoc ;
  • un système de traductions en ligne, là aussi par l'interface d'administration ;
  • la base de donnée est vue au travers d'objets Python et toute modification des descriptions de la base est répercuté sous forme de commandes SQL de mise à jour de la base ;
  • et bien sûr un soin tout particulier apporté au framework pour faire des applications web sûres par défaut.

En bref, web2py semble la plate-forme idéale de prototypage rapide d'applications web, améliorant les idées trouvées dans d'autres frameworks comme Django ou Ruby on Rail. Pour des développements longs et importants, je ne suis pas sûr qu'il soit totalement satisfaisant, les aspects dynamiques de Python ont leurs limites (qui ne connait pas le typage fort d'OCaml ne peut pas comprendre le sens de la vie ;-). Mais il faut reconnaître a développé en quelques semaines une application qu'on peut tester et facilement déployer.

J'ai installé un dépôt Mercurial pour consulter le code de Jean-Marc. Si vous voulez tester son code, sa dernière version publiée est utilisable sur ce site temporaire : http://bentobako.org:8000/Demexp/.

En guise de conclusion, l'expérience démocratique semble redémarrer et on ne peut que s'en réjouir.

Mon 25 May 2009

  • David Mentré

Les machines de vote électronique en Inde

Un message récent sur la liste de diffusion vote-electronique a attiré mon attention sur les machines utilisées en Inde où le vote électronique est utilisé de façon massive (environ 714 millions d'électeurs sur 1,2 milliards de citoyens, 800.000 bureaux de vote, 1 mois d'élection[1]).

Processus de vote électronique en Inde Les machines utilisées sont relativement simples : une unité de contrôle reliée par un long câble de 5 mètres à une unité de vote comportant 16 boutons. L'assesseur autorise un vote en pressant un bouton sur l'unité de contrôle. Dès qu'un vote a été choisi sur l'unité de vote, il est enregistré et il est impossible de changer son vote. Interface simple et claire, il ne faut juste pas se tromper de bouton. ;-) À la fin de l'élection, l'assesseur doit presser un bouton sur l'unité de vote pour obtenir les décomptes. Là aussi, un fonctionnement plutôt simple. La machine utilise massivement des scellés pour contrôler l'accès aux différentes parties. Cette présentation détaillée des machines (format PowerPoint) montre bien leur fonctionnement mécanique.

Il n'y a pas beaucoup d'information sur la partie logicielle qui est apparemment totalement fermée. Pas terrible pour la confiance qu'on peut avoir dans ces machines de vote[2]. :-( Apparemment, le programme est enregistré sur une mémoire non re-programmable.

L'ensemble de la machine semble couter environ 300$.

À noter un argument intéressant en faveur de ces machines de vote : elles seraient d'usage plus simple que le vote papier pour les illettrés.

Notes

[1] Chiffres donnés par Benoît Sibaud.

[2] Si tant est qu'on puisse avoir confiance dans un objet aussi compliqué qu'une machine de vote.

Mon 11 May 2009

  • David Mentré

Un client demexp pour Ubuntu 9.04 / amd64

J'ai compilé un client demexp (client de vote pour l'expérience démocratique) pour la version Ubuntu 9.04 Jaunty Jackalope en architecture amd64 (version 64 bits pour processeurs x86 d'Intel et d'AMD). Il est disponible dans cette archive.

J'ai aussi remis à jour le code et les notes de version dans les arbres Mercurial de la version de développement (la 0.9) et la dernière version stable 0.8.

Avec la doc fournie, il doit être relativement facile de compiler un client demexp stable 0.8 sur une Debian Lenny ou une Ubuntu 9.04, sur toutes les architectures x86, 32 ou 64 bits.