Просмотр кода страницы SQUARE

{{Карточка блочного шифра
| название = SQUARE
| изображение = 
| создатель = [[Винсент Рэймен]],<br> [[Йоан Даймен]],<br> [[Ларс Кнудсен]]
| создан = [[1997]]
| опубликован = [[1997]]
| размер ключа = 128 [[бит]]
| размер блока = 128 бит
| число раундов = 8
| тип = [[SP-сеть|Подстановочно-перестановочная сеть]]
}}
'''SQUARE''' — в [[Криптография|криптографии]] [[Симметричные криптосистемы|симметричный]] блочный [[криптоалгоритм]], разработанный в 1997 году [[Рэймен, Винсент|Винсентом Рэйменом]], [[Даймен, Йоан|Йоаном Дайменом]] и [[Кнудсен, Ларс|Ларсом Кнудсеном]].

Считается предшественником алгоритма [[Advanced Encryption Standard|AES]]. Структура алгоритма была подобрана авторами для возможности получения эффективной реализации на широком спектре процессоров, а также для [[Криптографическая стойкость|криптостойкости]] к [[Дифференциальный криптоанализ|дифференциальному]] и [[Линейный криптоанализ|линейному]] [[Криптоанализ|криптоанализу]].

== Описание алгоритма ==
[[Алгоритм]] SQUARE использует ключ длиной 128 [[бит]], данные шифруются 128-битными блоками, однако модульный подход к построению шифра позволяет легко расширить до больших размеров длину ключа и длину блока данных. Один раунд SQUARE состоит из четырёх отдельных преобразований. Данные представляются [[Байт|байтовым]] квадратом размера 4x4. Основные составляющие этого шифра — это пять различных обратимых преобразований, которые воздействуют на массив байтов размера <math>4 \times 4</math>.{{sfn|Панасенко|2009}}

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

==== Линейное преобразование <math>\theta</math> ====
[[Линейное преобразование]] <math>\theta</math> воздействует на каждую строку в квадрате данных. Оно представляется формулой <math>{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}  }</math>, где:
* <math>{a_{i,j}}</math> — значение байта, находящегося в <math>i</math>-й строке и <math>j</math>-м столбце в квадрате данных;
* <math>{b_{i,j}}</math> — новое значение байта в квадрате;
* <math>{c_n}</math> — набор констант;
* умножения выполняются в [[Конечное поле|поле Галуа]] <math>{GF(2^8)}</math>;
Важно, что поле <math>{GF(2^8)}</math> имеет [[Характеристика кольца|характеристику]] 2, то есть операция сложения соответствует побитовому <math>\mathrm{xor}</math>.
Каждая <math>i</math>-ая строка в квадрате может быть представлена в виде полинома <math>a_i(x) = a_{i,0} \oplus a_{i,1}x \oplus a_{i,2}x^2 \oplus a_{i,3}x^3 </math>. Тогда, определяя коэффициенты <math>{c_n}</math> как полином <math>{c(x) = \oplus _j c_jx^j}</math>, преобразование <math>\theta</math> можно представить в виде произведения полиномов: <math>b_i(x) = c(x)a_i(x) \mod 1 \oplus x^4</math>, здесь <math>b_i(x)</math> — новое значение строки квадрата, представленное в виде [[Многочлен|полинома]], и <math> c(x) = 2\oplus 1\cdot x\oplus 1\cdot x^2\oplus 3\cdot x^3 </math> . Обратному преобразованию <math>\theta^{-1}</math> соответствует полином <math>d(x)</math>, определённый по формуле <math>c(x)d(x)= 1 \pmod 1 \oplus x^4</math>.{{sfn|The Block Cipher SQUARE|1997}}

==== Нелинейное преобразование <math>\gamma</math> ====
Данное преобразование является табличной заменой <math>\gamma</math>. Таблица, по которой осуществляется замена:
{| class="wikitable"
|[[Шестнадцатеричная система счисления|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 transform.png|thumb|Преобразование <math>\pi</math>|356x356px]]
то есть 0 заменится на B1, 1 — на CE, и так далее.{{sfn|Панасенко|2009}}

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

==== Сложение с ключом раунда <math>\sigma[K_i]</math> ====
Эта операция — побитовое сложение 128 бит данных с ключом раунда, <math>{b=a\oplus K_i}</math>, где:
* <math>{a}</math> и <math>{b}</math> — значение 128 бит данных перед преобразованием и после;
* <math>{K_i}</math> — ключ раунда <math>{i}</math>.{{sfn|The Block Cipher SQUARE|1997}}

=== Процедура получения ключей ===
Для шифрования необходимо получить 8 128-битных ключей раундов, а также ключ для предварительного раунда из ключа шифрования алгоритма. [[Файл:Psi.png|thumb|Процедура <math>\psi</math> получения ключей.|355x355px]]
Процедура получения ключа описывается преобразованием <math>\psi: K_{i+1} = \psi(K_{i})</math>, выполняющимся над ключом, представленным, как и блок данных, байтовым квадратом 4x4. Преобразование <math>\psi</math> описывается следующими операциями:
* <math>{k_{0,i+1} = k_{0,i}\oplus rotl(k_{3,i})\oplus C_i}</math>;
* <math>{k_{1,i+1} = k_{1,i}\oplus k_{0,i+1}}</math>;
* <math>{k_{2,i+1} = k_{2,i}\oplus k_{1,i+1}}</math>;
* <math>{k_{3,i+1} = k_{3,i}\oplus k_{2,i+1}}</math>;
где:
* <math>{k_{n,i}}</math> — <math>n</math>-я строка байтового квадрата ключа <math>i</math>-го раунда;
* <math>C_i</math> — константа для <math>i</math>-го раунда, вычисляемая по формуле <math>{C_{i+1} = 2\cdot C_{i}}</math>, <math>C_0 = 1</math>;
* <math>{rotl()}</math> — операция циклического сдвига байтовой строки на один байт влево: <math>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}]</math>;
Исходный ключ алгоритма шифрования используется как ключ для предварительного раунда.{{sfn|The Block Cipher SQUARE|1997}}

== Шифрование ==
Обозначим один раунд шифрования как <math>\rho[k^t] = \sigma[k^t] \circ \pi \circ \gamma \circ \theta</math>. Также, восьми раундам преобразования предшествует сложение с ключом <math>\sigma[K_0]</math> и <math>\theta^{-1}</math>:<math> \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} </math>.{{sfn|The Block Cipher SQUARE|1997}}

== Расшифрование ==
Алгоритм расшифрования аналогичен алгоритму шифрования, но вместо преобразований <math>\gamma</math> и <math>\theta</math> используются обратные преобразования <math>\gamma^{-1}</math> и <math>\theta^{-1}</math>, при этом <math>\gamma^{-1}</math> — это обратная табличная замена, а <math>\theta^{-1}</math> — это умножение строки на полином <math>d(x)</math> такой, что <math>d(x)c(x) = 1\pmod {1 \oplus x^4}</math>, также в предварительном раунде используется преобразование <math>\theta</math> вместо <math>\theta^{-1}</math>. Из формулы для шифрования видно, что
:: <math> \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] </math>,
где <math> \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] </math>. Так как <math> \gamma^{-1} \circ \pi = \pi \circ \gamma^{-1} </math>, и, более того, так как <math> \theta^{-1}(a) \oplus k^t = \theta^{-1}(a + \theta(k^t)) </math>, получаем <math> \sigma[k^t] \circ \theta^{-1} = \theta^{-1}\circ\sigma[\theta(k^t)] </math>. Теперь один раунд для расшифрования можно определить как <math> \rho'[k^t] = \sigma[k^t]\circ\pi\circ\gamma^{-1}\circ\theta^{-1} </math>, и полная формула для расшифрования записывается как :
:: <math> \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 </math>.{{sfn|The Block Cipher SQUARE|1997}}

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

=== Исследование криптостойкости создателями алгоритма ===
Алгоритм обладает высокой стойкостью против линейного и дифференциального криптоанализа, благодаря преобразованиям <math>\theta</math> и <math>\gamma</math>, которые понижают максимальную вероятность появления дифференциальных следов и максимальную корреляцию линейных следов за 4 раунда преобразований. Первый криптоанализ SQUARE был проведён его авторами с использованием [[Интегральный криптоанализ|интегрального криптоанализа]], который позже стал известен как Square-атака.{{sfn|The Block Cipher SQUARE|1997}}

==== Описание Square-атаки ====
Прежде всего, введем несколько определений:

'''Определение 1:'''
Пусть <math>\Lambda</math>-множество — набор из 256 16-байтовых состояний, каждое из которых отличается от других в некоторых байтах, которые назовём активными, и совпадают в некоторых байтах, которые будем называть пассивными. Далее, <math>\lambda</math> — это набор индексов активных байтов.{{sfn|Impossible diﬀerential and square attacks: Cryptanalytic link and application to Skipjack|2001}} Имеем:
:: <math>\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}</math>.

'''Определение 2:'''
Если применение операции исключающего «или» ко всем байтам на одной позиции в <math>\Lambda</math>-множестве даёт 0, то эта позиция называется уравновешенной по <math>\Lambda</math>-множеству.{{sfn|Impossible diﬀerential and square attacks: Cryptanalytic link and application to Skipjack|2001}}

Применение преобразований <math>\gamma</math> и <math>\sigma[k^t]</math> к <math>\Lambda</math>-множеству даёт <math>\Lambda</math>-множество с тем же <math>\lambda</math>. Применение преобразования <math>\pi</math> даёт <math>\Lambda</math>-множество, в котором активные байты транспонированы (относительно активных байтов в исходном <math>\Lambda</math>-множестве). Также, применение <math>\theta</math> к <math>\Lambda</math>-множеству необязательно вернёт <math>\Lambda</math>-множество, однако, так как каждый выходной байт <math>\theta</math> является линейной комбинацией четырёх входных байт в той же строке, то, подавая строку с всего одним активным байтом, на выходе получим строку состоящую только из активных байт. {{sfn|The Block Cipher SQUARE|1997}}
Рассмотрим <math>\Lambda</math>-множество, в котором только один байт является активным и проследим, как изменяется позиция активного байта в течение трех раундов (здесь предварительный раунд объединён с первым: <math> \rho[k^1] \circ  \sigma[k^0] \circ  \theta^{-1}</math>, который в итоге записывается как <math>\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)]</math>). Так как первый раунд не содержит <math>\theta</math>, то к началу второго раунда остается один активный байт. Во втором раунде <math> \theta </math> преобразует в строку активных байтов, которые <math>\pi</math> преобразует в столбец активных байт. <math>\theta</math> в третьем раунде переводит результат в <math>\Lambda</math>-множество, состоящее только из активных байт. Значения байт на выходе третьего раунда пробегают все возможные значения, следовательно, уравновешены по множеству <math> \Lambda </math>, имеем
:: <math> \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,</math>
значит байты на выходе <math>\theta</math> в четвёртом раунде уравновешены по <math>\Lambda</math>-множеству. Эта уравновещенность нарушается последующим применением <math>\gamma</math>. Выходные байты четвёртого раунда могут быть выражены с помощью функции от промежуточного состояния <math>b</math>: <math> a_{i,j} = S_\gamma[b_{j, i}]\oplus k^4 _{i,j} </math>.
Предполагая значение <math> k^4 _{i,j}</math>, значение <math> b_{j,i} </math> для всех элементов <math>\Lambda</math>-множества могут быть вычислены из шифротекстов. Если значение этого байта оказалось неуравновешенным по <math>\Lambda</math>, то предположенное значение ключа <math> k^4 _{i,j}</math> является ложным.
Этот метод криптоанализа позволил взломать 6-раундовый вариант шифра с использованием <math>2^{32}</math> блоков открытого текста и соответствующих им блоков шифротекста и выполнением <math>2^{72}</math> операций шифрования.{{sfn|The Block Cipher SQUARE|1997}}

В 2010 году была представлена атака на связанных ключах методом бумеранга. Ранее подобная атака применялась к шифрам [[KASUMI]], [[COCONUT98]], [[IDEA]] и AES-192/256. Это была первая атака на полнораундовый SQUARE.{{sfn|Koo, Yeom, Song|2010}} В 2011 году был проведён криптоанализ полнораундового варианта SQUARE с помощью [[Полный двудольный граф|полного двудольного графа]]. Данный тип атаки позволил взломать шифр с использованием одного ключа, <math>2^{48}</math> открытых текстов и проведения <math>2^{126}</math> операций шифрования.{{sfn|Biclique Cryptanalisis of the Block Cipher SQUARE|2011}}

== Особенности шифра ==
Шифр SQUARE создавался, соответствуя стратегии широкого следа — каждый раунд шифра состоит из нескольких преобразований, нелинейной перестановки и композиции линейных преобразований — что дало шифру высокую криптостойкость против линейного и дифференциального криптоанализа. Составляющие блоки алгоритма и их взаимодействие подбирались также исходя из возможности быстрой реализации на широком спектре процессоров.<ref>{{Cite web |url=http://www.drdobbs.com/database/the-block-cipher-square-algorithm/184410296 |title=The Block Cipher Square Algorithm |access-date=2013-12-13 |archive-date=2013-12-13 |archive-url=https://web.archive.org/web/20131213193926/http://www.drdobbs.com/database/the-block-cipher-square-algorithm/184410296 |deadlink=no }}</ref> Реализация алгорима на языке Си имела скорость шифрования 2.63 Мбайт/с, запускаемая на процессоре [[Pentium]] с частотой 100 МГц, а реализация на языке [[Ассемблер]] увеличивала скорость шифрования вдвое. Данный алгоритм получил развитие и стал основой нового американского стандарта — шифра [[Rijndael]], который был разработан группой авторов '''SQUARE'''. Кстати, на конкурсе AES, эксперты отметили, что «в основе алгоритма Rijndael лежит нетрадиционная парадигма, поэтому он может содержать скрытые уязвимости»{{sfn|Панасенко|2009}}. Именно по этой причине сам SQUARE сейчас используется редко, уступая в популярности своему потомку — Rijndael. Также потомком шифра является южнокорейский алгоритм [[CRYPTON]], участник конкурса AES.

== См. также ==
* [[Rijndael]]

== Примечания ==
{{примечания|28em}}

== Литература ==
* {{книга
|заглавие = [ftp://ftp.man.szczecin.pl/pub/security/cryptography/algorithms/square/fse.pdf The Block Cipher SQUARE]
|номер выпуска = 
|автор = J. Daemen, L. Knudsen, V. Rijmen
|год = 1997
|архив = 
|ref = The Block Cipher SQUARE
}}
* {{книга
|заглавие = [http://www.bibsonomy.org/bibtex/25c03edbc87c8c5ac807776247835bc5d/dblp Related-Key Boomerang Attack on Block Cipher SQUARE]
|номер выпуска = 
|автор = B. Koo, Y. Yeom, J. Song
|год = 2010
|архив = 
|ref = Koo, Yeom, Song
}}
* {{книга
|заглавие = [http://www.bibsonomy.org/bibtex/168fa74d4b5f278f1c9bbf5407b1ae8fe Biclique Cryptanalisis of the Block Cipher SQUARE]
|номер выпуска = 
|автор = H. Mala
|год = 2011
|архив = 
|ref = Biclique Cryptanalisis of the Block Cipher SQUARE
}}
* {{книга
|заглавие = [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.23.8894 Impossible diﬀerential and square attacks: Cryptanalytic link and application to Skipjack]
|номер выпуска = 
|автор = G.Piret, J.-J. Quisquater
|год = 2001
|архив = 
|ref = Impossible diﬀerential and square attacks: Cryptanalytic link and application to Skipjack
}}
* {{h|Панасенко|2009|{{source|Q27942699|ref=Панасенко|ref-year=2009}}}} <!-- Алгоритмы шифрования. Специальный справочник -->

== Ссылки ==
* [http://www.drdobbs.com/database/the-block-cipher-square-algorithm/184410296 The Block Cipher Square Algorithm], Joan Daemen, Lars R. Knudsen and and Vincent Rijmen, ''Dr. Dobb’s Journal'', October 01, 1997.

{{симметричные криптоалгоритмы}}

[[Категория:Блочные шифры]]
[[Категория:SP-сеть]]