Розробка алгоритму хеш-функції на основі клітинних автоматів і теорії хаоса

Автор(и)

  • Юрій Георгійович Добровольський Чернівецький національний університет ім. Ю. Федьковича, Україна https://orcid.org/0000-0002-1248-3615
  • Георгій Валерійович Прохоров Чернівецький національний університет ім. Ю. Федьковича, Україна https://orcid.org/0000-0001-7810-2785
  • Марія Георгіївна Ганжело Чернівецький національний університет ім. Ю. Федьковича, Україна https://orcid.org/0000-0002-6312-740X
  • Дмитро Володимирович Ганжело Чернівецький національний університет ім. Ю.Федьковича, Україна https://orcid.org/0000-0002-0836-4568
  • Денис Володимирович Трембач Чернівецький національний університет ім. Ю.Федьковича, Україна https://orcid.org/0000-0001-8095-4186

DOI:

https://doi.org/10.15587/1729-4061.2021.242849

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

алгоритм хешування, теорія хаосу, клітинні автомати, функція стиснення, функція трансформації

Анотація

Захист інформації, надійність передачі даних, є сьогодні важливою складовою глобалізації інформаційних технологій. Тому пропонована робота присвячена висвітленню результатів проектування та розроблення стійкого до злому алгоритму, призначеного для забезпечення цілісності інформації, що передається і приймається засобами цифрової техніки і комп'ютерної інженерії. Для вирішення таких завдань використовуються криптографічні функції хешування. Зокрема, у розроблений циклічний алгоритм хешування внесено елементи детермінованого Хаосу. У дослідженні детально проаналізовані сильні і слабкі сторони відомих алгоритмів хешування. Показано, що вони мають певні недоліки. Основні з них, це велика кількість не збігів (відстаней Хемінга (Hamming (x, y) і наявність лавинного ефекту, які призводять до істотного зниження надійності та стійкості алгоритму до злому. Спроектований алгоритм хешування використовує ітеративну структуру Мерклі-Дамгарда, доповнену вхідним повідомленням до довжини кратної 512 біт. Додаткова обробка блоками по 128-біт використовує клітинні автомати зі змішаними правилами 30, 105 і 90, 150 і враховує залежність від вхідного повідомлення генерації початкового вектора. Це дозволяє половині з 10 тисяч пар довільних повідомлень мати відстань Хеммінга від 0 до 2. Запропонований алгоритм працює в чотири рази повільніше відомого сімейства «Безпечний хеш-алгоритм». Однак швидкість обчислення не є критичним вимогам, які ставляться до хеш-функції. Зменшення чутливості до лавинному ефекту дозволяє зменшити час генерації хеш-функції приблизно вдвічі. Оптимізація алгоритму, а також його тестування проводилося з використанням нових технологій мови програмування Java (версія 15). Наведено припущення і рекомендації щодо вдосконалення даного підходу до хешування даних.

Біографії авторів

Юрій Георгійович Добровольський, Чернівецький національний університет ім. Ю. Федьковича

Доктор технічних наук

Кафедра програмного забезпечення комп’ютерних систем

Георгій Валерійович Прохоров, Чернівецький національний університет ім. Ю. Федьковича

Кандидат фізико-математичних наук

Кафедра програмного забезпечення комп’ютерних систем

Марія Георгіївна Ганжело, Чернівецький національний університет ім. Ю. Федьковича

Кафедра програмного забезпечення комп’ютерних систем

Дмитро Володимирович Ганжело, Чернівецький національний університет ім. Ю.Федьковича

Кафедра програмного забезпечення комп’ютерних систем

Денис Володимирович Трембач, Чернівецький національний університет ім. Ю.Федьковича

Кафедра програмного забезпечення комп’ютерних систем

Посилання

  1. Toffoli, T., Margolis, N. (1987). Cellular Automata Machines. Cambridge: MIT Press. doi: http://doi.org/10.7551/mitpress/1763.001.0001
  2. Jeon, J.-Ch. (2013). Analysis of hash functions and cellular automata based schemes. International Journal of Security and Applications, 7 (3), 303–316. Available at: http://article.nadiapub.com/IJSIA/vol7_no3/28.pdf
  3. Paar, C., Pelzl, J. (2010). Understanding cryptography. Berlin-Heidelberg: Springer-Verlag. doi: https://doi.org/10.1007/978-3-642-04101-3
  4. Pasyeka, M., Pasieka, N., Bestylnyy, M., Sheketa, V. (2019). Analysis of the use of the highly effective implementation of the sha-512 hash functions for the development of software systems. Cybersecurity: Education, Science, Technique, 3 (3), 112–121. doi: http://doi.org/10.28925/2663-4023.2019.3.112121
  5. Kuznetsov, O. O., Horbenko, Yu. I., Onopriienko, V. V., Stelnyk, I. V., Mialkovskyi, D. V. (2019). The study of cryptographic hashing algorithms used in modern blockchain systems. Radiotekhnika, 3 (198), 54–74. doi: http://doi.org/10.30837/rt.2019.3.198.05
  6. Pro zatverdzhennia Polozhennia pro orhanizatsiiu zakhodiv iz zabezpechennia informatsiinoi bezpeky v bankivskii systemi Ukrainy (2017). Postanova Pravlinnia Natsionalnoho banku Ukrainy No. 95. 28.09.2017. Available at: https://zakon.rada.gov.ua/laws/show/v0095500-17#Text
  7. DSTU 7564: 2014 "Informatsionnye tekhnologii. Kriptograficheskaia zaschita informatsii. Funktsiia kheshirovaniia" (2014). Priniatii prikazom Ministerstva ekonomicheskogo razvitiia i torgovli Ukrainy No. 1431. 02.12.2014. Available at: https://usts.kiev.ua/wp-content/uploads/2020/07/dstu-7564-2014.pdf
  8. Tiwari, H., Asawa, K. (2012). A secure and efficient cryptographic hash function based on NewFORK-256. Egyptian Informatics Journal, 13(3), 199–208. doi: http://doi.org/10.1016/j.eij.2012.08.003
  9. El Moumni, S., Fettach, M., & Tragha, A. (2019). High throughput implementation of SHA3 hash algorithm on field programmable gate array (FPGA). Microelectronics Journal, 93, 104615. doi: http://doi.org/10.1016/j.mejo.2019.104615
  10. Hasheminejad, A., Rostami, M. J. (2019). A novel bit level multiphase algorithm for image encryption based on PWLCM chaotic map. Optik, 184, 205–213. doi: http://doi.org/10.1016/j.ijleo.2019.03.065
  11. Hao, W., Liming, Z., Haowei, M., Xingang, Z., Jinping, C. (2020). Perceptual Hash algorithm for GF-2 image using SIFT and SVD[J]. Bulletin of Surveying and Mapping, 8, 44–49. doi: https://doi.org/10.13474/j.cnki.11-2246.2020.0246
  12. Xue, Wang, Liu, Lv, Wang, Zeng. (2019). An RISC-V Processor with Area-Efficient Memristor-Based In-Memory Computing for Hash Algorithm in Blockchain Applications. Micromachines, 10 (8), 541. doi: http://doi.org/10.3390/mi10080541
  13. Li, Y. (2016). Collision analysis and improvement of a hash function based on chaotic tent map. Optik, 127 (10), 4484–4489. doi: http://doi.org/10.1016/j.ijleo.2016.01.176
  14. Tao, F., Qian, W. (2019). Image hash authentication algorithm for orthogonal moments of fractional order chaotic scrambling coupling hyper-complex number. Measurement, 134, 866–873. doi: http://doi.org/10.1016/j.measurement.2018.11.079
  15. Sodhi, G. K., Gaba, G. S., Kansal, L., Bakkali, M. E., Tubbal, F. E. (2019). Implementation of message authentication code using DNA-LCG key and a novel hash algorithm. International Journal of Electrical and Computer Engineering (IJECE), 9 (1), 352–358. doi: http://doi.org/10.11591/ijece.v9i1.pp352-358
  16. Sumagita, M., Riadi, I. (2018). Analysis of Secure Hash Algorithm (SHA) 512 for Encryption Process on Web Based Application. International Journal of Cyber-Security and Digital Forensics, 7 (4), 373. Available at: https://link.gale.com/apps/doc/A603050342/AONE?u=anon~26dfe3b7&sid=bookmark-AONE&xid=80bc955a
  17. Safaei Mehrabani, Y. (2018). Synthesis of an Application Specific Instruction Set Processor (ASIP) for RIPEMD-160 Hash Algorithm. International Journal of Electronics Letters, 7 (2), 154–165. doi: http://doi.org/10.1080/21681724.2018.1477182
  18. Mittelbach, A. Fischlin, M. (2021). The Theory of Hash Functions and Random Oracles. Springer International Publishing. doi: http://doi.org/10.1007/978-3-030-63287-8
  19. Georgacopoulou, C. (1986). An investigation of hashing algorithms and their performance. Bradford.
  20. Liu, Y. (2020). Modelling Urban Development with Geographical Information Systems and Cellular Automata. CRC Press. doi: http://doi.org/10.1201/9781420059908
  21. Ch, J. (2013). Analysis of hash functions and cellular automata based schemes. International Journal of Security and Applications, 7 (3), 303–316. Available at: http://article.nadiapub.com/IJSIA/vol7_no3/28.pdf
  22. Belfedhal, A. E., Faraoun, K. M. (2015). Building Secure and Fast Cryptographic Hash Functions Using Programmable Cellular Automata. Journal of Computing and Information Technology, 23 (4), 317–328. doi: http://doi.org/10.2498/cit.1002639
  23. Martinez, G. (2013), A Note on Elementary Cellular Automata Classification. Journal of Cellular Automata, 8 (3-4), 233–259. Available at: https://arxiv.org/pdf/1306.5577.pdf
  24. Vergili, I., Yucel, M. D. (2001). Avalanche and Bit Independence Properties for the Ensembles of Randomly Chosen n x n S-Boxes. Turkish Journal of Electrical Engineering and Computer Science, 9, 137–145. Available at: https://journals.tubitak.gov.tr/elektrik/issues/elk-01-9-2/elk-9-2-3-0008-1.pdf
  25. Mironov, I. (2005). Hash functions: Theory, attacks, and applications. Available at: https://www.microsoft.com/en-us/research/publication/hash-functions-theory-attacks-and-applications/
  26. Li, W., Packard, N. (1990). The Structure of the Elementary Cellular Automata Rule Space. Complex Systems, 4, 281–297.
  27. Wolfram, S. (2002). A New Kind of Science. Champaign: Wolfram Media, 1192.
  28. Wolfram, S. (2002). Cellular Automata and Complexity. Westview Press.
  29. Pieprzyk, J. (1993). Design of hashing algorithms. Springer-Verlag.
  30. Belfedhal, A. E., Faraoun, K. M. (2015). Building Secure and Fast Cryptographic Hash Functions Using Programmable Cellular Automata. Journal of Computing and Information Technology, 23 (4), 317–328. doi: http://doi.org/10.2498/cit.1002639
  31. Ostapov, S. E. Yevseiev, S. P., Korol, O. H. (2013). Tekhnolohii zakhystu informatsii. Kharkiv: Vyd. KhNEU, 476. Available at: http://kist.ntu.edu.ua/textPhD/tzi.pdf

##submission.downloads##

Опубліковано

2021-10-31

Як цитувати

Добровольський, Ю. Г., Прохоров, Г. В., Ганжело, М. Г., Ганжело, Д. В., & Трембач, Д. В. (2021). Розробка алгоритму хеш-функції на основі клітинних автоматів і теорії хаоса. Eastern-European Journal of Enterprise Technologies, 5(9 (113), 48–55. https://doi.org/10.15587/1729-4061.2021.242849

Номер

Том 5 № 9 (113) (2021): Інформаційно-керуючі системи

Розділ

Інформаційно-керуючі системи

Ліцензія

Авторське право (c) 2021 Yuriy Dobrovolsky, Georgy Prokhorov, Mariia Hanzhelo, Dmytro Hanzhelo, Denis Trembach

Creative Commons License

Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.

Закріплення та умови передачі авторських прав (ідентифікація авторства) здійснюється у Ліцензійному договорі. Зокрема, автори залишають за собою право на авторство свого рукопису та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons CC BY. При цьому вони мають право укладати самостійно додаткові угоди, що стосуються неексклюзивного поширення роботи у тому вигляді, в якому вона була опублікована цим журналом, але за умови збереження посилання на першу публікацію статті в цьому журналі.

Ліцензійний договір – це документ, в якому автор гарантує, що володіє усіма авторськими правами на твір (рукопис, статтю, тощо).
Автори, підписуючи Ліцензійний договір з ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР», мають усі права на подальше використання свого твору за умови посилання на наше видання, в якому твір опублікований. Відповідно до умов Ліцензійного договору, Видавець ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР» не забирає ваші авторські права та отримує від авторів дозвіл на використання та розповсюдження публікації через світові наукові ресурси (власні електронні ресурси, наукометричні бази даних, репозитарії, бібліотеки тощо).
За відсутності підписаного Ліцензійного договору або за відсутністю вказаних в цьому договорі ідентифікаторів, що дають змогу ідентифікувати особу автора, редакція не має права працювати з рукописом.
Важливо пам’ятати, що існує і інший тип угоди між авторами та видавцями – коли авторські права передаються від авторів до видавця. В такому разі автори втрачають права власності на свій твір та не можуть його використовувати в будь-який спосіб.