CAST-256

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

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

W = ( ( K m i + X i ) ⋘ K r i ) ( 1 ) {displaystyle W=((K_{m_{i}}+X_{i})lll K_{r_{i}})~~~(1)} Y i = ( ( S 1 [ W 1 ] ⊕ S 2 [ W 2 ] ) + S 3 [ W 3 ] − S 4 [ W 4 ] {displaystyle Y_{i}=((S_{1}left[W_{1} ight]oplus S_{2}left[W_{2} ight])+S_{3}left[W_{3} ight]-S_{4}left[W_{4} ight]}

где Xi представляет входные 32-бита данных, Wj входные 8-бит данных в Sj функции, Kmi и Kri представляют маскирующий подключ и подключ сдвига соответственно, Yi, есть выходные 32-бита данных, после воздействия раундовой функции, « ⊕ {displaystyle oplus } » операции «+» и «-», представляют собой сложение и вычитание соответственно по модулю 2. Обозначение « V ⋘ U {displaystyle Vlll 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: Зависимость шифра от раунда

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

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

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

P i 1 ⊕ P i 2 ⊕ . . . ⊕ P i a ⊕ C j 1 ⊕ C j 2 ⊕ . . . ⊕ C i b = K k 1 ⊕ K k 2 ⊕ . . . ⊕ K k c ( 2 ) {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)}

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

| p L − 1 2 | ⩽ 2 a − 1 ⋅ | p B − 1 2 | ( 3 ) {displaystyle |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 − 1 2 | − 2 ( 4 ) {displaystyle N_{L}=|p_{L}-{frac {1}{2}}|^{-2}~~~~~~~~~~~~~~~~(4)}

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

| p B − 1 2 | = 2 m − 1 − N L m i n 2 m ( 5 ) {displaystyle |p_{B}-{frac {1}{2}}|={frac {2^{m-1}-NL_{m}in}{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 {displaystyle 2^{122}} . Заметим, что это почти равно общему числу заданных открытых текстов ( 2 128 {displaystyle 2^{128}} ) и выступает против практичности линейного нападения на этот шифр.

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

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

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

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

p w r = ∏ i = 1 r p i ( 6 ) {displaystyle p_{w_{r}}=prod _{i=1}^{r}p_{i}~~~(6)}

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

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

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

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

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

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

p w r ⩽ ( 2 − 14 ) r / 4 ( 4 ) {displaystyle p_{w_{r}}leqslant (2^{-14})^{r/4}~~~~(4)}

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

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

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

G = G ⊕ f 1 ( H , t r 0 , t m 0 ) {displaystyle G=Goplus f_{1}(H,t_{r_{0}},t_{m_{0}})} F = F ⊕ f 2 ( G , t r 1 , t m 1 ) {displaystyle F=Foplus f_{2}(G,t_{r_{1}},t_{m_{1}})} E = E ⊕ f 3 ( F , t r 2 , t m 2 ) {displaystyle E=Eoplus f_{3}(F,t_{r_{2}},t_{m_{2}})} D = D ⊕ f 1 ( E , t r 3 , t m 3 ) {displaystyle D=Doplus f_{1}(E,t_{r_{3}},t_{m_{3}})} C = C ⊕ f 2 ( D , t r 4 , t m 4 ) {displaystyle C=Coplus f_{2}(D,t_{r_{4}},t_{m_{4}})} B = B ⊕ f 3 ( C , t r 5 , t m 5 ) {displaystyle B=Boplus f_{3}(C,t_{r_{5}},t_{m_{5}})} A = A ⊕ f 1 ( B , t r 6 , t m 6 ) {displaystyle A=Aoplus f_{1}(B,t_{r_{6}},t_{m_{6}})} H = H ⊕ f 2 ( A , t r 7 , t m 7 ) {displaystyle H=Hoplus f_{2}(A,t_{r_{7}},t_{m_{7}})}

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

k r 0 ( i ) = 5 L S B ( A ) , k r 1 ( i ) = 5 L S B ( C ) , k r 2 ( i ) = 5 L S B ( E ) , k r 3 ( i ) = 5 L S B ( G ) {displaystyle k_{r_{0}}^{(i)}=5LSB(A),k_{r_{1}}^{(i)}=5LSB(C),k_{r_{2}}^{(i)}=5LSB(E),k_{r_{3}}^{(i)}=5LSB(G)}

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

k m 0 ( i ) = H , k m 1 ( i ) = F , k m 2 ( i ) = D , k m 3 ( i ) = B {displaystyle k_{m_{0}}^{(i)}=H,k_{m_{1}}^{(i)}=F,k_{m_{2}}^{(i)}=D,k_{m_{3}}^{(i)}=B}

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

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

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

C m = 2 30 2 = 5 A 827999 1 6 {displaystyle Cm=2^{30}{sqrt {2}}=5A827999_{1}6} M m = 2 30 3 = 6 E D 9 E B A 1 1 6 {displaystyle Mm=2^{30}{sqrt {3}}=6ED9EBA1_{1}6} C r = 19 {displaystyle Cr=19} M r = 17 {displaystyle Mr=17}

Пусть T ( i ) m j {displaystyle T^{(i)}mj} = Tmij, T ( i ) r j {displaystyle 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 ← w 2 i ( k ) {displaystyle kleftarrow w_{2_{i}}(k)} » ∼ {displaystyle sim } « W 2 i ( k ) {displaystyle W2i(k)} », « k ← w 2 i + 1 ( k ) {displaystyle kleftarrow w_{2i+1}(k)} » ∼ {displaystyle sim } « W 2 i + 1 ( k ) {displaystyle W2i+1(k)} », « k r i ← k {displaystyle k_{r}^{i}leftarrow k} » ∼ {displaystyle sim } « k r {displaystyle kr} », « k m i ← k {displaystyle k_{m}^{i}leftarrow k} » ∼ {displaystyle sim } « k m {displaystyle km} » for(j=0; j<12; j++){ W2i(k) W2i+1(k) kr km }

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

( | K | = 128 ) ⇒ ( E = F = G = H = 0 ) {displaystyle (|K|=128)Rightarrow ,(E=F=G=H=0)} ( | K | = 160 ) ⇒ ( F = G = H = 0 ) {displaystyle (|K|=160)Rightarrow ,(F=G=H=0)} ( | K | = 192 ) ⇒ ( G = H = 0 ) {displaystyle (|K|=192)Rightarrow ,(G=H=0)} ( | K | = 224 ) ⇒ ( H = 0 ) {displaystyle (|K|=224)Rightarrow ,(H=0)}

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

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

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

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

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

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