Как имитозащитить $2^{75}$ блоков, используя шифр «Магма» и единственный ключ?

В. А. Кирюхин<sup>ab

a</sup> ООО «СФБ Лаб», Москва
^b АО «ИнфоТеКС», Москва

Аннотация: Пусть режим аутентифицированного шифрования с ассоциированными данными (AEAD) MGM используется только для контроля целостности, а синхропосылка зафиксирована. Доказано, что получившееся преобразование (MGM-PRF) является стойкой псевдослучайной функцией (PRF) и, следовательно, алгоритмом имитозащиты (MAC). При использовании шифра с блоком $n=64$ бита («Магма») для предельно допустимой вероятности навязывания $\pi_{\mathrm{mac}}=2^{-10}$ алгоритм MGM-PRF позволяет обработать на одном ключе $q\leq2^{26}$ сообщений по $l\leq2^{26}$ блоков каждое ($q\cdot l\leq2^{52}$).
Аналогичным образом с небольшими изменениями на основе AEAD-режима MGM2 (CTCrypt 2021) строится алгоритм MGM2-PRF, который позволяет имитозащищать сообщения с длиной вплоть до $l\leq2^{63}$ блоков ($q\cdot l\leq2^{89}$).
Переход границы парадокса дней рождения ($q>2^{\frac{n}{2}}$) возможен за счет удвоения внутреннего состояния криптоалгоритма. Предлагается алгоритм SUM-MGM, который по сути заключается в двукратном параллельном применении MGM2-PRF к одному сообщению и суммированию получившихся результатов. SUM-MGM использует один ключ шифрования, допустимая нагрузка составляет: $q\leq2^{37}$, $l\leq2^{38}$, $q\cdot l\leq2^{75}$ блоков.
Результаты получены с помощью метода H-коэффициентов, PRP-PRF лемма не используется.

Ключевые слова: MGM, PRF, SUM-MGM, доказуемая стойкость, AEAD, H-коэффициенты.

УДК: 519.719.2

Получено 14.X.2024

DOI: 10.4213/mvk494