Общая проблема / Введение: шифрование (вычислимого) отношения между двумя случайными числами, которые являются членами как можно меньшего набора, в то время как противнику известно все, кроме порядка выполнения.
Этот вопрос касается решения этой проблемы с помощью конкатенации блочного шифра.
Упрощение:
- мы рассматриваем только блочные шифры, похожие на AES
- вместо $N$ другой блочный шифр мы используем один блочный шифр с $N$ разные ключи (или даже больше)
- блочный шифр передает только один ввод другому (поэтому они работают в режиме ECB)
Что известно:
Если применить блочный шифр $BC$ на заданный вход $м$ снова и снова мы достигнем ввода в какой-то момент снова.
$$BC^l(m,k) = m$$
Для заданного случайного ввода $м$ и ключ $к$ длина цикла $l$ может быть любой длины от $1$ к размеру домена $м$ с (в оптимальном случае) одинаковой вероятностью каждый.
(почти уверен, что это тоже так :)
Если мы используем $N$ разные ключи и объединять блочный шифр с этими ключами друг с другом (всегда в одном и том же порядке и всегда кратно $N$ шагов) мы получаем длину цикла $N$ раз $[1,..,D]$ с $Д$ размер домена m.
$$BC(....BC(...BC(..BC(BC(BC(m,k_0),k_1),k_2)..,k_{N-1})...,k_{i \mod{N}})....,k_{l \equiv N-1 \mod{N}}) = m$$
Мы можем видеть эту конкатенацию как применение раундов внутри одного BC.
Применяя это к общей проблеме сверху:
При этом порядок исполнения (то есть порядок используемых ключей) противнику неизвестен (но сами ключи известны).
Например, значение $В$ может быть вычислено из значения $W$ с:
$$BC(BC(BC(BC(BC(W,k_5),k_2),k_3,k_5,k_1,k_1) =V$$
Противник знает $В,В$ а также всегда ключ сам по себе, но он хочет знать порядок выполнения ключа $5,2,3,5,1,1$ или любой другой заказ, который также выполняет эту работу.
Если мы больше не используем фиксированный порядок ключей, свойства размера цикла больше недействительны.
Пробная версия решения 1 (сбой):
Если противник хочет найти исполнительный приказ, который передает $W \стрелка вправо V$
он может вычислить $N$ возможные следующие значения $W$ и $N$ возможные предыдущие значения $В$ с обратным БК. Он может повторять это до тех пор, пока мах не будет найден.
При этом он должен найти исполнительный лист в среднем примерно $\sqrt{D}$ шаги, которые не являются достаточно безопасными.
Пробная версия решения 2 (сбой):
Для большей безопасности мы ограничиваем результат $В$ к значениям, которые были рассчитаны с использованием $я$-й ключ при последнем вычислении BC.
При этом противник может просто использовать обратную БК. $В$ с целью $я$-й ключ и сделайте то же самое, что и в пробной версии решения 1.
Пробная версия решения 3 (вопрос/редактирование: не удалось...):
Для обеспечения безопасности мы можем ограничить число выполнения кратным $Е$ шагов и при этом также изменяя ключи каждой глубины.
Помимо использования $я$-й ключ BC для вычисления $В$ теперь также должно быть кратно $Е$ на шаг впереди $W$
в нашем примере сверху с $Е=3$ это было бы:
$$BC(BC(BC(BC(BC(W,k_5^0),k_2^1),k_3^2,k_5^0,k_1^1,k_1^2) =V$$
Итак, для заданного $В$ с $я$-th последний ключ на глубине $д$ противник может вычислить отношение к данному $W$ с глубиной $д$:
Вычисление обратного $В$:
$$BC^{-1}(V,k_i^{d-1 \mod E}) = V'$$
И вычисляйте значения шаг за шагом, как он делал в пробном решении 1.
Это должно занять около $ N ^ {\ lfloor {\ гидроразрыва {E-1} {2}} \ rfloor} $ испытания, если он делает это грубой силой.
Если например $D=2^{128}, N=2^{16}, E=2^{5}$ это было бы $2^{16\cdot 15} = 2^{240}$ испытания.
.... после написания всего этого текста я заметил, что ему не нужно вычислять каждую часть каждой глубины, а просто нужно $\sqrt{D}$ снова шаги...
=====>
Вопрос: Есть ли у кого-нибудь другая идея, как конкатенация блочного шифра может быть более безопасной (близкой к $Д$)?
История
- $Д$ размер входного и выходного набора
- $В,В$ случайные значения, которые могут иметь до $Д$ разные значения
- $Е$ общее количество выполнений блочного шифра должно быть кратно $Е$
- $N$ количество различных ключей блочного шифра для каждой глубины
- $k_a^b$ ключевая переменная, используемая для блочного шифра с индексами $а,б$ с $a\in\{0,N-1\}, b\in\{0,E-1\}$
