Genetic Algorithm and Tabu Search attack on the Mono-Alphabetic Subsitution Cipher in Adhoc networks

Journal of Computer Science,  March, 2007  by A. K. Verma,  Mayank Dave,  R. C. Joshi

• E-mail
• Print
• Link

INTRODUCTION

The demand for effective network security is increasing exponentially day by day. Businesses have an obligation to protect sensitive data from loss or theft. Not only businesses see to the security needs; they have to understand where the computer is vulnerable and how to protect it. In the present scenario, where a user needs to be connected anyhow, anywhere, anytime we use ad-hoc networks(1),(2). Ad Hoc Networks are highly vulnerable to security attacks so there is a need to develop a scheme to guarantee certain properties of information (availability, confidentiality, authenticity, integrity). Cryptology is at the heart of providing such guarantee. Cryptology is concerned with the making (Cryptography) and breaking (Cryptanalysis) of Scheme. Cryptography applied by authorized information sharers to design and develop encryption scheme in order to ensure confidentiality of information while cryptanalysis method uses mathematical and statistical attempts by unauthorized person to break ciphers in order to reveal the meaning of the underlying protected data. The cryptanalyst looks for trapdoors; exploitable regularities in either the cipher system or the language or both, combinations of plaintext and ciphertext; or anything else which may prove helpful in breaking the cipher.

Classical ciphers fall into one of the two broad categories: Substitution cipher & transposition cipher. Modern cryptosystems have now supplanted the classical ciphers but cryptanalysis of classical ciphers is most popular crypto-logical application for metaheuristic search research. The basic concepts of substitution and transposition are still widely used today in Advanced Encryption Standard (AES). International Data Encryption Algorithm (IDEA) is also widely used encryption algorithm, which uses only three very simple operators, namely substitution, permutation (transposition) and bit-wise exclusive-OR operator. Since the operations of the classical cipher are the building blocks of modern ciphers, so the classical ciphers are usually the first ones considered when researching new attacks.

In a mono-alphabetic substitution cipher the value of a character or character string is changed when transforming the plaintext into ciphertext, but the position of the original string and its value replacement correspond exactly in the plain and ciphertext. This kind of scheme is usually found in the recreational crypto columns of popular publications such as newspaper and magazines.

For example, if we encrypt the plaintext "how are you" using a single character Mono-alphabetic Substitution Cipher with the shown in Fig. 1 the cipher text is ABSHLCZBX is obtained. In this case the key space consists of all possible permutation tables of the form in Fig. 1 the size of this key space 26! = 403 291 461 126 605 635 584 000 000, which clearly preempts a brute force search in order to break the system.

Example of a key of a singlw character mono-alphabetic
substitution cipher

Plaintext Chararacters->
a b c d e f g h i j k l m n

Ciphertext->
H W U G   C    T  V  A  E  K  DYQP
Plaintext
[right arrow]
o         p    q  r  s  t  u  v  w  x  y  z

Ciphertext
[right arrow]
B         R    J  L  F  I  X  M  S  O  Z  N

Although this cipher is no more secure, it turns out to be surprisingly time consuming to break by hand and is an example of what is known in general as a monoalphabetic substitution, because any single character in the plaintext is mapped onto some fixed single ciphertext character every time occurs. In more complicated mono-alphabetic substitution cipher it may happen that a specific plaintext character is mapped onto any one of a variety of different ciphertext character, depending on circumstances controlled by the cipher key. Examples of other substitution ciphers include the well-known Ceasar cipher, Affine substitutions, Vigenere cipher and Beaufort cipher.

Forsyth and Safavi-Naini (3) have published an attack on the simple substitution cipher using simulated annealing and Spillman et al.(4) presented an attack using genetic algorithm. Dimovski and Gligoroski (5) presented an attack on poly-alphabetic substitution cipher that utilized the parallel genetic algorithm.

Gester (6) has published an attack on Substitution Ciphers using Genetic Algorithm. Jakobsen and Knudsen (7) presented an attack on block ciphers of low algebraic degree.

This study introduces an attack on the monoalphabetic substitution cipher using the Tabu search (8). The previously published attacks using genetic algorithm were enhanced and modified in order that an accurate comparison of two techniques could be obtained.

All experiments presented in the study were performed on text using 27 characters alphabet, i.e., AZ and the space character. All punctuation and structure (sentences/ paragraphs) has been removed from the text before encryption. Any two words are separated by a single space character.

Genetic algorithm: The genetic algorithm is based upon Darwinian evolution theory. The genetic algorithm is modeled on a relatively simple interpretation of the evolutionary process (Fig. 2); however, it has proven to a reliable and powerful optimization technique in a wide variety of applications (9). Holland (10) in 1975 was first to propose the use of genetic algorithms for the problem solving. Goldberg (11) was also a pioneer in the area of applying genetic processes to optimization. Over the past twenty years numerous application and adaptation of genetic algorithms have appeared in the literature.