Research And Applications On Analysis Methods Of Chaotic Ciphers

We find a new law of information leaking out. We find that for each clock i, all possibleinputs (and the parameter-formed key) of a chaotic map at the i-th clock which can produce thekey stream forms an union of intervals, and the probability that each interval includes anequivalent solution is very high for many-to-one chaotic maps, meanwhile, the length ofintervals are decreased exponentially as the clock i decrease. Based on the new law ofinformation leaking out, an inversion and compression attack to iterative chaotic ciphers isproposed for the first time. Under some conditions, the success rate of the attack is 1 and thecomputational complexity, the memory complexity and the data complexity are linear in thelength of key. 100 experiments to the chaotic spreading sequences algorithm, presented by LiaoNi-huan etc in 2006, are done for 64 bits keys at a 2.5GHz of Pentium 4 PC. Each experimentjust costs about 0.11 second in average, which implies the correctness and validity of our attackalgorithm. Comparison with the known attack to chaotic ciphers, the inversion and compressionattack is the first general attack that the complexity is linear in the length of key.As the inversion and compression attack includes the question relating to solving thepreimage from image of function, a subdivision algorithm for solving preimage of function withbounded derivative based on Lagrange mean value theorem is proposed firstly. Sufficientcondition which minimizes the upper bound of computational complexity of subdivisionalgorithm is presented. The computational complexity of this algorithm is reduced fromexponential order to linear order and the success rate is 1.Then we analyze three chaotic stream ciphers and find that all of them are insecure.Composite Chaotic Pseudo-Random Sequence Encryption Algorithm (for short CCPRSEA),proposed by YUAN Chun etc, is alalysed deeply. Based on analyzing the linear congruentalgorithm on a prime field of CCPRSEA, the chaotic sequence is gained. Further more atally-degree-based and function-inverting-based divide-and-conquer attack algorithm is given byusing the information leak of the chaotic map itself. When base=10 and d=3, the success rate ofthe attack algorithm is 0.9827 and the complexity is 2. The experiment indicates that it justcosts 8 hours and 35 minutes for attacking all keys of CCPRSEA in 2.5GHz of Pentium 4 PC.For the chaos-based feedback cryptographic scheme, a divide-and-conquer attack algorithmagainst it is proposed by using the incompleteness of which the key information diffuses inkeystreams. The complexity of the attack algorithm is 2 and the success rate is 1. The decreaseof key entropy is 235bits.The chaos sequence-based image encryption and decryption algorithm is a shift cipher in essentially, and a known plaintexts attack is proposed. For a N₁×N₂ plain image, thecomputational complexity is O(N₁+N₂). From our analysis in theory and our experiment, thisimage encryption algorithm is insecure.We analyze two chaos-based watermarking algorithms and find that they are insecure.The novel robust content-based watermarking for image algorithm is proved to be insecureunder the known-plaintext attack. An attack algorithm to obtain the equivalent key is given.When the original image contain N₁×N₂ pixels, the complexity of the attack is less thanO(N₁×N₂/4).An in-depth analysis for the resisting cropping robust watermarking algorithm based onchaotic map is made. For two different choosing of key spaces of the watermarking algorithm,two chosen-plaintext attacks are proposed respectively. The data complexities of these twoattacks are 1 cover image and N₁×N₂ watermark images, and the computional complexities are 1and N₁×N₂+1 computations of watermarking algorithm respectively and the success rates areboth 1. From our analysis in theory and our experiments, this watermarking algorithm isinsecure.