Break a World War I ADFGVX Cipher - A Cipher Germans Believed was Unbreakable

#cryptology, #cryptography, #cryptanalysis
This short video shows how to create and break ADFGX and ADFGVX ciphers.
The ADFG(V)X cipher was invented in 1918 during WWI by German officer Fritz Nebel and also broken in 1918 by French officer Georges Painvin. These ciphers were one of the first fractionating ciphers based on substitution and transposition (see our other videos for introductions on substitution and transposition ciphers).
If you are further interested in the algorithmic background of breaking the ADFGVX and in its historic background, we recommend to read our paper about breaking ADFGVX messages from the Easter Front of Warld War I (see [1]).
You may download the latest version of CrypTool 2 from here: www.cryptool.o...
[1] Lasry, G., Niebel, I., Kopal, N., & Wacker, A. (2017). Deciphering ADFGVX messages from the Eastern Front of World War I. Cryptologia, 41(2), 101-136.

[@OliverdeClisson]

This French Guy Georges Painvin was a war hero. The Code Breaking of the German Codes, prevented the german offensive 1918 from breaking through into Paris.

[@CryptographyForEverybody]

Hello Heinrich IV, You probably refer to the decryption of "Le radiogramme de la victoire". It led to the counter-offensive from General Mangin, prepared in part thanks to the information obtained by the decrypion done by Painvin. Greetings, Nils See (translation to English) of this french website: translate.google.com/translate?sl=fr&tl=en&u=http%3A%2F%2Fwww.bibmath.net%2Fcrypto%2Findex.php%3Faction%3Daffiche%26quoi%3Ddebvingt%2Fradiogramme

[@OliverdeClisson]

@@CryptographyForEverybody yeah

[@OliverdeClisson]

@@CryptographyForEverybody on german wikipedia i read the stuff about George Painvin.

[@OliverdeClisson]

@@CryptographyForEverybody but this george painvin is extremly underrated. I cant find even a single video or article about him on yt and google.

[@CryptographyForEverybody]

There is a small error in the Polybius square used. The letter "N" appears twice, the "W" does not appear at all. To fix this error, one "N" must be replaced by the missing "W" 🙂 . A viewer pointed this out to me, thank you!

[@veehope2702]

Interesting. I wonder what is the minimum cipher length need for a decryption? I look forward to playing with this software tool.

[@CryptographyForEverybody]

Hi Vee Hope, You can compute the "unicity distance" -- a statistical value which tells you the minimum length of ciphertext needed to have a unique solution (when searching it with brute-force). I also have a video about unicity distance on the channel :-). Or you could just test it with a solver, e.g. with CrypTool 2. 1) Unicity distance: To compute the unicity distance, you have to first compute the keyspace size: this is the number of possible polybius squares (= 25!) multiplied with the possible transpositions (I assume transposition key length is 17, so its 17!). So we have 25! * 17! which is about 2^132. The unicity distance is U=entropy_keyspace / redundancy_language = log_2(2^132) / 3.2 (for English) which is 132 / 3.2 which is about 41.26. So we would need about 42 letters of ciphertext to get a solution for an ADFGVX cipher with a transpsition of length 17. Since we have 2 letters per plaintext letter I assume we would need 84 letters of ADFGVX-encoded ciphertext... Of course, this is the absolut minimum. Probably, since the algorithms are not perfect, we would need more ciphertext. 2) With a solver: I did a quick test with CrypTool 2's ADFGVX analyzer template: I removed ciphertexts (messages) from the input and let CT2 break the remaining texts. I was able to successfully solve the ADFGVX ciphertexts having only 2 messages with a total of 336 ciphertext letters (= 168 plaintext letters). In that case, the ciphertexts were encrypted with a transposition key of length 15, so a little shorter than in the computation above in (1). So to answer your question: the theoritcal possible (about 42 plaintext letters) value is of course shorter than the actual ciphertext (about 168 plaintext letters) that we need with a solver. I hope that answers your question :-)

[@12439524]

Is it difficult to solve the adfgvx cipher with double transposition?

[@CryptographyForEverybody]

Hiho, Yes, it is much more difficult. To attack a double columnar transposition, you can use a divide&conquer attack and split the attack into two parts (second transposition and then the first transpositon). Same is with ADFGVX, you perform also a divide&conquer attack. Here, you first solve the transpostion and then the substitution. Now, having two transpositions and the substitution, you cannot perform a divide&conquer on this type of cipher since you have basically three ciphers. I hope you understand what I mean :-) The difficulty of attacking an ADFGVX with double columnar is comparable to attacking the GRANIT cipher (see my video on that cipher: kzbin.info/www/bejne/aYO4q3qBorh6lc0). Greetings, Nils

[@napoleonnathan]

Error: Plaintext and cipher text length do not match

[@CryptographyForEverybody]

Hello Nathan Gallegos! Where did you see this/where did you get this ? Greetings, Nils

[@napoleonnathan]

I figured it out, there was a space in my text

[@GhirkoArt]

Nicely demonstrated. Thanks! I've been stuck with decrypting a code for ages now and this has made life so much easier.

[@CryptographyForEverybody]

Thank you! Always happy to hear when my videos actually help and interest viewers :-) Greetings, Nils

[@oliholbourns7274]

R u taking part in cipher challenge? 😆😆😆

[@GhirkoArt]

@@oliholbourns7274 A cipher challenge, yeah lol. Still, even with this tool I've had no luck. I've started at a key length of two all the way through to 20 and nothing yet.

[@oliholbourns7274]

@@GhirkoArt yeah, i made 27 iterations on part 6B on the second key. I got the first key as RDF. Hope that helps. Any help would be great 👍. Thanks

[@GhirkoArt]

@@oliholbourns7274 Unfortunately I'm not doing the same cipher as you there. Mine is part of a RP group I'm with (but really, they put a code infront of me. I don't care what it's for, I gots ta crack it). How I've been going about it is a mix of using the tool but also doing it manually, as I can assume the first 2 words, so I try every number combination then sub in that first phrase. That might help you, as that key is only 3 letters, it shouldn't take too long.

[@bullse]

It won't work to break a ADFGX cypher. Or am i doing it wrong?

[@CryptographyForEverybody]

Hiho Andreas Mandoe, It does. You can change the mode of the analyzer to adfgx. How much ciphertext do you have? Greetings, Nils

[@Mariano5869]

I followed your steps, and I receive the message: "one of the messages contain invalid characters" what am I doing wrong?

[@CryptographyForEverybody]

Hello there! I assume that your ciphertext contains an invalid symbol. For decryption, the ciphertext only may contain the letters a,d,f,g,v,x. So, i assume it may contain any other symbols. Also, have a look if it contains any whitespaces, for example a space symbol or a line break. If you remove these, the message should be decryptable. Also, it should show you which letter/symbol is wrong. I tested it with a wrong letter ("K") and it shows: "Ciphertext contains invalid character: K" - if it shows something like "Ciphertext contains invalid character: " and you don't see anything after the colon it is a white space as mentioned above.