8 0 0 Cryptanalysis 2 n of a a J Chaotic Image Encryption Algorithm 2 1 ] D C Nikhil Balaji . n Department of Electronics and Communicaton Engineering i l n National Institute of Technology Karnataka, Surathkal [ [email protected] 2 v 6 Nithin Nagaraj 7 2 School of Natural and Engineering Sciences 0 1. National Institute of Advanced Studies 0 IISc. Campus, Bangalore 560012 8 0 [email protected] : v i X January 10, 2008 r a Abstract Line map, an invertible, two-dimensional chaotic encryption algorithm was introduced re- cently. In this paper, we propose several weaknesses of the method based on standard cryptanalytic attacks. We perform a side-channel attack by observing the execution time of the encryption algorithm and successfully reduce the key space by a factor of 104 for a key length of 16 digits. We find the existence of equivalent keys which reduce the key space by a significant margin, even in the absence of any attack. Also, we find that the ciphertext is not sensitive to small changes in the plaintext due to poor diffusion. Cryptanalysis of the Line map 1 Introduction The need for fast and secure encryption schemes for bulky data such as audio, images and video has prompted the advance of chaos-based encryption schemes over traditional schemes, which make use of the inability to perform factorization of large numbers (RSA) ortosolve thediscrete logarithmproblem(ElGamal)inafastandefficient manner. Recent advances like distributed computing, quantum computing and new advances in algorithmic number theorycanpotentiallymakesuchtraditionalschemes totallyunusableinthefuture. In contrast, chaos-based encryption schemes are fast and easily realized in both hardware and software, which makes it more suitable for data encryption. The two basic properties of chaotic systems are the sensitivity to initial conditions and mixing. Sensitivity to initial conditions means that when a chaotic map is iteratively applied to two initially close points, the iterates quickly diverge, and bear no correlation after a few iterations. Sensitivity to parameters causes the properties of the map to change quickly when the parameters on which the map depends are mildly disturbed. Mixing is the tendency of the system to quickly confuse small portions of the state space into an intricate network so that two nearby points in the system totally lose the correlation they once shared and get scattered all over the state space. These properties are the key aspects of chaotic maps that have allowed them to be used to generate complicated patterns of pixels and the gray levels in an image. Traditionally, there aretwo ways in which chaos is used inimageencryption schemes: 1) 1-Dchaoticmapslikelogisticmapandgeneralizationsoflogisticmap[1]togeneratepseudo- random bits with desired statistical properties to realize secret encryption operations. 2) 2-D chaotic maps like Arnold’s cat map, Baker map or fractal-like curves to realize secret permutations of digital images. The first approach has been widely used to design chaotic stream ciphers, while the second is specially employed by chaos-based block encryption schemes. (Refer Table 1 for a brief overview on some recent chaos-based image encryption schemes and their properties). The rest of the paper is organized as follows: The next section gives a brief description of the original line map algorithm and its use in encrypting and decrypting images as developed in [2]. Section 3 points out to the major weaknesses of the algorithm and gives a list of attacks that can be performed on the scheme owing to the weaknesses discussed, Section 4 introduces the Joint Entropy function as a plausible metric for quantifying how well an algorithm or chaotic map, makes the encrypted image look random and Section 5 concludes the paper. 2 Line map algorithm The line map is an invertible, two-dimensional chaotic mapping introduced by Feng [2]. It achieves lossless encryption with a good sensitivity to change in key and exhibits good mixing properties. The line map proposed has two forms namely the left line map and the right line map. Here each pixel of a line perpendicular to the diagonal is inserted between the adjacent two pixels of the next line perpendicular to the diagonal. It is suggested that to arrange the original image in to a row of pixels is a process of stretching and rearranging the row of pixels to image is an operation of folding. From the point of view of these stretching and folding operations, the line map is chaotic, similar to the Baker map or the 1 Cryptanalysis of the Line map Table 1: A brief survey of the chaotic image encryption literature Scheme Strengths Weakness and known at- tacks Scharinger J “Fast en- Unstabledynamics ofthe Size of key space depends on cryptionofimagedata kolmogorov flow ensures size of image. using chaotic Kol- good mixing. mogorov Flows” [3] Fridrich J “Symmetric Cat map: high parame- Catmap: small key space; ciphers based on two- ter sensitivity; Baker and Baker and Standard map: dimensional chaotic Standard map: Large Higher computational com- maps” [4] [5] key space plexity. [6] Yen et al. “Bit Re- Low hardware and com- Weak keys, vulnerable to circulation Image En- putational complexity, known/chosen-plaintext at- cryption” (BRIE) [7] high encryption speed, tacks, since a mask image [8] no distortion that is equivalent to secret key can be derived from a pair of plain-image and cipher-image. [9] Yen et al. “Chaos Low computational Weak to chosen and known key based algorithm” complexity, Good mix- plaintext attacks, security to (CKBA) [10] ing/confusion in pixels brute-force attack is also ques- tionable. [11] Yen et al. “Hierarchi- Parallel and pipelined re- Permutation-only scheme. cal Chaotic Image En- alization of the scheme is Cannot resist chosen plaintext cryption”(HCIE) [12] possible, hence high en- attack. [15] [13] [14] cryption speed Mao et al. “Sym- Large key space, good Insensitivity to changes in metric image encryp- key sensitivity and resis- plaintext and key stream gen- tion based on 3D cat tance to statistical and erated by any key,poor diffu- maps” [16] differential attacks. sion function. [17] [18] Mao et al. “Fast Large key space Insensitivity to changes in image encryption plaintext and key stream gen- scheme based on the erated by any key,poor diffu- 3D chaotic baker sion function. [18] maps” [19] 2 Cryptanalysis of the Line map Cat map. Let A(i,j) be a square image matrix; l(i),i = 1,2,...,N.Nis a one dimensional vector mapped from A(i,j) and fix(X) is a function which rounds the elements of X to the nearest integers towards zero.The algorithm for the line map for square images is given by: i−1 (4i−j +1) (j +1) l (4k −1)+j +1 = A fix ,fix 2 2 ! k=0 (cid:18) (cid:19) X j = 1,2,...,4i−1 i = 1,2,...,fix(N) 2 N fix(2) i−1 N +1 (4i−j +1) (j +1) l (4k −1)+ (4N +1−4fix( )−1+j = A fix ,fix  2  2 2 Xk=0 k=Xfix(N2) (cid:18) (cid:19)   j = 1,2,...,4N +1−4i i = fix(N)+1,fix(N)+2,...,N 2 2 The equations above denote the left line map algorithm.To obtain the right line map,first the image has to be mirrored and then the left line map is applied to the mirrored image. This scheme can be extended to rectangular images according to the size of the image. Using the line map, the encryption of an image is done as follows: the key for encryption is the number of times the left and right line map is applied on the image in succession. For example, a key like ‘321’ means that the image is mapped to another encrypted image through 3 iterations of the left line map, 2 iterations of the right line map and 1 iteration of the left line map in that order successively. For image decryption, we use the inverse line map algorithm, which is straight away, the reverse of the encryption algorithm. When the correct key is entered, the original image is obtained without any loss of information. The line map shows good sensitivity to the changes in the key. To further enhance the security of the algorithm, it is proposed that the gray level values substitution is used together with the line map using XOR operation of the pixel co-ordinates (i and j). This flattens the histogram of the encrypted image, which resists plaintext attack according to [2].All the results throughout this paper have × been tested using a 128 128 Lena image (Figure 1(a)). 3 Weaknesses 1. Itisclaimedin[2]thatthekeyspaceforakeylengthof64bits(16digits)is1.84×1019. This is actuallynot possible because the totalnumber of expressible numbers through 16 digits is 1016 in a decimal number system. So the key space when key length (K) is specified/known can be a maximum of only 10K. 2. Thereexistsequivalent keysfortheencryptionoperationasdefinedbythescheme. As an example, it can be seen that cipher images resulting from keys 4, 103, 301, 202 and 1010101 all reduce to 4 successive iterations of the line map and are thus equivalent (they produce the same encrypted image). Hence, even without any attack, the key space is reduced by a considerable amount. 3 Cryptanalysis of the Line map 3. It is also believed that the scheme can have infinite key length. Practically, since different keys have different times of encryption, by doing a side channel attack (by recording the time taken for line map algorithm), the key used can be localized to a much smaller subset of the key space. 4. The diffusion operation defined by the scheme is weak. By diffusion we mean that, if a change occurs in a pixel’s gray-level, then the change can cause greater changes in other pixels resulting in a totally different cipher text after encryption. Thus, greater the changes caused by diffusion process, higher is the plaintext sensitivity of the cryptosystem, and the system is more secure against differential attack. In this scheme, the XOR of i and j with the plaintext affects only one pixel, which makes the scheme vulnerable to differential attacks. Moreover, the diffusion operation is very loosely defined: “In order to enhance the security, the gray level values substitution is used together with the line map using exclusive OR operation of i and j”(quoted from Feng [2]). Here, the XOR operation if assumed to be made between the current pixel value and the i and j coordinates of the pixel, has poor diffusion and affects only one pixel. 3.1 Side-Channel attack In [2], they claim that since the length of the key has no limit, its key space can be infinitely large according to security requirements. Though this feature has been highlighted as an important advantage of this scheme there are a few glaring weaknesses in using it. The encryption scheme takes variable time to encrypt the image for different keys. So a side- channel attack done by calculating the time taken for varying key lengths greatly reduces the key space for a brute force attack. We take an example of key length=3. There are only 103 possible keys of key length 3. But among those, a key like ‘123’(total number of times of application of either of the line maps is 7) takes a lot more time to encrypt/decrypt an image than a key like ‘111’(total number of iterations is 3).This is a grave weakness as it gives away the number of iterations of the line map involved in the encryption/decryption process. The graph(Figure 2) shows the variationof time taken for encryption with respect Figure 1: (a) Original Image. (b) Encrypted image (Key:1234567891123456). 4 Cryptanalysis of the Line map to the total number of iterations due to the key. From the linear slope, and intercept on the axes, one can narrow down the key search for brute force attack drastically. We derive the following results: 1. The upper bound on the size of key space after we have an estimate of the total number of iterations (N) with maximum error e can be derived from the theory of compositions [20] in number theory (Appendix). (It includes all possible keys of all possible key lengths for sum of iterations varying between N −e and N +e). When we sum over all possible key lengths (K) for this condition,the key space is given by N+e N+e N−1 n=N−e K=ceil(n/9) K−1 2. PFor the cPase where th(cid:0)e key(cid:1)length is exactly known (say equal to K), the brute force attack key search is reduced from 10K keys to N−1 = (N−1)! keys. K−1 (K−1)!(N−K)! Note that the given estimate of key space does (cid:0)not t(cid:1)ake in to account the reduction due to equivalent keys. In [2] a key like 1234567891123456 has been used as an example to encrypt images(N = 67andK = 16). Eventhoughitisclaimedthatthekeyspaceforsuch a key lengthis1.84×1019, withaknowledge ofthekey length, it isactually reducible to 67 15 which equals 2.683×1014 – a reduction in key space by a factor of 104. Such a reduction in (cid:0) (cid:1) key space makes the scheme extremely vulnerable against the computing facility available at the attacker’s disposal (A key space K < 2100 = 1030 is generally agreed to be insecure in the cryptography community [21]) 1.4 1.2 1 0.8 0.6 0.4 0.2 0 0 2 4 6 8 10 12 14 16 18 20 Figure 2: Execution time in seconds vs. sum of iterations (used in side-channel attack). The experiments were done on a machine running sempron processor at 1.8 GHz and 256 MB RAM using MATLAB/Dev C++. 3.2 Chosen plain text attack Even without a brute force attack, the line map scheme is vulnerable to a known/chosen plaintext attack. According to Fridrich [4], one of the important requirements of a good cryptosystem is not just sensitivity to the key, but also sensitivity to small changes in 5 Cryptanalysis of the Line map the plaintext. This means that changing one pixel in the plain-image should result in a completely different cipher-image. This results when the pixel permutation and diffusion operations are strong. The line map doesn’t possess this property and hence is vulnerable in this regard. We changed the first pixel value (137 originally) of the first row of the image to0. Thedifference image(difference between originalimageencrypted andmodifiedimage encrypted) is shown in Figure 3. We see that the difference is in one pixel only. This gives a lot of opportunity to known/chosen plaintext attacks. For instance, if we choose two images that differ in only one pixel and encrypt it using an unknown key, we can observe from the difference image how the different pixel moves after each iteration, from which the key can be recovered. Figure 3: (a) Left: Image with only the first pixel different from the original image. (b) Right: Difference image for key:1234567891123456. 4 Joint Entropy Throughout our experiments with encryption and decryption of images, we have noticed that there exists a need for a good metric to quantify the amount of randomness in the pixel permutation and diffusion operations. These operations are necessary for any secure encryption scheme and a definite way to characterize them will make comparison of the existing schemes much easier. We propose the Joint Entropy function of the image as a metric. Joint Entropy of an image (assuming a gray image with 2L gray levels) is defined as the number of bits required to represent every pair of adjacent pixels of the image at a time (pairs being non-overlapping), averaged over the entire image. With our test image, there are 256 gray levels, and hence the joint entropy for this image is found as follows: we find the frequency of occurrence of all possible combination of gray levels starting from (1,1) to (256,256) and with this statistical measurement, we obtain the probability of joint occurrence of any combination of pixel values (val and val ). Joint entropy is then 1 2 computed as follows: E = p log (p ) (1) val1val2 2 val1val2 Xval1 Xval2 6 Cryptanalysis of the Line map 1. Intuitively, entropy is a measure of randomness. With every iteration of the chaotic map, the pixel arrangement in an image should become uncorrelated and give a noisy appearance after a few iterations. This is evident from (Figure 4) where there is a steep ascent in the Joint Entropy after a few iterations of the map (the first value in the graph is the Joint Entropy of the original image without any iterations of the line map algorithm). 2. Weak keys should be avoided. All keys should produce the same ‘amount of random- ness’. This means that the attacker should not be able to distinguish between two ciphertexts by their way of permutation or diffusion. For some transformations like cat map, which exhibit periodicity, the Joint Entropy function can be used to guess the period of the transformation. We have calculated Joint Entropy here taking in to account only two adjacent column pixels at a time. But there can be other ways to do it, like taking two diagonal pixels or two row pixels or sometimes, more than two pixels at a time to calculate Joint Entropy, which might yield different results from the ones obtained. 12.9 12.8 12.7 12.6 12.5 12.4 12.3 12.2 12.1 12 11.9 0 2 4 6 8 10 12 14 16 18 20 Figure 4: Variation of Joint Entropy (in bits) with the successive iterations of the line map. The first value is the Joint Entropy of the original image. 5 Conclusions and Future Work In this paper, the security of a recently proposed image encryption scheme hasbeen studied in detail. It is found that there exist some serious problems with the key scheme, including weak ones and equivalent ones. The scheme is shown to lack sensitivity to plaintext albeit possessing sensitivity tochangesinthekey whichmakes itvulnerabletodifferentialattacks. The Joint Entropy function shows some promise for fulfilling the need for a good metric to quantify the extent of pixel permutation/diffusion in an encrypted image. But more research needs to be done on the relationship between the number of pixels taken in to consideration while calculating Joint Entropy and the way it affects the Entropy function, or how much more information it might give about the encryption scheme. 7 Cryptanalysis of the Line map Acknowledgements Nikhil Balaji would like to express his sincere gratitude to Department of Electronics and Communication Engineering, National Institute of Technology Karnataka (NITK) where he is an undergraduate student in his Final year. Nithin Nagaraj would like to express his sincere gratitude to Department of Science and Technology (DST) for funding the Ph.D. program at National Institute of Advanced Studies (NIAS) which enabled this work. We would like to thank Prof. Prabhakar G. Vaidya for being a constant source of inspiration and guidance in our research. Both the authors express their thanks to Chengqing Li, Department of Mathematics, Zhejiang University, Hangzhou 310027, China, for useful comments on the paper. References [1] M. C. Shastry, N. Nagaraj, P. G. Vaidya, “The B-Exponential Map: A Generalization of the Logistic Map, and Its Applications In Generating Pseudo-random Numbers”, arXiv:cs/0607069v2 [cs.CR], 2006. [2] Y.Feng, L.Li, F.Huang, “A Symmetric Image Encryption Approach based on Line Maps”, 1st Int. Symposium on Systems and Control in Aerospace and Astronautics 2006(ISSCAA’06), 19-21 Jan. 2006. [3] J. Scharinger, “Fast encryption of image data using chaotic Kolmogorov flows”, J. Electronic Imaging, Vol.7, No.2, pp.318-325, 1998. [4] J. Fridrich J, “Secure image ciphering based on chaos”, Final report for AFRL Rome, New York, 1997. [5] J. Fridrich, “Symmetric ciphers based on two-dimensional chaotic maps”, Int. J. Bifur- cation and Chaos, Vol.8, No.6, pp: 1259-1284, 1998. [6] S. Lian, J. Sun, Z. Wang, “Security Analysis of a Chaos-based Image Encryption Algo- rithm”, Physica A, Elsevier Science, 2005. [7] J. Yen, J. Guo, “A new image encryption algorithm and its VLSI architecture”, In Proc. IEEE Workshop on Signal Processing Systems (SiPS’99), pp. 430-437, 1999. [8] J.Yen, J.Guo, “Designofanewsignalsecurity system”, InProc.IEEE Int.Symposium on Circuits and Systems (ISCAS’02), Vol. 4, pp. 121-124, 2002. [9] S. Li, X. Zheng, “On the security of an image encryption method”, In Proc. IEEE Int. Conference on Image Processing (ICIP’02), Vol. 2, pp. 925-928, 2002. [10] J.Yen, J.Guo,“Anewchaotickey-based designforimageencryptionanddecryption”, In Proc. IEEE Int. Symposium on Circuits and Systems (ISCAS’00), Vol. 4, pp. 49-52, 2000. [11] S. Li, X. Zheng, “Cryptanalysis of a chaotic image encryption method”, In Proc. IEEE Int.Symposium on Circuits and Systems (ISCAS’02), Vol. 2, pp. 708-711, 2002. 8