How to solve cipher encrypted with Vigenère + Columnar Transposition?

Question

Vigenère's weakness is Kasiski's test and index of coincidence. However, if you put columnar transposition on top of Vigenère, that weakness is gone. The text is now shuffled and you can't search for digrams/trigrams, because they will give you wrong key length pattern.

You also can't solve Columnar Transposition. For example, you try key length $i$ and you put the text in $i$ columns. Normal Columnar Transposition is solved by matching columns with each other and counting how good the match is (compared to English text digrams). The best match is then the correct column order. But because the text is encrypted with Vigenère and letters are substituted, you won't get correct result.

Is such a cipher considered very good / unbreakable or how does one attack it?

Answer 1

Obviously such a combination of ciphers is stronger than any of these two ciphers alone.

The Vigenere cipher provides "confusion", while the transposition cipher provides "diffusion". These are terms used by C. Shannon, refer to http://en.wikipedia.org/wiki/Confusion_and_diffusion.

Modern ciphers like AES are making use of diffusion and confusion as well. But - besides additional other operations - here several rounds are applied.

I think applying these two encryption methods (vigenere & transposition) to a plain text only once will still be a rather weak encryption (at least compared to AES).

In the following I provide some of my thoughts. I haven't verified them, so I cannot guarantee that everything described below works as expected. :-)

Some thoughts of how to attack such an encryption: Evolutionary algorithms (http://en.wikipedia.org/wiki/Evolutionary_algorithm) are one way to break transposition ciphers (btw, EAs can be used to break Vigenere ciphers as well). One variant of such an algorithm is called genetic algorithm (http://en.wikipedia.org/wiki/Genetic_algorithm). Investigations in this area have been done, e.g. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.113.4358&rep=rep1&type=pdf.

One main function within a genetic algorithm (GA) is called fitness function. Once a key has been chosen the given cipher text is decrypted using this key and the resulting clear text is passed to the fitness function (http://en.wikipedia.org/wiki/Fitness_function). The fitness function returns a measure how close the result comes to an optimum solution.

In case simple transposition ciphers are to be solved the fitness function determines how close the clear text comes to the English language.

Now if a clear text is encrypted by the Vigenere cipher, and the resulting Vigenere cipher text is encrypted using the transposition cipher then the resulting cipher text can be attacked by treating it as a "simple" transposition cipher. The difference is now that the fitness function must return a measure how probable it is that the resulting clear text is a Vigenere cipher.

Vigenere ciphers have certain characteristics, e.g. an autocorrelation will show periodic maxima (http://www.cryptool-online.org/index.php?option=com_content&view=article&id=90&Itemid=107&lang=en). Thus it should not be a problem writing a fitness function which distinguishes a Vigenere cipher from a random sequence of characters.

Once the transposition cipher is solved solving the Vigenere cipher is rather straight forward.

Implementing a fitness function checking for the Vigenere cipher will probably be slower than a corresponding function checking for English text. Thus I expect that breaking the cipher "Vigenere & transposition" will require much more processing time than breaking any of these ciphers alone.

There is still an open question: How to find the key length for the transposition cipher? One possible way might be to apply an autocorrelation to the cipher text. I would expect to see maxima at multiples of the least common multiple of the Vigenere key length and the transposition key length. This should at least limit the potential key lengths to try.

Answer 2

The problem with these kind of “is it unbreakable” questions is that they are often the wrong question. Yes, technically a Vigenere plus columnar transposition is going to be breakable.

The first question is, though, why would anyone presented with a ciphertext about which they otherwise know nothing would think that both Vignenere and columnar transposition have been used? And why in that order, and not the other way round with the plaintext first being encrypted with a columnar transposition cipher before the Vigenere?

Because the real questions here are really, what is your motive for encryption and what is the threat model? In other words, understanding why you’re encrypting and understanding who your adversary is crucial. Every text book will tell you that the Vigenere is not safe and breakable: yet the following ciphertext is very likely to be unbreakable:

BUNGZ EAGQQ RXVJQ VAFIT OVVGJ LKFHT BGNGF SCKTI GOEDY

Why? Because no one is likely going to put in the time and resources to break this, plus the ciphertext is very limited. And I've not even bothered with a columnar transposition. So understanding the time and resources your adversary has or may have is a serious factor that can be used. In the real world, nobody is going to bother to spend much time cracking your ciphertexts if it doesn’t involve a law enforcement or national security issues, so using both Vigenere with a keyword of more than 8 letters or more and columnar transposition would be very secure. Not unbreakable: but perhaps it doesn’t need to be to achieve your aims (motive for encryption again).

At a guess, given that most police forces in Western liberal democracies have limited budgets, and if the encrypted messages do not appear to threaten national security, then probably using both a Vigenere with a key word of more than 8 letters plus columnar transposition is going to be safe, not least because it will be the criminal activity itself that may attract attention to you rather than anything the message may or may or not say. But in that case, I’d recommend examining your life decisions rather than worrying about encryption.