SQUARE

Линейное преобразование ${\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 \pi }$

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

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

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

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

Для шифрования необходимо получить 8 128-битных ключей раундов, а также ключ для предварительного раунда из ключа шифрования алгоритма.

Процедура ${\displaystyle \psi }$ получения ключей.

Процедура получения ключа описывается преобразованием ${\displaystyle \psi :K_{i+1}=\psi (K_{i})}$, выполняющимся над ключом, представленным, как и блок данных, байтовым квадратом 4x4. Преобразование ${\displaystyle \psi }$ описывается следующими операциями:

• ${\displaystyle {k_{0,i+1}=k_{0,i}\oplus rotl(k_{3,i})\oplus C_{i}}}$;
• ${\displaystyle {k_{1,i+1}=k_{1,i}\oplus k_{0,i+1}}}$;
• ${\displaystyle {k_{2,i+1}=k_{2,i}\oplus k_{1,i+1}}}$;
• ${\displaystyle {k_{3,i+1}=k_{3,i}\oplus k_{2,i+1}}}$;

где:

• ${\displaystyle {k_{n,i}}}$ — ${\displaystyle n}$-я строка байтового квадрата ключа ${\displaystyle i}$-го раунда;
• ${\displaystyle C_{i}}$ — константа для ${\displaystyle i}$-го раунда, вычисляемая по формуле ${\displaystyle {C_{i+1}=2\cdot C_{i}}}$, ${\displaystyle C_{0}=1}$;
• ${\displaystyle {rotl()}}$ — операция циклического сдвига байтовой строки на один байт влево: ${\displaystyle rotl[a_{i,0},a_{i,1},a_{i,2},a_{i,3}]=[a_{i,1},a_{i,2},a_{i,3},a_{i,0}]}$;

Исходный ключ алгоритма шифрования используется как ключ для предварительного раунда.[2]

Алгоритм обладает высокой стойкостью против линейного и дифференциального криптоанализа, благодаря преобразованиям ${\displaystyle \theta }$ и ${\displaystyle \gamma }$, которые понижают максимальную вероятность появления дифференциальных следов и максимальную корреляцию линейных следов за 4 раунда преобразований. Первый криптоанализ SQUARE был проведён его авторами с использованием интегрального криптоанализа, который позже стал известен как Square-атака.[2]

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

Определение 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]