Cryptanalysis of a Substitution-Permutation Network Using Gene Assembly in Ciliates

Arash Karimi, Hadi Shahriar Shahhoseini

Electrical Engineering Department, Iran University of Science and Technology, Tehran, Iran.

DOI: 10.4236/ijcns.2012.53020                

Abstract

In this paper we provide a novel approach for breaking a significant class of block ciphers, the so-called SPN ciphers, using the process of gene assembly in ciliates. Our proposed scheme utilizes, for the first time, the Turing-powerful potential of gene assembly procedure of ciliated protozoa into the real world computations and has a fewer number of steps than the other proposed schemes to break a cipher. We elaborate notions of formal language theory based on AIR systems, which can be thought of as a modified version of intramolecular scheme to model the ciliate bio-operations, for construction of building blocks necessary for breaking the cipher, and based on these nature-inspired constructions which are as powerful as Turing machines, we propose a theoretical approach for breaking SPN ciphers. Then, we simulate our proposed plan for breaking these ciphers on a sample block cipher based on this structure. Our results show that the proposed scheme has 51.5 percent improvement over the best previously proposed nature-inspired scheme for breaking a cipher.

Keywords

Nature-Inspired Computation; Accepting Intramolecular Recombination (AIR) Systems; Cryptanalysis; Gene Assembly; Block Ciphers

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	L. M. Adleman, “Molecular Computation of Solutions to Combinatorial Problems,” Science, Vol. 266, No. 5187, 1994, pp. 1021-1024. doi:10.1126/science.7973651
[2]	L. Kari and L. F. Landweber, “Computational Power of Gene Rearrangement,” In: V. E. Winfree and D. K. Gifford, Eds., Proceedings of DNA Bases Computers, American Mathematical Society, 1999, pp. 207-216.
[3]	L. F. Landweber and L. Kari, “The Evolution of Cellular Computing: Nature’s Solution to a Computational Problem,” Proceedings of the 4th DIMACS Meeting on DNA-Based Computers, Philadelphia, 15-19 June 1998, pp. 3-15.
[4]	R. Lipton, “Using DNA to Solve NP-Complete Problems,” Science, Vol. 268, 1995, pp. 542-545. doi:10.1126/science.7725098
[5]	L. M. Adleman, P. W. K. Rothemund, S. Roweis and E. Winfree, “On Applying Molecular Computation to the Data Encryption Standard,” Proceedings of 2nd Annual Meeting on DNA Based Computers, DIMACS Workshop, Princeton University, Princeton, 10-12 June 1996, pp. 28-48.
[6]	D. R. Stinson, “Cryptography: Theory and Practice,” CRC Press, Boca Raton, 2002.
[7]	T. Head, “Formal Language Theory and DNA: An Analysis of the Generative Capacity of Specific Recombinant Behaviors,” Bulletin of Mathematical Biology, Vol. 49, No. 6, 1987, pp. 737-759.
[8]	T.-O. Ishdorj and I. Petre, “Gene Assembly Models and Boolean Circuits,” International Journal of Foundations of Computer Science, Vol. 19, No. 5, 2008, pp. 1133-1145. doi:10.1142/S0129054108006182
[9]	T.-O. Ishdorj, I. Petre and V. Rogojin, “Computational Power of Intramolecular Gene Assembly,” International Journal of Foundations of Computer Science, Vol. 18, No. 5, 2007, pp. 1123-1136. doi:10.1142/S0129054107005169
[10]	W. Stallings, “Cryptography and Network Security Principles and Practices,” 4th Edition, Prentice Hall, Upper Saddle River, 2005, pp. 134-173.
[11]	http://www3.wittenberg.edu/bshelburne/Turing.htm
[12]	J. Castellanos, C. Martin-Vide, V. Mitrana and J. Sempere, “Networks of Evolutionary Processors,” Acta Informatica, Vol. 39, No. 6-7, 2003, pp. 517-529.
[13]	D. Boneh, C. Dunworth and R. Lipton, “Breaking DES Using a Molecular Computer,” In: R. J. Lipton and E. B. Baum, Eds., DNA Based Computers: Proceedings of a DIMACS Workshop, Princeton, 10-12 June 1996, pp. 37-66.
[14]	S. N. Krishna and R. Rama, “Breaking DES Using P System,” Theoretical Computer Science, Vol. 299, No. 1-3, 2003, pp. 495-508. doi:10.1016/S0304-3975(02)00531-5
[15]	A. Choudhary and K. Krithivasan, “Breaking DES Using Networks of Evolutionary Processors with Parallel String Rewriting Rules,” International Journal of Computer Mathematics, Vol. 86, No. 4, 2009, pp. 567-576. doi:10.1080/00207160701351168