Просмотр кода страницы CAST-256

{{смотри также|CAST-128}}
{{Блочный шифр
| название      = CAST-256
| изображение   = 
| подпись       = 
| создатель     = {{iw|Адамс, Карлайл|Карлайл Адамс|en|Carlisle Adams}}<br>{{iw|Таварес, Стаффорд|Стаффорд Таварес|en|Stafford Tavares}}
| создан        = [[1998 год]]
| опубликован   = [[1998 год]]
| размер ключа  = 128, 160, 192, 224 или 256 бит
| размер блока  = 128 бит
| число раундов = 48
| тип           = [[сеть Фейстеля]]
}}
'''CAST-256''' (или '''CAST6''') в [[криптография|криптографии]] — блочный алгоритм симметричного шифрования на основе [[Сеть Фейстеля|сети Фейстеля]], опубликованный в июне 1998 года в качестве кандидата на участие в конкурсе [[Advanced Encryption Standard|AES]]. Алгоритм разработан специалистами канадской компании Entrust Technologies.

== Основные сведения ==
Этот алгоритм основан на более раннем алгоритме '''[[CAST-128]]'''. Оба шифра построены на основе методологии [[CAST]], предложенной Карлайлом Адамсом ({{lang-en|}}Carlisle Adams) и Стаффордом Таваресом ({{lang-en|}}Stafford Tavares), первые две буквы имени которых формируют название методологии. В создании «дизайна» шифра принимали участие также [[Хейз, Говард|Хейз Говард]] и Майкл Винер.

CAST-256 построен из тех же элементов, что и CAST-128, включая S-боксы, но размер блока увеличен вдвое и равен 128 битам. Это влияет на диффузионные свойства и защиту шифра.

В RFC 2612 указано, что CAST-256 можно свободно использовать по всему миру в коммерческих и некоммерческих целях.

== Характеристики и структура алгоритма ==
[[Файл:Прямое смешивание.png|right|thumb|Алгоритм CAST 256]]
[[Файл:Раундовая функция CAST.png|right|thumb|Раундовая функция CAST256]]

Алгоритм шифрует информацию 128-битными блоками и использует несколько фиксированных размеров ключа шифрования: 128, 160, 192, 224 или 256 битов.

В алгоритме CAST-256 48 раундов. Рассмотрим первую половину шифра. 128-битный входной блок может быть разделён на четыре 32-битных субблока A<sub>in</sub>, B<sub>in</sub>, C<sub>in</sub> и D<sub>in</sub>. Субблок C<sub>in</sub> складывается по модулю 2 с D<sub>in</sub>, видоизмененного в зависимости от раундовой функции f. В результате, получаем субблок D<sub>out</sub>. После сдвига входных субблоков вправо на одну позицию, получаем четыре выходных субблока: A<sub>out</sub>, B<sub>out</sub>, C<sub>out</sub> и D<sub>out</sub>. Для второй половины шифра рассматривается сдвиг субблоков на одну позицию влево.

Нелинейные функции S<sub>j</sub> (где 1 < j < 4) являются подстановками из таблицы (S-бокс) 8x32 (в результате, происходит замена 8-битного входного значения на 32-битное). Из-за нелинейной природы, S-функции являются неотъемлемой составляющей безопасности шифра.

Операции «b», «c», и «d» представляют собой операции сложения и вычитания, которые выполняются с 32-битными операндами по модулю <math>2^{32}</math>. Операция «a» представляет собой наложение входного 32-битного субблока и 32-битного подключа (который называется маскирующим подключом). Эта операция, используя одну из 3 операций(«b», «c», или «d»), производит вращение в зависимости от 5-битного подключа (который называется подключом сдвига). Раундовые функции CAST-256 отличаются между раундами, потому что объединение операций, используемых для «a», «b», «c» и «d», различно.

Математически, типичная раундовая функция выглядит следующим образом:

: <math> W = ((K_{m_i}+X_i) \lll K_{r_i}) ~~~(1)</math>
: <math> Y_i = (( S_1 \left [ W_1 \right ] \oplus S_2 \left [ W_2 \right ] )+S_3 \left [ W_3 \right ]-S_4 \left [ W_4 \right ]</math>

где X<sub>i</sub> представляет входные 32-бита данных, W<sub>j</sub> входные 8-бит данных в S<sub>j</sub> функции, K<sub>mi</sub> и K<sub>ri</sub> представляют маскирующий подключ и подключ сдвига соответственно, Y<sub>i</sub>, есть выходные 32-бита данных, после воздействия раундовой функции, «<math>\oplus</math>» операции «+» и «-», представляют собой сложение и вычитание соответственно по модулю 2. Обозначение «<math>V \lll U</math>» представляет левый сдвиг V по отношению к U. W, X<sub>i</sub>, Y<sub>i</sub> и K<sub>mi</sub>, все они представляют собой 32-битные субблоки. K<sub>ri</sub> имеет длину 5 бит. Расшифровывание осуществляется по аналогии с шифрованием, с той лишь разницей, что подключи используются в обратной последовательности.

== Дифференциальные свойства ==
Важным критерием криптографического шифра, есть невырожденность: свойство, что все выходные биты зависят от всех входных битов, и наоборот. Влияния входных битов на выходные биты называется диффузией. Невырожденность раундовой функции вероятна, так как каждая S-функция невырожденная.

Отметим, что XOR операция не невырождена, так как только один бит из каждого субблока влияет на выходной бит. При рассмотрении дифференциальных свойств CAST-256, получаем, что выходной субблок D<sub>out</sub> в первом раунде зависит от всех входных бит субблока D<sub>in</sub>. Выходные биты субблоков A<sub>out</sub>, B<sub>out</sub> и C<sub>out</sub> не зависят от соответствующих входных бит субблоков A<sub>in</sub>, B<sub>in</sub> и C<sub>in</sub>.

В результате, получаем таблицу (таблица № 1), которая показывает зависимость шифра данных на выходе от указанных раундов. Пусть четырём 32-битным входным субблокам A<sub>in</sub>, B<sub>in</sub>, C<sub>in</sub> и D<sub>in</sub> соответствуют P<sub>1</sub>, P<sub>2</sub>, P<sub>3</sub> и P<sub>4</sub>.

=== Таблица № 1: Зависимость шифра от раунда ===
{| class="wikitable"
|-
! rowspan="2"|Раунд
|-
! Зависимости
|-
| 1 || <math>P_3</math>(<math>P_4</math>)
|-
| 2 || <math>P_2</math>(<math>P_3</math>, <math>P_4</math>)
|-
| 3 || <math>P_1</math>(<math>P_2</math>, <math>P_3</math>, <math>P_4</math>)
|-
| 4 || <math>P_4</math>(<math>P_1</math>, <math>P_2</math>, <math>P_3</math>, <math>P_4</math>)
|-
| 5 || <math>P_3</math>(<math>P_1</math>, <math>P_2</math>, <math>P_3</math>, <math>P_4</math>)
|-
| 6 || <math>P_2</math>(<math>P_1</math>, <math>P_2</math>, <math>P_3</math>, <math>P_4</math>)
|-
| 7 || <math>P_1</math>(<math>P_1</math>, <math>P_2</math>, <math>P_3</math>, <math>P_4</math>)
|}

После одного раунда биты, соответствующие P<sub>3</sub> субблока открытого текста теперь невырождены в биты преобразованного открытого текста субблока P<sub>4</sub>. Аналогично после двух раундов субблок P<sub>2</sub> невырожден в биты преобразованных P<sub>3</sub> и P<sub>4</sub>. После 4 раунда субблок, соответствующий субблоку P<sub>4</sub>, зависит от всех бит всех субблоков текста. После 7 раунда получаем полную зависимость выходных битов от входных, так как все четыре субблока P<sub>1</sub>, P<sub>2</sub>, P<sub>3</sub> и P<sub>4</sub> зависят от всех бит преобразованного открытого текста.

== Защита от линейного криптоанализа ==
[[Линейный криптоанализ]] использует построение соотношений между открытым текстом, шифротекстом и ключом, которые справедливы с высокой вероятностью в раундовой функции повторного шифрования. Основным принципом линейного криптоанализа является поиск аппроксимаций в виде:

: <math>P_{i_1} \oplus P_{i_2} \oplus... \oplus P_{i_a} \oplus C_{j_1} \oplus C_{j_2} \oplus... \oplus C_{i_b} = K_{k_1} \oplus K_{k_2} \oplus... \oplus K_{k_c} ~~~(2)</math>

где ''i<sub>1</sub>, i<sub>2</sub>,…, i<sub>a</sub>'' позиции бит открытого текста P, ''j<sub>1</sub>, j<sub>2</sub>,…, j<sub>b</sub>'' позиции зашифрованного текста C и ''k<sub>1</sub>, k<sub>2</sub>,…, k<sub>c</sub>'' позиции ключа К. Вероятность соотношений для раундов шифра оценивается следующим образом:

: <math>|p_L - \frac{1}{2}| \leqslant 2^{a-1}\cdot|p_B - \frac{1}{2}|~~~(3)</math>

где ''p<sub>L</sub>'' вероятность того, что линейное выражение (2) выполнено, ''p<sub>B</sub>'' вероятность наилучшей линейной аппроксимации любой S-функции, и ''a'' количество S-функций, участвующих в линейном аппроксимации. Стойкость к линейному криптоанализу строго зависит от общего линейного выражения, ограничивающей вероятность (которое также называют «линейной оболочкой»). Линейные атаки строятся на основе линейного выражения, включающего биты открытого текста и шифротекста (как показано в левой части (2)). В правой части равенства (2) вычисляется XOR сумма битов ключа. Для этого требуется, примерно, следующее число открытых текстов:

: <math>N_L = |p_L - \frac{1}{2}|^{-2}~~~~~~~~~~~~~~~~(4)</math>

Наилучшую линейную аппроксимацию определяет:

: <math>|p_B - \frac{1}{2}| = \frac{2^{m-1}-NL_min}{2^{m}} ~~~(5)</math>

где m количество бит входных текстов и NL<sub>min</sub> нелинейность S-функции. Для S-функций CAST-256, m = 8 и NL<sub>min</sub> = 74. В каждом раунде выходной бит данных раундовой функции равен XOR сумме всех бит 4-х входных подблоков данных (каждый подблок размером m). Поэтому линейная аппроксимация выходных бит должна состоять из линейных аппроксимаций бит всех входных подблоков. На практике вероятность линейных аппроксимаций CAST-256 гораздо больше 1/2.

Пусть для r-раундного шифра a = r. При r = 48, NL<sub>min</sub> = 74, число известных открытых текстов, которое требуется для линейного криптоанализа, составляет около <math>2^{122}</math>. Заметим, что это почти равно общему числу заданных открытых текстов (<math>2^{128}</math>) и выступает против практичности линейного нападения на этот шифр.

Более точную оценку числа открытых текстов, для линейного криптоанализа шифра CAST, можно получить, рассматривая объединение S-функций в раундовой функции. За счет объединения S-функций в результате XOR операции нелинейность NL<sub>min</sub> S-бокса (который состоит из S-функций) выше 74. Рассмотрим 32х32 S-бокс, тогда m=32 и а=r/4 (так как мы аппроксимируем раундовые функции каждый 4-й раунд). Таким образом, получаем число открытых текстов, необходимых для линейного криптоанализа 48-раундового шифра, более чем <math>2^{176}</math>(больше чем количество заданных открытых текстов). Экспериментальные данные свидетельствуют о том, что объединение S-функции, используя такие операции, как сложение или вычитание, а не XOR, может увеличить нелинейность S-бокса ещё больше.

== Защита от дифференциального криптоанализа ==
[[Дифференциальный криптоанализ]] основан на изучении преобразования разностей между шифруемыми значениями на различных раундах шифрования. Блочные шифры устойчивы по отношению к дифференциальному криптоанализу, если в каждом раунде для заданных разниц входных открытых текстов и выходных шифротекстов существует единственная пара разниц. Такие различия называют характеристиками. Как правило, наиболее эффективны различия в случае рассмотрения XOR двух блоков данных. В хорошем шифре вероятность всех отличий должна быть <math>2^{-N}</math>, где N размер блока. Для получения общей характеристики на входе и соответствующей ей характеристики на выходе XOR, составляется ряд характеристик, которые зависят от входных, выходных данных, подвергшихся операции XOR, в каждом раунде.

Анализ здесь основан на предположениях, что все ключи раундов независимы и, что выход XOR (результат, полученный после преобразования входных данных операцией XOR), соответствующий конкретному входу XOR (входные данные), независимы на разных раундах. При таких условиях, r-раундовая характеристика представляется в виде:

: <math>   p_{w_r} = \prod_{i=1}^{r} p_i ~~~(6)</math>

где ''p<sub>i</sub>'' вероятность разниц выхода XOR, соответствующие разнице входа XOR в раунде ''i''.

Шифр CAST-256 с R раундами, показанный в таблице № 2, основан на переборе 4-раудовой характеристики.

=== Таблица № 2: Наилучшая r-раундовая характеристика R-раундового шифра ===
{| class="wikitable"
| (0, 0, 0, <math>\Delta</math>) || <math>[input ~XOR~ to~ round ~1]</math>
|-
| <math>0\leftarrow\Delta</math> || <math>[round 1]</math>
|-
| <math>0\leftarrow0</math> || <math>[round 2]</math>
|-
| <math>0\leftarrow0</math> || <math>[round 3]</math>
|-
| <math>0\leftarrow0</math> || <math>[round 4]</math>
|-
| (0, 0, 0, <math>\Delta</math>) || <math>[input ~XOR~ to~ round~ 5]</math>
|-
| <math>0\leftarrow\Delta</math> || <math>[round 5]</math>
|-
| <math>0\leftarrow0</math> || <math>[round 6]</math>
|-
| <math>0\leftarrow0</math> || <math>[round 7]</math>
|-
| <math>0\leftarrow0</math> || <math>[round 8]</math>
|-
| <math>...</math> || <math>repeat~ up ~to~ R/2 ~rounds</math>
|-
| (0, 0, 0, <math>\Delta</math>) || <math>[input ~XOR~ to ~round~ R/2+1]</math>
|-
| <math>0\leftarrow\Delta</math> || <math>[round R/2+1]</math>
|-
| <math>0\leftarrow0</math> || <math>[round R/2+2]</math>
|-
| <math>0\leftarrow0</math> || <math>[round R/2+3]</math>
|-
| <math>0\leftarrow0</math> || <math>[round R/2+4]</math>
|-
| <math>...</math> || <math>repeat ~up~ to~ r~ rounds</math>
|}

XOR вектор (0, 0, 0, <math>\Delta</math>) заданных разниц, для 4 входных 32-битных субблоков, где 3 первых субблока (A<sub>in</sub>, B<sub>in</sub> и C<sub>in</sub>) имеют нулевые XOR разницы, а 4-й входной субблок (D<sub>in</sub> в раунде) имеет некоторую отличную от нуля XOR разницу, <math>\Delta</math>.

В таблице показана характеристика общего R-раундового шифра, вход XOR раунда R/2 + 1 представляет собой вектор, в котором разница одного из субблоков не равна нулю, а разницы остальных трёх субблоков равны нулю. Вектор (0, 0, 0, <math>\Delta</math>), представленный в таблице, соответствует шифру CAST-256 с R = 48.

Ненулевая разница на входе XOR соответствует нулевой разнице выхода XOR каждый 4 раунд характеристики в таблице № 2 (как показано в 1, 5 и т. д. раундах). Вероятность, с которой заданным разницам открытых текстов и заданным разницам шифротекстов соответствует единственная пара разниц, для CAST <math> p\leqslant 2^{-14}</math>. Это основано на том факте, что все четыре S-функции в раундовой функции CAST инъективны и XOR пары открытых текстов и шифротекстов имеют разницы, равные 0. В результате раундовой функции, использующей сочетание таких операций, как сложение и вычитание, будет уменьшена вероятность существования пары разниц открытых текстов и шифротекстов. Лучшая r-раунд характеристика, как показано в таблице № 2 и на основе предположений, описанных выше, определяется вероятностью:

: <math>p_{w_r}\leqslant(2^{-14})^{r/4}~~~~(4)</math>

В частности для 40-раундовой характеристики (которая потенциально могла бы быть использована для атаки 48-раундового шифра) вероятность должна быть меньше либо равна <math>2^{-140}</math>. Следовательно, число выбранных открытых текстов, необходимых для этой атаки, должно быть больше, чем <math>2^{140}</math> для 48-раундового шифра(существенно больше, чем количество открытых текстов для 128-битного размера блока).

== Расширение ключа ==
[[Файл:Расширения ключа.png|right|thumb|Расширения ключа]]
Процедура расширения ключа сложнее чем само шифрование данных. Пусть массив ключей k = (ABCDEFGH) представляющий собой 256-битный блок, где фрагменты A, B,…,H каждый длиной по 32 бита.
Пусть «k ← w<sub>i</sub>(k)», где w(<math>\cdot</math>) есть функция расширения и представима в следующем виде:

: <math>G = G \oplus f_1(H, t_{r_0}, t_{m_0})</math>
: <math>F = F \oplus f_2(G, t_{r_1}, t_{m_1})</math>
: <math>E = E \oplus f_3(F, t_{r_2}, t_{m_2})</math>
: <math>D = D \oplus f_1(E, t_{r_3}, t_{m_3})</math>
: <math>C = C \oplus f_2(D, t_{r_4}, t_{m_4})</math>
: <math>B = B \oplus f_3(C, t_{r_5}, t_{m_5})</math>
: <math>A = A \oplus f_1(B, t_{r_6}, t_{m_6})</math>
: <math>H = H \oplus f_2(A, t_{r_7}, t_{m_7})</math>

В результате 4 преобразований <math>k^{(i)}_r \leftarrow k</math> по 5 младших бита образуются подключи сдвига:

: <math>k^{(i)}_{r_0} = 5LSB(A), k^{(i)}_{r_1} = 5LSB(C), k^{(i)}_{r_2} = 5LSB(E), k^{(i)}_{r_3} = 5LSB(G)</math>

где 5LSB(x)означает образование 5 младших бит в результате операции x.
Аналогично <math>k^{(i)}_m \leftarrow k</math> образуются маскирующие подключи:

: <math>k^{(i)}_{m_0} = H, k^{(i)}_{m_1} = F, k^{(i)}_{m_2} = D, k^{(i)}_{m_3} = B</math>

=== Реализация процедуры расширения ключа ===
В каждом раунде функции расширения ключа используются по 8 дополнительных переменных <math> T^{(i)}mj </math> и <math> T^{(i)}rj </math>.

'''''1. Инициализация'''''

: <math> Cm = 2^{30}\sqrt{2} = 5A827999_16 </math>
: <math> Mm = 2^{30}\sqrt{3} = 6ED9EBA1_16 </math>
: <math> Cr = 19 </math>
: <math> Mr = 17 </math>
Пусть <math> T^{(i)}mj </math> = Tmij, <math> T^{(i)}rj </math> = Trij.

<pre>  for(i=0; i<24; i++)
     for(j=0; j<8; j++){
                Tmij = Cm
                Cm = (Cm + Mm)mod2^32
                Trij = Cr
                Cr = (Cr + Mm)mod32
          }
</pre>

'''''2. Ключ расширения:'''''

: k = ABCDEFGH = 256 бит исходного ключа K. Пусть «<math> k \leftarrow w_{2_i}(k) </math>» <math>\sim</math> «<math> W2i(k)</math>», «<math> k \leftarrow w_{2i+1}(k) </math>» <math>\sim</math>«<math>W2i+1(k) </math>», «<math>  k^{i}_r\leftarrow k </math>» <math>\sim</math>«<math>kr </math>», «<math>k^{i}_m \leftarrow k </math>»<math>\sim</math>«<math>km </math>»

<pre>    for(j=0; j<12; j++){ 
               W2i(k) 
               W2i+1(k) 
               kr
               km
         }
</pre>
Если размер ключа k меньше 256 бит, то «лишние» фрагменты ключа считаются нулевыми:

: <math>(|K| =128) \Rightarrow\,(E = F = G = H = 0) </math>
: <math>(|K| =160) \Rightarrow\, (F = G = H = 0) </math>
: <math>(|K| =192) \Rightarrow\, (G = H = 0) </math>
: <math>(|K| =224) \Rightarrow\, (H = 0) </math>

== Достоинства и недостатки алгоритма ==
В результате всестороннего анализа на первом этапе конкурса AES, причём исследовались не только криптографические свойства, такие как стойкость к известным атакам, отсутствие слабых ключей, хорошие статистические свойства, но и практические аспекты реализации: оптимизацию скорости выполнения кода на различных архитектурах (от ПК до смарт-карт и аппаратных реализаций), возможность оптимизации размера кода, возможность распараллеливания, были выявлены следующие достоинства и недостатки CAST-256 шифра.

Основными достоинствами являются:

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

В алгоритме было найдено ряд недостатков, из-за которых он не вошёл во второй раунд конкурса:

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

== Литература ==
* {{книга
 |автор         = Сергей Панасенко
 |часть         = 
 |заглавие      = Алгоритмы шифрования
 |язык          = ru
 |оригинал      = 
 |ссылка        = 
 |издание       = 
 |ответственный = 
 |место         = Санкт-Петербург
 |издательство  = БХВ-Петербург
 |год           = 2009
 |Volume        = 
 |pages         = 134—141
 |allpages      = 576 стр
 |isbn          = 978-5-9775-0319-8
 |ref           = 
}}

== Ссылки ==
* [http://www.rfc-editor.org/rfc/rfc2612.txt RFC 2612]
* [[Линейный криптоанализ]]
* [https://web.archive.org/web/20130329002354/http://www.mavi1.org/web_security/cryptography/aes-testing/cast/cast-256.pdf The CAST-256 Encryption Algorithm Carlisle Adams]
* [http://www.engr.mun.ca/~howard/PAPERS/cast256.pdf An Analysis of the CAST-256 Cipher]
* [http://www.ixbt.com/soft/alg-encryption-aes.shtml Конкурс AES]

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

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