Unlocking the Secrets of Cryptography: A Beginner’s Guide to Breaking Ciphers — Part 3
This is the third post and last part of my breaking ciphers series. If you haven’t read the previous one, you can find it here:
In my previous post, I showed how to break Product Cipher Composed of the same ciphers. In this post, I will make the cipher much more complicated and try to break it again.
I will use the same ciphertext for this post:
Cryptanalysis of Combination of Porta Cipher and Permutation Cipher
As I have demonstrated, the Product cipher of Porta Ciphers results in an idempotent system. As Shannon proposed, taking the product of substitution-type ciphers with permutation-type ciphers is a commonly used technique to fix that issue.
We have m! probabilities to find out the original key for the permutation cipher. However, in total, we have 13^key length ∗ m! of key space for a combination of Porta Cipher and Permutation Cipher, and this combination is not idempotent anymore.
To investigate it, I created a permutation cipher using that permutation key:
At this point, you may wonder that what is a Permutation Cipher. A Permutation Cipher is a type of encryption technique that involves rearranging the order of characters or blocks of text in the plaintext message to produce the ciphertext.
In a Permutation Cipher, each character or block of characters in the plaintext is assigned a unique position or index, and then the positions are shuffled or permuted according to a specific key. The resulting permutation is used to encrypt the plaintext message, resulting in a ciphertext that appears jumbled and unintelligible without knowledge of the key.
Here is how it works for my permutation key: divide the plaintext into 6-length chunks. Put 0th character into 3rd place, 1st character into 2nd place, so on so forth.
The resulting character frequency output of the permutation cipher is:
As expected, we can observe that the character frequency remains unchanged when using the permutation cipher compared to using only the Porta Cipher.
The Porta Cipher repeats a secret to cipher a text, regardless of the plaintext length. However, when the text size is not a multiple of the permutation key, we should find a solution for the permutation cipher. Padding is one solution, but in our case, since we have long text, we can remove the last 2 characters to align with the permutation key length. We can then use this modified text as the input for the permutation cipher.
For the permutation cipher operations, I created the following class:
For a key length of 6, we can find the original key by trying:
possibilities.
When I try it with below code, I could easily find the permutation key:
I found the permutation key in epoch 412. However, since this is an exhaustive search, the number of epochs may vary depending on the key, and we still need to try m! possibilities.
We can find a solution if we use a better search approach. Therefore, I decided to use a metaheuristic optimization algorithm to overcome this issue. There are some alternative for metaheuristic optimization algorithms. Hill Climbing and Genetic Algorithms are one of the most used ones.
Hill Climbing is a simple and efficient algorithm that can converge quickly to a local optimum, especially in small search spaces. However, it can get stuck in a local optimum and fail to find the global optimum, and it may not be effective in large or complex search spaces.
On the other hand, Genetic Algorithms are more robust and versatile than Hill Climbing. They can explore large search spaces efficiently and can potentially find global optima. However, they require more computational resources than Hill Climbing, and Genetic Algorithms can be slower in converging to a solution.
As I mentioned, our key space is 13^key length ∗ m! Since the key length is 6, we should try:
possibilities, which is large enough. Hence, I implemented a Genetic Algorithm as my metaheuristic optimization algorithm.
The product cipher is a combination of two distinct ciphers, namely, the Porta Cipher and the Permutation Cipher. Although the Porta Cipher has a larger key space than the permutation cipher, it is still susceptible to frequency analysis. Conversely, the permutation cipher has a smaller key space, but it is resistant to frequency analysis. Therefore, what if we assume that the output of the product cipher is not an output of a permutation cipher and try to break it? This approach can potentially reveal a shuffled key as the result, which we can then attempt to crack to determine the correct shuffle order. As a result, we can break that product cipher not within a 13^key length ∗ m! key search space, but 13^key length + m!.
Below are the results of the Chi-squared Statistics when directly applying each key element trans- formation to each cluster of permutation cipher output:
So, the candidate key is all of the combinations of these letters:
One of the candidate key is:
This is exactly a shuffled version of the original key. However, I didn’t use that information since I assumed that I don’t know how to crack the intermediate cipher, Porta Cipher.
I implemented a Genetic Algorithm as I mentioned. I created a weighted trigram approach as the fitness function. Here is the code I implemented:
With only 60 evaluations, I was able to discover the solution, which is significantly fewer than the m! = 720 possibilities that would have been required. This solution would also address the issue in the event of a lengthier key:
Here is the key that I found, which is the same as the original one:
The proposed method searches on a space of 13^key length+m! instead of 13^key length∗m!. Furthermore, as previously mentioned, by independently processing the elements of the key, we process 13 ∗ key_length candidates for the Porta Cipher. Therefore, we are able to consider 13 ∗ key length + m! possibilities. Moreover, the m! part of the Permutation Cipher can be reduced using the Genetic Algorithm as demonstrated. Effect of narrowing the key search space is demonstrated below (without adding the leverage of the Genetic Algorithm):
As I demonstrated, the proposed method exposes both keys of the Porta Cipher and Permutation Cipher.
Conclusion
I hope you enjoyed this series.
Don’t forget to follow me on Twitter: https://twitter.com/kamaci_furkan
Stay tuned!
References
[1] David Kahn. The Codebreakers: The Comprehensive History of Secret Communication from Ancient Times to the Internet. Scribner, 1996, p. 139. isbn: 9780684831305.
[2] Keith M. Martin. Everyday Cryptography. Oxford University Press, 2012, p. 142. isbn: 9780191625886.
[3] Berna Örs Yalçın. Lecture notes in Cryptography. Apr. 2023.
[4] William F Friedman. The index of coincidence and its applications in cryptography. Riverbank Laboratories. Department of Ciphers. Publ. OCLC, 1922.
[5] Practical Cryptography. Chi-squared Statistic. url: http://practicalcryptography.com/cryptanalysis/ text-characterisation/chi-squared-statistic/. (Accessed: 03.04.2023).
[6] Douglas R. Stinson and Maura B. Paterson. Cryptography: Theory and Practice. 4th. Boca Raton, FL: CRC Press, 2019, pp. 75–78. isbn: 9781138197015.
[7] Vittorio et. al Maniezzo. Matheuristics, Algorithms and Implementations. Springer International Pub- lishing, 2021.
[8] Bill Waggener. Pulse Code Modulation Techniques. Springer, 1995, p. 206. isbn: 9780442014360.
