Stage de M2 – Protocoles d'échange de clefs à base d'isogénies October 31, 2016

Contexte

Une isogénie est un morphisme surjectif et de noyau fini de variétés abéliennes. Les exemples les plus simples d’isogénies sont les morphismes algébriques de courbes elliptiques qui préservent les points à l’infini.

La cryptographie à base d’isogénies est une des branches les plus jeunes de la cryptographie asymétrique. Initiée il y a seulement 10 ans par les travaux sur les réductions de logarithmes discret1 2 3, et sur les fonctions de hachage prouvablement sûres4, elle s’est ensuite enrichie de protocoles d’échange de clef5 6 7. Il existe essentiellement deux protocoles d’échange de clefs à base d’isogénies : un basé sur les courbes elliptiques ordinaires5, et un autre basé sur les courbes elliptiques supersingulières6. Ces deux protocoles ont tous les deux l’intérêt de résister à des cryptanalyses par ordinateur quantique (algorithme de Shor), mais seulement le deuxième est considéré suffisamment efficace pour être utilisable en pratique.

Toutes les constructions cryptographiques à base d’isogénies reposent sur des problèmes de recherche de chemins dans des graphes d’isogénies ; ce sont des (multi)-graphes non-orientés où les sommets sont des variétés abéliennes à isomorphisme près, et les arêtes sont les isogénies.

La structure des graphes d’isogénies est régie par celle des anneaux d’endomorphismes des variétés abéliennes. Dans le cas des courbes elliptiques ordinaires, la théorie de la multiplication complexe lie les isogénies aux idéaux fractionnaires d’un corps de nombres quadratique imaginaire8 9. Dans le cas des courbes elliptiques supersingulières, ce sont les idéaux à gauche des ordres maximaux d’une algèbre de quaternions qui jouent le même rôle8 10. Ces théories se généralisent aux variétés abéliennes de dimension supérieure11 12 13, mais elles ne sont pas aussi complètes que pour le cas elliptique.

Sujet du stage

Le but du stage est d’étudier le protocole d’échange de clefs de Rostovtsev et Stolbunov5, d’en proposer une variante efficace, et d’en estimer soigneusement les paramètres de sécurité par une étude des attaques quantiques connues.

On cherchera des pistes pour améliorer le protocole dans les techniques utilisées dans les protocoles à base d’isogénies supersingulières, ainsi que dans les généralisations aux dimensions supérieures. L’analyse de sécurité se fera en tenant compte des modèles de sécurité en cryptographie classique, ainsi qu’en cryptographie post-quantique.

En cas de succès, le stage pourra se poursuivre naturellement par une thèse en cryptographie à base de courbes elliptiques et isogénies : construction de nouveaux cryptosystèmes, cryptanalyse, calcul d’anneaux d’endomorphismes, etc.

Compétences recherchées

  • Connaissances mathématiques en algèbre, théorie des nombres et géométrie (corps finis, corps de nombres, courbes elliptiques, …).

  • Connaissances en algorithmique (par ex.: grands entiers, factorisation, primalité, arithmétique des courbes elliptiques).

  • Maîtrise d’un système de calcul formel (par ex., SageMath, Pari/GP, Magma).

  • Connaissance d’un langage de programmation.

Aucune connaissance en calcul quantique n’est requise, mais ceci peut être un plus.

Laboratoire d’accueil

Le stage s’effectuera dans l’équipe GRACE de l’Inria Saclay, sous la direction de Luca De Feo et de François Morain. Le stagiaire sera amené à interagir avec le Laboratoire Cryptographie et Composants de l’ANSSI.

Pour candidater, envoyez un email à luca.de-feo@uvsq.fr en joignant votre CV et une lettre de motivation.

Bibliographie

8 weeks and 60 students with Cloud9 June 11, 2014

I would like to finish my series on teaching web programming with a report on how the online IDE Cloud9 helped improve my students productivity.

As you might know if you read French newspapers, UVSQ is a university on a low budget. The department has only one computer room, and it is best avoided. Students bring their own laptops to tutorials, or they can borrow one from the library.

When I gave my course the first year, several precious tutoring hours were lost installing, configuring and debugging WAMPs, LAMPs and virtual machines. The switch to Node.js eased things up: installation was generally smooth, apart for some version problems on Ubuntu machines and missing SQLite interfaces for Windows. Both years, I had to teach the students, especially those not on Linux, how to launch and use a terminal.

Having decided to go back to PHP, I absolutely wanted to avoid the painful installation of Apache and stacks. The cloud IDE Cloud9 looked like a promising alternative, lifting the burden of handling dozens of different configurations.

Cloud9 is a commercial product, offering free unlimited workspaces for public development, plus one private workspace. It has some integration with GitHub, BitBucket and Heroku, and some limited history and collaboration features are also available for free accounts. It can natively execute and debug Node.js instances, or run PHP applications via Apache (other runtimes are also supported). It includes a MySQL and a MongoDB server for development.

The good

Thanks to Cloud9, the only problems left to solve on the first tutorial were laptops not connecting to the network, and students having confirmation emails from Cloud9 delayed or blocked by their provider.

Once they were connected to the Cloud9 dashboard, the students could get started coding immediately by cloning the project skeleton I had hosted for them on GitHub. From then on they could work on their project (no knowledge of git required), while I could update their configuration files by asking them to pull. Some students eventually managed to mess with their local git clone, but fixing it was a minor annoyance overall.

Previewing static html files and running apps is as easy as a button click: all students quickly caught the workflow, although some of them were slow to grasp the difference between viewing static files and running apps.

Because all projects are public, I could connect to the students’ workspaces at any time and observe their work live. This was useful in the classroom, but even more important when addressing help requests out of the class. The embedded chat room was also very useful when helping students from home. Beyond the IDE front-end, each workspace also offers a publicly accessible webdav directory. This let me easily crawl and download all the students’ work for local examination and grading. I found this very convenient for the first part of the course, where only client code was involved. At least in one case, my local copy also served as a back-up save for a student who had accidentally erased all her work.

However, visitors to workspaces do not have the rights to run processes, hence they cannot run server code. When the students started writing server code and using SQL, reproducing their environment locally turned out to be too painful. Thus, I had to resort to asking them for write permissions on their workspaces, which also turned out to be a very convenient way to help them fixing Cloud9 glitches from a distance. In retrospect, I should have asked write permissions from the beginning.

Finally, some comments on cheating. Yes, any student could see any other student’s work, if he could guess his colleague’s login and workspace name. This is in my opinion very good, and most students used it constructively: taking example from their comrades’ code, using the chat to help each other, and even collaborating on code. Obviously some students didn’t refrain from using it to cheat, and some went even as far as creating Cloud9 accounts with logins similar to mine, so to not awake suspicions in their comrades. In reaction, some of the good students created accounts with unguessable usernames, or used the one free private project.

However it wasn’t too hard to unmask the cheaters. My own plagiarism detection scripts helped me narrow down the hunt, Cloud9 history tool did the rest: by rewinding history, I could easily know when the students had been working, when the copy-paste had happened, and what variables had been renamed. Not only I had a very easy time detecting cheating, but I even had irrefutable proofs of it.

The bad

Cloud9 wasn’t all joys and wonders. For one, it requires a good network connection to function properly. Wifi connections, such as eduroam, are likely to give a horrible experience. As obvious as this may sound, some students kept forgetting or refusing to bring ethernet cables: I had to always bring a stock with me.

Even on a wired connection, though, most students experienced serious problems. The IDE would often lock one file or freeze completely, the only solution being reloading. Before I prompted the students to enable auto-saving, network errors would occasionally destroy one hour worth of work. After they enabled auto-saving, some students experienced severe slow-downs of the interface, and even then some work was occasionally lost. Sometimes, after recovering from a freeze, some files would be empty; a peak at the history would usually yield all the contents back, but restoring previous versions is horribly clumsy in the free version of Cloud9.

About a dozen of workspaces got locked at some point, with the interface simply not able to read the filesystem. This required the intervention of Cloud9 staff, often holding the student from working for the rest of the day. In March, we were also unlucky enough to experience a major platform problem affecting POST requests right before a submission deadline.

Overall the use of Cloud9 turned out to be very frustrating for some students. I wonder if the time gained by not having to install anything locally wasn’t compensated by the time lost fighting Cloud9 glitches. Thankfully, Cloud9 staff was very kind and responsive, and usually solved all problems in one day’s time.

To my surprise, more than 50% of the students thought very well of Cloud9, grading it 4/5 or 5/5. In the end, I think the experiment turned out well, and, whatever platform I am going to use next year, there is no going back to the dear old local install. Beyond being stable and not loosing data, my ideal platform would:

  • Use Cloud9 IDE as front-end, or similar.
  • Let me manage my group of students, view their projects, and automatically grant me write privileges on their repositories.
  • Keep history robustly and often (e.g., using auto-save and Git).
  • Do not allow the students to create multiple logins, and force them to be connected in order to use the platform.
  • Simplify some workflows (e.g., using the MySQL database).
  • Redirect PHP logs to the IDE console.

Maybe this can be achieved by installing the open source version of Cloud9 on a university server with a customized back-end. I will likely be experimenting with this before next year’s course.

Appendix

For reference, I report here some non-trivial configuration details and bug fixes that I had to apply during the course.

  • Due to bugs in Cloud9, or to bugs in the students code, the interface may freeze repeatedly. While it is not guaranteed to work, adding ?reset=1 to the workspace URL may help fixing problems. It simply returns the workspace to its initial state: no files open, no previews, no applications running. Here’s one funny case where this was useful: a student had written an infinite loop in JavaScript, and opened its web page in the “Preview” tab. The preview would freeze the whole interface and crash the browser tab. But at each reload Cloud9 would open again the “Preview” tab… and crash again!

  • If a php.ini file is placed in a Cloud9 workspace, its settings supersede the global ones. This has various uses: activate sessions, printing errors, etc. One important use for Silex: the PHP package manager Composer wants the setting date.timezone to be set.

  • Integration with PHPMyAdmin is sure in the plans for Cloud9, but not ready yet. The simplest solution for me was to ship a lightweight open source MySQL manager, SqlBuddy, together with the project skeleton.

  • One of the most annoying bugs, happening almost systematically, prevents the MySQL server from starting after a workspace freeze. This is a known bug with a fix documented here, but, had I known it before, it would not have hold so many students for the entire tutorial following spring break (during which many workspaces froze).

  • Finally, one of the most random problems was caused by GitHub. The students working with Silex had to install it in Cloud9, together with its dependencies. I had given a composer.json file, so that they just had to run Composer in the Cloud9 terminal in order to download and install everything. Composer connects to GitHub’s API, and GitHub limits anonymous requests to 60 per hour per IP. Since every user in Cloud9 has the same IP, chances are that some student may get rate limited. Fortunately Composer will fail with a meaningful error message, and will ask for a GitHub login in order to solve the problem. Unfortunately, the average student will not have a GitHub account, and will not understand what the message is asking for, so if this happens outside the class, expect an email. I was lucky: this happened only once. Another fix is described here.

8 weeks, 60 students and 1 web application June 10, 2014

To continue my series of posts on teaching web programming, I would like to share on the project students had to realize for my web programming course.

In past years, I used to ask the students to develop a web application of their likes, setting some minimum requirements to pass the course. I picked this from beginner courses I had been tutoring for in École Polytechnique and in Paris VII, while I was a PhD student.

Although this formula was very successful in École Polytechnique, and reasonably good in Paris VII, it was very disappointing in my own course. I got tired of having to grade, over and over, the usual forum application, mostly grabbed off the Internet and poorly put together. Some of the best projects sure were able to blow my mind, like a fully functional battleship game, or an almost functional multiplayer Scrabble. But the large majority of it was just dull and boring, when it wasn’t cheating.

I think the reasons for this failure sum up to: student level highly inhomogenous, course requirements too high for most students, course duration too short. Mostly the opposite of what we had in Polytechnique and Paris VII. I was not ready to give up on the requirements, so I had to find a way to force the students to keep up with the course and do more work.

The directed project, to be developed during the tutoring sessions (3 class hours per week, plus a lot of homework for most students), turned out to work very good. It was rather ambitious: write a multi-user almost-real-time Connect-four application. I have to admit it even flirted with the impossible: the last part required to push play events from the server to the clients; something very natural to code in Node.js, but very unnatural in Silex.

The progression kept the students interested all along. They strove to complete all the requirements, going well beyond what they would have achieved on a project of their own. Almost everyone got to write some AJAX interaction: something I had not even dreamed of in past years. I was amazed to see several students complete all the requirements, delivering a fully functional Connect-four game.

According to the polls, 80% of the students found that the course required more work than other masters’ courses, but they got relatively high grades, and 75% of them where happy about it. But didn’t this make cheating worse? Quite the contrary, as I will develop in the next post.

One thing some students complained about was the lack of feedback on the quality of the work they were providing. I collected and graded their work twice (once mid-course, once at the end), was several weeks late giving grades, and could hardly have done more, given that I was alone grading 60 students. Also, just two numbers hardly give much information on what’s good and what’s bad in the code.

Auto-graders could provide one way of improving feedback. In the future, I think it would be interesting to experiment with them, although I am afraid they could hinder the students’ creativity by not inspiring them to freely explore. Another interesting way in which auto-graders could complement the directed project would be to isolate and teach fundamental concepts by short, self-contained exercises focusing on specific skills (e.g.: navigating the DOM, building a HTTP response by hand, etc.).

Given that the course already has a good deal of video material, and that I am planning more of it for next year, the use of auto-graders would make it more and more akin to a MOOC. Who knows…

8 weeks and 60 students with Silex June 5, 2014

From February to May, I have taught my usual eight weeks web programming course at Université de Versailles. The course, called Applications Web et Sécurité (Web Applications and Security) is aimed at first year masters’ students with a computer science major. This is the third time I have taught this course, and for the third time I have messed up with most of the syllabus in search of the magic formula. I haven’t found it yet, but I think I got a bit closer.

This year’s course was different from the previous ones in many ways:

  • Class material was written in French.
  • Tutorials were structured so to construct a full web application from the ground up. The design was mostly given in the syllabus. All students had to implement the same application, individually or in pairs. I would give marks to the final product, which would account for one third of the course grade.
  • Students had the choice to develop the application in Silex, or Node.js.
  • All development was done in the cloud, using the online IDE Cloud9.

I am going to share my experience in a series of blog posts, hoping to spark some thoughts/reactions/new ideas among my colleagues teaching similar subjects. I will start by discussing the technologies I chose.

The first year I gave this course, I taught standard PHP+MySQL over a WAMP, LAMP or MAMP stack; a common choice for this kind of course, also inherited from my previous experiences. The course was a big success.

Unfortunately, I hate PHP. The next year, I switched to native Node.js (no Express), with Mustache and SQLite/MySQL. Along the way, I wrote a micro-framework to guide the students in their development. The course was a disaster. Almost half of the students dropped the course midway. Of those who stayed, most could not grasp the basic concepts behind Node.js. I ended up receiving dozens of version of the classic chat room on web sockets app: I had not taught web sockets, but chat rooms were basically the only examples written in Node.js one could find on the Internet at the time.

Why was it so hard? The answer is: “basics”. Most of the students could not grasp the concept of callback, let alone event-driven design! Also, Node.js was not as popular as it is now: most students were expecting a PHP course (two thirds of the students already know some PHP), also in consideration of their employment perspectives. Fortunately, the usual handful of very good students was there to cheer me up.

So this year I had to go back to more familiar grounds, but I didn’t want to loose the work done with Node, and still wanted to keep some of the clean separation of concerns achieved by it. I first thought of Symfony: a very elegant PHP framework, open source, developed in France, and enjoying high demand from the industry. However, Symfony is a mastodon, with too much magic happening under the covers. By reading more about Symfony, I discovered Silex, a PHP micro-framework developed by the same company as Symfony, open source, remarkably similar to Node.

The match was perfect, I can even say Silex reconciled me with PHP. All the concepts I wanted to teach exist almost identically in Silex and Node (with Express, this time): HTTP, routers, views, template languages (Twig was a natural choice), DBALs, AJAX, REST APIs, Server push, security, … I could lecture on the theoretical principles giving examples both in PHP and Node, while the tutorials would have to be specialized for each language. This required a little more work on the tutorials, but nothing very serious (especially when compared with the huge amount of work the rest of the course gave me). I made very clear from the beginning that Node.js is for the good students, and that the official framework for the course is Silex. This had the perverse effect of pushing even some of the best students towards Silex (only 4 of 60 students chose Node), but I am confident that those ones will go back and have a look at Node anyway.

The cleanliness and lightness of the micro-frameworks made it possible to focus on fundamental low level details, and most importantly did not impose a specific pattern, such as MVC. Lecturing with two languages helped the students visualize the separation between coding patterns and actual technology.

I was afraid that students with a background in PHP would be reluctant to change their coding habits and learn how to use a modern framework and a template language. However this turned out to be a minor problem: it was enough to clearly state once or twice that they had to forget everything they knew about PHP. Most of the students, beginners and not, understood the added value of those modern tools on their employability, and happily followed the dense syllabus and adhered to its principles.

To conclude, I am really happy with the two technologies I chose and with the style of lecturing this implied. What’s most important, the students where happy too. At this stage, it does not seem implausible that I may add a third framework to the course someday (Python with Flask comes to the mind).

The Website Opens June 28, 2013

The new website is opening today!

It is still under heavy development, but you can already enjoy its basic features. The blog is not completely functional yet, come back soon!