close

Вход

Забыли?

вход по аккаунту

?

Разностная атака на 6-раундов whirlpool-подобных алгоритмов блочного шифрования.

код для вставкиСкачать
30
Прикладная дискретная математика. Приложение
k, k 0 , k 00 , k 000 ∈ V256 , удовлетворяющих равенствам
k ⊕ k 0 = k 00 ⊕ k 000 = (ε31 , 0, ε31 , 0, ε31 , 0, ε31 , 0, ε31 , 0),
k ⊕ k 00 = k 0 ⊕ k 000 = (ε31 , 0, 0, 0, 0, 0, 0, 0).
Для s-боксов из [7] применима только атака с четырьмя связанными ключами. Трудоёмкость алгоритма нахождения ключа шифрования оценивается как 244,8 зашифрований, число открытых текстов равно 226,2 , вероятность успеха — 0,99.
ЛИТЕРАТУРА
1. Seki H., Kaneko T. Differential cryptanalysis of reduced rounds of gost // Selected Areas in
Cryptography. Springer, 2000. No. 2012. P. 315–323.
2. Biham E., Dunkelman O., Keller N. Improved slide attacks // LNCS. 2007. No. 4593.
P. 153–166.
3. Kara O. Reflection Cryptanalysis of Some Ciphers // Ibid. 2008. No. 5365. P. 294–307.
4. Ko Y., Hong S., Lee W., et al. Related key differential attacks on 27 rounds of xtea and fullround gost // Ibid. 2004. No. 3017. P. 299–316.
5. Fleischmann E., Gorski M., Huhne J.-H., Lucks S. Key Recovery Attack on full GOST Block
Cipher with Zero Time and Memory // WEWoRC. 2009.
6. Rudskoy V. On zero practical significance of “Key recovery attack on full GOST block cipher
with zero time and memory” // http://eprint.iacr.org/2010/.
7. Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. М.: Триумф, 2002.
УДК 519.7
РАЗНОСТНАЯ АТАКА НА 6-РАУНДОВ WHIRLPOOL-ПОДОБНЫХ
АЛГОРИТМОВ БЛОЧНОГО ШИФРОВАНИЯ1
М. А. Пудовкина
В данной работе вводится семейство алгоритмов блочного шифрования, у которых
функция зашифрования и алгоритм развёртывания ключа имеют структуру, как у алгоритма блочного шифрования криптосистемы Whirlpool. Криптосистема Whirlpool
является одним из финалистов конкурса NESSIE и входит в международный стандарт ISO/IEC 10118-3. Это семейство алгоритмов характеризуется тем, что функция
зашифрования и алгоритм развёртывания ключа совпадают.
Обозначения: N — множество натуральных чисел; m, d, q ∈ N; n = m · d · q; Vd —
пространство d-мерных векторов над полем GF(2); ⊕ — операция сложения в векторном пространстве Vn ; α = (α̃0 , ..., α̃dq−1 ) = (α̂0 , ..., α̂q−1 ) ∈ Vn , α̃ ∈ Vm , α̂ ∈ Vmd ; S(X) —
симметрическая группа на множестве X; Xi = {id, ..., (i + 1)d − 1} , i = 0, ..., q − 1;
no — число пар открытых текстов; r̂ — произвольная подстановка из S ({0, ..., q − 1}) ,
индуцирующая при координатном действии линейное преобразование r векторов
α = (α̃0 , ..., α̃dq−1 ) векторного пространства; ĥ — произвольное линейное обратимое
−1
ĥ
преобразование из S(Vdm ); h : α = (α̃0 , ..., α̃qd−1 ) 7→ (α̂0ĥ , ..., α̂q−1
); α̂ir = α̂i∗ , i =
= 0, ..., q − 1; э. о. — элементарная операция; l — число раундов; произвольные подстановки s̃i ∈ S(Vm ) индуцируют покоординатные действия s ∈ S(Vn ), ŝj ∈ S(Vmd ) и
s̃qd−1
ŝq−1
ŝi = (s̃id , ..., s̃(i+1)d−1 ), т. е. s : α = (α̃0 , ..., α̃qd−1 ) 7→ (α̂0ŝ0 , ..., α̂q−1
) = (α̃0s̃0 , ..., α̃qd−1
).
1
Работа выполнена при поддержке гранта Президента РФ НШ № 4.2008.10.
Математические методы криптографии
31
В данной
работе
рассматриваются преобразования r, для которых выполняется соr̂
отношение Xi ∩ Xj = 1 для всех i, j ∈ {0, ..., q − 1} . Такие подстановки r̂ возможны
при q = d и используются, например, в алгоритме блочного шифрования криптосистемы Whirlpool. Приведём описание рассматриваемого семейства алгоритмов блочного
шифрования.
Алгоритм развёртывания ключа ϕ : k 7→ (k (1) , ..., k (l) ) задаётся следующим образом:
k (1) = k, k (j) = (c(j−1) ⊕ k (j−1) )srh = fk(j−1) (c(j−1) ),
где c(j) — фиксированные константы, j = 2, ..., l.
Для раундового ключа k (i) ∈ Vn раундовая функция зашифрования fk(i) : Vn → Vn
определяется как fk(i) (α) = (α ⊕ k (i) )srh .
Функция зашифрования gk : Vn → Vn определяется как
αgk = α(l) = αfk(1) ...fk(l) .
Отметим, что в рассматриваемое семейство алгоритмов при m = q = d = 8 и шести
раундах попадает алгоритм блочного шифрования криптосистемы Whirlpool.
В данной работе показано, что шесть раундов произвольного алгоритма из
рассматриваемого семейства атакуются разностным методом. Для этого построена
3-раундовая разностная характеристика с 2m + 1 активными s-боксами вероятностью
pchar > 2−(m−1)(2d+1) . Ещё три раунда удаётся «пройти» из-за следующего свойства
алгоритма развёртывания ключа.
Утверждение 1. Пусть α(0) — произвольный открытый текст из Vn и α(i) =
f
f
= α(0) k(1) ... k(i) , i ∈ {1, ..., 6} , k — ключ шифрования, ϕ : k → (k (1) , ..., k (l) ), l > 6.
Тогда справедливо равенство
(3)
(5)ĥ−1 r−1 ŝ−1
α̂j∗ = k̂j
(4)
⊕ ĉj∗ ⊕
−1 r −1 s−1 h−1 r −1
α(6)h
(5)
(5)
⊕ k̂j ⊕ cj
ŝj ŝ−1
j
!ĥ−1 r−1 ŝ−1
(5)
⊕ k̂j
.
j
(5)
Таким образом, по известным блоку шифртекста α(6) и подблокуk̂j раундового
(3)
ключа находится подблок промежуточного шифртекста α̂j∗ . Затем на основе 3-раундовой характеристики строится атака на 6-раундовый алгоритм.
Пусть pchar > 2−2dm или m 6 2d. Тогда трудоёмкость метода может быть оценена как 22dm+1 no + 2md+1 no (q − 2) э. о. При pchar 6 2−2dm трудоёмкость метода оценивается как 3 · 23dm no + 3 · 2md no (q − 3) э. о. Число необходимых пар текстов при
заданной надёжности метода находится по формуле (14) работы [1]. Оценка трудоёмкости атаки существенно зависит от выбора соотношений между параметрами m, d, q.
При m = q = d = 8 и n = 512 для алгоритма блочного шифрования криптосистемы Whirlpool оценка сверху трудоёмкости нахождения ключа шифрования равна
2236,3 э. о., а вероятность успеха — 0,9999999993, число открытых текстов — 2107,3 . Видно, что она меньше, чем корень из трудоёмкости полного перебора. Кроме того, из
свойств s-боксов в криптосистеме Whirlpool следует, что pchar > 2−(m−2)(2d+1) .
ЛИТЕРАТУРА
1. Selcuk A.,Bicak A. On Probability of Success in Linear and Differential Cryptanalysis // LNCS.
2002. No. 2365. P. 174–185.
Документ
Категория
Без категории
Просмотров
4
Размер файла
542 Кб
Теги
атаки, шифрование, алгоритм, разностные, подобные, whirlpool, блочного, раундов
1/--страниц
Пожаловаться на содержимое документа