Показатели и оценки стойкости блочных шифров относительно статистических атак первого порядка
Получены аналитические верхние оценки надежности различающей и, соответственно, «вскрывающей» статистической атаки первого порядка на блочные шифры. Указанные оценки позволяют ввести теоретически обоснованные показатели стойкости блочных шифров относительно обобщенного линейного, билинейного и ряда...
Збережено в:
| Опубліковано в: : | Реєстрація, зберігання і обробка даних |
|---|---|
| Дата: | 2006 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут проблем реєстрації інформації НАН України
2006
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/50863 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Показатели и оценки стойкости блочных шифров относительно статистических атак первого порядка / А.Н. Алексейчук, А.С. Шевцов // Реєстрація, зберігання і оброб. даних. — 2006. — Т. 8, № 4. — С. 53-63. — Бібліогр.: 15 назв. — pос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859613795283894272 |
|---|---|
| author | Алексейчук, А.Н. Шевцов, А.С. |
| author_facet | Алексейчук, А.Н. Шевцов, А.С. |
| citation_txt | Показатели и оценки стойкости блочных шифров относительно статистических атак первого порядка / А.Н. Алексейчук, А.С. Шевцов // Реєстрація, зберігання і оброб. даних. — 2006. — Т. 8, № 4. — С. 53-63. — Бібліогр.: 15 назв. — pос. |
| collection | DSpace DC |
| container_title | Реєстрація, зберігання і обробка даних |
| description | Получены аналитические верхние оценки надежности различающей и, соответственно, «вскрывающей» статистической атаки первого порядка на блочные шифры. Указанные оценки позволяют ввести теоретически обоснованные показатели стойкости блочных шифров относительно обобщенного линейного, билинейного и ряда других методов криптоанализа. В случае линейной различающей атаки полученная оценка стойкости блочных шифров является более точной по сравнению с ранее известной.
Отримано аналітичні верхні оцінки надійності розрізнювальної та, відповідно, «вскриваючої» статистичної атаки першого порядку на блокові шифри. Зазначені оцінки дозволяють ввести теоретично обґрунтовані показники стійкості блокових шифрів відносно узагальненого лінійного, білінійного і низки інших методів криптоаналізу. У випадку лінійної розрізнювальної атаки отримана оцінка стійкості блокових шифрів є більш точною у порівнянні з раніше відомою.
Analytical upper estimations of the success probability of a distinguishing and, consequently, a «breaking» first order statistical attack on block ciphers are obtained. These estimations form a foundament for the definition of measures that characterize provable security of block ciphers against generalized linear, bilinear and some other cryptanalysis techniques. For the case of linear distinguishing attack, the obtained estimation of block ciphers security is more accurate that the previous well-known estimation.
|
| first_indexed | 2025-11-28T16:53:26Z |
| format | Article |
| fulltext |
Методи захисту інформації
в комп’ютерних системах і мережах
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2006, Т. 8, № 4 53
УДК 621.391:519.2
А. Н. Алексейчук, А. С. Шевцов
Специальный факультет СБ Украины в составе Военного института
телекоммуникаций и информатизации НТУУ «КПИ»
Показатели и оценки стойкости блочных шифров
относительно статистических атак первого порядка
Получены аналитические верхние оценки надежности различающей и,
соответственно, «вскрывающей» статистической атаки первого по-
рядка на блочные шифры. Указанные оценки позволяют ввести тео-
ретически обоснованные показатели стойкости блочных шифров от-
носительно обобщенного линейного, билинейного и ряда других мето-
дов криптоанализа. В случае линейной различающей атаки полученная
оценка стойкости блочных шифров является более точной по сравне-
нию с ранее известной.
Ключевые слова: криптографическая защита информации, блочный
шифр, обоснованная стойкость, статистическая атака, статисти-
ческий критерий.
Введение
Одной из центральных проблем современной симметричной криптографии
является создание общей теории обоснования стойкости блочных шифров. Разно-
образие существующих методов их криптоанализа, появление новых перспектив-
ных направлений в этой области [1] требуют систематизации, упорядочения и ос-
мысления с единых, общих позиций накопленных фактов и отдельных теоретиче-
ских результатов. Отметим работы [2, 3], в которых представлены концептуаль-
ные подходы к обоснованию стойкости блочных шифров на основе понятий раз-
личающей атаки, декорреляции и, соответственно, стохастической коммутатив-
ной диаграммы.
Несмотря на повышенное внимание специалистов к проблеме теоретического
обоснования эффективности известных статистических методов криптоанализа
блочных шифров [2–6], эти методы, в подавляющем большинстве, остаются полу-
эвристическими, «работающими» на практике, но не имеющими строгого обосно-
вания. К их числу относятся классические методы дифференциального и линей-
ного криптоанализа, а также их многочисленные обобщения [1, 3, 7–10], в частно-
сти, предложенный недавно метод билинейного криптоанализа шифров Фейстеля
© А. Н. Алексейчук, А. С. Шевцов
А. Н. Алексейчук, А. С. Шевцов
54
[11]. Отсутствие строгости в обосновании известных оценок надежности (вероят-
ности правильного восстановления ключа) или сложности (необходимого числа
открытых сообщений) указанных статистических методов связано, прежде всего,
с использованием, в явном или неявном виде, различных эвристических или уп-
рощающих предположений, наподобие гипотез «о стохастической эквивалентно-
сти», «строгой различимости ключей» и др. [8–10, 12, 13]. Как отмечено в [13]
(стр. 414), проверить эти предположения для реальных криптосхем практически
невозможно; кроме того, обычно несложно построить пример криптосистемы, для
которой рассматриваемое предположение не выполнено. Безукоризненно строгое
обоснование условий, обеспечивающих стойкость блочных шифров относительно
различающих атак, предложено в [2]. Вместе с тем, модель различающей атаки
является несколько ограничительной, и результаты [2] непосредственно не при-
менимы к решению задач оценки или обоснования стойкости блочных шифров
относительно практических («вскрывающих») атак.
Целью настоящей статьи является построение теоретически обоснованных
верхних оценок надежности статистических (различающей и «вскрывающей»)
атак первого порядка на блочные шифры. (Согласно [2, 3], атаками первого по-
рядка называются атаки на основе известных или подобранных открытых сооб-
щений, при которых для получения очередной «порции» информации о ключе
криптоаналитику достаточно зашифровать ровно одно сообщение. Примерами
служат атаки, основанные на методах линейного, обобщенного линейного, били-
нейного криптоанализа или методе криптоанализа на основе разбиений [7–11].
Дифференциальному криптоанализу соответствуют атаки второго порядка, по-
скольку в этом случае зашифрованию подвергаются определенные пары откры-
тых сообщений). Полученные оценки позволяют ввести показатели стойкости
блочных шифров относительно указанных атак (методов криптоанализа), не при-
бегая к каким-либо эвристическим или упрощающим предположениям. Для слу-
чая линейной различающей атаки получена новая оценка стойкости блочных
шифров (сложности атаки), которая оказывается на один–два порядка точнее ра-
нее известной оценки [2].
Постановка задачи
Обозначим nVS симметрическую группу подстановок на множестве
n
nV }1 ,0{= . Зафиксируем отличную от константы булеву функцию
}1,0{: ®´ nn VVj . Для любой подстановки nVScÎ обозначим )(XIc индикатор
события }0))(,({ =XcXj , где X — случайный равновероятный двоичный вектор
длины n . По определению 1)( =XIc , если 0))(,( =XcXj ; 0)( =XIc — в про-
тивном случае. Положим:
}1)({ == XIp cc P , ,)12( 2-= cc pl nVScÎ .
Показатели и оценки стойкости блочных шифров
относительно статистических атак первого порядка
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2006, Т. 8, № 4 55
Для любого множества nVSN Í обозначим символом Nl среднее значение cl по
всем NcÎ : å
Î
-=
Nc
cN N ll 1|| .
Рассмотрим произвольный блочный шифр Â с множеством открытых (шиф-
рованных) сообщений nV , множеством ключей K и семейством шифрующих
преобразований ):( Kkf k Î=L . Различающая атака на шифр Â, основанная на
отображении j , осуществляется при следующих вероятностных предположениях
[2]. Вначале с вероятностью 2
1 выбирается число }1,0{În . Затем фиксируется
значение случайной подстановки C , которая распределена равномерно на всей
симметрической группе nVS , если 0=n , и совпадает с вероятностью 1|| -K с лю-
бой из подстановок kf , Kk Î , если 1=n . (Другими словами при 0=n C — слу-
чайная равновероятная подстановка на множестве nV , а при 1=n C — случайное
и равновероятное шифрующее преобразование данного шифра Â ). Атака состоит
в проведении t независимых испытаний, в і-м из которых криптоаналитик гене-
рирует случайный вектор iX с равномерным распределением на множестве nV и
вычисляет значение случайной величины:
tiXCXIXI iiiCi ,1},0))(,({)( Î=== jx . (1)
При этом предполагается, что случайные векторы tXX ...,,1 не зависят от слу-
чайной подстановки C . Целью атаки является проверка по наблюдаемой реализа-
ции случайной последовательности
t
t xxx ...,,1
)( = (2)
статистической гипотезы 0:0 =nH относительно альтернативы 1:1 =nH .
Итак, описанная атака состоит в том, чтобы отличить по результатам зашиф-
рования t открытых сообщений tXX ...,,1 (на основе информации, содержащейся
в реализации случайной последовательности (2)) данный шифр Â от случайной
равновероятной подстановки на множестве nV . В соответствии с терминологией
[2], указанная атака относится к классу неадаптивных различающих атак первого
порядка на блочный шифр Â . В частном случае, когда функция j имеет вид
)()(),( yhxgyx Å=j , 2),( nVyx Î , где }1,0{: , ®nVhg — уравновешенные буле-
вы функции, эта атака может быть названа обобщенной линейной [9] (в частно-
сти, если g и h — ненулевые линейные булевы функции, то это — классическая
линейная различающая атака на шифр Â [2, 3, 5]). В случае, когда Â является
шифром Фейстеля, )()(),( yhxgyx Å=j и T
21)()( xAxxhxg == , nVxxx Î= ),( 21 ,
mVxx Î21 , , где mn 2= , A — обратимая матрица порядка m над полем )2(GF ,
А. Н. Алексейчук, А. С. Шевцов
56
получаем билинейную различающую атаку [11]. Стойкость шифра Â относи-
тельно описанной атаки характеризуется предпочтением (advantage) оптимально-
го статистического критерия для проверки гипотезы 0H против альтернативы 1H
[2, 5].
Заметим, что различающую атаку нетрудно модифицировать таким образом,
чтобы получить «вскрывающую» статистическую атаку на блочный шифр Â . Эта
«вскрывающая» атака проводится на основе выбираемых открытых сообщений и
использует, помимо указанной выше булевой функции j , уравновешенную функ-
цию }1,0{: ®y K .
Пусть KkÎ — неизвестный ключ шифра Â , выбранный с вероятностью
1|| -K из множества K . При проведении атаки криптоаналитик генерирует t неза-
висимых, случайных и равновероятных открытых сообщений tXX ...,,1 , зашиф-
ровывает их на ключе k и вычисляет значения случайных величин (1), где C обо-
значает случайное и равновероятное шифрующее преобразование шифра Â . Цель
атаки состоит в том, чтобы восстановить значение )(ky , то есть проверить по
наблюдаемой реализации случайной последовательности (2) справедливость ги-
потезы 0)(ш:0 =KH относительно альтернативы 1)(ш:1 =KH .
Основная задача, решаемая в данной статье, заключается в нахождении ана-
литических выражений верхних границ предпочтения оптимального критерия для
проверки гипотез 0H и 1H (как для различающей, так и для «вскрывающей»
атак), явно зависящих от шифра Â и функции j .
Вспомогательные сведения о статистических критериях
для проверки простых гипотез
Пусть N — произвольное конечное множество, 0P и 1P — распределения ве-
роятностей на N , x — случайная величина, закон распределения которой с веро-
ятностью 2
1 может быть равен 0P или 1P . Рассмотрим две гипотезы относитель-
но распределения случайной величины x : 0H : x распределена по закону 0P ; 1H :
x распределена по закону 1P .
Статистический критерий для проверки гипотезы 0H против альтернативы
1H определяется критическим множеством A , состоящим из тех и только тех
значений случайной величины x , при реализации (наблюдении) каждого из кото-
рых гипотеза 0H отвергается. Средняя вероятность ошибки AeP , критерия, осно-
ванного на критическом множестве A , определяется по формуле:
))()((2
1
10, AAP Ae Ï+Î= xx PP . (3)
Число
|)()(||12| 10, AAP AeA Î-Î=-= xxp PP (4)
Показатели и оценки стойкости блочных шифров
относительно статистических атак первого порядка
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2006, Т. 8, № 4 57
называется предпочтением данного критерия [2], а число AeP ,1- — его надежно-
стью [13]. Известно (см., например, [13]), что оптимальным (в смысле минимума
значений (3) или, что тоже самое, максимума значений (4)) критерием различия
гипотез 0H и 1H является байесовский критерий, критическое множество *A ко-
торого состоит их тех и только тех значений a случайной величины x , которые
удовлетворяют неравенству )( )( 10 aa =<= xx PP . Ясно, что средняя вероятность
ошибки байесовского критерия 2
1
, £*AeP , то есть ** -= AeA P ,21p .
Рассмотрим задачу проверки гипотез 0H и 1H в частном случае, когда x
принимает значения во множестве tV двоичных векторов длины t , а распределе-
ния 0P и 1P имеют следующий вид:
)()(
0 )1()( astas ppa --=P , ta -= 2)(1P , tt Vaaa Î= )...,,( 1 ,
где ]1 ,0[Îp — фиксированное число; taaas ++= ... )( 1 . В этом случае x пред-
ставляет собой последовательность t независимых случайных величин, прини-
мающих значения во множестве }1 ,0{ и распределенных по закону Бернулли с
параметром p при условии справедливости гипотезы 0H , и по равномерному за-
кону — при условии справедливости гипотезы 1H . Обозначим
å
Î
--
Í
* --=
Aa
tastas
VA
pptp
t
)2)1((max);( )()(p (5)
предпочтение оптимального (байесовского) критерия для проверки указанных ги-
потез. В работе [2] (см. доказательство леммы 15) получено следующее утвержде-
ние.
Лемма 1. Для любых ]1 ,0[Îp , NÎt справедливо неравенство:
|12|2);( -£* pttpp . (6)
Из формулы (6) вытекает следующая верхняя граница надежности оптималь-
ного критерия для проверки гипотез 0H и 1H :
|12|2
11 , -+£- * ptP Ae
. (7)
Отметим, что в [2] приведены условия, при которых оценки (6), (7) являются не-
улучшаемыми по порядку величины.
А. Н. Алексейчук, А. С. Шевцов
58
Оценки стойкости блочных шифров
относительно представленных статистических атак
Получим верхнюю границу предпочтения ),( jp Â* оптимального критерия
для проверки по наблюдаемой реализации случайной последовательности (2) двух
простых гипотез: 0H — случайная подстановка C имеет равномерное распреде-
ление на множестве nVS ; 1H — эта подстановка является случайным и равноверо-
ятным шифрующим преобразованием блочного шифра Â . С этой целью найдем
апостериорное распределение вероятностей случайной последовательности )(tx
при условии справедливости каждой из указанных гипотез.
Обозначим )|()( )(
nn x Haa t == PP , tVaÎ , }1 ,0{În . Используя введенные
выше обозначения, получим:
=-==== å Õå
Î =
--
Î
-
nV
iin
nV
n
Sc
t
i
a
c
a
c
V
Sc
ttcc
V ppSaXIaXISa
1
11
11
1
0 )1(||} )( ...,,)({|| )( PP
å
Î
-- -=
nV
n
Sc
ast
c
as
c
V ppS )()(1 )1(|| , (8)
где taaas ++= ...)( 1 , tt Vaaa Î= )...,,( 1 . Аналогично найдем:
)()(1
1 )1(||)(
ast
Kk
f
as
f kk
ppKa -
Î
- å -=P , tVaÎ . (9)
Отсюда, согласно формуле (4), получим:
)2)(()2)(()()(),( 1010
t
Aa
t
AaAaAa
aaaa -
Î
-
ÎÎÎ
* -+-£-=Â åååå
****
PPPPjp , (10)
где *A — критическое множество оптимального критерия различения сформули-
рованных выше гипотез 0H и 1H .
Оценим сверху каждое из двух слагаемых в правой части неравенства (10).
Имеем:
£--=-=Â å åå
Î Î
----
Î
*
** nV
n
Sc Aa
tast
c
as
c
Vt
Aa
ppSaP )2)1((||)2)((),( )()(1
0
def
0 js
å å
Î Î
---
*
--£
nV
n
Sc Aa
tast
c
as
c
V ppS )2)1((|| )()(1 .
Отсюда на основании формул (5), (6) заключаем, что
Показатели и оценки стойкости блочных шифров
относительно статистических атак первого порядка
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2006, Т. 8, № 4 59
£=-£Â åå
Î
-
Î
-*
nV
n
nV
n
Sc
c
V
Sc
c
V StptS ljs 11
0 ||2|12|2||),(
2
12
1
1 )(2||2 nV
nV
n S
Sc
c
V tSt ll =÷÷
ø
ö
çç
è
æ
£ å
Î
- , (11)
где последнее неравенство следует из выпуклости вверх функции x , 0³x . Ана-
логично получаем:
2
1
12
1
1
def
1 ||2)(2)2)((),( ÷
ø
ö
ç
è
æ
=£-=Â åå
Î
-
L
Î
-*
* Kk
f
Aa
t
k
Ktta lljs P . (12)
Складывая неравенства (11), (12), в силу соотношения (10), получим следующую
оценку:
÷
ø
öç
è
æ +£Â L
* 2
1
2
1
)()(2),( lljp nVSt . (13)
Лемма 2. Для любой уравновешенной функции { }1,0: ®´ nn VVj справедли-
вы равенства:
å
Î
- =-==
nV
nnV
Sc
V
S XcXS 21 )1}0))(,({2(|| jl P
÷÷
ø
ö
çç
è
æ
-+-----= ååå
ÎÎÎ
----
nnn Vy
yx
Vy
xy
Vxx
xxnnnn
'
)',()',(
)',(
)',(211 )1()1()1(2)12(2)12(
2
jjj . (14)
В частности, если для любого nVxÎ функции ) ,( ×xj и ) , ( x×j являются уравно-
вешенными, то
1)12( --= n
S nVl . (15)
Доказательство. На основании формулы
å
Î
- -=-=
nVx
xcxnXcX ))(,()1(21}0))(,({2 jjP , nVScÎ ,
справедливы равенства:
=-= åå
Î
Å
Î
--
2),(
))(,( ))(,(12 )1(||2
n
nV
nnV
Vyx
ycyxcx
Sc
Vn
S S jjl
А. Н. Алексейчук, А. С. Шевцов
60
=--+ å å
Î
¹
Î
---
nV
n
n
Sc
yx
Vyx
ycyxcxVnn S
:),(
))(,())(,(12
2
)1()1(||22 jj
=--==Î+= å
¹¹
Î
---
'',
:)'',(),,(
)',()',(12 )1()1(|}')(,')(:{|||22
yxyx
Vyxyx
yyxxVVnn
n
nn yycxxcScS jj
å å
Î
¹¹
Î
---- ---+=
n nVxx
yxyx
Vyy
yyxxnnnn
)',(
'',
:)',(
)',()',(21
2
)1()1(2)12(22 jj . (16)
Заметим теперь, что в силу уравновешенности функции j :
å åå
¹¹
Î ÎÎ
÷÷
ø
ö
çç
è
æ
---+--=-
'',
:)',( '
)',()',()',()',(
2
)1()1()1()1(
yxyx
Vyy Vy
xxyx
Vy
xyyy
n nn
jjjj ,
откуда в силу соотношений (16) вытекает равенство (14). Лемма доказана.
Итак, на основании неравенства (13) и утверждения леммы 2 справедлива
следующая теорема, устанавливающая верхнюю границу параметра ),( jp Â* .
Теорема 1. Пусть )()(),( yhxgyx Å=j , 2),( nVyx Î , где }1,0{: , ®nVhg —
уравновешенные булевы функции, ),( jp Â* — предпочтение оптимального кри-
терия для проверки гипотез 0H и 1H по реализации случайной последовательно-
сти (2) (в случае различающей атаки на блочный шифр Â ). Тогда справедливо
неравенство:
))12()((2),( 2
1
2
1 -
L
* -+£Â nt ljp , (17)
где
å
Î
-
L -==
Kk
k XfXK 21 )1}0))(,({2(|| jl P . (18)
Получим теперь верхнюю оценку предпочтения )ш,;( jp Â* оптимального
критерия различения гипотез 0)(ш:0 =KH и 1)(ш:1 =KH , соответствующих
описанной выше «вскрывающей» атаке на шифр Â . Обозначим *A критическое
множество указанного критерия, )|()( )(
nn x Haa t == PP — апостериорную веро-
ятность реализации tt Vaaa Î= )...,,( 1 случайной последовательности (2) при усло-
вии справедливости гипотезы nH , }1 ,0{În . Положим }1)({ == XIp
kfk P ,
2)12( -= kk pl , Kk Î .
В силу уравновешенности функции y справедливо равенство:
Показатели и оценки стойкости блочных шифров
относительно статистических атак первого порядка
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2006, Т. 8, № 4 61
.)1(
2
||)1()1(
||
2)(
)(
:
)()(
1
)(
:
11 11 åå
=
Î
-
-
=
Î
-- -÷
ø
ö
ç
è
æ=-×××-=
nyny
n
K
Kk
ast
k
as
k
K
Kk
a
k
a
k
a
k
a
k ppKpppp
K
a ttP
Следовательно, согласно формуле (4),
ååå
*** Î
-
Î
-
Î
* -+-£-=Â
Aa
t
Aa
t
Aa
aaaa )2)(()2)(())()((),;( 1010 PPPPyjp , (19)
£--÷
ø
ö
ç
è
æ=- å åå
** Î
=
Î
--
-
Î
-
Aa
k
Kk
tast
k
as
k
Aa
t ppKa
ny
n
)(
:
)()(
1
)2)1((
2
||)2)((P
åå å
=
Î
-
=
Î Î
--
-
÷
ø
ö
ç
è
æ£--÷
ø
ö
ç
è
æ£
*
nyny
l
)(
:
2
1
1
)(
:
)()(
1
2
||2)2)1((
2
||
k
Kk
k
k
Kk Aa
tast
k
as
k
KtppK , }1,0{În , (20)
где последнее неравенство вытекает из леммы 1.
Складывая оценки (20) при 0=n и 1=n , на основании соотношений (19) и
выпуклости вверх функции x , 0³x , получим:
2
1
112
1
||4||22)ш,;( ÷÷
ø
ö
çç
è
æ
£÷÷
ø
ö
çç
è
æ
£Â åå
Î
--
Î
*
Kk
k
Kk
k KtKt lljp .
Итак, доказана следующая теорема.
Теорема 2. Пусть )ш,;( jp Â* — предпочтение оптимального критерия для
проверки гипотез 0)(ш:0 =KH и 1)(ш:1 =KH по реализации случайной после-
довательности (2) (в случае «вскрывающей» атаки на шифр Â ). Тогда справедли-
во неравенство:
2
1
)( 4)ш,;( L
* £Â ljp t , (22)
где Ll определяется по формуле (18).
Отметим, что в приведенном доказательстве теоремы 2 не используются ка-
кие-либо эвристические предположения (вроде гипотез «о стохастической экви-
валентности» или «строгой различимости ключей» [8–10, 12, 13]) относительно
шифра Â .
Обсуждение полученных результатов
Соотношения (17) и (22) устанавливают верхние границы стойкости произ-
вольного блочного шифра относительно описанных выше (соответственно, разли-
А. Н. Алексейчук, А. С. Шевцов
62
чающей и «вскрывающей») статистических атак. Эти соотношения позволяют
ввести (обоснованно, не прибегая к эвристическим рассуждениям) показатели
стойкости блочных шифров относительно известных методов криптоанализа
(обобщенного линейного [9], билинейного [11]), а также их возможных обобще-
ний. Как следует из описаний статистических атак на шифр Â , каждый из ука-
занных криптоаналитических методов определяется выбором функции j из под-
ходящего класса булевых функций n2 переменных. При этом параметр, характе-
ризующий стойкость шифра Â к данному методу криптоанализа, определяется по
формуле (18). Отметим, что в частном случае, когда j является линейной буле-
вой функцией, «вскрывающая» атака на шифр Â близка к так называемому Алго-
ритму 1, предложенному М. Матцуи [8], а параметр (18) совпадает с классиче-
ским показателем стойкости блочных шифров относительно метода линейного
криптоанализа [14].
Для линейной различающей атаки на шифр Â в [2] получена верхняя грани-
ца предпочтения ),( jp Â* , которая имеет следующий вид:
))12()(( 3),( 3
1
3
13 -
L
* -+£Â nt ljp . (23)
Заметим, что в случае, когда оценка (23) является нетривиальной (то есть вы-
ражение в правой части неравенства (23) не превосходит 1), она оказывается бо-
лее грубой по сравнению с оценкой (17). Ниже, в таблице приведены численные
значения параметра Ll t , характеризующего сложность линейной различающей
атаки на шифр Â , при различных значениях надежности =Â ),( jN
)),(1(5,0 jp Â+= * , полученные с использованием неравенств (17) и (23). (Дан-
ные в таблице рассчитаны по формулам 2)5,0),((4
1 -³L jl Nt и
3)5,0),((27
1 -³L jl Nt , вытекающим из неравенств (17) и (23) соответственно,
а также известного неравенства 1)12( -
L -³ nl ; см., например, лемму 1 в [15]).
Сравнение оценок сложности различающей линейной атаки на блочные шифры
Надежность атаки Неравенство (17) Неравенство (23)
0,9 0,04000 0,00237
0,8 0,02250 0,00100
0,7 0,01000 0,00029
0,6 0,00250 0,00004
Как видно из таблицы, оценка сложности атаки, полученная с использовани-
ем формулы (17), примерно на один–два порядка точнее оценки, вытекающей из
формулы (23). (Например, согласно неравенству (23), для того, чтобы отличить
шифр Â от случайной равновероятной подстановки с надежностью 0,9, требуется
зашифровать не менее 1) (00237,0 -
Ll открытых сообщений. В то же время, со-
Показатели и оценки стойкости блочных шифров
относительно статистических атак первого порядка
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2006, Т. 8, № 4 63
гласно неравенству (17), для этого необходимо не менее 1) (04000,0 -
Ll открытых
сообщений).
В целом, полученные результаты составляют теоретическую основу для
дальнейших исследований в области анализа и обоснования стойкости блочных
шифров относительно статистических атак первого порядка, позволяя сосредото-
чить основные усилия на разработке методов построения нетривиальных верхних
границ параметров вида (18).
1. Biryukov A. Block Ciphers and Stream Ciphers: the State of the Art //
http://eprint.iacr.org/2004/094.
2. Vaudenay S. Decorrelation: a Theory for Block Cipher Security // J. of Cryptology. — 2003. —
Vol. 16, N 4. — P. 249–286.
3. Wagner D. Towards a Unifying View of Block Cipher Cryptanalysis // Fast Software Encryp-
tion. — FSE’04, Proceedings. — Springer Verlag, 2004. — P. 116–135.
4. Vaudenay S. On the Security of CS-Cipher // Fast Software Encryption. — FSE’99, Proceedings.
— Springer Verlag, 1999. — P. 260–274.
5. Junod P. On the Optimality of Linear, Differential and Sequential Distinguishers // Advances in
Cryptology — EUROCRYPT’03 — Springer Verlag, 2003. — P. 17–32.
6. Baigneres T., Vaudenay S. Proving the Security of AES Substitution-Permutation Network //
http://lasecwww.eptf.ch./php_code/publications.
7. Biham E, Shamir A. Differential Cryptanalysis of DES-Like Cryptosystems // J. of Cryptology.
— 1991. — Vol. 4, N 1. — P. 3–72.
8. Matsui M. Linear Cryptanalysis Methods for DES Cipher // Advances in Cryptology —
EUROCRYPT’93, Proceedings. — Springer Verlag, 1994. — P. 386–397.
9. Harpes C., Kramer G.G., Massey J.L. A Generalization of Linear Cryptanalysis and the Appli-
cability of Matsui’s Piling-up Lemma // Advances in Cryptology — EUROCRYPT’95, Proceedings. —
Springer Verlag, 1995. — P. 24–38.
10. Harpes C., Massey J.L. Partitioning Cryptanalysis // Fast Software Encryption. — FSE’97, Pro-
ceedings. — Springer Verlag, 1997. — P. 13–27.
11. Courtois N.T. Feistel Schemes and Bi-Linear Cryptanalysis // Advances in Cryptology —
CRYPTO’04, Proceedings. — Springer Verlag, 2004. — P. 23–40.
12. Junod P. On the Complexity of Matsui’s Attack // Fast Software Encryption. — FSE’01, Pro-
ceedings. — Springer Verlag, 2001. — P. 199–211.
13. Логачев О.А., Сальников А.А., Ященко В.В. Булевы функции в теории кодирования и
криптологии. — М.: МЦНМО, 2004. — 470 с.
14. Chabaud F., Vaudenay S. Links Between Differential and Linear Cryptanalysis // Advances in
Cryptology — EUROCRYPT’94, Proceedings. — Springer Verlag, 1995. — P. 356–365.
15. Keliher L., Meier H., Tavares S. Improving the Upper Bond on the Maximum Average Linear
Hull Probability for Rijndael // Selected Areas in Cryptography. — SAC 2001. — Proceedings. — Sprin-
ger Verlag, 2001. — P. 112–128.
Поступила в редакцию 08.12.2006
Получены аналитические верхние оценки надежности различающей и, соответственно, «вскрывающей» статистической атаки первого порядка на блочные шифры. Указанные оценки позволяют ввести теоретически обоснованные показатели стойкости блочных шифров относительно обобщенного линейного, билинейного и ряда других методов криптоанализа. В случае линейной различающей атаки полученная оценка стойкости блочных шифров является более точной по сравнению с ранее известной.
Ключевые слова: криптографическая защита информации, блочный шифр, обоснованная стойкость, статистическая атака, статистический критерий.
Введение
Одной из центральных проблем современной симметричной криптографии является создание общей теории обоснования стойкости блочных шифров. Разнообразие существующих методов их криптоанализа, появление новых перспективных направлений в этой области [1] требуют систематизации, упорядочения и осмысления с единых, общих позиций накопленных фактов и отдельных теоретических результатов. Отметим работы [2, 3], в которых представлены концептуальные подходы к обоснованию стойкости блочных шифров на основе понятий различающей атаки, декорреляции и, соответственно, стохастической коммутативной диаграммы.
Обсуждение полученных результатов
|
| id | nasplib_isofts_kiev_ua-123456789-50863 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1560-9189 |
| language | Russian |
| last_indexed | 2025-11-28T16:53:26Z |
| publishDate | 2006 |
| publisher | Інститут проблем реєстрації інформації НАН України |
| record_format | dspace |
| spelling | Алексейчук, А.Н. Шевцов, А.С. 2013-11-05T19:57:26Z 2013-11-05T19:57:26Z 2006 Показатели и оценки стойкости блочных шифров относительно статистических атак первого порядка / А.Н. Алексейчук, А.С. Шевцов // Реєстрація, зберігання і оброб. даних. — 2006. — Т. 8, № 4. — С. 53-63. — Бібліогр.: 15 назв. — pос. 1560-9189 https://nasplib.isofts.kiev.ua/handle/123456789/50863 621.391:519.2 Получены аналитические верхние оценки надежности различающей и, соответственно, «вскрывающей» статистической атаки первого порядка на блочные шифры. Указанные оценки позволяют ввести теоретически обоснованные показатели стойкости блочных шифров относительно обобщенного линейного, билинейного и ряда других методов криптоанализа. В случае линейной различающей атаки полученная оценка стойкости блочных шифров является более точной по сравнению с ранее известной. Отримано аналітичні верхні оцінки надійності розрізнювальної та, відповідно, «вскриваючої» статистичної атаки першого порядку на блокові шифри. Зазначені оцінки дозволяють ввести теоретично обґрунтовані показники стійкості блокових шифрів відносно узагальненого лінійного, білінійного і низки інших методів криптоаналізу. У випадку лінійної розрізнювальної атаки отримана оцінка стійкості блокових шифрів є більш точною у порівнянні з раніше відомою. Analytical upper estimations of the success probability of a distinguishing and, consequently, a «breaking» first order statistical attack on block ciphers are obtained. These estimations form a foundament for the definition of measures that characterize provable security of block ciphers against generalized linear, bilinear and some other cryptanalysis techniques. For the case of linear distinguishing attack, the obtained estimation of block ciphers security is more accurate that the previous well-known estimation. ru Інститут проблем реєстрації інформації НАН України Реєстрація, зберігання і обробка даних Методи захисту інформації в комп’ютерних системах і мережах Показатели и оценки стойкости блочных шифров относительно статистических атак первого порядка Показники та оцінки стійкості блокових шифрів відносно статистичних атак першого порядку Measures and Estimations for Block Ciphers Security against First Order Statistical Attacks Article published earlier |
| spellingShingle | Показатели и оценки стойкости блочных шифров относительно статистических атак первого порядка Алексейчук, А.Н. Шевцов, А.С. Методи захисту інформації в комп’ютерних системах і мережах |
| title | Показатели и оценки стойкости блочных шифров относительно статистических атак первого порядка |
| title_alt | Показники та оцінки стійкості блокових шифрів відносно статистичних атак першого порядку Measures and Estimations for Block Ciphers Security against First Order Statistical Attacks |
| title_full | Показатели и оценки стойкости блочных шифров относительно статистических атак первого порядка |
| title_fullStr | Показатели и оценки стойкости блочных шифров относительно статистических атак первого порядка |
| title_full_unstemmed | Показатели и оценки стойкости блочных шифров относительно статистических атак первого порядка |
| title_short | Показатели и оценки стойкости блочных шифров относительно статистических атак первого порядка |
| title_sort | показатели и оценки стойкости блочных шифров относительно статистических атак первого порядка |
| topic | Методи захисту інформації в комп’ютерних системах і мережах |
| topic_facet | Методи захисту інформації в комп’ютерних системах і мережах |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/50863 |
| work_keys_str_mv | AT alekseičukan pokazateliiocenkistoikostibločnyhšifrovotnositelʹnostatističeskihatakpervogoporâdka AT ševcovas pokazateliiocenkistoikostibločnyhšifrovotnositelʹnostatističeskihatakpervogoporâdka AT alekseičukan pokaznikitaocínkistíikostíblokovihšifrívvídnosnostatističnihatakperšogoporâdku AT ševcovas pokaznikitaocínkistíikostíblokovihšifrívvídnosnostatističnihatakperšogoporâdku AT alekseičukan measuresandestimationsforblockcipherssecurityagainstfirstorderstatisticalattacks AT ševcovas measuresandestimationsforblockcipherssecurityagainstfirstorderstatisticalattacks |