Security Analysis Of Cryptosystem Based On Quasigroups

A quasigroup is a algebra (Q, *), where Q is a set,"*"is a binary operation onQ and the equations x ? a = b and a * y = b are uniquely solvable for every pair ofelements a,b∈Q.Using the operations of quasigroups, we can construct stream cipher which hasmany good natures including the higher speed of encryption, the good distributionof substrings in ciphertexts and the large key space. So compared with anothercipher systems, it can better meet the requires of the development of contemporaryinformation society.There are special concerns associated with the cryptosystems based on the quasi-group string transformation E(n) (that used in the candidate algorithms of the thirdround of the European stream cipher scheme, i.e. Edon-80) and the hash functionEdon-R (which is one of the first round candidates of the SHA-3 competition startedby the National Institute of Standards and Technology (NIST)). In recent years, theinvestigation on them has received a lot of attention.Regarding security of the E(n)-based cryptosystem, Smile Markovski et al. provedthat the"brute force attack"and"statistical kind of attacks"are not reasonable. Andthe cryptosystem is widely used in pseudo random number generators (PRNGs), All-Or-Nothing (AON) encryption and designing secure databases.However, because the probability distribution of the substrings of length l forl > n is not generally uniform, where the substrings are obtained by using E(n).There is some relationship between the substrings of length l for l > n in ciphertextsand substrings in plaintexts. This is just one object of study in this paper.In addition, we analyse cryptographic hash functions Edon-R as well in this paper.This algorithm is one of the first round candidates of the public competition startedby NIST, which selected a new cryptographic hash algorithm. So it has received anextensive attention of many cryptographers and some security cryptanalysises have been done on it. The ?rst cryptanalysis of Edon-R was made by Dmitry Khovratovichet al.. They veri?ed that this cipher can not resistant to preimage attack, which ismaintained using the meet-in-the-middle approach. The other cryptanalysis of Edon-R was made by Vlastimil Klima. He provided a method for enabling the Edon-R hashfunctions (for n=256, 512) to be easily attacked by using generic multicollisions andmultipreimages attacks, and small additional work factor will be used on them.However, it is much more di?cult to improve the design of Edon-R. We mustguarantee that the improved Edon-R can satisfy some security properties that arerequired by a hash function. So, Vlastimil Klima and Dmitry Khovratovich et al.can not give a corresponding improvement on Edon-R. In this paper, we analyse thedesign of Edon-R and give the corresponding improvement.The whole paper is divided into six chapters.Chapter 1 In this chapter, we introduce the backgrounds and developmentsof the E(n)-based cryptosystems and cryptographic hash function Edon-R, presentthe definition of quasigroup string transformation E(n) and the concept of a hashfunction.Chapter 2 In this chapter, we give the distribution of substrings of length lfor l > n in cryptosystems based on quasigroup string transformation E(n), and adetailed proof is also showed.Chapter 3 We mainly analyse the security of the E(n)-based cryptosystems inthis chapter. At first, we show that the chosen plaintext attack can partially breakthe cryptosystems, and give an algorithm for realizing the target. Then we analysethe complexity of the algorithm. And a corresponding improvement is presented aswell.Chapter 4 In this chapter, we give a simple description of Edon-R hash functionfirst. Then we mainly analyse the design of Edon-R, and present a fatal weakness onit. They will be used in chapter 5.Chapter 5 In this chapter, we give an improvement of Edon-R hash functionbased on the analysis showed in Chapter 4. And we proof that the improved Edon-R has some strong security natures, such as to be resistant on preimage attack andmulticollision attack.Chapter 6 In this chapter, we summarize the main results of this paper.