WikiSort.ru - Не сортированное

Линейное преобразование ${\displaystyle \theta }$

Линейное преобразование ${\displaystyle \theta }$ воздействует на каждую строку в квадрате данных. Оно представляется формулой ${\displaystyle {b_{i,j}=c_{j}a_{i,0}\oplus c_{j-1}a_{i,1}\oplus c_{j-2}a_{i,2}\oplus c_{j-3}a_{i,3}}}$ , где:

• ${\displaystyle {a_{i,j}}}$  — значение байта, находящегося в ${\displaystyle i}$ -й строке и ${\displaystyle j}$ -м столбце в квадрате данных;
• ${\displaystyle {b_{i,j}}}$  — новое значение байта в квадрате;
• ${\displaystyle {c_{n}}}$  — набор констант;
• умножения выполняются в поле Галуа ${\displaystyle {GF(2^{8})}}$ ;

Важно, что поле ${\displaystyle {GF(2^{8})}}$ имеет характеристику 2, то есть операция сложения соответствует побитовому ${\displaystyle \mathrm {xor} }$ . Каждая ${\displaystyle i}$ -ая строка в квадрате может быть представлена в виде полинома ${\displaystyle a_{i}(x)=a_{i,0}\oplus a_{i,1}x\oplus a_{i,2}x^{2}\oplus a_{i,3}x^{3}}$ . Тогда, определяя коэффициенты ${\displaystyle {c_{n}}}$ как полином ${\displaystyle {c(x)=\oplus _{j}c_{j}x^{j}}}$ , преобразование ${\displaystyle \theta }$ можно представить в виде произведения полиномов: ${\displaystyle b_{i}(x)=c(x)a_{i}(x)\mod 1\oplus x^{4}}$ , здесь ${\displaystyle b_{i}(x)}$  — новое значение строки квадрата, представленное в виде полинома, и ${\displaystyle c(x)=2\oplus 1\cdot x\oplus 1\cdot x^{2}\oplus 3\cdot x^{3}}$ . Обратному преобразованию ${\displaystyle \theta ^{-1}}$ соответствует полином ${\displaystyle d(x)}$ , определённый по формуле ${\displaystyle c(x)d(x)=1{\pmod {1}}\oplus x^{4}}$ .^[2]

Нелинейное преобразование ${\displaystyle \gamma }$

Данное преобразование является табличной заменой ${\displaystyle \gamma }$ . Таблица, по которой осуществляется замена:

то есть 0 заменится на B1, 1 — на CE, и так далее.^[1]

Байтовая перестановка ${\displaystyle \pi }$

Байтовая перестановка осуществляет транспонирование байтового квадрата, то есть ${\displaystyle {a_{i,j}=a_{j,i}}}$ .

Сложение с ключом раунда ${\displaystyle \sigma [K_{i}]}$

Эта операция — побитовое сложение 128 бит данных с ключом раунда, ${\displaystyle {b=a\oplus K_{i}}}$ , где:

• ${\displaystyle {a}}$ и ${\displaystyle {b}}$  — значение 128 бит данных перед преобразованием и после;
• ${\displaystyle {K_{i}}}$  — ключ раунда ${\displaystyle {i}}$ .^[2]

Описание Square-атаки

Прежде всего, введем несколько определений,

Определение 1: Пусть ${\displaystyle \Lambda }$ -множество — набор из 256 16-байтовых состояний, каждое из которых отличается от других в некоторых байтах, которые назовём активными, и совпадают в некоторых байтах, которые будем называть пассивными. Далее, ${\displaystyle \lambda }$  — это набор индексов активных байтов.^[3] Имеем:

${\displaystyle \forall x,y\in \Lambda :{\begin{cases}x_{i,j}\neq y_{i,j},for(i,j)\in \lambda \\x_{i,j}=y_{i,j},for(i,j)\notin \lambda \end{cases}}}$ .

Определение 2: Если применение операции исключающего «или» ко всем байтам на одной позиции в ${\displaystyle \Lambda }$ -множестве даёт 0, то эта позиция называется уравновешенной по ${\displaystyle \Lambda }$ -множеству.^[3]

Применение преобразований ${\displaystyle \gamma }$ и ${\displaystyle \sigma [k^{t}]}$ к ${\displaystyle \Lambda }$ -множеству даёт ${\displaystyle \Lambda }$ -множество с тем же ${\displaystyle \lambda }$ . Применение преобразования ${\displaystyle \pi }$ даёт ${\displaystyle \Lambda }$ -множество, в котором активные байты транспонированы(относительно активных байтов в исходном ${\displaystyle \Lambda }$ -множестве). Также, применение ${\displaystyle \theta }$ к ${\displaystyle \Lambda }$ -множеству необязательно вернёт ${\displaystyle \Lambda }$ -множество, однако, так как каждый выходной байт ${\displaystyle \theta }$ является линейной комбинацией четырёх входных байт в той же строке, то, подавая строку с всего одним активным байтом, на выходе получим строку состоящую только из активных байт.^[2] Рассмотрим ${\displaystyle \Lambda }$ -множество, в котором только один байт является активным и проследим, как изменяется позиция активного байта в течение трех раундов (здесь предварительный раунд объединён с первым: ${\displaystyle \rho [k^{1}]\circ \sigma [k^{0}]\circ \theta ^{-1}}$ , который в итоге записывается как ${\displaystyle \sigma [k^{1}]\circ \pi \circ \gamma \circ \theta \circ \sigma [k^{0}]\circ \theta ^{-1}=\sigma [k^{1}]\circ \pi \circ \gamma \circ \sigma [\theta (k^{0})]}$ ). Так как первый раунд не содержит ${\displaystyle \theta }$ , то к началу второго раунда остается один активный байт. Во втором раунде ${\displaystyle \theta }$ преобразует в строку активных байтов, которые ${\displaystyle \pi }$ преобразует в столбец активных байт. ${\displaystyle \theta }$ в третьем раунде переводит результат в ${\displaystyle \Lambda }$ -множество, состоящее только из активных байт. Значения байт на выходе третьего раунда пробегают все возможные значения, следовательно, уравновешены по множеству ${\displaystyle \Lambda }$ , имеем

${\displaystyle {\underset {b=\theta (a),a\in \Lambda }{\bigoplus }}b_{i,j}={\underset {a\in \Lambda }{\bigoplus }}{\underset {k}{\bigoplus }}c_{j-k}a_{i,k}={\underset {l}{\bigoplus }}c_{l}{\underset {a\in \Lambda }{\bigoplus }}a_{i,l+j}={\underset {l}{\bigoplus }}c_{l}0=0,}$

значит байты на выходе ${\displaystyle \theta }$ в четвёртом раунде уравновешены по ${\displaystyle \Lambda }$ -множеству. Эта уравновещенность нарушается последующим применением ${\displaystyle \gamma }$ . Выходные байты четвёртого раунда могут быть выражены с помощью функции от промежуточного состояния ${\displaystyle b}$ : ${\displaystyle a_{i,j}=S_{\gamma }[b_{j,i}]\oplus k_{i,j}^{4}}$ . Предполагая значение ${\displaystyle k_{i,j}^{4}}$ , значение ${\displaystyle b_{j,i}}$ для всех элементов ${\displaystyle \Lambda }$ -множества могут быть вычислены из шифротекстов. Если значение этого байта оказалось неуравновешенным по ${\displaystyle \Lambda }$ , то предположенное значение ключа ${\displaystyle k_{i,j}^{4}}$ является ложным. Этот метод криптоанализа позволил взломать 6-раундовый вариант шифра с использованием ${\displaystyle 2^{32}}$ блоков открытого текста и соответствующих им блоков шифротекста и выполнением ${\displaystyle 2^{72}}$ операций шифрования.^[2]

В 2010 году была представлена атака на связанных ключах методом бумеранга. Ранее подобная атака применялась к шифрам KASUMI, COCONUT98, IDEA и AES-192/256. Это была первая атака на полнораундовый SQUARE.^[4] В 2011 году был проведён криптоанализ полнораундового варианта SQUARE с помощью полного двудольного графа. Данный тип атаки позволил взломать шифр с использованием одного ключа, ${\displaystyle 2^{48}}$ открытых текстов и проведения ${\displaystyle 2^{126}}$ операций шифрования.^[5]