Cryptanalysis and Improvement of a Chaotic Map-Control-Based and the Plain Image

Bin Lu1,Fenlin Liu1, Xin Ge1,＊ and Zhenyu Li

Abstract:Due to the characteristics of chaotic systems,different cryptosystems based on chaos have been proposed to satisfy the security of multimedia data.A plain image-related chaotic algorithm is proposed by Luo et al.with high speed and efficiency.Security weaknesses of the cryptosystem are studied in this paper.It is found that the important secret key information is leaked because an important parameter can be obtained after an inverse operation in the last step of the cryptosystems without secret key.Meanwhile,the value zero is processed improperly in quantification algorithm.Based on the weaknesses,chosen plaintext attack on the cryptosystem is proposed,by which,an important parameter,equivalent to secret key,can be calculated with a specific chosen plain image.With the obtained parameter,the plain image of any ciphered image,encrypted by the cryptosystem,can be recovered.Then,an improvement is proposed to solve the problems after modifying the quantification algorithm.It is from the experiments that chosen plaintext attack is valid and improved algorithm possesses better performance.

Keywords:Multimedia cryptosystem,cryptanalysis,chaos,chosen plaintext attack.

1 Introduction

With the continuous development of mobile communication technology,social networks are gradually integrating into people’s life,which deeply affects our work habits,daily life and way of thinking.Images and videos,as important multimedia in social networks,involve a large number of important information about individuals and organizations.The protection of multimedia data has become an urgent problem for social network security.There are many ways to protect multimedia data,such as encryption [Fridrich (1998);Ge,Lu,Liu et al.(2016);Luo,Cao,Qiu et al.(2016)],information hiding [Xiong and Shi(2018)] and so on.Encryption as a basic data protection method has attracted more attention.Traditional cryptosystems possess relatively high security,but it is difficult to meet the requirements of massive data encryption in social networks due to their complex operations.The encryption technique based on chaos theory [Matthews (1989);Fridrich(1998)] is regarded to be a new choice considering its good cryptographic properties,such as the extreme sensitivity of the parameters,good pseudo randomness and so on.

Some cryptosystems based on chaos are proposed in order to improve the security of images [Hua and Zhou (2016);Chen,Mao and Chui (2004);Xiang,Hu and Sun (2015);Chai,Fu,Gan et al.(2019)] and videos [Lin,Yu,Lu et al.(2015)].But some algorithms[Fridrich (1998);Lian (2009);Ye (2010)] are suffered from security problems due to important information leakage such as secret key information leakage,plain image information leakage.For examples,the hyper chaotic mage/video algorithm in [Lian(2009)] is broken due to the re-usage of keystream which equals to the secret key [Ge,Liu,Lu et al.(2011)];Fridrich’s chaotic image encryption [Fridrich (1998)] is broken by using influence network between cipher-pixels and the corresponding plain-pixels [Xie,Li,Yu et al.(2017)];Ye’s algorithm [Ye (2010)] is broken because the secret permutation does not change the values of the permuted elements [Li and Lo (2011)].

As one of the candidate algorithms,a chaotic map-control-based and the plain imagerelated cryptosystem [Luo,Cao,Qiu et al.(2016)] is proposed by Luo et al.(refers to as Luo algorithm in this paper),which is sensitive to both the secret key and the plain image,with high speed and efficiency.However,a key parameter generated from secret key and plaintext is embedded into the ciphertext,and it can be extracted after an inverse operation,which resulting in important information leaking of the secret key.Meanwhile,it is also a weakness by substituting zero with constant in quantification algorithm.In this paper,chosen plaintext attack on Luo algorithm is proposed with the secret key information leakage and the defect of the quantification algorithm.Then an improvement is proposed to solve the problem by improving the quantification algorithm and embedding the key parameter with secret key.Experiments and analysis show the validity of chosen plaintext attack and the security of improved algorithm.

The rest of the paper is organized as follows.Luo algorithm is briefly described in Section 2.A chosen plaintext attack is proposed after analyzing on the defect of Luo algorithm in Section 3.An improved algorithm is proposed in Section 4.Experimental results and analyses are reported in Section 5.

2 Luo algorithm

Luo algorithm is a single round encryption algorithm,including pixel value diffusion and pixel position scrambling.For an plain imageof sizesecret keyisNbytes,ciphered image ofcan be denoted byThe procedure of Luo algorithm is briefly described below.

Then generate parameterJby applying quantification algorithm on

Quantification algorithmQ(M)

For any matrixM= (mi,j)W×V,the quantification algorithm multiply each element ofMand get a sequence of products noted asMEj,j= 1,2,…,W×V.Judge and ensure each value ofbe smaller than 1014.MEjis replaced by the multiplication of all digits in the decimal representation ofMEjwhenMEj＞1014.To avoid the product equals to 0,digit number ‘0’ is replaced byandaccording to the position before multiplication.LetThenD2is calculated by multiplying the elements ofMin reverse order with the above steps.Finally,calculate

(3)Generate the pixel permutation vectorsand the divisor parameteraccording

(4)Pixel value diffusion：Divide the （8i+j）thpixel valueofPby 2ki,get the corresponding quotientv8i+jand remainderr8i+j.Pixel valueq8i+jof the image after the pixel value diffusionis calculated by

(5)Pixel position permutation：PermuteQ= (qi,j)L×Hwith permutation vectorsanddenote the result bywhere

(6)Embed the parameterIintoD= (di,j)L×H：Ican be denoted byI=0.I1…I8with eight integersI1,…,I8among 0 to 99 becauseIis a 10-15precision decimal.EmbedI1,…,I8intoin fixed positions.

(7)ReprocessD= (di,j)L×Hby a round of bit-XOR operation and obtain the ciphertextwherei= 1,2,…,H-1,j= 1,2,…,L-1.

3 Cryptanalysis of Luo algorithm

In Luo algorithm,pixel value diffusion and pixel position permutation are both based on chaotic sequence.Considering chaotic system,its control parameter is public,initial value is calculated byI,Jwhich are obtained by the quantification algorithm with secret key and plain image.IfI,Jare recovered by attacker,the initial value can be recovered,then the chaotic sequence can be obtained,and plain image can be correctly recovered.Therefore,key parameterI,Jare important for the security of the algorithm.

3.1 Cryptanalysis on key parameter

Firstly,analysis on parameterI：According to Steps (6)and (7)of Luo algorithm,Iis publicly embedded into imagedirectly by substituting the corresponding values of fixed pixels,andD= (di,j)L×Hcan be obtained after a round of reverse bit-XOR operation onC= (ci,j)L×H.So the attacker can extractIwithout secret key.

Secondly,analysis on parameterJ：parameterJandIare both calculated by quantification algorithm.The difference is that the calculation ofJdepends only on the secret key,while that ofIdepends not only on the secret key but also the plain image.IfIhas been obtained by the attacker,part information ofJwould also be leaked.And the leaking information ofJis explored in Proposition 1.

Proposition 1.ParameterJsatisfiesJ=Iif plain imageP= (pi,j)L×HsatisfiesL=N,pi,j=1for alli=1,2,…,L,j=1,2,…,H,whereNis the number of secret key bytesK=K1K2…KN.

Proof:According to quantification algorithm in the generation of parameterJ,J= ((E1+E2)mod 1 014)× 1 0-14whereE1=K1⊗K2⊗…⊗KN,E2=KN⊗KN-1⊗…⊗K1,⊗denotes the multiplication defined in quantification algorithm.

According to the generation of parameterI,I=Q(A)=((D1+D2)mod1014)× 1 0-14,whereA=(ai,j)L×(H+1)(see Eq.(1)).

If plain imageP= (pi,j)L×HsatisfiesL=N,pi,j=1for alli=1,2,…,L,j=1,2,…,H,whereNis the number of secret key bytesK=K1K2…KN,then matrixA=(ai,j)L×(H+1)equals to：

Then

D1=1⊗1⊗…⊗K1⊗1⊗…⊗K2⊗…⊗KN=K1⊗K2⊗…⊗KN

D2=KN⊗1⊗…⊗KN-1⊗1⊗…⊗K1⊗…⊗1=KN⊗KN-1…⊗K2⊗K1

SoE1=D1andE2=D2,therefore

J=((E1+E2)mod1014)× 1 0-14=((D1+D2)mod1014)× 1 0-14=I.□

Note.According to Proposition 1,we can design a chosen plaintext attack,in which the chosen plain image satisfies the conditions of Proposition 1,the parameterJcan be recovered from the ciphertext of the chosen plain image.

3.2 Chosen plaintext attack

According to the analysis above,a chosen plaintext attack (CPA)is proposed in this subsection.The goal of the attack is to recover the parameterJinstead of secret key,and then any ciphered image can be correctly recovered with the parameterJ.The details of CPA are shown as follows.

(1)Recover the key parameterJ

(1.1)Construct a plain imageQ= (qi,j)N×H,whereNis the bytes number of secret keyK,qi,j=1for alli=1,2,…,L,j=1,2,…,H.InputQ= (qi,j)N×Hinto encryption machine,obtain the ciphered imageCT= (cti,j)N×H.

(1.2)CalculateCT′= (cti′,j)N×HwithCT= (cti,j)N×Hbyct'i,j+1=cti,j+1⊕ct'i,j,ct'i+1,1=cti+1,1⊕ct'i,1,i= 1,2,…,H-1,j= 1,2,…,L-1.

(1.3)Extract pixels’ values from fixed position ofand denote them bythen recover the parameterI′=0.a1…a8.So obtainJ=I′=0.a1…a8according to Proposition 1.

(2)Recover any ciphered image with key parameterJ：

(2.1)CalculateCW×Vwithbyj= 1,2,…,V-1.

(2.2)Extract pixels’ values from fixed position ofdenote them byb1,…b8,and constructI=0.b1…b8.

(2.3)Calculate the initial valueof Tent map withIandJ：

(2.4)Iterate Tent map with initial valuefor 200 times,obtain the chaotic sequence.

Note.According to Proposition 1,we know thatJ=I′=0.a1…a8,so initial valuex0obtained by the attack is correct.Therefore any ciphered image can be correctly recovered.

Although,to resist the CPA above,the cryptology designer could modify the encryption algorithm easily by refusing to encrypt the plain image whose row number equals to the number of secret key bytes.Security problem still exists because the quantification algorithmQ(M)=Q(m1,m2,…,mn)deals with the value '0' improperly.According to the procedure of quantification algorithm,D1=m1⊗m2⊗…⊗mn.Ifmiequals to 0,thenD1=m1⊗m2⊗…⊗mi⊗mi+1⊗…⊗mn=m1⊗m2⊗…⊗0⊗mi+1⊗…⊗mn=c⊗mi+1⊗…⊗mn,wherecis a constant number.So another more complicated chosen plaintext attack algorithm can be designed.

4 Improvement of Luo algorithm

From the analyses in Section 3,Luo algorithm mainly has several weaknesses：(1)The parameterIcan be obtained,and leaks part information of secret key.Especially,when plain image satisfies the conditions of Proposition 1,the key parameterJequals toI,which means that the information of secret key is leaked completely.(2)The inverse operation of the last step of Luo algorithm (step (7))can be performed without secret key,so the step has no validity for security.(3)The quantification algorithm of Luo algorithm deals with the value ‘0’ improperly.In order to solve the above problems,an improvement of Luo algorithm is proposed in the section.The improved algorithm is proposed after the modification of quantification algorithm.

4.1 Improvement of quantification algorithm

In the improvement of quantification algorithm,irrational numberpjis introduced whenmi=0,in order to overcome the weakness that the quantification algorithm of Luo algorithm deals with the value ‘0’ improperly.

4.2 Improvement of Luo algorithm

In the improvement of Luo algorithm,the chaotic system,the control parameter and the secret key are the same as the original Luo algorithm.Letbe the secret key,be the plain image of sizewhere pixelThe improved Luo algorithm is described below：

(2)Iterate Tent map with initial valuefornbtimes(nbis a large constant integer negotiated by encryption and decryption parties)to avoid the non-randomness,continue to iterate Tent map and obtain a chaotic sequence,whereis the maximum significant number of operations when implementation of encryption algorithm performed under finite precision operations,for examplenv=15.

(3)Calculate the parameterIandJwith the new quantification algorithm in section 4.1.That isand

(4)Calculate another initial valuex0of Tent map with Eq.(5).

Iterate Tent map with initial valuex0fornctimes (ncis a large constant negotiated by encryption and decryption parties),and continue to iterate Tent map and obtain a chaotic sequenceoflength (is the positive integer negotiated in advance,for examplenp=8).

(6)ConvertP= (pi,j)L×Hinto a one-dimensional vectorP=(p0,p1,…,pL×H-1),and then diffuse the pixel values with Eq.(6),denote the result of diffusion asQ= (q0,q1,…,qL×H-1).

wherei= 0,1,…,L×H-1,＜＜is left cyclic shift operation.ConvertQ= (q0,q1,…,qL×H-1)into a two-dimensional matrixQ= (qi,j)L×H.

(9)CalculateT= (t0,…tL+H-1)with chaotic sequenceproduced in step (1),whereti=～xu+i⋅256,and the ciphertextC= (ci,j)L×Hcan be obtained by Eq.(7).

Decryption procedure is the inverse procedure of encryption.

In the improved algorithm,another chaotic sequence,generated with initial value(is calculated from secret key),is introduced.The first part ofis used to produce the embedding positions of key parameterI,as a result,the positions are determined by secret key,and the attacker cannot getIwithout secret key,which guards against the information leakages of secret key.The second part ofis used to diffuse the pixel values (in Step (9)),thus the attacker can’t reverse Step (9)without secret key,which is useful to resist statistical analysis attacks and differential attacks.In summary,the improved algorithm is more secure than the original Luo algorithm.

5 Experiments

In this section,the correctness of chosen plaintext attack on Luo algorithm is tested,and experiments on the improved algorithm is carried out.Experiments are performed with double precision floating point numbers represented by 64 bits specified in IEEE on the PC in the Matlab2013a environment.

5.1 Experiments on CPA

According to section 3,CPA is proposed on Luo algorithm.Correctness of the attack is verified by experiments below.

Luo algorithm is first implemented,where secret keyKeyis 64 bytes generated randomly,control parameter of Tent map is 0.76589,and the embedding positions of parameterIareFig.1(a)of size 512×512is encrypted with Luo algorithm,and the ciphered image is shown in Fig.1(b).

Figure1:Plain image and its ciphered image

Figure2:Chosen image and its ciphered image

CPA on Luo algorithm is then implemented with chosen plain image of 64×64(shown in Fig.2(a)).According to the procedure of CPA,Fig.2(a)is encrypted with Luo algorithm and the ciphered image is shown in Fig.2(b),then key parameterJis obtained 0.025167271329850.With key parameterJ,the plain image of any ciphered image encrypted with Luo algorithm can be correctly recovered.The ciphered image in Fig.1(b)is taken as an example,and the recovered plain image is shown in Fig.3.It is clear that the chosen plaintext attack in Section 3 is correct.

Figure3:Result of chosen plaintext attack

5.2 Experiments on improved algorithm

Experimental results on improvement are carried out in this section.In the experiments,secret keyKeyis 64 bytes generated randomly,control parameter of Tent map is 0.76589.

The plain and ciphered image is shown in Fig.4(a)and Fig.4(b)respectively.The histogram of plain image is shown in Fig.5(a),and that of ciphered image is shown in Fig.5(b).It is obvious that the histogram of ciphered image has a more uniform distribution.

Figure4:Plain and ciphered image with improved algorithm

Figure5:Histogram of plain image and ciphered image with improved algorithm

(1)Statistical analysis

Generally,high correlation exists among adjacent pixels for natural images in horizontal,vertical and diagonal directions.Therefore,the correlation between two adjacent pixels should be reduced in the ciphered image to withstand statistical attack.The correlation can be measured by correlation coefficient,which can be calculated by Eq.(8).

wherexandyare gray-scale values of two adjacent pixels,and,

It is expected that the correlation coefficient of plain image should be close to 1 while that of the ciphered image should be close to 0.

In experiments,4096 pairs of two adjacent pixels of image in three directions are randomly selected for the calculation of the correlation coefficients.

Taking image “Deer” (Fig.4(a))and its ciphered image (Fig.4(b))as an example,the distributions of randomly selected 4096 pairs of two adjacent pixels in three directions are shown in Fig.6 respectively.And then correlation coefficients of plain and ciphered image are calculated.The correlation coefficients of plain image for horizontally,vertically and diagonally adjacent pixels are 0.948904,0.979602 and 0.929812 respectively;and those of ciphered image are -0.003246,-0.034536 and -0.011568 respectively.According to the results,we find that the correlation coefficients between the pixels in three directions after encryption by with the improved algorithm are greatly reduced,and the correlation is destroyed to a great extent.

Figure6:Correlation distributions of adjacent pixels in plain and ciphered images(2)Key sensitivity test

For key sensitivity test,we make a tiny change in the secret key,change one bit of the secret key and keep other parameters unchanged,then decrypt the ciphered image with the changed key.The experimental results are shown in Fig.7.Decryption result with the changed key is shown in Fig.7(a)and difference between decryption with the changed and original key is shown in Fig.7(b).The rate of different pixels in the two images is about 93%,which means that nothing can be recovered as long as the attacker has tiny error of secret key.Therefore the improved algorithm is sensitive to the change of secret key.

Figure7:Key sensitivity test

6 Conclusions

In this paper,we study the security weaknesses of Luo algorithm,important information leaking of the secret key is found because a key parameterIcan be extracted after an inverse operation.And it is also a weakness by substituting zero with constant in quantification algorithm.Based on the weaknesses,CPA attack on the cryptosystem is proposed.Meanwhile,to solve the problems,an improvement is proposed after modifying the quantification algorithm.Finally,experiments and analyses show the validity of chosen plaintext attack and the security of improved algorithm.

Acknowledgement:The work described in this paper was partially supported by the National Natural Science Foundation of China (Grant No.61601517),basic and advanced technology research project of Henan Province,China (Grant No.2014302703).