Меню Главная Случайная статья Настройки SQUARE Материал из https://ru.wikipedia.org SQUARE — в криптографии симметричный блочный криптоалгоритм, разработанный в 1997 году Винсентом Рэйменом, Йоаном Дайменом и Ларсом Кнудсеном. Считается предшественником алгоритма AES. Структура алгоритма была подобрана авторами для возможности получения эффективной реализации на широком спектре процессоров, а также для криптостойкости к дифференциальному и линейному криптоанализу. Содержание 1 Описание алгоритма 1.1 Преобразования в раунде шифрования 1.1.1 Линейное преобразование '"`UNIQ--postMath-00000002-QINU`"' 1.1.2 Нелинейное преобразование '"`UNIQ--postMath-00000018-QINU`"' 1.1.3 Байтовая перестановка '"`UNIQ--postMath-0000001B-QINU`"' 1.1.4 Сложение с ключом раунда '"`UNIQ--postMath-0000001D-QINU`"' 1.2 Процедура получения ключей 2 Шифрование 3 Расшифрование 4 Безопасность 4.1 Исследование криптостойкости создателями алгоритма 4.1.1 Описание Square-атаки 5 Особенности шифра 6 См. также 7 Примечания 8 Литература 9 Ссылки Описание алгоритма Алгоритм SQUARE использует ключ длиной 128 бит, данные шифруются 128-битными блоками, однако модульный подход к построению шифра позволяет легко расширить до больших размеров длину ключа и длину блока данных. Один раунд SQUARE состоит из четырёх отдельных преобразований. Данные представляются байтовым квадратом размера 4x4. Основные составляющие этого шифра — это пять различных обратимых преобразований, которые воздействуют на массив байтов размера ${\displaystyle 4\times 4}$.[1] Преобразования в раунде шифрования Линейное преобразование ${\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}}$.[2] Данное преобразование является табличной заменой ${\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, и так далее.[1] Байтовая перестановка осуществляет транспонирование байтового квадрата, то есть ${\displaystyle {a_{i,j}=a_{j,i}}}$. Эта операция — побитовое сложение 128 бит данных с ключом раунда, ${\displaystyle {b=a\oplus K_{i}}}$, где: ${\displaystyle {a}}$ и ${\displaystyle {b}}$ — значение 128 бит данных перед преобразованием и после; ${\displaystyle {K_{i}}}$ — ключ раунда ${\displaystyle {i}}$.[2] Процедура получения ключей Для шифрования необходимо получить 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}]}$; Исходный ключ алгоритма шифрования используется как ключ для предварительного раунда.[2] Шифрование Обозначим один раунд шифрования как ${\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}}$.[2] Расшифрование Алгоритм расшифрования аналогичен алгоритму шифрования, но вместо преобразований ${\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 }$.[2] Безопасность Исследование криптостойкости создателями алгоритма Алгоритм обладает высокой стойкостью против линейного и дифференциального криптоанализа, благодаря преобразованиям ${\displaystyle \theta }$ и ${\displaystyle \gamma }$, которые понижают максимальную вероятность появления дифференциальных следов и максимальную корреляцию линейных следов за 4 раунда преобразований. Первый криптоанализ SQUARE был проведён его авторами с использованием интегрального криптоанализа, который позже стал известен как Square-атака.[2] Прежде всего, введем несколько определений: Определение 1: Пусть ${\displaystyle \Lambda }$-множество — набор из 256 16-байтовых состояний, каждое из которых отличается от других в некоторых байтах, которые назовём активными, и совпадают в некоторых байтах, которые будем называть пассивными. Далее, ${\displaystyle \lambda }$ — это набор индексов активных байтов.[3] Имеем: ${\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 }$-множеству.[3] Применение преобразований ${\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 }$ является линейной комбинацией четырёх входных байт в той же строке, то, подавая строку с всего одним активным байтом, на выходе получим строку состоящую только из активных байт. [2] Рассмотрим ${\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}}$ операций шифрования.[2] В 2010 году была представлена атака на связанных ключах методом бумеранга. Ранее подобная атака применялась к шифрам KASUMI, COCONUT98, IDEA и AES-192/256. Это была первая атака на полнораундовый SQUARE.[4] В 2011 году был проведён криптоанализ полнораундового варианта SQUARE с помощью полного двудольного графа. Данный тип атаки позволил взломать шифр с использованием одного ключа, ${\displaystyle 2^{48}}$ открытых текстов и проведения ${\displaystyle 2^{126}}$ операций шифрования.[5] Особенности шифра Шифр SQUARE создавался, соответствуя стратегии широкого следа — каждый раунд шифра состоит из нескольких преобразований, нелинейной перестановки и композиции линейных преобразований — что дало шифру высокую криптостойкость против линейного и дифференциального криптоанализа. Составляющие блоки алгоритма и их взаимодействие подбирались также исходя из возможности быстрой реализации на широком спектре процессоров.[6] Реализация алгорима на языке Си имела скорость шифрования 2.63 Мбайт/с, запускаемая на процессоре Pentium с частотой 100 МГц, а реализация на языке Ассемблер увеличивала скорость шифрования вдвое. Данный алгоритм получил развитие и стал основой нового американского стандарта — шифра Rijndael, который был разработан группой авторов SQUARE. Кстати, на конкурсе AES, эксперты отметили, что «в основе алгоритма Rijndael лежит нетрадиционная парадигма, поэтому он может содержать скрытые уязвимости»[1]. Именно по этой причине сам SQUARE сейчас используется редко, уступая в популярности своему потомку — Rijndael. Также потомком шифра является южнокорейский алгоритм CRYPTON, участник конкурса AES. См. также Rijndael Примечания 1 2 3 Панасенко, 2009. 1 2 3 4 5 6 7 8 The Block Cipher SQUARE, 1997. 1 2 Impossible dierential and square attacks: Cryptanalytic link and application to Skipjack, 2001. Koo, Yeom, Song, 2010. Biclique Cryptanalisis of the Block Cipher SQUARE, 2011. The Block Cipher Square Algorithm  (неопр.). Дата обращения: 13 декабря 2013. Архивировано 13 декабря 2013 года. Литература J. Daemen, L. Knudsen, V. Rijmen. The Block Cipher SQUARE. — 1997. Панасенко С. П. Алгоритмы шифрования. Специальный справочник — СПб.: BHV-СПб, 2009. — 576 с. Ссылки The Block Cipher Square Algorithm, Joan Daemen, Lars R. Knudsen and and Vincent Rijmen, Dr. Dobb’s Journal, October 01, 1997.