ON THE UNIVERSAL TREE MODE OF HASH CODE GENERATION
Abstract
Classical approaches to the construction of hash function modes, based on the using of iterative procedures, do not allow efficient processing of large amounts of data and can’t be adapted to parallel computing architectures. It applies to both the Russian cryptographic standard GOST R 34.11-2012, which determines the algorithm and procedure for calculating the hash function, as well as many other foreign standards (for example, SHA-3). The absence of standards for parallelized modes for the hash functions of GOST R 34.11-2012 creates an urgent need for the development of the domestic standard of the parallelized mode of hash code. This article is devoted to the research and development of new modes of hash code generation that allow efficient parallelization of the computation process and provide cryptographic resistance satisfying modern requirements. This work continues the research carried out by the authors, and offers a fundamentally new tree mode of hash code generation ("FT-mode"), based on l-ary hash trees and allowed to use any compression mapping for a mechanism of forming tree nodes. The resistance of the mode is completely determined by the resistance of the corresponding compressive mapping. In particular, the FT-mode allows using block ciphers and substitution transformations to form nodes of a hash tree along with compression functions and hash functions. In addition, the FT-mode excludes the main functional disadvantages of the known tree modes of hash code generation that affect their operational, technical and cryptographic quality. Within the framework of the present research a number of characteristics of FT-mode are calculated, and a comparative analysis of the time and computational complexity of implementations of FT-mode and some foreign tree hash modes is carried out. The corresponding results showed that the developed mode is not inferior to any of the considered modes.
References
[2] Dourado E., Brito J. Cryptocurrency. The New Palgrave Dictionary of Economics, Online Edition, 2014. 10 p. Available at: https://www.mercatus.org/system/files/cryptocurrency-article.pdf (accessed 11.04.2018).
[3] Reshevsky M. Gold fever ΧΧΙ century. Computer Bild. 2011; 17:64-69. (In Russian)
[4] Ammous S. The Bitcoin Standard: The Decentralized Alternative to Central Banking. New York: John Wiley and Sons Inc, 2018. Pp. 304.
[5] Aumasson J.-P., Neves S., Wilcox-O'Hearn Z., Winnerlein C. BLAKE2 – fast secure hashing, 2013. Available at: https://blake2.net (accessed 11.04.2018).
[6] Bertoni G., Daemen J., Peeters M., Van Assche G. Sakura: a flexible coding for tree hashing. Cryptology ePrint Archive. Report 2013/231, 2013. Available at: http://eprint.iacr.org (accessed 11.04.2018).
[7] Ferguson N., Lucks S., Schneier B., Whiting D., Bellare M., Kohno T., Callas J. The Skein Hash Function Family. Schneier on Security. Version 1.3. – 1 October, 2010. 92 p. Available at: https://www.schneier.com/academic/skein (accessed 11.04.2018).
[8] Kaminsky A., Radziszowski S.P. A case for a parallelizable hash. Proceedings of 2008 IEEE Military Communications Conference MILCOM 2008, San Diego, CA, 2008. Pp. 1-7. DOI: 10.1109/MILCOM.2008.4753182
[9] Rivest R.L., Agre B., Bailey D.V., Crutchfield C., Dodis Y., Fleming K.E., Khan A., Krishnamurthy J., Lin Y., Reyzin L., Shen E., Sukha J., Sutherland D., Tromer E., Yin Y.L. The MD6 hash function – a proposal to NIST for SHA-3, Submission to NIST, October, 2008. Available at: http://groups.csail.mit.edu/cis/md6 (accessed 11.04.2018).
[10] Dali F.A., Mironkin V.O. Review of approaches to the construction of tree-like modes of operation of some hash functions. Information Security Problems. Computer Systems. 2017; 2:46-55. (In Russian)
[11] Dali F.A., Mironkin V.O. On some models of tree hashing. Obozrenie prikladnoi i promyshlennoi matematiki = Applied and Industrial Mathematics Review. 2017; 24(4):241-244. (In Russian)
[12] Dali F.A., Mironkin V.O. On the tree modes of hash functions. Information Security Problems. Computer Systems. 2018; 1:113-121. (In Russian)
[13] Merkle R.C. Secrecy, authentication, and public key systems. PhD thesis, UMI Research Press, 1982. 104 p.
[14] Dali F.A., Mironkin V.O. On probabilistic characteristics of a single class of tree hashing models. Obozrenie prikladnoi i promyshlennoi matematiki = Applied and Industrial Mathematics Review. 2016; 23(4):345-347. (In Russian)
[15] Mironkin V.O. Urusov M.I. On collisions of Merkle trees. Obozrenie prikladnoi i promyshlennoi matematiki = Applied and Industrial Mathematics Review. 2018; 25(1):84-88. (In Russian)
[16] Bertoni G., Daemen J., Peeters M., Van Assche G. Keccak. Johansson T., Nguyen P.Q. (eds). Advances in Cryptology – Eurocrypt 2013. Eurocrypt 2013. Lecture Notes in Computer Science. Vol. 7881. Springer, Berlin, Heidelberg, 2013. DOI: 10.1007/978-3-642-38348-9_19
[17] Bertoni G., Daemen J., Peeters M., Van Assche G. Sufficient conditions for sound tree and sequential hashing modes. International Journal of Information Security. 2014; 13(4):335-353. DOI: 10.1007/s10207-013-0220-y
[18] Gapanovich D.A., Chubarikov V.N. Hash algorithm with the controlling tree-like structure and the method of its implementation on parallel architectures. Modern Information Technology and IT-education. 2017; 13(1):35-42. DOI: 10.25559/SITITO.2017.1.489 (In Russian)
[19] Mineev M.P., Chubarikov V.N. Lectures on arithmetic questions of cryptography. Moscow: Scientific and Publishing Center «Ray», 2014. 224 p. (In Russian)
[20] Chapweske J., Mohr G. Tree Hash EXchange format (THEX), 2003. Available at: http://adc.sourceforge.net/draft-jchapweske-thex-02.html (accessed 11.04.2018).
[21] Dodis Y., Reyzin L., Rivest R., Shen E. Indifferentiability of permutation-based compression functions and tree-based modes of operation, with applications to MD6. O. Dunkelman ed. Fast So ware Encryption. Lecture Notes in Computer Science. Vol. 5665, Springer-Verlag Berlin Heidelberg, 2009. Pp. 104-121. DOI: 10.1007/978-3-642-03317-9
[22] Sarkar P., Schellenberg P.J. A parallelizable design principle for cryptographic hash functions. Cryptology ePrint Archive, Report 2002/031, 2002. Available at: http://eprint.iacr.org (accessed 11.04.2018).
[23] Bellare M., Guerin R., Rogaway P. XOR MACs: new methods for message authentication using finite pseudorandom functions. D. Coppersmith ed. Advances in Cryptology CRYPTO ’95. Proceedings of the 15th Annual International Cryptology Conference, Santa Barbara, California, USA, August 27–31, 1995. Springer-Verlag Berlin Heidelberg, 1995. Pp. 15-28. DOI: 10.1007/3-540-44750-4
[24] Bellare M., Micciancio D. A New Paradigm for Collision-free Hashing: Incrementality at Reduced Cost. W. Fumy. Advances in Cryptology — EUROCRYPT ’97. Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques Konstanz, Germany, May 11–15, 1997. Springer, Berlin, Heidelberg, 1997. Pp. 163-192. DOI: 10.1007/3-540-44750-4
[25] Barreto P., Rijmen V. The Whirlpool Hashing Function. NESSIE Report, Revised, May 2003.
[26] Damgard I.B. A design principle for hash functions. G. Brassard ed. Advances in Cryptology Crypto ’89. Conference proceedings. LNCS, Vol. 435, Springer, New York, NY, 1989. Pp. 416-427. DOI: 10.1007/0-387-34805-0
[27] Maurer U., Renner R., Holenstein C. Indifferentiability, Impossibility Results on Reductions, and Applications to the Random Oracle Methodology. M. Naor ed. Theory of Cryptography. TCC 2004. Lecture Notes in Computer Science. Vol. 2951, Springer, Berlin, Heidelberg, 2004. Pp. 21-39. DOI: 10.1007/978-3-540-24638-1_2
This work is licensed under a Creative Commons Attribution 4.0 International License.
Publication policy of the journal is based on traditional ethical principles of the Russian scientific periodicals and is built in terms of ethical norms of editors and publishers work stated in Code of Conduct and Best Practice Guidelines for Journal Editors and Code of Conduct for Journal Publishers, developed by the Committee on Publication Ethics (COPE). In the course of publishing editorial board of the journal is led by international rules for copyright protection, statutory regulations of the Russian Federation as well as international standards of publishing.
Authors publishing articles in this journal agree to the following: They retain copyright and grant the journal right of first publication of the work, which is automatically licensed under the Creative Commons Attribution License (CC BY license). Users can use, reuse and build upon the material published in this journal provided that such uses are fully attributed.
