Я хотел бы понять алгебру безопасности GCM.
Ну, вы описали механику того, как работает аутентификационная часть GCM; однако, чтобы понять, почему эта механика работает, было бы полезно подойти к ней по-другому.
GCM использует арифметику в $GF(2^{128})$; это поле; важно то, что в поле любой ненулевой многочлен степени не выше $n$ имеет не более $n$ нули; то есть для любого уравнения:
$$a_n x^n + a_{n-1} x^{n-1} + ... + a_0 x^0 = 0$$
имеет не более $n$ решения для $х$ (при условии, что хотя бы один из $a_i$ значение не равно нулю).
Почему это критично, станет ясно позже.
Что GCM делает для аутентификации, так это то, что он берет зашифрованные данные (и AAD) и переводит их в полином; затем он преобразует одноразовый номер в постоянное значение полинома, а затем оценивает этот полином как секретное значение. $к$, и результатом этой оценки является тег; это:
$$tag := a_n k^n + a_{n-1} k^{k-1} + ... + a_1 k^1 + \text{хэш}(nonce)$$
Теперь предположим, что у нас есть другая пара сообщение/тег для одного и того же одноразового номера; это сообщение/тег пройдет проверку целостности GCM, если:
$$tag' := a'_n k^n + a'_{n-1} k^{k-1} + ... + a'_1 k^1 + \text{хэш}(nonce)$$
Что мы можем сделать, так это вычесть два полинома (один, соответствующий хорошему зашифрованному тексту, сгенерированному действительным шифровальщиком, и один, соответствующий догадке злоумышленника); получаем тогда [1]:
$$0 = (a_n-a'_n)k^n + (a_{n-1} - a'_{n-1})k^{n-1} + ... + (a_1 - a'_1) k^1 + (тег - тег')k^0$$
Это уравнение выполняется только в том случае, если вторая пара зашифрованный текст/метка действительна.
Теперь вернемся к нашему исходному наблюдению: это многочлен степени не выше $n$ и так есть максимум $n$ различные значения $к$ для которых это равенство верно. Мы также знаем, что по крайней мере один коэффициент многочлена отличен от нуля (многочлен со всеми нулями верен, если «поддельный» зашифрованный текст точно такой же, как действительный, что не считается подделкой). И если $к$ выбирается непредсказуемо, то есть $2^{128}$ возможные значения, и, таким образом, вероятность того, что это просто одно из этих $n$ значения не более $n2^{-128}$, который действительно крошечный.
Теперь, чтобы превратить этот аргумент в фактическое доказательство (что и было сделано), нам нужно предположить, что а) $к$ выбирается равномерно случайным образом, и б) $\text{хэш}(одноразовый номер)$ также выбирается случайным образом (потому что в противном случае злоумышленник может вывести некоторые вещи о значении полинома, что было бы плохо); оказывается, мы можем связать и то, и другое с криптографической силой AES.
Теперь, чтобы ответить на ваши вопросы:
- Верно ли вышесказанное?
Закрывать; вы ошиблись в одной детали; используя вашу нотацию, мы получаем вычисление тега как $tag_k(c_1, c_2,...c_n) = c_0 + \сумма k^nc_n$ (Обратите внимание, что $c_0$ не умножается на $к$):
- Как AES-GCM выбирает $к$?
Он шифрует нулевой блок с помощью AES с помощью ключа GCM.
- Если $к=0$, $тег(\текст{любой_шифртекст})=0$
Нет, $c_0$ не умножается на $к$, поэтому в этом случае имеем:
$$тег(\текст{любой_шифртекст}) = c_0$$
Это по-прежнему означает, что в этом конкретном случае зашифрованный текст может быть изменен произвольно без изменения тега, однако это не очевидно.
Очевидный вопрос: «Разве это не все еще плохо?». Что ж, при 128-битном теге у злоумышленника всегда есть вероятность $2^{-128}$ просто слепого угадывания действительной пары зашифрованный текст/тег - $к=0$ имеет ту же вероятность появления и, следовательно, не увеличивает вероятность подделки.
- Делает $c_n=0$ поставить проблему?
Нет; если вы пройдёте вышеописанную логику, $c_n=0$ не является частным случаем.
- Но если $к$ окажется низкого порядка, схема не сработает.
Этот конкретный сценарий отказа по-прежнему находится в пределах вероятности $n2^{-128}$ как показано выше; если вы (скажете) проверите, если $к$ имели небольшой заказ и отклонили эти значения, вы на самом деле не уменьшите вероятность подделки.
[1]: В четном характеристическом поле, таком как $GF(2^{128})$, сложение и вычитание — это одна и та же операция, поэтому мы обычно записываем обе как $+$; Я сохранил это как $-$ сделать несколько понятнее для тех, кто не привык к таким условностям.
