• Posted on

    Low Tech Crypto : ThreeBallot

    Previously in this blog, I have mentioned that cryptographers designed algorithms allowing us to conceal messages without the use of a computer, like Solitaire. Although message privacy is the first subject that comes into everyone’s mind when talking about cryptography, it has many other applications, one of them being the design of secure voting systems. In this post, I will talk about ThreeBallot voting system, a system designed by Ronald Rivest (the R in RSA) which aims at creating a secure voting protocol entirely based (almost entirely) on paper ballots.

    Someone voting during french elections
    Illutration by Arnaud Jaegers

    End-to-end auditable voting systems

    Before we start taking a look at ThreeBallot, we need to summarize the objectives of cryptographic voting systems. In general, cryptographic voting systems aims at being end-to-end auditable, which means two things:

    • Anyone can proceed to a recount
    • Every voter has a way to know if their vote was counted

    This second property is usually achieved by giving a receipt of its vote to the voter. However, this receipt should not contain enough information to allow an attacker to breach the privacy of the vote, as each vote must remain secret to avoid vote-buying or coercion.

    Introducing the multi-ballot

    A sample ThreeBallot multi-ballot
    A sample ThreeBallot multi-ballot

    The ThreeBallot system aims at solving this problem with the use of a “multi-ballot”. The multi-ballot is a voting ballot that can be split into 3 parts (one per column), all containing the list of candidates (one per row) with optical-scan checkboxes as well as a unique identifier. To vote, simply check 2 boxes on the row of the candidate you want to vote for, and 1 box on the row of each candidate you want to vote against. A ballot will be considered spoilt if all three boxes for a candidate are checked, or none for another candidate.

    A sample filled ThreeBallot multi-ballot
    A sample filled ThreeBallot multi-ballot

    The validity of the ballot will need to be checked (by machine) before being split into 3 separate ballots. The voter will then chose which parts of the ballot to be used as a receipt and receive a printed copy of it, before casting the 3 ballots.

    A receipt
    A single ballot, used as receipt

    When the election is complete, every ballot is displayed publicly. Anyone can proceed to a count, the results are inflated by the number of voters (one box as to be checked minimum) but the difference between candidates will remain the same. The voters can each check that their ballot appears with the correct vote and ballot ID, or contest the vote using their receipt. The voters cannot use their receipt as a proof of having voted for a candidate, as you need at least 2 of the 3 ballots to tell that, thus maintaining vote secrecy.


    Despite looking very good on paper, this voting system sadly has many practical vulnerabilities. First of all, despite being paper-based it still requires a machine to print ballots with unique identifiers, and another one to check the validity of the ballots before casting them. Both of these machines represent weak points of the system, as one of them failing would stop the election from taking place correctly. A single malfunction of the checker machine would also be enough to make the entire election null because the system doesn’t provide any way of spoiling a vote after it’s cast. Privacy breaches could also happen if these machines were to be compromised, as an attacker could record which identifiers are part of the same multi-ballot and use it to connect receipts to a full ballot.

    In a follow up paper, Charlie Strauss points out that voter coercion can still happen with methods as simple as asking the voter to take a picture of their ballot using a smartphone. According to Strauss, it would also be trivial to double or triple vote by modifying the ballot after having validated it and before casting it. Voters might also give away their receipts or simply throw them in the nearest trash can, making their vote non-auditable and giving an attacker the opportunity of changing them.

    In a second paper, Strauss also points out the cryptographic weakness of ThreeBallot. Since one part of the multi-ballot restricts choice on the two other parts (a candidate can’t be entirely blank or checked), the receipt is leaking information about the actual vote. Combining this information with voter bias (ie. party preference), and the publicly displayed ballots, it becomes statistically possible to link a receipt with its two other ballot parts. This is especially concerning in a situation where the attacker could coerce the voter into not only voting for a specific candidate but also checking a specific pattern on its ballot.


    Many improvements to the ThreeBallot voting system have been suggested, but as with many security protocols, improving security often comes with useability issues. This led to the slow abandonment of this protocol. However, the insights gained through ThreeBallot later allowed the creations of new secure voting systems, such as Scantegrity, which was used in actual elections by the city of Takoma Park, in 2009 and 2011.

  • Posted on

    FOSDEM 2020 recap

    This year was the 20th edition of FOSDEM, and the third time I managed to attend it. FOSDEM is a yearly Free & Open Source Software meeting taking place in Brussels, Belgium and organized by the Free University of Brussels (ULB). This edition gathered more than 8000 FOSS enthusiasts from all around the world for 837 talks, making it an exceptional event for anyone interested in learning more about open-source projects and communities.

    The city of Brussels
    Illutration by Yeo Khee


    One of the very first talks I managed to see this year was about SpecFuzz, a tool made by Oleksii Oleksenko and his colleagues to help to test against Spectre vulnerability. The talk does an amazing job of explaining what causes the new speculative execution vulnerabilities, how can we detect them and how can we fix them. Since there’s no doubt these vulnerabilities will remain a major hardware and software security issue it’s an essential talk for anyone wanting to understand the topic. If you want to know more about SpecFuzz, Oleksii Oleksenko’s paper is available on arXiv and the source code is on GitHub.

    Then I managed to see two talks about Falco, a new Kubernetes threat detection engine. The first one by Lorenzo Fontana, explained how they managed to find a reliable way of monitoring Linux system calls. The second one by Kris Nova, shows practical use cases of k8s threat detection against real attacks.

    At the end of the first day of talks, Daniel Stenberg (curl’s developer) gave one of the most important lectures of this Fosdem, titled HTTP/3 for everyone. This talk is in my opinion largely enough to answer every question developers might have about HTTP/3 and QUIC, except maybe for “when will it release?”.

    The main ULB amphitheater

    On Sunday, Ecaterina Moraru came to talk about UI and UX. Her talks contain great and easily applicable tips for developers to build more accessible applications. I feel like this is an extremely important talk since too many open source projects focus on being technically perfect while forgetting that they need to be usable first.

    Last but not least, in the Go room, Derek Parker presented the state of Delve. For those who don’t know it already, Delve is a debugger for Go, usable from the command line or with integrations in Vim, Emacs, IntelliJ… This talk explains Delve’s support for “deterministic debugging” through Mozilla RR (Record and Replay Framework) which is a feature allowing you to capture and replay a bug until you fix it.


    I sadly can’t make an exhaustive list of all the great talks that I might have missed at Fosdem this year. Hopefully, I will be able to see talks of the same quality next year. As usual, I thank all the Fosdem organizers and the ULB for their amazing work and allowing this event to happen for free.

  • Posted on

    Low Tech Crypto : Solitaire

    In a previous post, I talked about the One-Time Pad, as an example of cryptography that’s achievable without a computer. It’s a very simple, yet perfectly secure cryptographic algorithm, that comes with a lot of practical limitations, the biggest one being that it requires a truly random key as long as the text you want to encrypt (the plaintext). The good news is that cryptographers have been hard at work creating algorithms that are more usable while still providing privacy.

    Solitaire, an algorithm made by Bruce Schneier in 1999 is definitely the most famous of the low-tech cryptography algorithm since it was featured in Neal Stephenson’s book Cryptonomicon under the name “Pontifex”. As its name suggests, it uses a deck of cards to encrypt and decrypt messages.

    A regular card deck
    Illustraton by Aditya Chinchure

    Encrypting messages

    Solitaire is a stream cipher, which means it works just like the one-time pad, except instead of using a truly random key for the whole length of the plaintext, they generate a pseudo-random keystream from a smaller key. In this case, our base key is a shuffled deck of 54 cards, with two differentiable jokers (we will call them A and B).

    Let’s say we have the thoroughly shuffled deck of cards below and want to encrypt the message HAPPY NEW YEAR:

    49 50 51 3 4 5 6 7 1
    10 11 12 52 15 16 17 18 19
    20 21 2 9 26 27 28 29 30
    31 32 33 34 35 36 37 38 39
    40 41 42 43 44 45 23 A 14
    22 8 24 25 B 46 47 48 13

    Step 0: First we need to format the message into blocks of 5 characters (pad it with X if necessary) to avoid leaking pieces of informations. This gives us: HAPPY NEWYE ARXXX. We will then use a number representation of this plaintext.

    H A P P Y N E W Y E A R X X X
    8 1 16 16 25 14 5 23 25 5 1 18 24 24 24

    Step 1: We can then start generating the keystream, by taking the joker A and swapping it with the card beneath it. If it’s the last card put it after the first card.

    49 50 51 3 4 5 6 7 1
    10 11 12 52 15 16 17 18 19
    20 21 2 9 26 27 28 29 30
    31 32 33 34 35 36 37 38 39
    40 41 42 43 44 45 23 14 A
    22 8 24 25 B 46 47 48 13

    Step 2: You then find joker B and move it the same way two cards down.

    49 50 51 3 4 5 6 7 1
    10 11 12 52 15 16 17 18 19
    20 21 2 9 26 27 28 29 30
    31 32 33 34 35 36 37 38 39
    40 41 42 43 44 45 23 14 A
    22 8 24 25 46 47 B 48 13

    Step 3: Swap the cards above the first joker, with the cards below the second joker.

    48 13 A 22 8 24 25 46 47
    B 49 50 51 3 4 5 6 7
    1 10 11 12 52 15 16 17 18
    19 20 21 2 9 26 27 28 29
    30 31 32 33 34 35 36 37 38
    39 40 41 42 43 44 45 23 14

    Step 4: Take the value of the bottom card as a number. The simplest way to do that is to use the position of the card in the bridge suit (clubs < diamonds < hearts < spades). For example 10 of heart is 36 and a 2 of club is just 2. Jokers are both 53.

    Use this value as the index where to cut the deck for the next step. Now swap both parts of the cut, without moving the bottom card:

    4 5 6 7 1 10 11 12 52
    15 16 17 18 19 20 21 2 9
    26 27 28 29 30 31 32 33 34
    35 36 37 38 39 40 41 42 43
    44 45 23 48 13 A 22 8 24
    25 46 47 B 49 50 51 3 14

    Step 5: To find the output value, use the value of the top card as the index of the output card. If the output card is not a joker, write down its value. Start back with the deck in its current state at step 1 until you have as many numbers in your keystream as letters in your plaintext.

    In our example, we find the following keystream:

    1 34 29 35 39 46 11 12 29 50 24 26 45 6 6

    Step 7: Add your keystream to your plaintext (as numbers) modulo 26 to obtain the ciphertext:

    8 1 16 16 25 14 5 23 25 5 1 18 24 24 24
    1 34 29 35 39 46 11 12 29 50 24 26 45 6 6
    I I S Y L H P I B C Y R Q D A

    You can now safely send IISYL HPIBC YRQDA to anyone who has a deck shuffled in the same order as yours. To decrypt it, you will need to generate the same keystream and subtract it to the ciphertext you just produced.

    A regular card deck
    Illustraton by Aaron Burden


    Solitaire is a great low-tech cipher since it’s both practically secure and uses items that are both easy to find and unsuspicious. However, there are a few limitations to keep in mind while using this cipher:

    1. You should never use the same key twice, as it would allow an attacker to gather information about your messages without even knowing the key.
    2. You should only encrypt small messages with it. A recent analysis of Solitaire found that it leaks information at a rate of 0.0005 bits per character, while this is reasonably safe for encoding you 140 character long tweet, it isn’t safe to use for your copy of War and Peace.
    3. You still need to be careful about any extra information you could give to an attacker, especially notes you take of the keystream, or decks that you used / intent to use, as those can be used to crack your messages.

    If you want a more complete overview of Solitaire, I recommend the lecture of the original Bruce Schneier’s article on it. If code talks to you more than English, I made a small Python implementation of Solitaire that can be useful for testing purposes, you can find it on GitHub.

  • Posted on

    Introducing tartiflette-plugin-scalars

    This month I worked on a plugin for the Tartiflette GraphQL engine. It’s called tartiflette-plugin-scalars and it is here to help you validate data using scalar types in your GraphQL schema.

    If you’ve never heard of Tartiflette before, it’s Dailymotion’s in-house GraphQL engine in Python 3.6. It aims at offering an SDL-first schema definition, allowing developers to focus on business-critical code. Tartiflette makes use of asyncio and can be used over aiohttp or ASGI.

    A tartiflette, with fried ham
    Illustraton by Hayford Peirce

    Tartiflette-plugin-scalars come with a list of common types such as DateTime, URL or IPv4. Using those types in your GraphQL schema will guarantee that the data you receive, as well as the data you send back, is in the correct format. When possible, the plugin will automatically serialize and unserialize the types you use toward Python3 types, like datetime.datetime.

    If you want to start using it right now, you can install it through pip:

    pip install tartiflette && pip install tartiflette-plugin-scalars

    Then initialize the engine with create_engine, indicating you want to use tartiflette_plugin_scalars and an SDL file.

    from tartiflette import create_engine
    with open("schema.sdl") as schema:
        engine = await create_engine(
                    "name": "tartiflette_plugin_scalars",
                    "config": {},

    Then you can start using the custom scalars to define your SDL. In the following example, we have a query that can return an IPv4 address with a port and a mutation that accepts a GUID as input and returns it:

    type Query {
      ipAddress: IPv4
      port: Port
    type Mutation {
      checkGUID(input: GUID!): GUID!

    Write your resolvers as simple functions using the @Resolver decorator:

    from tartiflette import Resolver
    async def resolve_ip_address(parent, args, ctx, info):
        return ip_address("")
    async def resolve_port(parent, args, ctx, info):
        return 8080
    async def resolve_guid(parent, args, ctx, info):
        return args["input"]

    Your program will be ready to accept requests. Tartiflette’s type system will automatically validate the data you resolve in queries and mutations:

    >>> await engine.execute("query ip { ipAddress port }")
    {'data': {'ipAddress': '', 'port': 8080}}
    >>> await engine.execute("mutation GUID { checkGUID(input:\"1df282eb-a458-4763-a3ca-619c320c5a3e\") }")
    {'data': {'checkGUID': '1df282eb-a458-4763-a3ca-619c320c5a3e'}}

    If you want to use tartiflette with an HTTP server, the plugin tartiflette-aiohttp is there to help you do this. You can install it by running :

    pip install tartiflette-aiohttp

    And start your engine with aiohttp using register_graphql_handlers:

    from aiohttp import web
    from tartiflette_aiohttp import register_graphql_handlers

    The API will be exposed by default on http://localhost:8080/graphql. You can try it with a simple query and HTTPie:

    ➜ http --json POST http://localhost:8080/graphql \
    > query="query ip { ipAddress port }"
    HTTP/1.1 200 OK
    Content-Length: 50
    Content-Type: application/json; charset=utf-8
    Date: Thu, 31 Oct 2019 18:24:02 GMT
    Server: Python/3.7 aiohttp/3.6.2
        "data": {
            "ipAddress": "",
            "port": 8080

    As you can see, Tartiflette makes getting started with GraphQL in Python a simple and straightforward process. The full code for this article’s example is available on GitHub as well as Tartiflette source code.

  • Posted on

    Low Tech Crypto : One-Time Pad

    Have you ever wondered how you would secure your communication if an electromagnetic pulse destroyed all the computers around you? Do you distrust hardware manufacturers so much that you refuse to rely on anything you didn’t carve out of wood?

    If you answered yes to any of these questions, this series of articles is for you, as it will explore the world of “low tech” cryptography. By this, I mean cryptographic tools that can be used without a computer while still preserving high-security standards.

    As an introduction, I will talk about one of the most famous encryption technique (and the only one that’s theoretically uncrackable): One-Time Pads.

    A typewriter
    Illustraton by James Pond

    A bit of history

    The One-Time Pad is one of the oldest ciphers to be still considered secure in 2019, even though it was invented in 1882, by Frank Miller. At the time, it served to secure telegraphic communications between American banks.

    It only gained popularity amongst the worldwide military and diplomatic corps after being re-invented by Gilbert S. Vernam in 1917. In 1945, Claude Shannon from Bell Labs proved that one-time pads were secure, even against an adversary with unlimited computing power.

    Coins, cards and dices

    The one-time pad has a simple requirement to work securely: a truly random key as long as the text you want to encrypt. True randomness is something that’s not doable for computers, as they are deterministic systems that can hardly generate anything unplanned by their programs. That’s why computer random number generators are usually considered pseudo-random.

    The good thing is that even if randomness is hard for computers, it doesn’t have to be hard for us. There’s plenty of good sources of randomness around that can be used to generate a key. The only thing you have to keep in mind is to pick one that’s in the same base as the kind of text you want to encrypt:

    • If you have binary-encoded data (or morse code) coin flips make for a perfect base 2 random number generator
    • If you want to encrypt letters from the Latin alphabet (base 26), half a 52 cards deck can work
    • If your plaintext is made of letters and numbers from the Latin alphabet (36 characters in total), you can throw 6 times a 6 sided dice
    Illustraton by Ian Gonzalez

    OTP in practice

    Once you have generated a key as long as the text you want to encrypt, you can generate a ciphertext by adding the key to the plaintext, modulo the basis.

    Let’s take the string “HELLOWORLD” as an example. If you convert it to number of base 26 (0 for A, 25 for Z), it becomes [7, 4, 11, 11, 14, 22, 14, 17, 11, 3] Now using half a pack or card, or two dice of ten and a dice of 6, we pick the following random numbers [0, 23, 25, 14, 6, 15, 22, 6, 9, 23]. The last step is to add the plaintext to the key, modulo 26. In python it would match the following code:

    >>> plaintext = [7, 4, 11, 11, 14, 22, 14, 17, 11, 3]
    >>> key = [0, 23, 25, 14, 6, 15, 22, 6, 9, 23]
    >>> [(p + k) % 26 for p, k in zip(plaintext, key)]
    [7, 1, 10, 25, 20, 11, 10, 23, 20, 0]

    If anyone tried to directly decode the given ciphertext obtained above, they would read “HBKZULKXUA”. If they have the key, they can do the opposite of the previous operation which is simply subtracting the ciphertext with the key, modulo 26.

    >>> ciphertext = [7, 1, 10, 25, 20, 11, 10, 23, 20, 0]
    >>> key = [0, 23, 25, 14, 6, 15, 22, 6, 9, 23]
    >>> [(c - k) % 26 for c, k in zip(ciphertext, key)]
    [7, 4, 11, 11, 14, 22, 14, 17, 11, 3]


    Sadly, this algorithm has a big issue: since the key is as long as the plaintext, it creates a key distribution problem. You will need a secure channel over which you can send a key as long as the plaintext efficiently, which is usually exactly the kind of thing you lack if you need to use secure encryption.

    The key also needs to be regenerated for every single message (or it stops being random and the cipher stops being secure). This can be a very tedious and long process, which makes one-time pad unsuitable for any lengthy message.

    As I will show in my next articles, multiple cryptographers worked on solving those problems by creating more sophisticated ciphers that rely on fixed lengths key.

subscribe via RSS