IJCNS  Vol.5 No.3 , March 2012
Cryptanalysis of a Substitution-Permutation Network Using Gene Assembly in Ciliates
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.
Cite this paper: A. Karimi and H. Shahhoseini, "Cryptanalysis of a Substitution-Permutation Network Using Gene Assembly in Ciliates," International Journal of Communications, Network and System Sciences, Vol. 5 No. 3, 2012, pp. 154-164. doi: 10.4236/ijcns.2012.53020.

[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.


[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