Безключові геш-функції регістрового типу

Authors

  • Антон Миколайович Олексійчук Інститут спеціального зв’язку та захисту інформації НТУУ «КПІ»
  • Катерина Вікторівна Король Донецький національний університет

DOI:

https://doi.org/10.18372/2410-7840.16.5395

Keywords:

безключова геш-функція, пошук колізій, скінченний автомат, нелінійний регістр зсуву, система автоматних рівнянь, MDx, SHA.

Abstract

Безключові геш-функції відносяться до найважливіших криптографічних примітивів і застосовуються в сучасних системах шифрування, автентифікації, цифрового підпису, генерації ключів тощо. Незважаючи на помітний прогрес у розробці різноманітних атак на “конкретні” геш-функції, розуміння закономірностей, що лежать в основі зазначених атак, визначення умов їх застосовності та розробка методів оцінювання їх ефективності є предметом активних подальших досліджень. Метою статті є встановлення загальних умов, що визначають практичну стійкість широкого класу геш-функцій, які базуються на регістрах зсуву, відносно атак, спрямованих на побудування колізій їх стискувальних функцій. Показано, що задача побудування колізій зводиться до розв’язання автоматних рівнянь відносно двійкових невідомих, які задовольняють певним обмеженням. При цьому множини всіх розв’язків таких рівнянь (без урахування обмежень) мають простий алгоритмічний опис, що дозволяє перелічувати ці розв’язки в режимі реального часу

Author Biography

Антон Миколайович Олексійчук, Інститут спеціального зв’язку та захисту інформації НТУУ «КПІ»

доктор технічних наук, професор Інституту спеціального зв’язку та захисту інформації НТУУ «КПІ»

References

Бабаш А.В. Решение автоматных уравнений с искажениями в функции перехода автомата // Проблемы передачи информации. – 2002. – Т. 38. – Вып. 3. – С. 62 – 71.

Балакин Г.В. О вероятностном подходе к решению систем уравнений с целочисленными неизвестными // Дискретная математика.  1995.  Т. 7.  Вып. 1.  С. 88  98.

Карпунин Г.А., Ермолаева Е.З. Оценки сложности поиска коллизий для хэш-функции RIPEMD // Прикладная дискретная математика. Приложение. – 2012. – № 5. – С. 43 – 44.

Фергюссон Н., Шнайер Б. Практическая криптография: Пер. с англ. – М.: “Вильямс”, 2005. – 424 с.

Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. – М.: Триумф, 2002. – 816 с.

Chabaud F., Joux A. Differential collision search attack on SHA-0 // Advances in Cryptology – CRYPTO’98, Proceedings. – Springer-Verlag, 1998. – P. 56 – 71.

Damgård IB. A design principle for hash function // Advances in Cryptology – CRYPTO’89, Proceedings. – Springer-Verlag, 1990. – P. 416 – 427.

ECRYPT II: Final hash function status report / http://www.ecrypt.eu.org/documents/D.SYM.11, 31 Jan., 2013.

Merkle R.C. On way hash function and DES // Advances in Cryptology – CRYPTO’89, Proceedings. – Springer-Verlag, 1990. – P. 428 – 436.

National Institute of Standards and Technology (NIST). FIPS-180-2: Secure Hash Standard, http://www.itl.nist.gov/fipspubs.

Pramstaller N., Rechberger C., Rijmen V. Exploiting coding theory for collision attacks on SHA-1 // Cryptography and Coding 2005, Proceedings. – Springer-Verlag, 2005. – P. 78 – 95.

Rijmen V., Oswald E. Update on SHA-1 // Topics in Cryptology. – CT-RSA, Proceedings. – Springer-Verlag, 2005. – P. 58 – 71.

Wang X., Lai X., Feng D., Chen H., Yu X. Cryptanalysis of the hash functions MD4 and RIPEMD // Advances in Cryptology – EUROCRYPT’2005, Proceedings. – Springer-Verlag, 2005. – P. 1 – 18.

Wang X., Yu H. How to break MD5 and other hash functions // Advances in Cryptology – EUROCRYPT’2005, Proceedings. – Springer-Verlag, 2005. – P. 19

Wang X., Yu H., Yin Y.L. Efficien collisions search attacks on SHA-0 // Advances in Cryptology – CRYPTO’2005, Proceedings. – Springer-Verlag, 2005. – P. 1 – 16.

Wang X., Yu H., Yin Y.L. Finding collisions in the full SHA-1 // Advances in Cryptology – CRYPTO’2005, Proceedings. – Springer-Verlag, 2005. – P. 17 – 36.

Babash A. V. Solving automaton equations with distortions in the automaton transition function. Problems of Information Transmission, 2002, vol. 38(3), pp. 218-226.

Balakin G. V. On a probabilistic approach to solving systems of equations with integer-valued unknowns, Discrete Mathematics and Applications, 1995, vol. 5(1), pp. 43–51.

Kapurnin G. A., Ermolaeva E. Z. Estimates of collision resistance comlexity for the hash function RIPEMD. Discrete Applied Mathematics. Application. 2012, № 5, pp. 43 – 44.

Ferguson N., Schneier B. Practical cryptography. John Wiley & Sons, 2003, 432 p.

Schneier B. Applied cryptography: Protocols, algorithms, and source code in C, 2nd Edition. John Wiley & Sons, 1995, 784 p.

Chabaud F., Joux A. Differential collision search attack on SHA-0. Advances in Cryptology – CRYPTO’98, Springer-Verlag, 1998, pp. 56 – 71.

Damgård I.B. A design principle for hash function. Advances in Cryptology – CRYPTO’89, Springer-Verlag, 1990, pp. 416 – 427.

ECRYPT II: Final hash function status report. http://www.ecrypt.eu.org/documents/D.SYM.11, 31 Jan., 2013.

Merkle R.C. On way hash function and DES. Advances in Cryptology – CRYPTO’89., Springer-Verlag, 1990, pp. 428 – 436.

National Institute of Standards and Technology (NIST). FIPS-180-2: Secure Hash Standard, http://www.itl.nist.gov/fipspubs.

Pramstaller N., Rechberger C., Rijmen V. Exploiting coding theory for collision attacks on SHA-1. Cryptography and Coding 2005, Springer-Verlag, 2005, pp. 78 – 95.

Rijmen V., Oswald E. Update on SHA-1. Topics in Cryptology. CT-RSA, Springer-Verlag, 2005, pp. 58 – 71.

Wang X., Lai X., Feng D., Chen H., Yu X. Cryptanalysis of the hash functions MD4 and RIPEMD. Advances in Cryptology – EUROCRYPT’2005, Springer-Verlag, 2005, pp. 1 – 18.

Wang X., Yu H. How to break MD5 and other hash functions. Advances in Cryptology – EUROCRYPT’2005, Springer-Verlag, 2005, pp. 19 – 35.

Wang X., Yu H., Yin Y.L. Efficien collisions search attacks on SHA-0. Advances in Cryptology – CRYPTO’2005, Springer-Verlag, 2005, pp. 1 – 16.

Wang X., Yu H., Yin Y.L. Finding collisions in the full SHA-1. Advances in Cryptology – CRYPTO’2005, Springer-Verlag, 2005, pp. 17 – 36.

Published

2014-03-24

Issue

Section

Articles