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

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

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

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

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

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

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

Нелинейное преобразование ${\displaystyle \gamma }$

Данное преобразование является табличной заменой ${\displaystyle \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

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

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

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

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

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

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

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

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

Процедура получения ключа описывается преобразованием ${\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}]}$ ;

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

Шифрование

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

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

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

${\displaystyle \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}]}$ ,

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

${\displaystyle \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 }$ .

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

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

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

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

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

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

${\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 }$ -множеству.

Применение преобразований ${\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 }$ является линейной комбинацией четырёх входных байт в той же строке, то, подавая строку с всего одним активным байтом, на выходе получим строку состоящую только из активных байт. Рассмотрим ${\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}}$ операций шифрования.

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

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

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

См. также

• Rijndael

Примечания

Литература

• J. Daemen, L. Knudsen, V. Rijmen. . — 1997.
• B. Koo, Y. Yeom, J. Song. . — 2010.
• H. Mala. . — 2011.
• G.Piret, J.-J. Quisquater. . — 2001.
• — СПб. : , 2009. — 576 с. — ISBN 978-5-9775-0319-8

Ссылки

• , Joan Daemen, Lars R. Knudsen and and Vincent Rijmen, Dr. Dobb’s Journal , October 01, 1997.