SQUARE

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

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

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

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

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

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

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

Линейное преобразование $\theta$ воздействует на каждую строку в квадрате данных. Оно представляется формулой ${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}}$, где:

• ${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_{j}x^{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}$.

Нелинейное преобразование $\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, и так далее.

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

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

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

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

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

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

Для шифрования необходимо получить 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}]$;

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

Шифрование

Обозначим один раунд шифрования как $\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}$.

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

Алгоритм расшифрования аналогичен алгоритму шифрования, но вместо преобразований $\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$.

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

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

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

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

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

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

$\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: Если применение операции исключающего «или» ко всем байтам на одной позиции в $\Lambda$-множестве даёт 0, то эта позиция называется уравновешенной по $\Lambda$-множеству.

Применение преобразований $\gamma$ и $\sigma [k^{t}]$ к $\Lambda$-множеству даёт $\Lambda$-множество с тем же $\lambda$. Применение преобразования $\pi$ даёт $\Lambda$-множество, в котором активные байты транспонированы (относительно активных байтов в исходном $\Lambda$-множестве). Также, применение $\theta$ к $\Lambda$-множеству необязательно вернёт $\Lambda$-множество, однако, так как каждый выходной байт $\theta$ является линейной комбинацией четырёх входных байт в той же строке, то, подавая строку с всего одним активным байтом, на выходе получим строку состоящую только из активных байт. Рассмотрим $\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_{i,j}^{4}$. Предполагая значение $k_{i,j}^{4}$, значение $b_{j,i}$ для всех элементов $\Lambda$-множества могут быть вычислены из шифротекстов. Если значение этого байта оказалось неуравновешенным по $\Lambda$, то предположенное значение ключа $k_{i,j}^{4}$ является ложным. Этот метод криптоанализа позволил взломать 6-раундовый вариант шифра с использованием $2^{32}$ блоков открытого текста и соответствующих им блоков шифротекста и выполнением $2^{72}$ операций шифрования.

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

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

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

См. также

• Rijndael

Литература

• 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

Ссылки

• The Block Cipher Square Algorithm, Joan Daemen, Lars R. Knudsen and and Vincent Rijmen, Dr. Dobb’s Journal, October 01, 1997.