Edon- ℛ ( 256 , 384 , 512 ) – an efficient implementation of Edon- ℛ family of cryptographic hash functions

Danilo Gligoroski; Svein Johan Knapskog

Commentationes Mathematicae Universitatis Carolinae (2008)

  • Volume: 49, Issue: 2, page 219-239
  • ISSN: 0010-2628

Abstract

top
We have designed three fast implementations of a recently proposed family of hash functions Edon– ℛ . They produce message digests of length n = 256 , 384 , 512 bits and project security of 2 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å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.

How to cite

top

Gligoroski, Danilo, and Knapskog, Svein Johan. "Edon-$\mathcal {R} (256,384,512)$ – an efficient implementation of Edon-$\mathcal {R}$ family of cryptographic hash functions." Commentationes Mathematicae Universitatis Carolinae 49.2 (2008): 219-239. <http://eudml.org/doc/252558>.

@article{Gligoroski2008,
abstract = {We have designed three fast implementations of a recently proposed family of hash functions Edon–$\mathcal \{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å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.},
author = {Gligoroski, Danilo, Knapskog, Svein Johan},
journal = {Commentationes Mathematicae Universitatis Carolinae},
keywords = {hash function; Edon–$\{\mathcal \{R\}\}$; quasigroup; hash function; Edon-; quasigroup},
language = {eng},
number = {2},
pages = {219-239},
publisher = {Charles University in Prague, Faculty of Mathematics and Physics},
title = {Edon-$\mathcal \{R\} (256,384,512)$ – an efficient implementation of Edon-$\mathcal \{R\}$ family of cryptographic hash functions},
url = {http://eudml.org/doc/252558},
volume = {49},
year = {2008},
}

TY - JOUR
AU - Gligoroski, Danilo
AU - Knapskog, Svein Johan
TI - Edon-$\mathcal {R} (256,384,512)$ – an efficient implementation of Edon-$\mathcal {R}$ family of cryptographic hash functions
JO - Commentationes Mathematicae Universitatis Carolinae
PY - 2008
PB - Charles University in Prague, Faculty of Mathematics and Physics
VL - 49
IS - 2
SP - 219
EP - 239
AB - We have designed three fast implementations of a recently proposed family of hash functions Edon–$\mathcal {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å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.
LA - eng
KW - hash function; Edon–${\mathcal {R}}$; quasigroup; hash function; Edon-; quasigroup
UR - http://eudml.org/doc/252558
ER -

References

top
  1. Belousov V.D., Osnovi teorii kvazigrup i lup, Nauka, Moskva, 1967. MR0218483
  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. (1994) MR1301402
  6. Dénes J., Keedwell A.D., 10.1016/0012-365X(92)90543-O, Discrete Math. 106/107 (1992), 157-161. (1992) MR1181910DOI10.1016/0012-365X(92)90543-O
  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. Zbl1145.94436MR2237321
  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. MR1062248
  10. DesignTheory.org,, http://designtheory.org/, . 
  11. Gligoroski D., Markovski S., Kocarev L., Edon- ℛ , 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/ GLIGOROSKIEdonR-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. Zbl1104.68043MR2147510
  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. MR2352205
  15. Lai X., Massey J.L., Murphy S., 10.1007/3-540-46416-6_2, 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. MR1227793DOI10.1007/3-540-46416-6_2
  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. Zbl1073.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. (1999) MR1938525
  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. MR1928410
  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. (1995) Zbl0824.05010MR1346877
  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. MR1062249
  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. Zbl1044.00002MR1725200
  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. MR1479648
  25. Shannon C.E., 10.1002/j.1538-7305.1949.tb00928.x, Bell System Tech. J. 28 (1949), 656-715. (1949) MR0032133DOI10.1002/j.1538-7305.1949.tb00928.x
  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. Zbl0939.94550

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.