| Title:
|
Edon-$\Cal R (256,384,512)$ -- an efficient implementation of Edon-$\Cal R$ family of cryptographic hash functions (English) |
| Author:
|
Gligoroski, Danilo |
| Author:
|
Knapskog, Svein Johan |
| Language:
|
English |
| Journal:
|
Commentationes Mathematicae Universitatis Carolinae |
| ISSN:
|
0010-2628 (print) |
| ISSN:
|
1213-7243 (online) |
| Volume:
|
49 |
| Issue:
|
2 |
| Year:
|
2008 |
| Pages:
|
219-239 |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
hash function |
| Keyword:
|
Edon--${\Cal R}$ |
| Keyword:
|
quasigroup |
| MSC:
|
05B05 |
| MSC:
|
20N05 |
| MSC:
|
68P30 |
| MSC:
|
94A60 |
| idZBL:
|
Zbl 1201.94084 |
| idMR:
|
MR2426887 |
| . |
| Date available:
|
2009-05-05T17:10:53Z |
| Last updated:
|
2013-09-22 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/119717 |
| . |
| Reference:
|
[1] Belousov V.D.: Osnovi teorii kvazigrup i lup.Nauka, Moskva, 1967. MR 0218483 |
| Reference:
|
[2] Bernstein D.: Salsa20.eSTREAM - ECRYPT Stream Cipher Project, Report 2005/025, http://www.ecrypt.eu.org/stream. |
| Reference:
|
[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. |
| Reference:
|
[4] Carter G., Dawson E., Nielsen L.: A latin square version of DES.in Proc. Workshop of Selected Areas in Cryptography, Ottawa, Canada, 1995. |
| Reference:
|
[5] Cooper J., Donovan D., Seberry J.: Secret sharing schemes arising from Latin squares.Bull. Inst. Combin. Appl. 12 (1994), 33-43. MR 1301402 |
| Reference:
|
[6] Dénes J., Keedwell A.D.: A new authentication scheme based on Latin squares.Discrete Math. 106/107 (1992), 157-161. MR 1181910, 10.1016/0012-365X(92)90543-O |
| Reference:
|
[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. Zbl 1145.94436, MR 2237321 |
| Reference:
|
[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. |
| Reference:
|
[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 |
| Reference:
|
[10] DesignTheory.org,: http://designtheory.org/.. |
| Reference:
|
[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}. |
| Reference:
|
[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). |
| Reference:
|
[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. Zbl 1104.68043, MR 2147510 |
| Reference:
|
[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 |
| Reference:
|
[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. MR 1227793, 10.1007/3-540-46416-6_2 |
| Reference:
|
[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 |
| Reference:
|
[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. |
| Reference:
|
[18] Lucks S.: Design principles for iterated hash functions.Cryptology ePrint Archive, report 2004/253. |
| Reference:
|
[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 |
| Reference:
|
[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 |
| Reference:
|
[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. Zbl 0824.05010, MR 1346877 |
| Reference:
|
[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 |
| Reference:
|
[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. Zbl 1044.00002, MR 1725200 |
| Reference:
|
[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 |
| Reference:
|
[25] Shannon C.E.: Communication theory of secrecy systems.Bell System Tech. J. 28 (1949), 656-715. MR 0032133, 10.1002/j.1538-7305.1949.tb00928.x |
| Reference:
|
[26] Thomsen S.S.: Personal communication.May 2007. |
| Reference:
|
[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 |
| . |
