SQUARE

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

SQUARE
Создатель Винсент Рэймен,
Йоан Даймен,
Ларс Кнудсен
Создан 1997
Опубликован 1997
Размер ключа 128 бит
Размер блока 128 бит
Число раундов 8
Тип Подстановочно-перестановочная сеть

Считается предшественником алгоритма AES. Структура алгоритма была подобрана авторами для возможности получения эффективной реализации на широком спектре процессоров, а также для криптостойкости к дифференциальному и линейному криптоанализу.

Описание алгоритма

править

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

Преобразования в раунде шифрования

править

Линейное преобразование  

править

Линейное преобразование   воздействует на каждую строку в квадрате данных. Оно представляется формулой  , где:

  •   — значение байта, находящегося в  -й строке и  -м столбце в квадрате данных;
  •   — новое значение байта в квадрате;
  •   — набор констант;
  • умножения выполняются в поле Галуа  ;

Важно, что поле   имеет характеристику 2, то есть операция сложения соответствует побитовому  . Каждая  -ая строка в квадрате может быть представлена в виде полинома  . Тогда, определяя коэффициенты   как полином  , преобразование   можно представить в виде произведения полиномов:  , здесь   — новое значение строки квадрата, представленное в виде полинома, и   . Обратному преобразованию   соответствует полином  , определённый по формуле  .[2]

Нелинейное преобразование  

править

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

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
 
Преобразование  

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

Байтовая перестановка  

править

Байтовая перестановка осуществляет транспонирование байтового квадрата, то есть  .

Сложение с ключом раунда  

править

Эта операция — побитовое сложение 128 бит данных с ключом раунда,  , где:

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

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

править

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

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

Процедура получения ключа описывается преобразованием  , выполняющимся над ключом, представленным, как и блок данных, байтовым квадратом 4x4. Преобразование   описывается следующими операциями:

  •  ;
  •  ;
  •  ;
  •  ;

где:

  •   —  -я строка байтового квадрата ключа  -го раунда;
  •   — константа для  -го раунда, вычисляемая по формуле  ,  ;
  •   — операция циклического сдвига байтовой строки на один байт влево:  ;

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

Шифрование

править

Обозначим один раунд шифрования как  . Также, восьми раундам преобразования предшествует сложение с ключом   и  : .[2]

Расшифрование

править

Алгоритм расшифрования аналогичен алгоритму шифрования, но вместо преобразований   и   используются обратные преобразования   и  , при этом   — это обратная табличная замена, а   — это умножение строки на полином   такой, что  , также в предварительном раунде используется преобразование   вместо  . Из формулы для шифрования видно, что

 ,

где  . Так как  , и, более того, так как  , получаем  . Теперь один раунд для расшифрования можно определить как  , и полная формула для расшифрования записывается как :

 .[2]

Безопасность

править

Исследование криптостойкости создателями алгоритма

править

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

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

править

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

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

 .

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

Применение преобразований   и   к  -множеству даёт  -множество с тем же  . Применение преобразования   даёт  -множество, в котором активные байты транспонированы (относительно активных байтов в исходном  -множестве). Также, применение   к  -множеству необязательно вернёт  -множество, однако, так как каждый выходной байт   является линейной комбинацией четырёх входных байт в той же строке, то, подавая строку с всего одним активным байтом, на выходе получим строку состоящую только из активных байт. [2] Рассмотрим  -множество, в котором только один байт является активным и проследим, как изменяется позиция активного байта в течение трех раундов (здесь предварительный раунд объединён с первым:  , который в итоге записывается как  ). Так как первый раунд не содержит  , то к началу второго раунда остается один активный байт. Во втором раунде   преобразует в строку активных байтов, которые   преобразует в столбец активных байт.   в третьем раунде переводит результат в  -множество, состоящее только из активных байт. Значения байт на выходе третьего раунда пробегают все возможные значения, следовательно, уравновешены по множеству  , имеем

 

значит байты на выходе   в четвёртом раунде уравновешены по  -множеству. Эта уравновещенность нарушается последующим применением  . Выходные байты четвёртого раунда могут быть выражены с помощью функции от промежуточного состояния  :  . Предполагая значение  , значение   для всех элементов  -множества могут быть вычислены из шифротекстов. Если значение этого байта оказалось неуравновешенным по  , то предположенное значение ключа   является ложным. Этот метод криптоанализа позволил взломать 6-раундовый вариант шифра с использованием   блоков открытого текста и соответствующих им блоков шифротекста и выполнением   операций шифрования.[2]

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

Особенности шифра

править

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

См. также

править

Примечания

править

Литература

править
  • J. Daemen, L. Knudsen, V. Rijmen. The Block Cipher SQUARE. — 1997.
  • B. Koo, Y. Yeom, J. Song. Related-Key Boomerang Attack on Block Cipher SQUARE. — 2010.
  • H. Mala. Biclique Cryptanalisis of the Block Cipher SQUARE. — 2011.
  • G.Piret, J.-J. Quisquater. Impossible differential and square attacks: Cryptanalytic link and application to Skipjack. — 2001.
  • Панасенко С. П. Алгоритмы шифрования. Специальный справочникСПб.: BHV-СПб, 2009. — 576 с. — ISBN 978-5-9775-0319-8

Ссылки

править