SQUARE

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
SQUARE
Создатель:

Винсент Рэймен, Йоан Даймен, Ларс Кнудсен

Создан:

1997 г.

Опубликован:

1997 г.

Размер ключа:

128 бит

Размер блока:

128 бит

Число раундов:

8

Тип:

Подстановочно-перестановочная сеть

SQUARE — в криптографии симметричный блочный криптоалгоритм, разработанный в 1997 году Винсентом Рэйменом, Йоаном Дайменом и Ларсом Кнудсеном. SQUARE считается предшественником алгоритма AES. Структура алгоритма была подобрана авторами для возможности получения эффективной реализации на широком спектре процессоров, а также для криптостойкости к дифференциальному и линейному криптоанализу.

Описание алгоритма[править | править исходный текст]

Алгоритм SQUARE использует ключ длиной 128 бит, данные шифруются 128-битными блоками, однако модульный подход к построению шифра позволяет легко расширить до больших размеров длину ключа и длину блока данных. Один раунд SQUARE состоит из четырёх отдельных преобразований. Данные представляются байтовым квадратом размера 4x4. Основные составляющие этого шифра — это пять различных обратимых преобразований, которые воздействуют на массив байтов размера 4 \times 4.[1]

Преобразования в раунде шифрования[править | править исходный текст]

Линейное преобразование \theta[править | править исходный текст]

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

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

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

Нелинейное преобразование \gamma[править | править исходный текст]

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

B1 CE C3 95 5A AD E7 02 4D 44 FB 91 0C 87 A1 50
CB 67 54 DD 46 8F E1 4E F0 FD FC EB F9 C4 1A 6E
5E F5 CC 8D 1C 56 43 FE 07 61 F8 75 59 FF 03 22
8A D1 13 EE 88 00 0E 34 15 80 94 E3 ED B5 53 23
4B 47 17 A7 90 35 AB D8 B8 DF 4F 57 9A 92 DB 1B
3C C8 99 04 8E E0 D7 7D 85 BB 40 2C 3A 45 F1 42
65 20 41 18 72 25 93 70 36 05 F2 0B A3 79 EC 08
27 31 32 B6 7C B0 0A 73 5B 7B B7 81 D2 0D 6A 26
9E 58 9C 83 74 B3 AC 30 7A 69 77 0F AE 21 DE D0
2E 97 10 A4 98 A8 D4 68 2D 62 29 6D 16 49 76 C7
E8 C1 96 37 E5 CA F4 E9 63 12 C2 A6 14 BC D3 28
AF 2F E6 24 52 C6 A0 09 BD 8C CF 5D 11 5F 01 C5
9F 3D A2 9B C9 3B BE 51 19 1F 3F 5C B2 EF 4A CD
BF BA 6F 64 D9 F3 3E B4 AA DC D5 06 C0 7E F6 66
6C 84 71 38 B9 1D 7F 9D 48 8B 2A DA A5 33 82 39
D6 78 86 FA E4 2B A9 1E 89 60 6B EA 55 4C F7 E2
Преобразование \pi

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

Байтовая перестановка \pi[править | править исходный текст]

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

Сложение с ключом раунда \sigma[K_i][править | править исходный текст]

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

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

Процедура получения ключей[править | править исходный текст]

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

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

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

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

где:

  • {k_{n,i}} — n-я строка байтового квадрата ключа i-го раунда;
  • C_i — константа для i-го раунда, вычисляемая по формуле {C_{i+1} = 2\cdot C_{i}}, C_0 = 1;
  • {rotl()} — операция циклического сдвига байтовой строки на один байт влево: 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]

Шифрование[править | править исходный текст]

Обозначим один раунд шифрования как \rho[k^t] = \sigma[k^t] \circ \pi \circ \gamma \circ \theta. Также, восьми раундам преобразования предшествует сложение с ключом \sigma[K_0] и \theta^{-1}: \mathrm{Square}[k] = \rho[k^8] \circ  \rho[k^7] \circ  \rho[k^6]  \circ \rho[k^5] \circ  \rho[k^4] \circ  \rho[k^3] \circ  \rho[k^2] \circ  \rho[k^1] \circ  \sigma[k^0] \circ  \theta^{-1} .[2]

Расшифрование[править | править исходный текст]

Алгоритм расшифрования аналогичен алгоритму шифрования, но вместо преобразований \gamma и \theta используются обратные преобразования \gamma^{-1} и \theta^{-1}, при этом \gamma^{-1} — это обратная табличная замена, а \theta^{-1} — это умножение строки на полином d(x) такой, что d(x)c(x) = 1\pmod {1 \oplus x^4}, также в предварительном раунде используется преобразование \theta вместо \theta^{-1}. Из формулы для шифрования видно, что

 \mathrm{Square^{-1}}[k] = \theta \circ \sigma^{-1}[k^0] \circ  \rho^{-1}[k^1] \circ  \rho^{-1}[k^2] \circ  \rho^{-1}[k^3]  \circ  \rho^{-1}[k^4] \circ  \rho^{-1}[k^5] \circ  \rho^{-1}[k^6] \circ  \rho^{-1}[k^7] \circ  \rho^{-1}[k^8] ,

где  \rho^{-1}[k^t] = \theta^{-1} \circ \gamma^{-1} \circ \pi^{-1} \circ \sigma^{-1}[k^t] = \theta^{-1} \circ \gamma^{-1} \circ \pi \circ \sigma[k^t] . Так как  \gamma^{-1} \circ \pi = \pi \circ \gamma^{-1} , и, более того, так как  \theta^{-1}(a) \oplus k^t = \theta^{-1}(a + \theta(k^t)) , получаем  \sigma[k^t] \circ \theta^{-1} = \theta^{-1}\circ\sigma[\theta(k^t)] . Теперь один раунд для расшифрования можно определить как  \rho'[k^t] = \sigma[k^t]\circ\pi\circ\gamma^{-1}\circ\theta^{-1} , и полная формула для расшифрования записывается как :

 \mathrm{Square}^{-1} = \rho'[k^8] \circ  \rho'[k^7] \circ  \rho'[k^6]  \circ \rho'[k^5] \circ  \rho'[k^4] \circ  \rho'[k^3] \circ  \rho'[k^2] \circ  \rho'[k^1] \circ  \sigma[k^0] \circ  \theta .[2]

Безопасность[править | править исходный текст]

Исследование криптостойкости создателями алгоритма[править | править исходный текст]

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

Описание Square-атаки[править | править исходный текст]

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

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

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

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

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

 \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,

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

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

Особенности шифра[править | править исходный текст]

Шифр SQUARE создавался, соответствуя стратегии широкого следа — каждый раунд шифра состоит из нескольких преобразований, нелинейной перестановки и композиции линейных преобразований — что дало шифру высокую криптостойкость против линейного и дифференциального криптоанализа, составляющие блоки алгоритма и их взаимодействие, подбирались также исходя из возможности быстрой реализации на широком спектре процессоров.[6] Реализация алгорима на языке Си имела скорость шифрования 2.63 Мбайт/с, запускаемая на процессоре Pentium с частотой 100 МГц, а реализация на языка ассемблер увеличивала скорость шифрования вдвое. Данный алгоритм получил развитие и стал основой нового американского стандарта — шифра Rijndael, который был разработан группой авторов SQUARE. Кстати, на конкурсе AES, эксперты отметили, что «в основе алгоритма Rijndael лежит нетрадиционная парадигма, поэтому он может содержать скрытые уязвимости».[1] Именно по этой причине сам SQUARE сейчас используется редко, уступая в популярности своему потомку — Rijndael. Также потомком шифра является южнокорейский алгоритм CRYPTON, участник конкурса AES.

См. также[править | править исходный текст]

Rijndael

Ссылки[править | править исходный текст]

Примечания[править | править исходный текст]

Литература[править | править исходный текст]

  • С.Панасенко Алгоритмы шифрования. Специальный справочник. — СПб.: БХВ-Петербург, 2009. — С. 576. — ISBN 978-5-9775-0319-8