Tag: cryptanalysis

How We Solved Five Encrypted Letters of Maximilian II Written in 1574 and 1575

As a (historical) cryptology expert, a few years ago during my work for the DECRYPT project [4], I delved into a fascinating historical mystery that took me back to the year 1575. It was a pivotal year for the Habsburg Emperor, Maximilian II, who was vying for the crown, which was vacant at that time, of the Polish-Lithuanian Commonwealth, a vast parliamentary monarchy.

Portrait of Maximilian II. Emperor of the Holy Roman Empire (1527-1576), son of Ferdinand I.

While today’s election campaigns are awash with digital media strategies and online propaganda, back in the day, things were a tad different. Maximilian, being a foreign candidate, relied heavily on written correspondence to communicate his political promises and strategies to allies in Poland-Lithuania campaigning for his election. But there was a catch – these letters contained sensitive political information, and there was always a risk of them being intercepted by “the enemies”.

To my surprise, Emperor Maximilian II and his secretaries didn’t rely on the digit ciphers that were already popular at the time, e.g., in the Vatican. Instead, they encrypted their messages using a mix of alchemical symbols, astrological signs, Latin and Greek letters, numbers, and even some characters of their own invention.

What caught my attention was a discovery in Vienna’s state archives by two of my DECRYPT project colleagues (historian Prof. Benedek Láng and his PhD student of that time Anna Lehofer) – five encrypted letters related to Maximilian’s candidacy for the Polish-Lithuanian throne.

Using CrypTool 2, I was able to decipher the ciphertexts partially. Then, with the help of my good colleague and later co-author of two research articles [1,2] and an article for the German magazine c’t [2] about the topic, we we finally were able to decipher like 95% of the letters.

Deciphering Maximilian’s Letters – A Closer Look

Deciphering historical encrypted manuscripts is always a blend of art and science. When I first set my eyes on Maximilian’s letters, I realized that the challenge was not just in the encryption but also in the transcription. Also, I did not even know that the emperor Maximilian II was the author since there were no visible signs of sender and receiver marks on the letters. Only after Michelle suggested that Maximilian II may have been the author (she has a really good intution!) and we finally deciphered his name in one of the letters, we were sure about his authorship. The handwritten letters are filled with symbols that were not easily recognizable. There were alchemical and astrological symbols, Latin and Greek letters, and some characters that seemed entirely unique:

The start of the first letter of Maximilian II — Copyright Haus-, Hof- und Staatsarchiv Vienna

The initial step was to transcribe the symbols of the letters into a machine-readable format. To do this, we translated each symbol into a designated UTF-8 character. It sounds straightforward, but the challenge for us was in identifying and distinguishing between similar symbols.

A peculiar aspect of Maximilian’s ciphers was the use of spaces between words. This provided a significant clue. In most advanced ciphers, spaces (or the lack thereof) can serve as a method of obfuscation. But here, the spaces helped in identifying potential word structures, especially for shorter words.

Using my “Homophonic Substitution Analyzer” component of CrypTool 2, we began the decipherment process. The component uses a hill-climbing algorithm, which starts with a random assignment of ciphertext symbols to plaintext letters (a start key). It then continually refines this key by making small changes, improving the quality of the decipherment using a language model.

However, the tool isn’t just a “set-it-and-forget-it” solution. It requires active involvement. As we interacted with the software, we could manually adjust assignments, fixing correct letter identifications and choosing an appropriate language model based on the text’s suspected language. After several trials, it became evident to us that the letters were written in a German dialect of that era. Michelle, my colleague in this project, came to the conclusion that the letters were written by the sender(s) in a so-called “neutral” Austrian-Bavarian written dialect and in an office style typical of the Early New High German period. She also improved the decipherment significantly by correcting my initial work.

One particularly intriguing discovery in the letters was the use of “nulls” (which are usually meaningless filler characters; here denotated as hash symbols #) in the ciphers. These characters were likely used to confound potential eavesdroppers. But, upon close cryptanalysis and some educated guessing, phrases like “###MAX#IMILI#AN##” and “####DAT#PRAG DEN 5## IULII####1#5#7#5####” (Prague the 5th July 1575) were revealed, indicating the sender’s name, date, and location of dispatch.

The successful decipherment of the first letter paved us the way for the four others. In total Maximilian (or, more probably, one or even multiple of his secretaries) wrote three letters and two letters were written by Jan Chodkiewicz, a nobleman of that time. Some of the letters are encrypted using the same key, while others, though they were encrypted using a different key, were made easier for us to cryptanalyze due to the foundational understanding from the initial deciphering. Thus, this deciphering journey was a dance between manual analysis and algorithmic prowess.

Our Conclusion

In conclusion, our journey into the past showcased the encryption methods of the 16th century Holy Roman Empire. While Maximilian’s ciphers might have been challenging for contemporaries, they are no match for our modern computational power and algorithms. Nevertheless, compared to Vatican ciphers Maximilians ciphers are quite poorly designed and cryptanalysts of the time would have probably been able to also solve the ciphers. All in all it was a very interesting project to read letters that probably no one else was able to read for the last nearly 500 years.

Bibliography

If you want to read more details about the decipherment and the historical background, you may have a look at our two research papers [1] and [2]. If you are able to read and understand German, you may have a look at our c’t article [3].

[1] Kopal, Nils, and Michelle Waldispühl. “Deciphering three diplomatic letters sent by Maximilian II in 1575.” Cryptologia 46.2 (2022): 103-127. See https://www.tandfonline.com/doi/full/10.1080/01611194.2020.1858370
[2] Kopal, Nils, and Michelle Waldispühl. “Two Encrypted Diplomatic Letters Sent by Jan Chodkiewicz to Emperor Maximilian II in 1574-1575.” International Conference on Historical Cryptology. 2021. See https://ecp.ep.liu.se/index.php/histocrypt/article/view/160
[3] Kopal, Nils, und Michelle Waldispühl. Kryptische Propaganda – Entschlüsselt: Briefe von Kaiser Maximilian II. c’t 4/2022.
https://www.heise.de/select/ct/2022/4/2134408482322873782
[4] The DECRYPT project. https://www.de-crypt.org/


I Implemented the “Mexican Army Cipher Disk” and also its Cryptanalysis in CrypTool 2

In the last view days, I implemented the Mexican Army Cipher Disk and its cryptanalysis in CrypTool 2. I also made a YouTube video about that (see below in this blog post).

The Constitutionalists in Mexico used the Mexican Army Cipher Disk at the beginning of the 20th century during the Mexican revolution. It is a homophonic substitution cipher, but rather weak. For encrypting a letter, you have either a 3-symbol or a 4-symbol homophone group, with a total of 100 homophones (01 to 00).

My self-created Mexican Army Cipher Disk

The groups are created using the disk device, which consists of 5 disks (see shown figure above):
• The outer disk contains the Latin alphabet
• Four inner disks contain 2 digits numbers
• Four inner disks can be turned

The key of the cipher is the rotation of the four inner disks and can be described in two ways:
1) The digit groups below the letter A : 01, 27, 53, 79
2) With four Latin letters ; each letter is the one above the first digit group of the corresponding disk: A, A, A, A

Build your own Mexican Army Cipher Disk

Now, if you want to also build your own cipher disk, you may use my self-created template here:

Mexican-Army-Cipher-DiskDownload

Since I used powerpoint to create the template, the angles are not 100% perfect, but it still works well. You need to print it five times and always cut a smaller disk out of each printout. To get more stability, you may also use some cardboard and glue the disks onto these before assembling the device. Finally, all the disks are placed on top of each other. I used a paper clip that I bent and put through all the slices.

Cryptanalysis

If we want to break the Mexican Army Cipher Disk, it is a rather easy task. By hand, we just search in each number group (01 to 26, 27 to 52, 53 to 78, and 79 to 00) for the most frequent homophone. This stands probably for the letter E. Move your disks to all found E positions and you should be able to decrypt your ciphertext.

If you don’t want to break it by hand, you can use CrypTool 2 and the “Mexican Army Cipher Disk Analyzer” component for automatic cryptanalysis. It performs a brute-force attack and searches through all disk settings. Here, with the help of a language model (e.g. English pentagrams) it scores each of the decrypted texts. The correct plaintext should be on the first position of the best list of the analyzer.

YouTube Video

I alse created a YouTube video about the Mexican Army Cipher Disk. You may watch it here:

My YouTube video about the Mexican Army Cipher Disk

Some References

Cryptography for everybody: Safe primes for RSA?

Generation of “safe” primes in CT2 using the RSA KeyGenerator component

I recently got some interesting feedback to the “Break reduced RSA” YouTube video I made some time ago. Of course I used CrypTool 2 (CT2) in that video. One viewer asked me, why we chose to generate non-safe primes, as well as if the quadratic sieve component of CT2 is able to break RSA challenge numbers. My answer to the second question: Since we have a quite old implementation of msieve (the library we use) converted to C# long ago, I don’t think the factorization algorithm is as powerful as the current state-of-the-art factorization libraries. Nevertheless, it is “good enough” to show how to break RSA (up to N in range of 2^300).

The answer to the safe prime question: Good question! I never thought of generating such numbers in CT2 and thought standard prime numbers are ok for CT2. I mean, it is a tool for education and not meant for any security purposes. Nevertheless, in real world applications you use large primes for RSA with additional requirements: They should be safe. So I updated the RSA KeyGenerator component to also allow the generation of safe primes. But are safe prime numbers still needed with RSA modules in the range of 2^2048 and above? For the current state-of-the-art of RSA factorization, you may have a look at https://en.wikipedia.org/wiki/RSA_Factoring_Challenge.

But what is a safe prime?

A number p is a prime number, if it is only divisible by itself and by 1. For example 13 is a prime number, or 17, or 23, … etc. A “safe prime” number p is a number, that is prime AND (p – 1) / 2 is also a prime number which we then call a Sophie Germain prime. An example for a safe prime is 23, because (23 – 1) / 2 = 11 is a Sophie Germain prime. Safe prime numbers are more resistant against some factorization methods, which could be used to factorize the RSA’s N (which is the product of two large primes p and q).

But are safe primes really needed for RSA?

I questioned that myself and found a paper by Rivest, who is the R in RSA. Already in 1999, Rivest stated that: “We find that for practical purposes using large “random” primes offers security equivalent to that obtained by using “strong” primes. Current requirements for “strong” primes do not make them any more secure than randomly chosen primes of the same size. Indeed, these requirements can lead a general audience to believe that if a prime is “strong” that it is secure and that if it isn’t “strong” then it must be “weak” and hence insecure. This simply is not true.” [1]

Rivest speaks about “strong” primes, not about safe primes. Strong primes have additional properties, from which “safe” primes fullfil one. But today, the usage of just “random” primes is good enough to keep RSA secure, since the primes are so large, that the properties for “strong” and “safe” are negligible. The “safe” property for primes was introduced to counter special factorization algorithms, like Pollard-Rho. But the modules we use today with RSA are too large to be factored with e.g. Pollard-Rho.

Nevertheless, now we have the choice in CT2 to generate either “random” or “safe” primes. Also, the RSA KeyGenerator uses a cryptographic random number generator during the generation of the RSA keys. In the CT2 workspace shown at the beginning of the blog article, we generate a 1024 bit RSA key and set the generator to “safe” prime generation. The prime test components evaluate the generated primes p and q and if both are “green” this means that the primes are safe.

You may be interested in my RSA YouTube video:

Basics of Cryptology – Part 11 (Modern Cryptography – Asymmetric Ciphers – RSA)


And you may also be interested in my “How to break reduced RSA” YouTube video:

Break (Reduced) RSA Using Factorization


[1] Rivest, Ronald L., and Robert D. Silverman. “Are Strong Primes Needed for RSA?” IN THE 1997 RSA LABORATORIES SEMINAR SERIES, SEMINARS PROCEEDINGS. 1999.

Nils

Cryptography for everybody: I updated the Transposition Analyzer in CrypTool 2 to Make it More Convenient

Today, I updated the “transposition analyzer” component of CrypTool 2 (CT2) to make its usage more convenient. The analyzer allows the cryptanalysis of ciphertexts that are encrypted using the columnar transposition cipher. It was written some time ago in the early days of CT2 by some of my commolitons when I was doing my masters.

The CrypTool 2 transposition analyzer component now supports keylength ranges


It always bugged me that you needed to restart the analyzer when you wanted to analyze different key lengths. For example, if you assumed that a ciphertext had been encrypted using a columnar transposition cipher, but you were unsure which key length had been used (e.g. between 5 and 15), you had to restart it for any of the assumed key lengths.

Now, its a matter of setting minimum and maximum key lengths, and the analyzer will test all lengths of the defined range 🙂

Btw, the transposition analyzer supports different cryptanalysis methods/heuristics: brute-force for smaller key lengths, genetic algorithm and hillclimbing for longer key lengths. Also, if you have a crib (a part of known plaintext), the crib analysis can be used.

But besides simply just updating the component, I fixed a few bugs and generally improved the C# code a bit 🙂

If you want to see how to use the transposition analyzer of CT2, I created a video about it in the past:

Break a Columnar Transposition Cipher

Probably, I will also create a new video about columnar transposition ciphers and the updated transposition analyzer in the near future.

We published some years ago a paper about cryptanalysis of the columnar transposition cipher in Cryptologia [1].

Finally, if you want to simply encrypt or decrypt using the columnar transposition cipher, you may have a look at the nice implementation in CrypToolOnline: https://www.cryptool.org/en/cto/transposition

[1] Lasry, George, Nils Kopal, and Arno Wacker. “Cryptanalysis of columnar transposition cipher with long keys.” Cryptologia 40.4 (2016): 374-398.

Nils

Cryptography for everybody: I Created a Text-Based AES-Like Cipher – A Cipher Built Using Only Classical Ciphers

Can you build a cipher with the structure of the Advanced Encryption Standard (AES), our current standard modern symmetric cipher, but only use classical ciphers? I asked myself this question when I implemented AES in C# as a preparation for my upcoming AES videos on my YouTube channel in 2021.

AES’ structure (10 rounds for AES-128) consists of 4 different building blocks:
1) AddRoundKey,
2) SubBytes,
3) ShiftRows, and
4) MixColumns:

AES structure

The AddRoundKey building block adds a round key to the state array of 16 bytes (or plain and/or ciphertext) using XOR. The SubBytes building block substitutes each byte using AES’ S-Box, the ShiftRows building block performs a shift of the rows of the state array, and the MixColumns building block mixes the columns of the state array by multiplying each “vector” with an invertible matrix in the finite field GF(2^8).

When I implemented each of these four steps, I was reminded of some classical ciphers: AddRoundKey reminded me of an additive cipher, SubBytes reminded me of a simple substitution cipher, MixColumns reminded me of a transposition cipher, and the matrix multiplication finally reminded me of a Hill cipher.

Thus, I changed the inputs (plaintext and key) and the output (ciphertext) of the AES to simple text (just letters from A to Z), exchanged AddRoundKey with an additive cipher (using MOD 26), exchanged SubBytes by SubBigrams (a bigram substitution cipher), I kept ShiftRows as it was, and exchanged MixColumns with a 4×4 Hillcipher (also using MOD 26). The “TextAES” was born :-).

To also allow decryption, I computed the inverse S-Box (an inverse lookup table for the bigram substitution cipher) and an inverse matrix for the Hill cipher.

I kept the key expansion more or less as it was, but with text, and also used the bigram substitution and replaced its round constants by “AAAA”,”BAAA”,”CAAA”, etc.

Finally, I was convinced that you can create an AES-like cipher using only classical ciphers :-).

If you are interested in details of this self-made crazy cipher, have a look at the video I made about it:

I Created a Text-Based AES-Like Cipher

If you are interested in details of the real AES, you may also have a look at my other two videos about AES and AES key schedule:

AES – The Advanced Encryption Standard Explained
AES – Key Schedule/Key Expansion Explained

Also, if you want to play with my source code in C# of AES and TextAES, you can find it freely available on GitHub: https://github.com/n1k0m0/AES-and-Text-Based-AES

Finally, here is the original publication of AES:
Daemen, Joan, and Vincent Rijmen. The design of Rijndael. Vol. 2. New York: Springer-verlag, 2002.

Nils

Cryptography for everybody: Basics of Cryptology Series (correct ordering)

In 2020 I started my “Basics of Cryptology” series on my “Cryptography for everybody” YouTube channel.

Right now, the series consists of 23 different videos. The videos cover topics from the beginnings of cryptology and basic terminology up to modern cryptology (e.g. RSA and AES).

While creating the series I jumped with the focus and created videos, as the topics came into my mind. Thus, today, I tried to order the videos to a “correct” order. Here is my current list 🙂

Clearly, you can just watch the videos as they are present in the YouTube playlist 🙂
Maybe, in the future, I will create a single long video, a new playlist, or maybe even re-create all videos. When I started creating my videos, my YouTube channel was new and I had not so much experience as I have now.

Nevertheless, I hope you’ll find my videos in that series interesting and helpful. If you have any questions, ideas, or wishes, feel free to write below this blogpost or directly below my videos in the comment section 🙂

Nils