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

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

Vol. 16 No. 1 (2014)

Section

Articles

License

Authors who publish with this journal agree to the following terms:

  1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.

  2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.

  3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).