Материал из РУВИКИ — свободной энциклопедии

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

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

где Xi представляет входные 32-бита данных, Wj входные 8-бит данных в Sj функции, Kmi и Kri представляют маскирующий подключ и подключ сдвига соответственно, Yi, есть выходные 32-бита данных, после воздействия раундовой функции, «» операции «+» и «-», представляют собой сложение и вычитание соответственно по модулю 2. Обозначение «» представляет левый сдвиг 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 ()
2 (, )
3 (, , )
4 (, , , )
5 (, , , )
6 (, , , )
7 (, , , )

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

Защита от линейного криптоанализа[править | править код]

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

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

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

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

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

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

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

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

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

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

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

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

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

(0, 0, 0, )
(0, 0, 0, )
(0, 0, 0, )


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

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

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

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

Расширение ключа[править | править код]

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

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

В результате 4 преобразований по 5 младших бита образуются подключи сдвига:

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

Реализация процедуры расширения ключа[править | править код]

В каждом раунде функции расширения ключа используются по 8 дополнительных переменных и .

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

Пусть = Tmij, = 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. Пусть «» «», «» «», «» «», «»«»
    for(j=0; j<12; j++){ 
               W2i(k) 
               W2i+1(k) 
               kr
               km
         }

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

Достоинства и недостатки алгоритма[править | править код]

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

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

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

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

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

Литература[править | править код]

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

Ссылки[править | править код]