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

Антон Миколайович Олексійчук, Катерина Вікторівна Король

Анотація


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

Ключові слова


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

Посилання


Бабаш А.В. Решение автоматных уравнений с искажениями в функции перехода автомата // Проблемы передачи информации. — 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.

Damgard IB. 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,

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. — SpringerVerlag, 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-35.

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. Applica¬tion. 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.

Damgard 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,

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.


Повний текст: PDF

Посилання

  • Поки немає зовнішніх посилань.


ISSN 2410-7840 (Online), ISSN 2221-5212 (Print)

Ліцензія Creative Commons
Цей твір ліцензовано за ліцензією Creative Commons Із зазначенням авторства - Некомерційна - Без похідних творів 3.0 Неадаптована

РИНЦ SSM WorldCat BASE Національна бібліотека ім. Вернадського Науково-технічна бібліотека НАУ Ulrich's Periodicals Directory

Ulrich's Periodicals Directory