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 можно свободно использовать по всему миру в коммерческих и некоммерческих целях.

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

Алгоритм CAST 256
Раундовая функция CAST256

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

В алгоритме CAST-256 48 раундов. Рассмотрим первую половину шифра. 128-битный входной блок может быть разделен на четыре 32-битных субблока Ain, Bin, Cin и Din. Субблок Cin складывается по модулю 2 с Din, видоизмененного в зависимости от раундовой функции f. В результате, получаем субблок Dout. После сдвига входных субблоков вправо на одну позицию, получаем четыре выходных субблока: Aout, Bout, Cout и Dout. Для второй половины шифра рассматривается сдвиг субблоков на одну позицию влево.

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

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

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

 W = ((K_{m_i}+X_i) \lll K_{r_i}) ~~~(1)
 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 ]

где Xi представляет входные 32-бита данных, Wj входные 8-бит данных в Sj функции, Kmi и Kri представляют маскирующий подключ и подключ сдвига соответственно, Yi, есть выходные 32-бита данных, после воздействия раундовой функции, «\oplus» операции «+» и «-», представляют собой сложение и вычитание соответственно по модулю 2. Обозначение «V \lll U» представляет левый сдвиг V по отношению к U. W, Xi, Yi и Kmi, все они представляют собой 32-битные субблоки. Kri имеет длину 5 бит. Расшифровывание осуществляется по аналогии с шифрованием, с той лишь разницей, что подключи используются в обратной последовательности.

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

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

Отметим, что XOR операция не невырождена, так как только один бит из каждого субблока влияет на выходной бит. При рассмотрении дифференциальных свойств CAST-256, получаем, что выходной субблок Dout в первом раунде зависит от всех входных бит субблока Din. Выходные биты субблоков Aout, Bout и Cout не зависят от соответствующих входных бит субблоков Ain, Bin и Cin.

В результате, получаем таблицу(таблица № 1), которая показывает зависимость шифра данных на выходе от указанных раундов. Пусть четырём 32-битным входным субблокам Ain, Bin, Cin и Din соответствуют P1, P2, P3 и P4.

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

Раунд
Зависимости
1 P_3(P_4)
2 P_2(P_3, P_4)
3 P_1(P_2, P_3, P_4)
4 P_4(P_1, P_2, P_3, P_4)
5 P_3(P_1, P_2, P_3, P_4)
6 P_2(P_1, P_2, P_3, P_4)
7 P_1(P_1, P_2, P_3, P_4)

После одного раунда биты, соответствующие P3 субблока открытого текста теперь невырождены в биты преобразованного открытого текста субблока P4. Аналогично после двух раундов субблок P2 невырожден в биты преобразованных P3 и P4. После 4 раунда субблок, соответствующий субблоку P4, зависит от всех бит всех субблоков текста. После 7 раунда получаем полную зависимость выходных битов от входных, так как все четыре субблока P1, P2, P3 и P4 зависят от всех бит преобразованного открытого текста.

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

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

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)

где i1, i2,…, ia позиции бит открытого текста P, j1, j2,…, jb позиции зашифрованного текста C и k1, k2,…, kc позиции ключа К. Вероятность соотношений для раундов шифра оценивается следующим образом:

|p_L - \frac{1}{2}| \leqslant 2^{a-1}\cdot|p_B - \frac{1}{2}|~~~(3)

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

N_L = |p_L - \frac{1}{2}|^{-2}~~~~~~~~~~~~~~~~(4)

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

|p_B - \frac{1}{2}| = \frac{2^{m-1}-NL_min}{2^{m}} ~~~(5)

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

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

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

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

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

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

   p_{w_r} = \prod_{i=1}^{r} p_i ~~~(6)

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

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

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

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


XOR вектор (0, 0, 0, \Delta) заданных разниц, для 4 входных 32-битных субблоков, где 3 первых субблока (Ain, Bin и Cin) имеют нулевые XOR разницы, а 4-й входной субблок (Din в раунде) имеет некоторую отличную от нуля XOR разницу, \Delta.

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

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

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

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

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

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

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

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

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

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

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

k^{(i)}_{m_0} = H, k^{(i)}_{m_1} = F, k^{(i)}_{m_2} = D, k^{(i)}_{m_3} = B

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

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

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

 Cm = 2^{30}\sqrt{2} = 5A827999_16
 Mm = 2^{30}\sqrt{3} = 6ED9EBA1_16
 Cr = 19
 Mr = 17

Пусть  T^{(i)}mj = Tmij,  T^{(i)}rj = 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. Пусть « k \leftarrow w_{2_i}(k) » ~\sim ~ « W2i(k)», « k \leftarrow w_{2i+1}(k) » ~\sim ~«W2i+1(k) », «  k^{i}_r\leftarrow k » ~\sim ~«kr », «k^{i}_m \leftarrow k »~\sim ~«km »
    for(j=0; j<12; j++){ 
               W2i(k) 
               W2i+1(k) 
               kr
               km
         }

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

(|K| =128) \Rightarrow\,(E = F = G = H = 0)
(|K| =160) \Rightarrow\, (F = G = H = 0)
(|K| =192) \Rightarrow\, (G = H = 0)
(|K| =224) \Rightarrow\, (H = 0)

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

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

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

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

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

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

Литература

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

Ссылки


Wikimedia Foundation. 2010.

Смотреть что такое "CAST-256" в других словарях:

  • CAST-256 — Trois rondes de CAST 128, à partir duquel est tiré CAST 256 Résumé Concepteur(s) Carlisle Adams, Stafford Tavares, Howard Heys et Michael Wiener Première publicatio …   Wikipédia en Français

  • CAST-256 — Entwickler Carlisle Adams, Stafford Tavares, Howard Heys, Michael Wiener Veröffentlicht 1998 Abgeleitet von CAST 128 Schlüssellänge 128, 160, 192, 224, or 256 Bits Blockgröße 128 Bit Struktur …   Deutsch Wikipedia

  • CAST-256 — Saltar a navegación, búsqueda En criptografía, CAST 256 (o CAST6) es un algoritmo de cifrado por bloques publicado en junio de 1998 y propuesto como candidato para el programa Advanced Encryption Standard (AES). Es una extensión de algoritmo de… …   Wikipedia Español

  • CAST-256 — Infobox block cipher name = CAST 256 caption = designers = Carlisle Adams, Stafford Tavares, Howard Heys, Michael Wiener publish date = 1998 derived from = CAST 128 derived to = key size = 128, 192 or 256 bits block size = 128 bits structure =… …   Wikipedia

  • CAST-256 — CAST5 Kryptografiealgorithmus mit 256 Bit Schlüssellänge (RFC2612) …   Acronyms

  • CAST-256 — CAST5 Kryptografiealgorithmus mit 256 Bit Schlüssellänge (RFC2612) …   Acronyms von A bis Z

  • CAST-128 — Создатель: Карлайл Адамс, Стаффорд Таварес Размер ключа: 40 128 бит Размер блока: 64 бит Число раундов: 12 (16 при ключе > 80 бит) Тип: Сеть Фейстеля …   Википедия

  • CAST-128 — Trois rondes de CAST 128 Résumé Concepteur(s) Carlisle Adams et Stafford Tavares pour Entrust Première publication 1996 …   Wikipédia en Français

  • CAST (криптографический алгоритм) — CAST  криптографический алгоритм с открытым ключом. CAST это популярный 64 битовый шифр, допускающий размеры ключа вплоть до 128 бит, который был разработан в Канаде Карлайслом Адамсом (Carlisle Adams) и Стаффордом Таваресом (Stafford Tavares).… …   Википедия

  • Cast (homonymie) — Cast Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Cast est un nom propre ou un nom commun d orgine anglaise ou un acronyme qui peut désigner : Sommaire 1 Saint chrétien 2 …   Wikipédia en Français


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»