CAST-256

CAST-256
CAST-256
Создатель	Карлайл Адамс[англ.]; Стаффорд Таварес[англ.]
Создан	1998 год
Опубликован	1998 год
Размер ключа	128, 160, 192, 224 или 256 бит
Размер блока	128 бит
Число раундов	48
Тип	сеть Фейстеля

CAST-256 (или CAST6) в криптографии — блочный алгоритм симметричного шифрования на основе сети Фейстеля, опубликованный в июне 1998 года в качестве кандидата на участие в конкурсе AES. Алгоритм разработан специалистами канадской компании Entrust Technologies.

Основные сведения

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

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

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

Характеристики и структура алгоритма

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

В алгоритме CAST-256 48 раундов. Рассмотрим первую половину шифра. 128-битный входной блок может быть разделён на четыре 32-битных субблока A_in, B_in, C_in и D_in. Субблок C_in складывается по модулю 2 с D_in, видоизмененного в зависимости от раундовой функции f. В результате, получаем субблок D_out. После сдвига входных субблоков вправо на одну позицию, получаем четыре выходных субблока: A_out, B_out, C_out и D_out. Для второй половины шифра рассматривается сдвиг субблоков на одну позицию влево.

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

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

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

[math]\displaystyle{ W = ((K_{m_i}+X_i) \lll K_{r_i}) ~~~(1) }[/math]

[math]\displaystyle{ 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_i представляет входные 32-бита данных, W_j входные 8-бит данных в S_j функции, K_mi и K_ri представляют маскирующий подключ и подключ сдвига соответственно, Y_i, есть выходные 32-бита данных, после воздействия раундовой функции, «[math]\displaystyle{ \oplus }[/math]» операции «+» и «-», представляют собой сложение и вычитание соответственно по модулю 2. Обозначение «[math]\displaystyle{ V \lll U }[/math]» представляет левый сдвиг V по отношению к U. W, X_i, Y_i и K_mi, все они представляют собой 32-битные субблоки. K_ri имеет длину 5 бит. Расшифровывание осуществляется по аналогии с шифрованием, с той лишь разницей, что подключи используются в обратной последовательности.

Дифференциальные свойства

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

Отметим, что XOR операция не невырождена, так как только один бит из каждого субблока влияет на выходной бит. При рассмотрении дифференциальных свойств CAST-256, получаем, что выходной субблок D_out в первом раунде зависит от всех входных бит субблока D_in. Выходные биты субблоков A_out, B_out и C_out не зависят от соответствующих входных бит субблоков A_in, B_in и C_in.

В результате, получаем таблицу (таблица № 1), которая показывает зависимость шифра данных на выходе от указанных раундов. Пусть четырём 32-битным входным субблокам A_in, B_in, C_in и D_in соответствуют P₁, P₂, P₃ и P₄.

Таблица № 1: Зависимость шифра от раунда

Раунд
Раунд	Зависимости
1	[math]\displaystyle{ P_3 }[/math]([math]\displaystyle{ P_4 }[/math])
2	[math]\displaystyle{ P_2 }[/math]([math]\displaystyle{ P_3 }[/math], [math]\displaystyle{ P_4 }[/math])
3	[math]\displaystyle{ P_1 }[/math]([math]\displaystyle{ P_2 }[/math], [math]\displaystyle{ P_3 }[/math], [math]\displaystyle{ P_4 }[/math])
4	[math]\displaystyle{ P_4 }[/math]([math]\displaystyle{ P_1 }[/math], [math]\displaystyle{ P_2 }[/math], [math]\displaystyle{ P_3 }[/math], [math]\displaystyle{ P_4 }[/math])
5	[math]\displaystyle{ P_3 }[/math]([math]\displaystyle{ P_1 }[/math], [math]\displaystyle{ P_2 }[/math], [math]\displaystyle{ P_3 }[/math], [math]\displaystyle{ P_4 }[/math])
6	[math]\displaystyle{ P_2 }[/math]([math]\displaystyle{ P_1 }[/math], [math]\displaystyle{ P_2 }[/math], [math]\displaystyle{ P_3 }[/math], [math]\displaystyle{ P_4 }[/math])
7	[math]\displaystyle{ P_1 }[/math]([math]\displaystyle{ P_1 }[/math], [math]\displaystyle{ P_2 }[/math], [math]\displaystyle{ P_3 }[/math], [math]\displaystyle{ P_4 }[/math])

После одного раунда биты, соответствующие P₃ субблока открытого текста теперь невырождены в биты преобразованного открытого текста субблока P₄. Аналогично после двух раундов субблок P₂ невырожден в биты преобразованных P₃ и P₄. После 4 раунда субблок, соответствующий субблоку P₄, зависит от всех бит всех субблоков текста. После 7 раунда получаем полную зависимость выходных битов от входных, так как все четыре субблока P₁, P₂, P₃ и P₄ зависят от всех бит преобразованного открытого текста.

Защита от линейного криптоанализа

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

[math]\displaystyle{ 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₁, i₂,…, i_a позиции бит открытого текста P, j₁, j₂,…, j_b позиции зашифрованного текста C и k₁, k₂,…, k_c позиции ключа К. Вероятность соотношений для раундов шифра оценивается следующим образом:

[math]\displaystyle{ |p_L - \frac{1}{2}| \leqslant 2^{a-1}\cdot|p_B - \frac{1}{2}|~~~(3) }[/math]

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

[math]\displaystyle{ N_L = |p_L - \frac{1}{2}|^{-2}~~~~~~~~~~~~~~~~(4) }[/math]

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

[math]\displaystyle{ |p_B - \frac{1}{2}| = \frac{2^{m-1}-NL_min}{2^{m}} ~~~(5) }[/math]

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

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

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

Защита от дифференциального криптоанализа

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

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

[math]\displaystyle{ p_{w_r} = \prod_{i=1}^{r} p_i ~~~(6) }[/math]

где p_i вероятность разниц выхода XOR, соответствующие разнице входа XOR в раунде i.

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

Таблица № 2: Наилучшая r-раундовая характеристика R-раундового шифра

(0, 0, 0, [math]\displaystyle{ \Delta }[/math])	[math]\displaystyle{ [input ~XOR~ to~ round ~1] }[/math]
[math]\displaystyle{ 0\leftarrow\Delta }[/math]	[math]\displaystyle{ [round 1] }[/math]
[math]\displaystyle{ 0\leftarrow0 }[/math]	[math]\displaystyle{ [round 2] }[/math]
[math]\displaystyle{ 0\leftarrow0 }[/math]	[math]\displaystyle{ [round 3] }[/math]
[math]\displaystyle{ 0\leftarrow0 }[/math]	[math]\displaystyle{ [round 4] }[/math]
(0, 0, 0, [math]\displaystyle{ \Delta }[/math])	[math]\displaystyle{ [input ~XOR~ to~ round~ 5] }[/math]
[math]\displaystyle{ 0\leftarrow\Delta }[/math]	[math]\displaystyle{ [round 5] }[/math]
[math]\displaystyle{ 0\leftarrow0 }[/math]	[math]\displaystyle{ [round 6] }[/math]
[math]\displaystyle{ 0\leftarrow0 }[/math]	[math]\displaystyle{ [round 7] }[/math]
[math]\displaystyle{ 0\leftarrow0 }[/math]	[math]\displaystyle{ [round 8] }[/math]
[math]\displaystyle{ ... }[/math]	[math]\displaystyle{ repeat~ up ~to~ R/2 ~rounds }[/math]
(0, 0, 0, [math]\displaystyle{ \Delta }[/math])	[math]\displaystyle{ [input ~XOR~ to ~round~ R/2+1] }[/math]
[math]\displaystyle{ 0\leftarrow\Delta }[/math]	[math]\displaystyle{ [round R/2+1] }[/math]
[math]\displaystyle{ 0\leftarrow0 }[/math]	[math]\displaystyle{ [round R/2+2] }[/math]
[math]\displaystyle{ 0\leftarrow0 }[/math]	[math]\displaystyle{ [round R/2+3] }[/math]
[math]\displaystyle{ 0\leftarrow0 }[/math]	[math]\displaystyle{ [round R/2+4] }[/math]
[math]\displaystyle{ ... }[/math]	[math]\displaystyle{ repeat ~up~ to~ r~ rounds }[/math]

XOR вектор (0, 0, 0, [math]\displaystyle{ \Delta }[/math]) заданных разниц, для 4 входных 32-битных субблоков, где 3 первых субблока (A_in, B_in и C_in) имеют нулевые XOR разницы, а 4-й входной субблок (D_in в раунде) имеет некоторую отличную от нуля XOR разницу, [math]\displaystyle{ \Delta }[/math].

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

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

[math]\displaystyle{ p_{w_r}\leqslant(2^{-14})^{r/4}~~~~(4) }[/math]

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

Расширение ключа

Процедура расширения ключа сложнее чем само шифрование данных. Пусть массив ключей k = (ABCDEFGH) представляющий собой 256-битный блок, где фрагменты A, B,…,H каждый длиной по 32 бита. Пусть «k ← w_i(k)», где w([math]\displaystyle{ \cdot }[/math]) есть функция расширения и представима в следующем виде:

[math]\displaystyle{ G = G \oplus f_1(H, t_{r_0}, t_{m_0}) }[/math]

[math]\displaystyle{ F = F \oplus f_2(G, t_{r_1}, t_{m_1}) }[/math]

[math]\displaystyle{ E = E \oplus f_3(F, t_{r_2}, t_{m_2}) }[/math]

[math]\displaystyle{ D = D \oplus f_1(E, t_{r_3}, t_{m_3}) }[/math]

[math]\displaystyle{ C = C \oplus f_2(D, t_{r_4}, t_{m_4}) }[/math]

[math]\displaystyle{ B = B \oplus f_3(C, t_{r_5}, t_{m_5}) }[/math]

[math]\displaystyle{ A = A \oplus f_1(B, t_{r_6}, t_{m_6}) }[/math]

[math]\displaystyle{ H = H \oplus f_2(A, t_{r_7}, t_{m_7}) }[/math]

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

[math]\displaystyle{ 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]\displaystyle{ k^{(i)}_m \leftarrow k }[/math] образуются маскирующие подключи:

[math]\displaystyle{ k^{(i)}_{m_0} = H, k^{(i)}_{m_1} = F, k^{(i)}_{m_2} = D, k^{(i)}_{m_3} = B }[/math]

Реализация процедуры расширения ключа

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

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

[math]\displaystyle{ Cm = 2^{30}\sqrt{2} = 5A827999_16 }[/math]

[math]\displaystyle{ Mm = 2^{30}\sqrt{3} = 6ED9EBA1_16 }[/math]

[math]\displaystyle{ Cr = 19 }[/math]

[math]\displaystyle{ Mr = 17 }[/math]

Пусть [math]\displaystyle{ T^{(i)}mj }[/math] = Tmij, [math]\displaystyle{ T^{(i)}rj }[/math] = Trij.

  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
          }

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

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

    for(j=0; j<12; j++){ 
               W2i(k) 
               W2i+1(k) 
               kr
               km
         }

Если размер ключа k меньше 256 бит, то «лишние» фрагменты ключа считаются нулевыми:

[math]\displaystyle{ (|K| =128) \Rightarrow\,(E = F = G = H = 0) }[/math]

[math]\displaystyle{ (|K| =160) \Rightarrow\, (F = G = H = 0) }[/math]

[math]\displaystyle{ (|K| =192) \Rightarrow\, (G = H = 0) }[/math]

[math]\displaystyle{ (|K| =224) \Rightarrow\, (H = 0) }[/math]

Достоинства и недостатки алгоритма

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

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

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

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

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

Литература

Сергей Панасенко. Алгоритмы шифрования (рус.). — Санкт-Петербург: БХВ-Петербург, 2009. — P. 134—141. — 576 стр p. — ISBN 978-5-9775-0319-8.

Ссылки

Симметричные криптосистемы
Потоковые шифры	A3 A5 A8 Decim F-FCSR Grain HC-256 KCipher-2 MICKEY MUGI PIKE Phelix RC4 Rabbit SEAL SNOW SOSEMANUK Salsa20 STRUMOK Trivium VMPC
Сеть Фейстеля	ГОСТ 28147-89 (Магма) Blowfish Camellia CAST-128 CAST-256 CIPHERUNICORN-A CIPHERUNICORN-E CLEFIA Cobra DEAL DES DESX DFC E2 EnRUPT FEAL HPC IDEA KASUMI Khafre Khufu LOKI97 MacGuffin MARS MESH MISTY1 NewDES NDS RC5 RC6 SEED Simon Sinople Skipjack SM4 Speck TEA XTEA XXTEA Raiden RTEA Triple DES Twofish
SP-сеть	Кузнечик 3-WAY ABC ARIA AES (Rijndael) Akelarre Anubis BaseKing BassOmatic BelT CRYPTON Diamond2 Grand Cru Hierocrypt-3 Hierocrypt-L1 KHAZAD Kalyna Lucifer Present Rainbow SAFER SHARK SQUARE Serpent Threefish
Другие	FROG NUSH REDOC SC2000 SHACAL CS-Cipher