ОБ УНИВЕРСАЛЬНОМ ДРЕВОВИДНОМ РЕЖИМЕ ВЫРАБОТКИ ХЭШ-КОДА
Аннотация
Классические подходы к построению режимов работы хэш-функций, основанные на использовании итеративных процедур, не позволяют обеспечить эффективную обработку больших объемов данных и не могут быть адаптированы к параллельным вычислительным архитектурам. Это касается как российского криптографического стандарта ГОСТ Р 34.11-2012, определяющего алгоритм и процедуру вычисления хэш-функции, так и многих других зарубежных стандартов (например, SHA-3). Отсутствие действующих стандартов в части режимов работы хэш-функций ГОСТ Р 34.11-2012 создает острую необходимость разработки отечественного стандарта параллелизуемого режима выработки хэш-кода. Настоящая статья посвящена исследованию и разработке новых режимов выработки хэш-кода, допускающих эффективное распараллеливание процесса вычислений и обеспечивающих криптографическую стойкость, удовлетворяющую современным требованиям. Данная работа продолжает исследования, проводимые авторами, и предлагает принципиально новый универсальный древовидный режим выработки хэш-кода («FT-режим»), построенный на основе l-арных деревьев хэширования и позволяющий применять в качестве механизма формирования узлов дерева любое сжимающее отображение. При этом стойкость режима полностью определяется стойкостью соответствующего сжимающего отображения. Так, в частности, для формирования узлов дерева хэширования, наряду с функциями сжатия и хэш-функциями, FT-режим допускает использование блочных шифров, подстановочных преобразований и т.д. В дополнение к этому FT-режим исключает основные функциональные недостатки известных древовидных режимов выработки хэш-кода, влияющие на их эксплуатационно-технические и криптографические качества. В рамках настоящих исследований вычислен ряд характеристик FT-режима, а также проведен сравнительный анализ временной и вычислительной трудоемкостей реализаций FT-режима и некоторых иностранных режимов древовидного хэширования, по результатам которого разработанный режим не уступает ни одному из рассмотренных.
Литература
[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
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Редакционная политика журнала основывается на традиционных этических принципах российской научной периодики и строится с учетом этических норм работы редакторов и издателей, закрепленных в Кодексе поведения и руководящих принципах наилучшей практики для редактора журнала (Code of Conduct and Best Practice Guidelines for Journal Editors) и Кодексе поведения для издателя журнала (Code of Conduct for Journal Publishers), разработанных Комитетом по публикационной этике - Committee on Publication Ethics (COPE). В процессе издательской деятельности редколлегия журнала руководствуется международными правилами охраны авторского права, нормами действующего законодательства РФ, международными издательскими стандартами и обязательной ссылке на первоисточник.
Журнал позволяет авторам сохранять авторское право без ограничений. Журнал позволяет авторам сохранить права на публикацию без ограничений.
Издательская политика в области авторского права и архивирования определяются «зеленым цветом» в базе данных SHERPA/RoMEO.
Все статьи распространяются на условиях лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная, которая позволяет другим использовать, распространять, дополнять эту работу с обязательной ссылкой на оригинальную работу и публикацию в этом журналe.
