Data & Security/Donnée & Sécurité #1: Symmetric Ciphers / Chiffrement symétrique

Today, we live in a world of data. It is great, because it helps Google perform amazing searches and retrieve exactly the info you want; because it allows Facebook and Instagram to show you news that are relevant for you; because it makes it easy to connect to hundreds of applications and enjoy thousands of new technologies. But, at the same time, some scammers are currently take advantage of the Covid pandemic to trick people into giving out info and money with phishing, possible medical data leaks from the French to the American government have been pointed out and there are more and more scandals about hackers attacking hospitals or banks mixing up their clients data and having them stolen.

To me, this is proof that the question of security is paramount and should be addressed in order to help us understand what data is, where it comes from and where it goes to, who has eyes on it, to whom it is obfuscated and for who it is a merchandise worth billions.

In this new series “Data & Security”, I’ll paint a (personal) picture of how I believe we experience the omnipresence of data nowadays, how we consume or produce it and how it is profoundly more complex than we would think at first glance.

First things first: data encryption and ciphers

People have long wanted to convey secret messages and to share crucial information while making sure the enemy could not understand it. Be it during battles, conspiracies or discreet love affairs, they’ve had to find ever new ways of encrypting or hiding messages.

When you use a cipher, you want to encode information into an unreadable set of data, so that it can be transmitted more easily – and while making sure that it’s no big deal if it is leaked to the public. This process of transforming the initial “clear and readable” data (the plain text) into a secret message that only a chosen few can decode and read is called encryption (it produces the cipher text). The reverse operation is called decryption. So, basically, if your text is properly encrypted, you don’t run any risk by giving it to your worst enemy: any third-party can look at it, read through it, try and understand it, but they won’t have enough meta information with just the encoded content to retrieve the original data.

Of course, this depends on how secure the cipher you choose is. Over the centuries, tons of techniques have been invented – some are very safe, others not so much… At the same time, new attacks have been designed to try and crack the new codes, making for a sort of endless battle between “encoders” and “attackers”.

There are many ways to classify ciphers but a common one is to distinguish between “symmetric” and “asymmetric” ones. Today, we’ll focus on symmetric ciphers that are simpler and have a longer history.

Symmetric ciphers: one key to rule them all

A symmetric cipher is an encoding technique that relies on the same key (or “parameters”, more generally speaking) both to cipher and decipher content. Suppose your encoding scheme is super-simple: you just shift all letters by one in the alphabet (so “A” becomes “B”, “B” becomes “C” and so on). Then this “shift” of 1 is your one-and-only parameter and your cipher is symmetric, because just by knowing the amount of the shift, you can easily decipher the encrypted content and retrieve back the initial plain text.

Symmetric ciphers are fairly straight-forward to use since you don’t need a lot of metadata to cipher or decipher messages, but they are often pretty weak too: any one who is able to access your algorithm parameters can do two really harmful things:

  • first, they can decode all the secret messages you send
  • second, they can also impersonate you to write messages in your name!

Note: I will talk more about the second problem relating to online identity in an upcoming article in this series.

Despite these (rather big) issues, symmetric ciphers have been in use for a very long time, and they are still interesting to study because they are simpler than the asymmetric ones and they can, under some specific conditions, actually be absolutely ok to use!

Basic techniques

One-time pad

As I’ve said before, the main problem with symmetric ciphers is that they use the same password (or other parameters) for the encoding and decoding operations. This sadly means that if the aforementioned third-party catches on what password you used to encode the message, they can easily decode it back.

Something you can do to improve upon this slightly is to, at least, change the password you use each time. But this is pretty hard in practice since you need to be in sync with the people who will receive the message so that they have the same password as the one you used for encoding and can actually decipher the encoded content.

This is the main idea behind the “one-time pad” technique. It was invented during World War I by Vernam and Mauborgne and was later the main encrypting technique for the military all over the world throughout the 1930s. It uses a unique random key with the same length as the text to encode: the idea is to “combine” the plain text with the key (usually with a XOR operation) to get quite a powerful and safe encoding process.

While this has been proven to be mathematically unbreakable by the famous mathematician Claude Shannon (well, some disagree), it’s complex to use in real-life: you need to get truly random keys each time that are as long as the text itself, you need to keep them completely secret but to transfer them to the end-users… If any of these conditions are not verified, then the theoretical safety of the cipher is not insured anymore. For example, during the Second World War, the Soviet Union army made a mistake while using the one-time pad and duplicated the same keys multiple times. The messages were thus deciphered partially or entirely by the US cryptanalysts as part of the Venona project.

Shift ciphers

Named after the well-known Julius Caesar who used this shift encoding method in his private correspondence, the Caesar cipher (or shift cipher) is a basic symmetric encoding method where you apply a given shift on each letter of your message. Then, decoding is performed by applying a reverse shift of the same amount. The example I gave above is a Caesar cipher with a shift of 1.

Note: of course when you reach the end of the alphabet, you cycle the back to the begin; so with a shift of 1, “Z” becomes “A”!

ROT13 is another example of shift cipher (with a shift of 13, you guessed it!) that is often in online forums to hide spoilers, solutions, offensive messages, etc. A fun fact about this algorithm is that, because there are 26 letters in the latin alphabet, you can apply the exact same process to encode and decode: shifting each letter by 13 encodes, and re-shifting by 13 decodes 🙂

Even though it is really handy to encode a message with this technique and you don’t have too complex a set of parameters to convey to the recipient, this type of ciphers is never used because it is way too easy to crack: it is a great example of weak encryption. In particular, frequency analysis allows you to quickly find the shift that was used if the message is long enough. This attack relies on the fact that in any natural language (e.g. English, French, German, Spanish…), some letters appear more frequently than others. If you know what language the message was originally written in, you can refer to a letters frequency table and compare it with the letters frequency in the encoded content: since only a shift was applied, the letter that appears most frequently after encoding is probably among the ones that appear most frequently in the plain text alphabet.

If the message is short, it is quite fast to brute-force it, meaning that you simply try out all possible shifts in the alphabet (in the latin alphabet, there are 26 possibilities) one after the other and see if one gives off a credible decoded message.

If you want to get a feel for this simple encryption algorithm, here is a small HTML/JS game I made: try and guess the message that was encoded using a shift cipher!

(The message is in English, it only contains lowercase and spaces are kept as is in the encoded message – each reboot takes a random shift amount and encodes a message picked at random from a small list)

[advanced_iframe use_shortcode_attributes_only=”true” src=”https://minapecheux.com/wp/wp-content/custom-code/ciphers/shift/index.html” width=”600″ height=”380″]

Permutation ciphers

A permutation cipher can refer to two things.

If you think of a permutation cipher as a cipher using a permuted alphabet, then it is similar to a shift cipher (in the sense that you also use a “ciphertext alphabet” to simply translate each letter). The difference is that the newly created alphabet is not obtained by a translation process but rather by replacing each letter by another according to some specific pattern. You can a random permutation, switch each letter with the next one in the alphabet, use homophones… Knights Templar and freemasons have also used the pigpen cipher, a geometric substitution cipher that produces really nice-looking encrypted messages:

Example of Pigpen cipher with the plain text “X marks the spot” (By Matt Crypto, from: https://en.wikipedia.org/wiki/Pigpen_cipher)

However, the permutation cipher can also be a bit more complex and instead use a keyword to “group” letters in blocks. Here, you first choose a keyword of length L and split your initial plain text into blocks of L characters. You then place these blocks of length L in columns in order of appearance, number each column by the position of the matching keyword character in the alphabet and reorder the columns to have these numbers in ascending order. Finally, you rewrite each shuffled block one after the other to get your encrypted message.

Small diagram to represent the process of encryption with the permutation cipher on the plain text “hello world”, with the key “yes” (of length L = 3).

Deciphering a text is just as straight-forward: you create a grid of blocks of length L where the columns have the “sorted” keyword as headers; then, you reorder the keyword and you can read the plain text blocks on each row.

This type of cipher has the same weakness as the shift cipher: short messages can be brute-forced and longer ones can be decrypted pretty easily thanks to frequency analysis.

Note: to a certain extent, it might even be quicker to decode when used on relatively small data because the human eye is quite good at solving anagrams: in the example above, if given the cipher text “ELHO LORWD L” and the information that the plain text was in English, you could find out pretty quickly that the initial data was “HELLO WORLD”.

Polyalphabetic substitution ciphers

In 1585, the French diplomat Blaise de Vigenère invented one of the most famous polyalphabetic ciphers: the Vigenère cipher. It was unbroken until the 1860s and was nicknamed “le chiffre indéchiffrable” (which is French for “indecipherable cipher”). Vigenère’s idea was to use a key to “shift the shift” along the message: rather than keeping the same translation throughout the encryption, you refer to the position of the current character in your key in the alphabet to know what the shift is. The big advantage of this technique is that, contrary to the methods mentioned before, the same letter is not always encoded to the same cipher character.

Suppose your initial message is “hello world” and your key is “yes”, just like in the example of the previous section. After repeating the key as many times as needed to span over the entire plain text (similarly to step (2) in the diagram) and numbering each key character by its position in the alphabet (Y = 25, E = 5, S = 19), you know the shift to apply to each letter. For example, “H” will be shifted by 25 positions to give “G” and “E” by 5 positions to give “J”. The interesting thing happens for the two consecutive “L”s: while the first one gets a 19 shift and becomes an “E”, the second one gets a 25 shift and becomes a “K”. For the attacker, it is therefore impossible to use the frequencies as a mean of attack: the frequency of “L”s will be “spread” across “E”s and “K”s!

Vigenère’s cipher is usually done with a grid where you write the plain alphabet on the first row and then all the possible alphabets on the following rows, increasing the shift by 1 each time. The first row corresponds to a 0-shift (no encryption) and to an “A” character in your key; the second one to a 1-shift (all letters are transformed into the next one) and to a “B” character in the key…

Example of a Vigenère-cipher grid: each row contains the entire alphabet with increasing shifts (and cycling back at the end) – by checking the current character in your key, you know which row to read through to encrypt.

Note: you might think that you should avoid any “A” in your key, because it leads to a 0 shift. But the beauty of this technique is that because the rest of the key will perform shift-varying encryption, an attacker cannot distinguish between a 0-shift encryption on a given letter and a 1-shift on the previous one!

Note 2: even though a grid is handy to use, cryptographers have invented amazing objects to help with on-the-road activities, for example cipher disks.

Despite making frequency analysis much harder, the Vigenère cipher is not flawless (else it wouldn’t have been broken!). In particular, because the key is repeated again and again, an attacker can eventually guess the length of the key and then treat the algorithm as a multi-layer Caesar cipher. However Vigenère’s cipher is still pretty secure if the alphabet is big enough, if the key is truly random and if it is long enough (with respect to the length of the plain text). Because these rules are rarely met in practice, Kasinski found a process in 1863 (and Charles Babbage probably did too before that) to guess the length of the key.

Other ciphers

To take advantage of mathematical complexity, some ciphers do not rely on a 1-by-1 letter permutation but instead on permutations of groups of letters. These “polygraphic substitutions” mix up n-grams of 2, 3 or more letters to make it harder to identify the initial combinations. Even if it doesn’t prevent the use of frequency analysis completely (some bigrams are still more frequent than others, for example in French you never see “WW” but you see “OU” a lot), it slows it down a lot because it “flattens” the frequencies.

During the Renaissance, plenty of conspirators used the “nomenclator” as a mean of hiding the names of the people involved: they would simply have a huge table matching some plain letters to some cipher symbols and replace some words in the message by their symbol equivalent. This encryption is fairly easy to break but the diplomats and spies kept on using nomenclators from the 15th to the 18th century, just making the conversion table bigger and bigger throughout the years. In the end, some tables had over 50,000 symbols!

Among those nomenclators was the Rossignols’ Great Cipher (supposedly unbreakable) that used homophonic and polygraphic substitutions to replace syllables, letters or words by numbers. The same plain text could have multiple “translations” like the vowel e, quite common in French, that had more than 100 corresponding cipher symbols.

A Great Cipher encryption nomenclator (1860 – Scanned from the journal Cryptologia, January 2005, volume XXIX, number 1, p. 47, from: https://en.wikipedia.org/wiki/Great_Cipher)

Enigma and the importance of cryptanalysts during wars

During the last century, we had already entered an era of communications and armies knew that whatever they aired on their radio would be listened to by the enemy. Encrypting messages had become necessary and most of the ciphers at the time lacked the required security.

Enters the Enigma machine. It was originally invented by Scherbius and Ritter in 1918 “for fun” but it quickly became a commercial hit and, soon, numerous banks and big companies were equipped with this new technological marvel.

When World War II began, encoding messages became of particular concern to the German submarines spread in the oceans that needed to talk to the on-land headquarters. They invested massively in Enigma machines and started to use it to encrypt all their messages. Being absolutely sure that these ciphers were unbreakable, they did not take any additional precautions and simply sent the cipher texts through radio.

In truth, Enigma is nothing but a polyalphabetic permutation cipher like Vigenere’s. The reason Enigma’s ciphers were so difficult to decode was that this machine used mathematical complexity at its fullest: by providing an insanely high amount of possible configurations, it was impossible for a human to find the correct cipher alphabet in a reasonable time. The machine had 5 rotors and a whole panel of wires that each participated in the creation of a unique permutation for the alphabet. Given the various configurations you could set the machine in, you could have more than 1020 different keys!

Enigma’s machine is a real technical feat that makes the most out of mechanics and mathematics to create a humanly unbreakable cipher method! (Image taken from: https://historictales.wordpress.com/)

On the Allies side, panic quickly set in and the English army decided to create a team of specialists fully devoted to working on Enigma’s message at Bletchtley Park. Mathematicians, linguists and other logicians gathered to perform cryptanalysis on the German messages and hopefully break the code. Among them was Alan Turing, the father of modern computer science and the inventor of our current computers. In a recent article, I talked about his work in biochemistry but he is better known for breaking the Enigma machine cipher. This specific episode of his life is depicted in the 2014 movie with Benedict Cumberbatch, The Imitation Game.

Turing’s breakthrough was to delegate this cumbersome search phase to a mechanical invention: the “Bombe”, an amazing precursor of a computer based on a previous Polish creation of Marian Rejewski (that had already deciphered the early versions of Enigma in the 1930s). This fantastic machine was an ensemble of thousands or rotors that could test out hundreds of configurations in a minute. When the Bombe was finished and worked properly, it would crack the daily German message in about twenty minutes.

In spite of some stepbacks due to further improvements on the Enigma machine in 1942, it is largely recognized that Bletchley Park’s contribution shortened the war by several years and saved many lives. It is a historical proof that as the importance of data and communications grows, the might of the ones that hold it and understand it grows as well…

Modern symmetric cryptography

Although symmetric cryptography as presented so far in this article is too weak to be used as is in modern security, some current algorithms still rely on some sort of substitution or permutation.

For example, the AES (for Advanced Encryption Standard) is a block cipher that implements a sort of substitution cipher on a very large binary alphabet. It was invented at the end of the 1970s because the previous gold standard for the American government, the DES (Data Encryption Standard) had become too unsecure. The AES was chosen among various proposals during a call for applications and the version we know refer to is the one of two Belgian scientists, Rijmen and Daemen.

AES has been approved by the National Security Agency (NSA) as a safe algorithm and is now the new encryption standard for the US government.

Today, there is still no proof, even theoretical, of an efficient attack against the AES (despite a lot of attempts…) when the encryption is done with a key that is long enough.

Until next time…

There is a lot to say about data security. At our age of ever-increasing data flows, it is crucial that we understand how data is used and how safe it is to share our personal information (be it on the Internet, in mobile apps…). We need to remember that despite tremendous discoveries in the art of cryptography, attackers have sharpened their blade too and a top-notch security system can become out-of-date pretty quickly. The point is not to be paranoid but instead to stay sharp and regularly ask ourselves: should I make this data publicly available? if I give this piece of information, will it become public? to which extent can I trust this specific authority to protect my data?

I think the issue of security is too broad and too important to be glossed over in a few lines, so I plan on writing several articles on this topic in the months to come. Just like the AfI/IAf series, it will be a long-term “background series”. Next time, I’ll talk about key exchange and asymmetric cryptography. The following articles will revolve around things like data dissimulation, quantum cryptography or online identity and fingerprint…

Nous vivons aujourd’hui dans un monde de la donnée. C’est formidable parce que ça permet à Google de faire d’incroyables recherches et de retrouver exactement l’information que nous voulons ; parce que ça laisse Facebook et Instagram nous présenter des nouvelles pertinentes ; parce que ça facilite la connexion à des centaines d’applications et l’utilisation de milliers de nouvelles technologies. Mais, en même temps, certains arnaqueurs profitent de la pandémie du coronavirus pour tromper des gens et les pousser à donner des informations ou de l’argent à travers du phishing, on a découvert un possible transfert de données médicales du gouvernement français vers le gouvernement américain et il y a de plus en plus de scandales à propos de hackers qui attaquent des hôpitaux, ou de banques qui mélangent les données de leurs clients ou les laissent fuiter.

Pour moi, ceci prouve que la question de la sécurité est essentielle et qu’elle doit être discutée pour nous aider à comprendre ce qu’est la donnée, d’où elle vient et où elle va, qui a droit de regard sur elle, à qui elle est dissimulée et pour qui c’est une marchandise qui vaut des milliards.

Dans cette nouvelle série “Donnée & Sécurité”, je vais peindre un tableau (personnel)  de la façon dont, je pense, nous vivons l’omniprésence des données, comment nous en consommons et nous en produisons, et en quoi c’est un sujet bien plus complexe qu’au premier abord.

Pour commencer : cryptage des données et chiffrement

On souhaite depuis longtemps transmettre des messages secrets et partager des informations cruciales tout en s’assurant que l’ennemi ne peut pas les comprendre. Que ce soit au cours de batailles, de conspirations ou de liaisons discrètes, il a fallu trouver des moyens de crypter ou cacher les messages.

Quand on utilise un chiffre, on veut encoder l’information en un ensemble de données incompréhensibles pour pouvoir la transmettre plus facilement – et en étant sûr que ce n’est pas grave si elle fuite dans l’espace public. Ce processus qui transforme les données initiales “claires et lisibles” (le texte en clair) en un message secret que seuls certains initiés peuvent décoder et lire est appelé chiffrage ou cryptage (il produit un texte chiffré). L’opération inverse est appelée déchiffrage ou décryptage. Donc, en fait, si le texte est correctement chiffré, on ne court aucun risque à le donner à son pire ennemi : n’importe qui peut y avoir accès, le lire et essayer de le comprendre, mais il n’aura pas suffisamment de méta-information avec le contenu chiffré seul pour récupérer les données originelles.

Bien sûr, cela dépend du niveau de sécurité du chiffre choisi. Au cours des siècles, beaucoup de techniques ont été inventées – certaines sont très sûres, d’autres moins… En même temps, de nouvelles attaques ont été conçues pour tâcher de craquer ces nouveaux codes, mettant ainsi en place une sorte de guerre infinie entre les cryptographes et les attaquants.

On peut classer les chiffres de nombreuses façons mais on distingue souvent entre le chiffrement “symétrique” et le chiffrement “asymétrique”. Aujourd’hui, nous allons nous concentrons sur les chiffres symétriques qui sont plus simples et ont une histoire plus longue.

Le chiffrement symétrique : une clé pour les gouverner tous

Un chiffre symétrique est une technique de cryptage qui se repose sur la même clé (ou les mêmes “paramètres”, plus généralement) à la fois pour le chiffrage et le déchiffrage du contenu. Supposons que notre méthode d’encodage est très simple : on décale simplement toutes les lettres d’une position dans l’alphabet (donc “A” devient “B”, “B” devient “C” et ainsi de suite). Alors ce “décalage” de 1 est notre seul et unique paramètre et ce chiffre est symétrique car en ne connaissant que la valeur du décalage, on peut facilement déchiffrer le contenu chiffré et récupérer le texte en clair initial.

Les chiffres symétriques sont assez évidents à utiliser car ils ne nécessitent pas beaucoup de méta-information pour le chiffrement et le déchiffrement de messages, mais ils sont souvent assez faibles également : toute personne qui arrive à accéder aux paramètres de l’algorithme peut faire deux choses nuisibles :

  • d’abord, elle peut décoder tous les messages secrets que vous envoyez
  • ensuite, elle peut se faire passer pour vous et écrire des messages en votre nom !

Note : je parlerai plus en détail du second problème lié à l’identité numérique dans un article à venir dans cette série.

Malgré ces problèmes (assez conséquents), les chiffres symétriques sont utilisés depuis très longtemps et ils sont intéressants à étudier car ils sont plus simples que les chiffres asymétriques et qu’ils peuvent être, sous certaines conditions spécifiques, tout à fait valables !

Techniques basiques

Le “masque jetable”

Comme je l’ai évoqué plus haut, le principal problème avec le chiffrement symétrique est que l’on utilise le même mot de passe (ou d’autres paramètres) pour les opérations de chiffrement et de déchiffrement. Cela veut malheureusement dire qu’une personne tierce qui trouve votre mot de passe pourra facilement décoder les messages.

Pour améliorer un peu la sécurité, on peut au moins changer de mot de passe à chaque fois. En pratique, c’est relativement compliqué à faire car il faut synchroniser l’émetteur et le récepteur pour qu’ils utilisent le même mot de passe sur le même message et que ce dernier puisse effectivement décoder le message chiffré.

C’est l’idée principale derrière la technique du “masque jetable”. Elle a été inventée pendant la Première guerre mondiale par Vernam et Mauborgne et a été par la suite la technique de chiffrement la plus utilisée par l’armée à travers le monde pendant les années 1930. Elle utilise une clé aléatoire unique de la même longueur que le texte à chiffrer : le principe est de “combiner” le texte en clair avec la clé (généralement avec une opération de ou exclusif) pour avoir un processus de chiffrement assez puissant et sécurisé.

Même si le fameux mathématicien Claude Shannon a démontré que cette technique est mathématiquement incassable (bon, certains ne sont pas d’accord), le masque jetable est difficile à utiliser dans la vraie vie : il faut générer des clés réellement aléatoires à chaque fois qui soient aussi longues que le message puis parvenir à les transférer en garantissant le secret absolu… Si une de seule de ces conditions n’est pas vérifiée, la sécurité théorique du chiffre n’est plus assurée. Par exemple, pendant la Seconde guerre mondiale, l’armée d’Union Soviétique a fait une erreur en utilisant le masque jetable et a dupliqué les mêmes clés plusieurs fois. Ces messages ont ainsi pu être déchiffrés partiellement ou même complètement par les cryptanalystes américains pendant le projet Venona.

Chiffrement par décalage

Le chiffre de César a été nommé en référence au bien connu Jules César qui utilisait cette méthode dans sa correspondance privée. Avec cette méthode de cryptage symétrique, on applique un décalage donné à chacune des lettres du message. Le déchiffrage est ensuite effectué en appliquant un décalage inverse. L’example que je donnais avant était un chiffre de César avec un décalage de 1.

Note : bien sûr, quand on arrive à la fin de l’alphabet, on reboucle au début ; donc avec un décalage de 1, “Z” devient “A” !

ROT13 est un autre exemple de chiffrement par décalage (avec un décalage de 13, vous l’aurez deviné !) qui est souvent utilisé dans les forums en ligne pour cacher des spoilers, des solutions, des messages offensants, etc. Ce qui est amusant avec ce chiffre est qu’étant donné qu’il y a 26 lettres dans l’alphabet, on peut appliquer exactement le même procéder pour chiffrer et déchiffrer : décaler les lettres de 13 positions encode, et décaler à nouveau de 13 positions décode 🙂

Même si cette technique est très pratique pour chiffrer des messages et qu’elle ne nécessite pas d’envoyer un ensemble de paramètres trop complexe à l’interlocuteur, elle n’est jamais utilisée en réalité car elle beaucoup trop simple à casser : c’est un très bon exemple de chiffrement peu fiable. En particulier, une analyse de fréquence permet de trouver assez rapidement le décalage choisi si le message est assez long. Cette attaque se base sur le fait que tous les langages naturels (ex : l’anglais, le français, l’allemand, l’espagnol…) ont certaines lettres qui apparaissent plus que d’autres. Une fois que l’on sait dans quel langage le texte en clair a été écrit, on peut se référer à une table de fréquences et la comparer avec les fréquences des lettres dans le contenu chiffré : comme on a seulement appliqué un décalage, les lettres qui apparaissent le plus souvent après cryptage sont probablement parmi celles qui apparaissent le plus fréquemment dans l’alphabet du texte en clair.

Si le message est court, il est assez rapide de procéder à une attaque de “force brute”, en d’autres termes un essai systématique de tous les décalages possibles dans l’alphabet (il y en 26 dans l’alphabet latin) l’un après l’autre jusqu’à en trouver un qui donne un message déchiffré crédible.

Si vous voulez tester un peu cet algorithme de cryptage, voilà un petit jeu que j’ai fait en HTML/JS game I made : essayez de deviner le message qui a été codé avec un chiffre par décalage !

(Le message est en anglais, il ne contient que des minuscules et les espaces sont recopiés tel quel dans le texte chiffré – chaque reboot choisit au hasard un nouveau décalage et encode un message au hasard parmi une petite liste)

[advanced_iframe use_shortcode_attributes_only=”true” src=”https://minapecheux.com/wp/wp-content/custom-code/ciphers/shift/index.html” width=”600″ height=”380″]

Chiffrement par permutation

Un chiffre par permutation peut correspondre à deux choses.

Si on pense à un chiffre qui utilise un alphabet permuté, alors il est assez similaire à un chiffre par décalage (dans le sens où il se sert également d’un “alphabet chiffré” pour simplement traduire chaque lettre). La différence vient du fait que le nouvel alphabet n’est pas obtenu par une translation mais plutôt en remplaçant chaque lettre par une autre selon un schéma donné. On peut se servir d’une permutation aléatoire, échanger chaque lettre avec la suivante dans l’alphabet, utiliser des homophones… Les Templiers et les francs-maçons ont aussi utilisé le chiffre pigpen, un chiffre par substitution géométrique qui produit des messages chiffrés visuellement très intéressants :

Example de chiffre pigpen avec le texte en clair “X marks the spot” (“X marque l’endroit”) (Par Matt Crypto, de : https://en.wikipedia.org/wiki/Pigpen_cipher)

Néanmoins, le chiffre par permutation peut aussi être un peu plus compliqué et utiliser une clé pour “grouper” les lettres en blocs. Ici, on choisit d’abord une clé de longueur L et on découpe le texte en clair en blocs de L caractères. Ensuite, on place ces blocs de longueur L en colonnes dans l’ordre d’apparition, on numérote chaque colonne par la position du caractère de la clé correspondant dans l’alphabet et on réordonne les colonnes pour placer ces nombres dans l’ordre croissant. Enfin, on réécrit chacun des blocs mélangés l’un après l’autre pour obtenir le message chiffré.

Petit schéma représentant le processus de cryptage avec le chiffre par permutation sur le texte en clair “hello world”, avec la clé “yes” (de longueur L = 3).

Déchiffrer le texte est tout aussi facile : on crée une grille de blocs de longueur L où les colonnes sont “triées” ; puis on réordonne la clé et on peut lire le texte en clair ligne après ligne.

Ce type de chiffrement est aussi fragile que le chiffrement par décalage : les messages courts peuvent être décryptés par force brute et les messages plus longues peuvent être déchiffrés assez rapidement avec une analyse de fréquence.

Note : dans une certaine mesure, il peut même être plus simple de “craquer” ces codes quand il y a assez peu de données, car l’oeil humain est très bon pour résoudre des anagrammes : dans l’exemple ci-dessus, si le texte chiffré est  “ELHO LORWD L”  et que l’on sait que le texte en clair est en anglais, on peut retrouver rapidement que le message initial était “HELLO WORLD”.

Chiffrement par substitution polyalphabétique

En 1585, le diplomate français Blaise de Vigenère a inventé l’un des chiffres polyalphabétiques les plus connus : le chiffre de Vigenère. Il est resté inviolable jusque dans les année 1860 et a été surnommé “le chiffre indéchiffrable”. L’idée de Vigenère a été d’utiliser une clé pour “décaler le décalage” au cours du message : plutôt que de choisir toujours la même translation pendant tout le processus de chiffrement, on se sert de la position du caractère courant dans la clé dans l’alphabet pour savoir quel décalage prendre. L’avantage principal de cette technique est que, contrairement aux techniques mentionnées avant, la même lettre n’est pas toujours encodée avec le même caractère chiffré.

Imaginons que le messag initial soit “hello world” et que la clé soit “yes”, comme dans l’exemple de la section précédent. Après avoir répété la clé autant de fois que nécessaire pour l’étirer sur tout le texte en clair (comme dans l’étape (2) du diagramme) et avoir numéroté chaque lettre de la clé par sa position dans l’alphabet (Y = 25, E = 5, S = 19), on connaît le décalage à appliquer sur chaque lettre. Par exemple, “H” sera décalé de 25 positions pour donner “G” et “E” de 5 positions pour donner “J”. Là où c’est intéressant, c’est de voir ce qui arrive aux deux “L”s consécutifs : alors que le premier est décalé de 19 positions et devient un “E”, le second est décalé de 25 positions et devient un “K”. Pour l’attaquant, il est alors impossible d’utiliser les fréquences comme moyen de déchiffrement : les fréquences des “L”s sont “éparpillées” entre les “E”s et les “K”s !

Le chiffrement de Vigénère s’effectue généralement avec une grille dans laquelle on écrit l’alphabet en clair sur la première ligne, puis tous les alphabets possibles sur les lignes suivantes en augmentant le décalage de 1 à chaque fois. La première ligne correspond à un décalage de 0 (pas de chiffrement) et la lettre “A” dans la clé ; la seconde à un décalage de 1 (toutes les lettres deviennent la suivante dans l’alphabet) et à un “B” dans la clé…

Exemple de grille pour le chiffre de Vigenère : chaque ligne contient l’alphabet complet avec des décalages de plus en plus grands (et un bouclage à la fin de la ligne) – en regardant le caractère courant dans la clé, on sait quelle ligne lire pour chiffrer.

Note : on pourrait penser qu’il faudrait éviter d’avoir un “A” dans la clé, car cela correspond à un décalage de 0. Mais la beauté de cette technique est que, comme le reste de la clé crée un cryptage avec un décalage qui varie, un attaquant ne peut pas distinguer un décalage de 0 sur une lettre d’un décalage de 1 sur la lettre précédente !

Note 2 : même si cette grille est pratique à utiliser, les cryptographes ont inventé des objets incroyables pour les aider dans leurs activités pendant les voyages, comme par exemple les disques de chiffrement.

Même s’il rend l’analyse de fréquence beaucoup plus difficile, le chiffre de Vigenère n’est pas infaillible (sinon, il n’aura pas été cassé !). En particulier, puisque la clé est répétée de nombreuses fois, un attaquant peut parvenir à deviner la longueur de la clé et ensuite traiter l’algorithme comme un chiffre de César multi-couches. Cependant, le chiffre de Vigénère reste assez sécurisé si l’alphabet est assez gros, si la clé est vraiment aléatoire et si elle est assez longue (relativement à la longueur du texte en clair). Parce que ces règles sont rarement suivies en pratique, Kasinski a trouvé un processus en 1863 (et Charles Babbage également, probablement avant lui) pour deviner la longueur de la clé.

D’autres chiffres

Pour profiter de la complexité mathématique, certains chiffres n’utilisent pas une permutation de lettre à lettre mais à la place des permutations de groupes de lettres. Ces “substitutions polygraphiques” mélangent des n-grammes de 2, 3 voire plus de lettres pour rendre l’identification des combinaisons initiales plus difficile. Même si cela n’empêche pas totalement l’usage d’analyse des fréquences (certains bigrammes sont plus fréquents que d’autres, par exemple en français on ne voit jamais de “WW” mais on voit souvent de “OU”), cela ralentit singulièrement l’attaque car ce type de substitution “aplatit” les fréquences.

Pendant la Renaissance, beaucoup de conspirateurs utilisaient des chiffres “à répertoire” pour dissimuler le noms des personnes impliquées : ils se servaient tout simplement d’une immense table de correspondance entre certaines lettres en clair et des symboles chiffrés, et ils remplaçaient certains mots dans le message par leur équivalent en symboles. Ce code est relativement facile à casser mais les diplomates et les espions ont continué à l’utiliser entre le 15e et le 18e siècle en augmentant juste la taille des tables au cours des années. A la fin, certaines tables contenaient plus de 50 000 symboles !

Parmi ces chiffres à répertoire figurait le Grand Chiffre des Rossignols (supposément incassable) qui utilisait des substitutions homophoniques et polygraphiques pour remplacer des syllabes, des lettres ou des mots par des chiffres. Le même texte en clair pouvait avoir plusieurs “traductions” comme la voyelle e, très fréquente en français, qui correspondaient à plus de 100 symboles chiffrés.

Un exemple de répertoire pour le Grand Chiffre (1860 – Scan du journal Cryptologia, Janvier 2005, volume XXIX, numéro 1, p. 47, de : https://en.wikipedia.org/wiki/Great_Cipher)

Enigma et l’importance des cryptanalystes en temps de guerre

Au cours du siècle dernier, nous étions déjà entrés dans une nouvelle ère des communications et l’armée savait que ce qu’elle émettait sur les ondes radios serait écouté par l’ennemi. Chiffrer les messages devenait nécessaires et la plupart des méthodes de l’époque n’étaient pas assez sûres.

Arrive la machine Enigma. Initialement inventée par Scherbius et Ritter en 1918 “pour s’amuser”, elle est vite devenue un succès commercial et, très vite, de nombreuses banques et grandes entreprises s’étaient équipées de cette merveille technologique.

Quand la Seconde guerre mondiale a commencé, crypter les messages est devenu une priorité pour les sous-marins allemands répartis dans les océans qui devaient parler à leur état-major sur terre. Ils ont ainsi investi massivement dans des machines Enigma et ont commencé à s’en servir pour chiffrer tous leurs messages. Convaincus de son absolue inviolabilité, ils n’ont pris aucune précaution supplémentaire et ont simplement envoyé les messages chiffrés par radio.

En vérité, Enigma n’est rien d’autre qu’un chiffre de permutation polyalphabétique comme celui de Vigenère. La raison pour laquelle les messages chiffrés par Enigma étaient si difficiles à décoder est que la machine utilise la complexité mathématique à son plein potentiel : en permettant un nombre incroyablement élevé de configurations, la machine rendait le déchiffrement de messages par un humain impossible en un temps raisonnable. La machine avait 5 rotors et un panneau de câbles qui participaient tous à la création d’une permutation unique de l’alphabet. Au vu de toutes les configurations possibles, on pouvait obtenir plus de 1020 clés !

La machine Enigma est une vraie prouesse technologique qui tire avantage de la mécanique et des mathématiques pour créer une méthode de chiffrement impossible à casser pour un humain ! (Image issue de : https://historictales.wordpress.com/)

Du côté des Alliés, la panique s’installe et l’armée anglaise décide de créer une équipe d’experts entièrement dédié à l’étude des messages d’Enigma à Bletchley Park. Des mathématiciens, des linguistes et d’autres logiciens se rassemblent pour faire une cryptanalyse des messages allemands et, avec un peu chance, percer le code. Parmi eux, il y avait Alan Turing, le père de l’informatique moderne et l’inventeur de nos ordinateurs actuels. Dans un article récent, j’ai parlé de ses travaux en biochimie mais il est plus connu pour avoir cassé le chiffrement de la machine Enigma. Cet épisode spécifique de sa vie est relaté dans le film de 2014 avec Benedict Cumberbatch, The Imitation Game.

La révélation de Turing a été de déléguer la fastidieuse phase de recherche à une invention mécanique, la “Bombe”, un incroyable précurseur de nos ordinateurs basé sur une création polonaise plus ancienne de Marian Rejewski (qui avait déjà cassé des versions précédentes d’Enigma dans les années 1930). Cette fantastique machine était un ensemble de milliers de rotors qui pouvaient tester des centaines de configurations à la minute. Quand la Bombe a été terminée et qu’elle fonctionnait parfaitement, elle était capable de déchiffrer le message quotidien des allemands en une vingtaine de minutes.

Malgré quelques reculs dûs à des améliorations de la machine Enigma en 1942, il est communément admis que la contribution de Bletchley Park a raccourci la guerre de plusieurs années et sauvé de nombreuses vies. C’est une preuve historique du fait que lorsque le rôle des données et des communications grandit, le pouvoir de ceux qui les détiennent et les comprennent grandit tout autant…

Cryptographie symétrique moderne

Bien que la cryptographie symétrique présentée jusqu’à maintenant dans cet article soit trop faible pour être utilisée telle quelle dans les protocoles de sécurité modernes, certains algorithmes actuels utilisent quand même un type de substitution ou de permutation.

Par exemple, l’AES (pour Advanced Encryption Standard) est un chiffre par bloc qui implémente une sorte de chiffre par substitution utilisant un alphabet binaire avec beaucoup de caractères. Il a été inventé à la fin des années 1970 car le standard précédent du gouvernement américain, le DES (Data Encryption Standard), n’était plus assez fiable. L’AES a été choisis parmi un ensemble de propositions lors d’un appel à candidatures et la version que nous connaissons maintenant est celle de deux scientifiques belges, Rijmen et Daemen.

L’AES a été reconnu par la National Security Agency (NSA) comme un algorithme sûr et est aujourd’hui le nouveau standard de chiffrement pour le gouvernement américain.

Aujourd’hui, il n’y a toujours aucun preuve, même théorique, d’une attaque efficace contre l’AES (malgré de nombreux essais) quand le chiffrement avec une clé qui est assez longue.

D’ici la prochaine fois…

Il y a beaucoup de choses à dire à propos de la sécurité des données. A notre époque où il y a toujours plus de données, il est crucial de comprendre comment elles sont utilisées et quand il est sûr de partager nos informations personnelles (sur Internet, dans des apps mobiles…). Il faut se rappeler que malgré des découvertes phénoménales dans l’art de la cryptographie, les attaquants ont aussi aiguisé leurs lames et un système de sécurité à la pointe de la technologique peut devenir obsolète assez rapidement. Le but n’est pas de devenir paranoïaque mais plutôt de rester vigilant et de se demander régulièrement : est-ce une bonne idée de rendre ces données publiques ? si je donne ces informations, vont-elles devenir publiques ? dans quelle mesure puis-je faire confiance à cette autorité particulière pour protéger mes données ?

Je pense que la question de la sécurité est trop large et trop importante pour être évoquée en quelques lignes, c’est pourquoi je prévois d’écrire plusieurs articles sur ce sujet dans les mois à venir. Comme la série AfI/IAf, ce sera une série de fond au long cours. La prochaine fois, je parlerai d’échange de clés et de chiffrement asymétrique. Les articles suivants se concentreront sur la dissimulation de données, la cryptographie quantique ou l’identité numérique et l’empreinte digitale…

REFERENCES / SOURCES
  1. Simon Singh’s website: https://simonsingh.net/
  2. S. Singh, The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography (https://www.amazon.fr/Code-Book-Science-Secrecy-Cryptography/dp/0385495323), 1999. [Online; last access 18-May-2020].
  3. C. Shannon, “Communication Theory of Secrecy Systems” (http://netlab.cs.ucla.edu/wiki/files/shannon1949.pdf), 1949. [Online; last access 18-May-2020].
  4. T. Olzak, “Chapter 7: The Role of Cryptography in Information Security” (https://resources.infosecinstitute.com/role-of-cryptography/), June 2012. [Online; last access 18-May-2020].
  5. J. Deneut, “An (Important) Disproof Of The One-Time Pad” (https://techcrunch.com/2015/08/16/a-disproof-of-the-one-time-pad/), Aug. 2015. [Online; last access 18-May-2020].
  6. D. Rodriguez-Clark, “Permutation Cipher” (https://crypto.interactive-maths.com/permutation-cipher.html), 2017. [Online; last access 18-May-2020].
  7. A. Hern, “How did the Enigma machine work?” (https://www.theguardian.com/technology/2014/nov/14/how-did-enigma-machine-work-imitation-game), Nov. 2014. [Online; last access 18-May-2020].
  8. Bibmath, “Histoire de la machine Enigma” (http://www.bibmath.net/crypto/index.php?action=affiche&quoi=debvingt/enigmaguerre). [Online; last access 18-May-2020].
  9. F. Manens, “Phishing : des cybercriminels ont fait miroiter une fausse aide financière du gouvernement français” (https://cyberguerre.numerama.com/5065-phishing-des-cybercriminels-ont-fait-miroiter-une-fausse-aide-financiere-du-gouvernement-francais.html), May 2020. [Online; last access 18-May-2020].
  10. J. Hourdeaux, “La Cnil s’inquiète d’un possible transfert de nos données de santé aux Etats-Unis” (https://www.mediapart.fr/journal/france/080520/la-cnil-s-inquiete-d-un-possible-transfert-de-nos-donnees-de-sante-aux-etats-unis), May 2020. [Online; last access 18-May-2020].
  11. I. Wikimedia Foundation, “Venona project” (https://en.wikipedia.org/wiki/Venona_project), May 2020. [Online; last access 18-May-2020].
  12. I. Wikimedia Foundation, “Caesar cipher” (https://en.wikipedia.org/wiki/Caesar_cipher), May 2020. [Online; last access 18-May-2020].
  13. I. Wikimedia Foundation, “ROT13” (https://en.wikipedia.org/wiki/ROT13), Apr. 2020. [Online; last access 18-May-2020].
  14. I. Wikimedia Foundation, “Caesar cipher” (https://en.wikipedia.org/wiki/Caesar_cipher), May 2020. [Online; last access 18-May-2020].
  15. I. Wikimedia Foundation, “Great Cipher” (https://en.wikipedia.org/wiki/Great_Cipher), Feb. 2020. [Online; last access 18-May-2020].
  16. I. Wikimedia Foundation, “Enigma machine” (https://en.wikipedia.org/wiki/Enigma_machine), May 2020. [Online; last access 18-May-2020].
  17. I. Wikimedia Foundation, “Alan Turing” (https://en.wikipedia.org/wiki/Alan_Turing), May 2020. [Online; last access 18-May-2020].
  18. I. Wikimedia Foundation, “Advanced Encryption Standard” (https://en.wikipedia.org/wiki/Advanced_Encryption_Standard), May 2020. [Online; last access 18-May-2020].
  19. Collins Dictionary, “anagram” (https://www.collinsdictionary.com/dictionary/english/anagram). [Online; last access 18-May-2020].
  20. IMDB, “The Imitation Game” (https://www.imdb.com/title/tt2084970/), 2014. [Online; last access 18-May-2020].

Leave a Reply

Your email address will not be published. Required fields are marked *