SQUARE

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

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

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

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

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

Линейное преобразование $\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{x}\mathrm{o}\mathrm{r}$. Каждая $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)mod1\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(\mathrm{mod}1)\oplus x^4$.Шаблон:Sfn

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

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

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

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

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

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

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

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

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

Шифрование

Обозначим один раунд шифрования как $\rho [k^t]=\sigma [k^t]\circ \pi \circ \gamma \circ \theta$. Также, восьми раундам преобразования предшествует сложение с ключом $\sigma [K_0]$ и ${\theta }^{-1}$:$\mathrm{S}\mathrm{q}\mathrm{u}\mathrm{a}\mathrm{r}\mathrm{e}[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}$.Шаблон:Sfn

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

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

$\mathrm{S}\mathrm{q}\mathrm{u}\mathrm{a}\mathrm{r}{\mathrm{e}}^{\mathrm{-}\mathrm{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 }^{\prime }[k^t]=\sigma [k^t]\circ \pi \circ {\gamma }^{-1}\circ {\theta }^{-1}$, и полная формула для расшифрования записывается как :

${\mathrm{S}\mathrm{q}\mathrm{u}\mathrm{a}\mathrm{r}\mathrm{e}}^{-1}={\rho }^{\prime }[k^8]\circ {\rho }^{\prime }[k^7]\circ {\rho }^{\prime }[k^6]\circ {\rho }^{\prime }[k^5]\circ {\rho }^{\prime }[k^4]\circ {\rho }^{\prime }[k^3]\circ {\rho }^{\prime }[k^2]\circ {\rho }^{\prime }[k^1]\circ \sigma [k^0]\circ \theta$.Шаблон:Sfn

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

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

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

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

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

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

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

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

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

$\underset{b=\theta (a),a\in \mathrm{\Lambda }}{⨁}{b}_{i,j}=\underset{a\in \mathrm{\Lambda }}{⨁}\underset{k}{⨁}{c}_{j-k}{a}_{i,k}=\underset{l}{⨁}{c}_l\underset{a\in \mathrm{\Lambda }}{⨁}{a}_{i,l+j}=\underset{l}{⨁}{c}_{l}0=0,$

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

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

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

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

См. также

• Rijndael

Литература

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:H

Ссылки

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