Сегментация древовидных структур данных и их параллельная обработка в методах аутентификации, основанных на кодировании в режиме сцепления блоков

Цель исследования. В задачах аутентификации групп сообщений, кодированных в режиме сцепления блоков, возникает необходимость формирования и обработки специфических древовидных структур. Содержимое таких структур, помимо информации о размещении данных во внутренней памяти вычислителей, описывает взаимное расположение сообщений в потоке данных между абонентами одноранговой сети. Данная информация необходима для выделения из всего потока сообщений в приёмник структурированного множества, для которого однозначно определён его источник. Использование подходов к сегментации древовидных структур позволяет распараллелить процессы добавления элементов в неё и поиска участков, соответствующих ошибке аутентификации.

Методы. В основе разбиения древовидной структуры на области, подлежащие модификации, и участки для анализа, лежит динамически формируемая из кодов аутентификации сообщений метрика – позиция конкретного сообщения в структурированном множестве сообщений, предаваемых от источника в приёмник. Значение данной метрики определяет расстояние от корня дерева, определяющее границу между двумя названными областями.

Результаты. За счёт изолирования модифицируемого и анализируемого участков древовидной структуры исключаются гонки процессов, реализующих независимые алгоритмы работы с ней. Показана возможность обнаружения ошибок аутентификации до получения последнего сообщения в структурированном множестве сообщений. В результате отпадает необходимость передачи тех сообщений группы, отправка которых предполагалась после момента обнаружения ошибки. Приведены формулы оценки среднего времени передачи множества сообщений при последовательной и параллельной реализации процедур формирования и обработки древовидной структуры, содержащей описатели поступающих в приёмник сообщений.  

Заключение. В работе показано, что параллельная реализация алгоритмов добавления элементов в древовидную структуру и алгоритма поиска участков, соответствующих ошибке, позволяет уменьшить среднее время передачи группы сообщений на 5 -12% по сравнению с последовательной реализацией указанных алгоритмов. Это снижает нагрузку на канал связи для целевого класса систем, использующих для аутентификации кодирование в режиме сцепления блоков.

1. Bellare M., Kilian J., Rogaway P. The security of the cipher block chaining message authentication code. M. // Journal of Computer and System Sciences. 2000 61(3): pp. 362-399 DOI: 10.1006/jcss.1999.1694

2. Iwata T., Kurosawa K. OMAC: one-key CBC MAC // Fast Software Encryption. 2003. P. 129 – 53.

3. Dworkin M. SP 800-38D: Recommendation for Block Cipher Modes of Operation: Galois/Counter Mode (GCM) and GMAC, 2007.

4. Dworkin M. Recommendatin for Block Cipher Modes of Operation: The CCM Mode for Authentication and Confidentiality // Nist Spec. Publ. 2004. Vol. 800. 38 р.

5. Stallings W. The advanced encryption standard // Cryptologia. 2002. Vol. 26. № 3. P. 165–188.

6. Black J. Authenticated Encryption // Encycl. Cryptogr. Secur. 2005. P. 11–21.

7. Black J., Rogaway P. CBC MACs for arbitrary-length messages: The three-key constructions // J. Cryptol. 2005. Vol. 18. № 2. P. 111–131.

8. IEEE Standard for Low-Rate Wireless Networks // IEEE Std 802.15.4-2020, pp.1800, 23 July 2020, doi: 10.1109/IEEESTD.2020.9144691.

9. Модель размещения данных во внутренней памяти вычислителя, реализующего схему кодирования данных в режиме сцепления блоков / М.О. Таныгин, А.А. Ахмад, О.В. Казакова, Д.А. Голубов // Известия Юго-Западного государственного университета. 2023; 27(1): 73-91. https://doi.org/10.21869/2223-1560-2023-27-1-73-91.

10. Пасечников К. А., Иванова Г. С. Синтез оптимальных структур данных для решения задач на графах // Вестник Московского государственного технического университета им. Н.Э. Баумана. Серия Приборостроение. 2008. № 4(73). С. 29-37.

11. Колганов А. С. Параллельная реализация алгоритма поиска минимальных остовных деревьев с использованием центрального и графического процессоров // Вестник Южно-Уральского государственного университета. Серия: Вычислительная математика и информатика. 2016. Т. 5. № 3. С. 5-19. DOI 10.14529/cmse160301

12. Tasci S., Demirbas, M Employing in-memory data grids for distributed graph processing // IEEE 2015 IEEE International Conference on Big Data (Big Data), 2015, pp. 1856–1864. doi:10.1109/bigdata.2015.7363959

13. Волчихин В. И., Вашкевич Н. П., Бикташев Р. А. Модели событийных недетерминированных автоматов представления алгоритмов управления взаимодействующими процессами в многопроцессорных вычислительных системах на основе использования механизма монитора // Известия высших учебных заведений. Поволжский регион. Технические науки. 2013. № 2(26). С. 5-14.

14. Courtois P. J., Heymans F., Parnas D. L. Concurrent Control with "Readers" and "Writers" // Communications of the ACM. 14 (10), 1971. P. 667–668. doi:10.1145/ 362759.362813.S2CID 7540747.

15. Babionitakis K., Doumenis G.A., Georgakarakos G. et al. A real-time motion estimation FPGA architecture // J. Real-Time Image Proc. 2008. № 3. Pp. 3–20. https://doi.org/10.1007/s11554-007-0070-9

16. Дородных Н. О., Юрин А. Ю. Подход к автоматизированному наполнению графов знаний сущностями на основе анализа таблиц // Онтология проектирования. 2022. Т. 12. № 3(45). С. 336-352. DOI 10.18287/2223-9537-2022-12-3-336-352.

17. Путнин В. И. Автоматизация процесса построения расписания с применением топологической сортировки на графе // E-Scio. 2021. № 3(54). С. 584-588.

18. Метод ограничения множества обрабатываемых приёмником блоков данных для повышения достоверности операций определения их источника / М. О. Таныгин, О. Г. Добросердов, А. О. Власова, А. А. Ахмад // Труды МАИ. 2021. Т. 118, №3. 15 doi 10.34759/trd-2021-118-14.

19. Modinger D., Frohlich N., Hauck F.J. Pixy: A Privacy-Increasing Group Creation Scheme // Conference: ICNCC 2020: 2020 The 9th International Conference on Networks, Communication and Computing. December 2020 DOI: 10.1145/3447654.3447671.

20. Хабибулин Н. Ф., Шкердин А. Н., Щербенко А. Н. Повышение пропускной способности систем передачи с переспросом за счет введения дополнительной связи между процессами декодирования с исправлением и обнаружением ошибок // Науковедение. 2016. Т. 8, № 3(34). С. 143.

21. Тучкин А. В. Принципы функционирования протокола канального уровня для пакетной передачи разнородного трафика по низкоскоростным каналам // T-Comm: Телекоммуникации и транспорт. 2008. Т. 2, № 3. С. 31-33.

22. Мальцев Г. Н. Помехоустойчивость и скрытность передачи информации по радиоканалам на основе комбинированного случайного кодирования // Информационноуправляющие системы. 2015. № 2(75). С. 82-89. DOI 10.15217/issn1684-8853.2015.2.82

23. Таныгин М. О., Чеснокова А. А., Ахмад А. А. А. Снижение ресурсных затрат на обработку кодов аутентификации сообщений за счет ограничения числа обрабатываемых сообщений // Прикаспийский журнал: управление и высокие технологии. 2022. № 4(60). С. 22-29.

24. Таныгин М. О., Чеснокова А. А., Ахмад А. А. А. Повышение скорости определения источника сообщений за счет ограничения множества обрабатываемых блоков данных // Труды МАИ. 2022. № 125. DOI 10.34759/trd-2022-125-20.

25. IEEE Standard for Low-Rate Wireless Networks // IEEE Std 802.15.4-2020, pp.1800, 23 July 2020, doi: 10.1109/IEEESTD.2020.9144691