Summary
Since its very beginnings, the logo of the La French Connection podcast has displayed an encrypted message. Many people have dreamed of unravelling the mystery of this cipher. Fair warning to those who don’t want to break the spell: read no further, because this text reveals the secrets and the message behind the logo. (1)
Analysis
Fans of the La French Connection podcast noticed long ago that the bottom of the podcast’s logo bears a mysterious inscription that, without a doubt, conceals a secret message (Figure 1).
The encrypted message
The mysterious cipher is made up of 25 hexadecimal numbers. It is often easier to convert hexadecimal numbers into decimal numbers. CyberChef handles this kind of chore very well (Table 1).
Figure 1: Logo of the La French Connection podcast.
Table 1: The mysterious cipher.
4E 39 44 60 35 63 3B 19 24 55 62 3A 2E 4F 56 42 4F 2D 21 3F 62 1C 26 3C 5F
78 57 68 96 53 99 59 25 36 85 98 58 46 79 86 66 79 45 33 63 98 28 38 60 95
Frequencies
Since we’re already putting CyberChef to good use, we might as well take advantage of it to run a frequency analysis. Figure 2 shows the result of this analysis. We can see that out of 25 numbers, only two are repeated (4F and 62). At the same time, the sequence is not random, since the values are not evenly distributed across the range of 256 possible numbers (from 00 to FF).
Figure 2: Frequency analysis of the numbers.
These results allow us to rule out modern encryption or a hash function, which would produce more uniform data. Moreover, we are not dealing with a simple substitution cipher either, since there are few repetitions. Because the encrypted message is very short, it is hard to carry out a more thorough statistical analysis or to use brute force without first identifying the encryption method.
Looking more closely at the decimal numbers, we notice that none of them ends in 1, 2 or 4. In addition, the units digits are not evenly distributed, as shown in Table 2. The distribution of the tens digit is a bit more uniform, but there is no digit smaller than 20 at all (Table 3).
Table 2: Distribution of the units digit.
Unité %
0 4
3 12
5 16
6 20
7 4
8 28
9 16
Table 3: Distribution of the tens digit.
Dizaine %
2 8
3 12
4 8
5 16
6 16
7 12
8 8
9 20
In search of the lost cipher
With the little information we have gathered, we can explore several leads to try to identify the cipher that was used. The numbers in the cipher were almost certainly generated using simple mathematical rules that give them the characteristics we observed. A good place to start looking for the cipher is dCode. This site is a valuable resource for learning more about codes and encryption. It offers not only very detailed descriptions of several dozen classical ciphers, but also tools to encode, decode and break some of them.
Polybius
We are probably dealing with a substitution or transposition cipher that includes additional elements to make decryption harder. The most fun way to identify the cipher used is to spend long hours exploring the various classical ciphers, reading their descriptions, and encrypting and decrypting different messages. It is also the most time-consuming method. If you use it, you will probably end up stumbling on the Polybius cipher, which uses the Polybius square, a 5x5 grid that maps each letter of the alphabet to a number between 11 and 55. Table 4 shows one possible square. Since the alphabet has 26 letters, one of them has to be sacrificed. In this case, Z is sacrificed, but J, V or W are also frequently dropped.
Table 4: Polybius square.
1 2 3 4 5
1 A B C D E
2 F G H I J
3 K L M N O
4 P Q R S T
5 U V W X Y
To encrypt a message using a Polybius square, you simply find the letter in the table and replace it with the number formed by the row number followed by the column number. For example, the letter Q would be replaced by the number 42.
Polybius on steroids
To make life harder for the curious, you can use a key to change the order of the letters in the grid. The word used must have distinct letters. You write the letters of this secret word at the top of the grid and continue with the remaining letters. For example, with the key HACK we would get the square shown in Table 5.
Table 5: Polybius square with the key HACK.
1 2 3 4 5
1 H A C K B
2 D E F G I
3 J L M N O
4 P Q R S T
5 U V W X Y
The Polybius cipher shows a regularity in the numbers it uses, which makes it easy to identify, since only the numbers 11, 12, 13, 14, 15, 21, 22, 23, 24, 25, 31, 32, 33, 34, 35, 41, 42, 43, 44, 45, 51, 52, 53, 54, 55 can be used.
Polybius or not Polybius? That is the question!
Although the Polybius cipher shares some similarities with the characteristics of our message, the possible numbers do not match. So we are dealing either with another cipher or with a variant of the Polybius cipher using a different grid.
Reading up a bit more on the Polybius cipher, we find that it is often associated with the Nihilist cipher, which is a superencryption of the Polybius square. The Nihilist cipher can be recognized by the following clues:
-
Contains only numbers between 22 and 110.
-
Contains none of the following numbers:
21, 31, 41, 51, 61, 71, 81, 91, 101. -
The cipher comes with some kind of reference to Russia.
Mini OSINT
The first two characteristics match the secret message at the bottom of the logo perfectly, but some mention of Russia in an episode would seal the deal. A bit of white-belt Google Fu (logo site:securite.fm) reveals that the encoded message in the logo is mentioned in episode 0x017 (around the 40-minute mark), as shown in Figure 3. In that episode, Damien, ever the foodie, gives us a hint: "Poutine"... Unless he is referring to another kind of "Putin", far less digestible.
Figure 3: Episode 0x017 mentions the logo mystery.
The Nihilist cipher
Made famous by its use by the Russian nihilists of the 19th century. This cipher is easy to memorize and allows a message to be transmitted in several ways. For example, Russian prisoners passed messages of this kind by knocking on the walls of their cells a number of times corresponding to the row and then the column of each letter.
How it works
The Nihilist cipher works simply:
-
You choose a Polybius square, with the letters possibly scrambled using a key agreed upon in advance. For example, the square in Table 5.
-
You encode the message with the grid. Each letter is assigned a number corresponding to a row and a column. The message "MESSAGESECRET" would, for example, become: 33 22 44 44 12 24 22 44 22 13 43 22 45.
-
You choose a superencryption key and encode it with the Polybius square. If you choose "PLANET" as the key, you get 41 32 12 34 22 45.
-
You write the encoded key out as many times as needed under the encoded message and add the two numbers together, as in Table 6.
Table 6: Superencryption.
M E S S A G E S E C R E T
---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----
33 22 44 44 12 24 22 44 22 13 43 22 45
41 32 12 34 22 45 41 32 12 34 22 45 41
74 54 56 78 34 69 63 76 34 47 65 67 86
What you end up with is a substitution cipher to which a key is repeatedly added. In the end, you get a fractionated polyalphabetic cipher, since two identical letters can be encoded differently depending on their position in the message.
Vulnerabilities
The Nihilist cipher has multiple vulnerabilities, including those below:
-
The superencryption key is repeated. When the encrypted message is longer than the key, similarities can be observed between blocks of text that are the same length as the key.
-
There is a limited number of combinations for the additions. For example, the number 80 can only be obtained with the additions $25+55$ or $35+45$.
-
The larger or smaller the numbers, the more limited the possibilities. For example, 22 or 110 can only be obtained if the encoded letter is the same as the superencryption key letter and that letter is in the top-left or bottom-right corner of the grid, respectively.
-
A number with a 0 in the units position indicates that the numbers added together come from the last column.
-
Similarly, a number with a 2 in the units position comes from an addition of numbers from the first column.
-
Once the key length is identified and the key space narrowed down, the key can be found (if it is a word) by deduction or with a dictionary.
-
Once the superencryption key is found, the problem boils down to a simple substitution cipher, a Polybius cipher.
Cryptanalysis of the Nihilist cipher becomes much easier if the encoded message is long and/or if we have another decoded message that was encrypted with the same grid and the same superencryption key. Unfortunately, in this case, we have neither of these helpful elements.
Decryption
There are very few repetitions in the encoded message, 78 57 68 96 53 99 59 25 36 85 98 58 46 79 86 66 79 45 33 63 98 28 38 60 95, which indicates that the superencryption key is probably not trivially short (1, 2 or 3 characters).
Key length
The first step is to determine the length of the superencryption key, which will give us the period of the cipher. A cipher will have a period of 4 if a 4-character key is repeated for the encryption, since every block of 4 letters will use the same key.
To determine the key length, we will build tables with a number of columns matching the key length we want to test. For example, if we want to check whether a 6-character key is possible, we need to build Table 7 with 6 columns and fill it with the encrypted message, in order.
Table 7: Table to test whether a 6-character key is possible.
78 57 68 96 53 99
59 25 36 85 98 58
46 79 86 66 79 45
33 63 98 28 38 60
95
We need to build a table like this for every superencryption key length we want to test. In our case, between 1 and 25 columns.
For each column of a table, we apply the algorithm below. First to the tens digit, then to the units digit. If, for a given column, this algorithm returns false for either the tens or the units digit, it means no addition is possible for the combinations of numbers in that column. The superencryption key therefore cannot have the assumed length.
Essentially, we check that the difference between the maximum and minimum digit is less than 5. If it isn’t, it is impossible for a single digit (between 1 and 5) to have superencoded the units or tens digit. For example, if the units digits for a column are 2, 4, 7, 3, 4, the difference between 7 and 2 is 5. And it is impossible to find two digits such that $x_1 + y = 7$ and $x_2 + y = 2$ where $1\leq x_i \leq 5$ and $1\leq y \leq 5$
array $A \gets$ chiffres des unités ou dizaines
for all 𝑛 ∈ {0, . . . , 𝑎𝑟𝑟𝑎𝑦𝑙𝑒𝑛𝑔𝑡ℎ − 1} do
if 𝐴[𝑖] == 0 then
$A[i] \gets 10$
end if
end for
return max(A) - min(A) \< 5
Going back to Table 7, we see that the tens digits for the first column are 7, 5, 4, 3, 9. There is a difference of 6 between the maximum and minimum digits, so no 6-character key could have been used.
If we apply this rule to tables of 2 to 25 rows (using a homemade Python script), we get possible key lengths of 10, 20, 22, 23, 24 or 25. Since the message is 25 characters long, keys between 20 and 25 characters are considered possible, because in those cases most columns will contain only one number. However, they are unlikely, since if the key length is close to the message length, we would almost have a Vernam cipher (one-time pad), which would be practically impossible to decode without knowing the key.
Under these circumstances, the key length is most likely 10.
Key space
Once the key length is established, we can try to narrow down the key space. Indeed, with the Nihilist cipher, not every 10-character key is possible, only a reduced number of them. To limit the number of possible keys, we need Table 8, with as many columns as the key length.
Table 8: 10-column table.
78 57 68 96 53 99 59 25 36 85
98 58 46 79 86 66 79 45 33 63
98 28 38 60 95
For each column of this table, we need to apply the following algorithm, which will produce the list of numbers possibly used to superencrypt a column. Once again, this is a direct consequence of using the Polybius square, which limits the units or tens digit to a number between 1 and 5.
array $col \gets$ une colonne du tableau
$dizaineMin \gets 1$
$dizaineMax \gets 5$
$uniteMin \gets 1$
$uniteMax \gets 5$
for all 𝑛 ∈ 𝑐𝑜𝑙 do
$unite \gets n \mod 10$
if $unite == 0$ then
$uniteMin \gets 5$
$uniteMax \gets 5$
else if $unite < 7$ then
$uniteMin \gets 1$
$uniteMax \gets unite - 1$
else
$uniteMin \gets unite - 5$
$uniteMax \gets 5$
end if
array $unitesPossibles \gets \{uniteMin, \dots, uniteMax\}$
$dizaine \gets floor(n/10) \mod 10$
if $dizaine == 0$ then
$dizaineMin \gets 5$
$dizaineMax \gets 5$
else if $dizaine < 7$ then
$dizaineMin \gets 1$
$dizaineMax \gets dizaine - 1$
else
$dizaineMin \gets dizaine - 5$
$dizaineMax \gets 5$
end if
array $dizainesPossibles \gets \{dizaineMin, \dots, dizaineMax\}$
end for
return $combinaisons(dizainesPossibles, unitesPossibles)$
If we apply this algorithm to each column of Table 8, we get the possibilities in Table 9 for each character of the superencryption key.
Table 9: Key space.
Position Possibilités
1 43, 44, 45, 53, 54, 55
2 13, 14, 15
3 13, 14, 15, 23, 24, 25
4 45
5 41, 42
6 44, 45, 54, 55
7 24, 25, 34, 35, 44, 45
8 11, 12, 13, 14
9 11, 12, 21, 22
10 31, 32, 41, 42, 51, 52
Even though all these calculations can be done by hand, a Python script can be a big help, both in terms of time and of mental health.
Numbers
For this cipher, we therefore have a 10-character key, with each character having 6, 3, 6, 1, 2, 4, 6, 4, 4 and 6 possibilities respectively. The number of possible combinations is $6 \times 3 \times 6 \times 1 \times 2 \times 4 \times 6 \times 4 \times 4 \times 6 = 497664$. Many of these combinations are not words. We could start by excluding them but, in the end, if the key is random, we have 497664 keys to test.
Furthermore, if we don’t want to have to manually validate every decryption attempt, we would need to automate the whole thing by comparing each 4-character block of a decoding attempt against French and English quadgrams (we assume the message is in one of those two languages), of which there are about 400000 each. Note that there are 22 possible 4-character blocks in a 25-character sequence.
Finally, nothing guarantees that a completely random Polybius square wasn’t used for the initial substitution. For 26 letters, there are $26! \approx 4 \times 10^{26}$ possible squares.
We would have approximately $497644 \times 400000 \times 400000 \times 22 \times 4 \times 10^{26} \approx 7 \times 10^{44}$ tests to run.
That’s a lot of paths to explore, so we need to narrow this search space even further by making several assumptions.
Assumptions
To start with, we will make the following assumptions:
-
The superencryption key is a word. Probably related to the podcast.
-
The Polybius square used is one of the few best-known squares (with the letters of the alphabet practically in order).
-
The language used for the key and the original message is either French or English.
-
The Nihilist algorithm used to encrypt the message was not modified to make decryption harder.
Finding the superencryption key
Armed with these assumptions, we can finally tackle the superencryption key. We assume that the most common Polybius square, which omits the letter "J", was used (Table 10). Encoding the message with this square would imply using the letters in Table 11 to encrypt the key.
Table 10: Polybius square presumably used.
1 2 3 4 5
1 A B C D E
2 F G H I K
3 L M N O P
4 Q R S T U
5 V W X Y Z
Table 11: Possible letters for the key.
1 2 3 4 5 6 7 8 9 10
S C C U Q T I A A L
T D D R U K B B M
U E E Y O C F Q
X H Z P D G R
Y I T V
Z K U W
The 10 most common letters in French words are e, a, i, s, n, r, t, o, l, u, while in English they are e, t, a, o, i, n, s, h, r, d. For now, let’s keep only the letters that are most common in both languages. Doing so, we realize almost immediately, if we have ever played Scrabble or done word searches, that we almost have the word SECURITÉ or SECURITY (Table 12). This is most certainly no coincidence.
Table 12: Filtered possible letters.
1 2 3 4 5 6 7 8 9 10
S C U T I A A L
T D D R U
U E E O
H D R
I T
U
A good way to check whether we’re on the right track is to use this partial superencryption key to decode the message. Using dCode greatly speeds up this kind of test, since it lets you quickly change either the Polybius square or the key. Since we are missing a few letters in the key to form a word, we will arbitrarily replace them with the first letter of each column. This gives us the key SECURTTAAL. Using it together with Table 10 to try to decrypt the message, we get PRZVAZEDKYZSNOTGPOGMZCKEX.
We notice a short English word and a few common English bigrams in the
partially decoded message:
PRZVAZEDKYZSNOTGPOGMZCKEX.
This is a big step, since we have identified the language of the original message. Moreover, there are more "Z"s than there should be in this message, which suggests there is a problem with the Polybius square used. Looking at the list of the 10 most common letters in English, we notice that "I", the fifth most used letter in that language, never appears, while "Z" appears four times. If we swap the positions of "I" and "Z" in the Polybius square and try decoding the message again, we get a partially decoded message with even more words and partial words PRIVAIEDKYISNOTGPOGMICKEX.
At this point, it is much easier to try a few other keys than to try to modify the Polybius square. Trying the keys SECURITEAL and SECURITYAL, we get:\
SECURITEAL: PRIVATE?KYISNOTAP?GMICKEX
SECURITYAL: PRIVATE?BIUYNNTQC?BHKVMVI?
The first key attempt, with the French word, is clearly better, even though two letters cannot be decoded with the Polybius square used. For the last two letters of the key, we can either use brute force and test every possible combination, or remember (thanks to our mini OSINT) that the podcast’s website is securite.fm.
With the superencryption key "SECURITEFM", we decode the message PRIVATE?EXISNOTAP?BLICKEX, which we can guess is "PRIVATEKEXISNOTAPUBLICKEY". However, the message cannot be fully decoded with this key. We can easily improve the situation by swapping the letters "X" and "Y" in the Polybius square to get Table 13.
Table 13: Final Polybius square.
1 2 3 4 5
1 A B C D E
2 F G H Z K
3 L M N O P
4 Q R S T U
5 V W Y X I
With this key and this Polybius square, two numbers in our initial sequence cannot be decoded 78 57 68 96 53 99 59 25 36 85 98 58 46 79 86 66 79 45 33 63 98 28 38 60 95. They correspond to the letters at positions 8 and 18 of the message. With the current superencryption key, the number 25 should be 10, since we should subtract 15 (because of the "E"), and the number 45 should be 30, for the same reason.
But 10 and 30 cannot be obtained with the key and Polybius square we found. However, the numbers 25 and 45 correspond to the missing letters "K" and "U". These two letters were simply not superencrypted with the key! This is either an unintentional mistake or an attempt to make decrypting the message harder. In the end, everyone will agree with the secret message: "private key is not a public key".
Official solution
After I validated the secret message with the official authorities of La French Connection, the higher-ups sent me the official solution, which I am passing on to you. One particular point in it may leave us puzzled:
- Text to encode: PRIVATEKEYISNOTAPUBLICKEY
- Key character set: ABCDEFGHIJKLMNOPQRSTUVVVXYZ (w = VV)
- Key: SECURITE.FM
- Encode the answer in hex
The whole thing was encoded using an unspecified tool, almost certainly using the Nihilist cipher. The tricky point in this solution is, of course, the period “.” between SECURITE and FM. It appears nowhere among the characters used in the cipher. And yet, the tool used did encrypt the message. This unconventional key probably explains why two letters were not encoded as expected.
This illustrates how hard it is to decrypt a message encoded with an unknown algorithm and unknown tools. You’re never safe from surprises.
References
-
https://alexbarter.com/cryptanalysis/breaking-nihilist-substitution-cipher/
-
http://www.benburlingham.com/core/articles/nihilist-cipher.html
(1) This work is subject to the WTFPL license. Visit http://www.wtfpl.net/ for a full copy of this license.
