Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
hash function; Edon--${\Cal R}$; quasigroup
hash function; Edon--${\Cal R}$; quasigroup
Summary:
We have designed three fast implementations of a recently proposed family of hash functions Edon--$\Cal R$. They produce message digests of length $n=256, 384, 512$ bits and project security of $2^{\frac{n}{2}}$ hash computations for finding collisions and $2^{n}$ hash computations for finding preimages and second preimages. The design is not the classical Merkle-Damg\aa rd but can be seen as wide-pipe iterated compression function. Moreover the design is based on using huge quasigroups of orders $2^{256}$, $2^{384}$ and $2^{512}$ that are constructed by using only bitwise operations on 32 bit values (additions modulo $2^{32}$, XORs and left rotations). Initial Reference C code achieves processing speeds of 16.18 cycles/byte, 24.37 cycles/byte and 32.18 cycles/byte on x86 (Intel and AMD microprocessors). In this paper we give their full description, as well as an initial security analysis.
References:
[1] Belousov V.D.: Osnovi teorii kvazigrup i lup. Nauka, Moskva, 1967. MR 0218483
[2] Bernstein D.: Salsa20. eSTREAM - ECRYPT Stream Cipher Project, Report 2005/025, http://www.ecrypt.eu.org/stream
[3] Berson T.A.: Differential Cryptanalysis Mod $2^{32}$ with Applications to MD5. in Advances in Cryptology - EUROCRYPT '92, Lecture Notes in Comput. Sci. 658, 1993, pp.71-80.
[4] Carter G., Dawson E., Nielsen L.: A latin square version of DES. in Proc. Workshop of Selected Areas in Cryptography, Ottawa, Canada, 1995.
[5] Cooper J., Donovan D., Seberry J.: Secret sharing schemes arising from Latin squares. Bull. Inst. Combin. Appl. 12 (1994), 33-43. MR 1301402
[6] Dénes J., Keedwell A.D.: A new authentication scheme based on Latin squares. Discrete Math. 106/107 (1992), 157-161. DOI 10.1016/0012-365X(92)90543-O | MR 1181910
[7] Coron J.-S., Dodis Y., Malinaud C., Puniya P.: Merkle-Damgård revisited: How to construct a hash function. in Advances in Cryptology - CRYPTO 2005, Lecture Notes in Comput. Sci. 3621, Springer, Berlin, 2005. MR 2237321 | Zbl 1145.94436
[8] Damgård I.B.: Collision free hash functions and public key signature schemes. in Advances in Cryptology - EUROCRYPT 87, Lecture Notes in Comput. Sci. 304, Springer, Berlin, 1988, pp.203-216.
[9] Damgård I.B.: A design principle for hash functions. in Advances in Cryptology - CRYPTO 89, Lecture Notes in Comput. Sci. 435, Springer, New York, 1990, pp.416-427. MR 1062248
[10] DesignTheory.org,: http://designtheory.org/</b>
[11] Gligoroski D., Markovski S., Kocarev L.: Edon-${\Cal R}$, an infinite family of cryptographic hash functions. Second NIST Cryptographic Hash Workshop, University of California - Santa Barbara, August, 2006, http://www.csrc.nist.gov/pki/HashWorkshop/2006/Papers/ {GLIGOROSKI$_{-}$EdonR-ver06.pdf}.
[12] Gligoroski D.: On a family of minimal candidate one-way functions and one-way permutations. in print, International Journal of Network Security, ISSN 1816-3548, (see also ePrint archive http://eprint.iacr.org/2005/352.pdf for an early version of the paper).
[13] Joux A.: Multicollisions in iterated hash functions. Application to cascaded constructions. in M. Franklin, ed., Advances in Cryptology - CRYPTO 2004, Lecture Notes in Comput. Sci. 3152, Springer, Berlin, 2004, pp.306-316. MR 2147510 | Zbl 1104.68043
[14] Kelsey J., Schneier B.: Second preimages on $n$-bit hash functions for much less than $2^n$ work. in R. Cramer, ed., Advances in Cryptology - EUROCRYPT 2005, Lecture Notes in Comput. Sci. 3494, Springer, Berlin, 2005, pp.474-490. MR 2352205
[15] Lai X., Massey J.L., Murphy S.: Markov ciphers and differential cryptanalysis. in Advances in Cryptology - EUROCRYPT '91, Proceedings of the Workshop on the Theory and Application of Cryptographic Techniques (Brighton, April 1991), Lecture Notes in Comput. Sci. 547, Springer, Berlin, 1991, pp.17-38. DOI 10.1007/3-540-46416-6_2 | MR 1227793
[16] Lipmaa H., Moriai S.: Efficient algorithms for computing differential properties of addition. in Fast Software Encryption 2001, Lecture Notes in Comput. Sci. 2355, Springer, Berlin, 2002, pp.336-350. Zbl 1073.68635
[17] Lipmaa H., Wallén J., Dumas P.: On the additive differential probability of exclusive-or. in Fast Software Encryption 2004, Lecture Notes in Comput. Sci. 3017, Springer, Berlin, 2004, pp.317-331.
[18] Lucks S.: Design principles for iterated hash functions. Cryptology ePrint Archive, report 2004/253.
[19] Markovski S., Gligoroski D., Bakeva V.: Quasigroup string processing, Part 1. Makedon. Akad. Nauk Umet. Oddel. Mat.-Tehn. Nauk. Prilozi 20 1-2 (1999), 13-28. MR 1938525
[20] Markovski S., Gligoroski D., Bakeva V.: Quasigroup and hash functions. Discrete Mathematics and Applications, Sl. Shtrakov and K. Denecke, eds., Proceedings of the 6th ICDMA, Bansko, 2001, pp.43-50. MR 1928410
[21] McKay B.D., Rogoyski E.: Latin squares of order $10$. Electron. J. Comb. 2 (1995), http://ejc.math.gatech.edu:8080/Journal/journalhome.html MR 1346877 | Zbl 0824.05010
[22] Merkle R.: One way hash functions and DES. Advances in Cryptology - Crypto'89, Lecture Notes in Comput. Sci. 435, Springer, New York, 1990, pp.428-446. MR 1062249
[23] Rosen K.H., Michaels J.G., Gross J.L., Grossman J.W., Shier D.R.: Handbook of Discrete and Combinatorial Mathematics. ISBN 0-8493-0149-1, CRC Press, Boca Raton, Florida, 2000. MR 1725200 | Zbl 1044.00002
[24] Schnorr C.P., Vaudenay S.: Black Box Cryptanalysis of hash networks based on multipermutations. Advances in Cryptology - EUROCRYPT '94, Lecture Notes in Comput. Sci. 950, Springer, Berlin, 1995, pp.47-57. MR 1479648
[25] Shannon C.E.: Communication theory of secrecy systems. Bell System Tech. J. 28 (1949), 656-715. DOI 10.1002/j.1538-7305.1949.tb00928.x | MR 0032133
[26] Thomsen S.S.: Personal communication. May 2007.
[27] Wheeler D.J., Needham R.M.: TEA, a tiny encryption algorithm. Fast software encryption: second international workshop, Leuven, Belgium, December 1994, Proceedings, Lecture Notes in Comput. Sci. 1008, 1995, pp.363-366. Zbl 0939.94550
Search
Partner of
