�ݺ�ߣ

АСИММЕТРИЧНЫЙ SPN-ШИФР НА
БАЗЕ WHITE-BOX-КРИПТОГРАФИИ
И ХАОТИЧЕСКИХ ОТОБРАЖЕНИЙ
к.т.н, Щелкунов Д.А.
КФ МГТУ имени Н.Э. Баумана

White-box-криптография
✓Набор техник, позволяющих преобразовать симметричный блочный шифр
в асимметричный посредством сокрытия ключа в реализации алгоритма
шифрования
✓Предназначена для создания быстрых асимметричных шифров,
позволяющих и шифровать, и подписывать сообщения
✓В случае стойкой и быстрой реализации позволит существенно упростить и
сделать более безопасными протоколы обмена зашифрованной
информацией (в частности, отпадёт необходимость использовать алгоритм
Диффи-Хеллмана)
✓Быстрый безопасный обмен между 3-мя и более абонентами с
подтверждением авторства сообщений

Предыдущие исследования
✓Chow S., Eisen P., Johnson H., Van Oorschot P.C. (2003), White-Box Cryptography and an AES Implementation.
In: Nyberg K., Heys H. (eds) Selected Areas in Cryptography. SAC 2002. Lecture Notes in Computer Science, vol
2595. Springer, Berlin, Heidelberg
✓Olivier Billet and Henri Gilbert. A Traceable Block Cipher. In Advances in Cryptology - ASIACRYPT 2003, volume
2894 of Lecture Notes in Computer Science, pages 331-346. Springer-Verlag, 2003
✓Olivier Billet, Henri Gilbert, and Charaf Ech-Chatbi. Cryptanalysis of a White-Box AES Implementation. In
Proceedings of the 11th International Workshop on Selected Areas in Cryptography (SAC 2004), volume 3357 of
Lecture Notes in Computer Science, pages 227–240. Springer-Verlag, 2004.
✓Brecht Wyseur, White-box cryptography, PhD thesis, March 2009
✓Dmitry Schelkunov, White-Box Cryptography and SPN ciphers. LRC method, Cryptology ePrint Archive: Report
2010/419
✓Brecht Wyseur, White-box cryptography: hiding keys in software, MISC magazine, April 2012
✓Joppe W. Bos and Charles Hubain and Wil Michiels and Philippe Teuwen, Differential Computation Analysis:
Hiding your White-Box Designs is Not Enough, Cryptology ePrint Archive: Report 2015/753

Атаки на white-box-реализации
Практически во всех white-box-реализациях известны линейная
и нелинейная части исходного алгоритма для каждого из
раундов. Необходимо «отделить» white-box-преобразования
✓Дифференциальный криптоанализ (в том числе fault injection)
✓Алгебраический криптоанализ
✓Извлечение нелинейной части (Olivier Billet, Henri Gilbert, and
Charaf Ech-Chatbi. Cryptanalysis of a White-Box AES
Implementation)

Метод сокрытия линейной
зависимости
(1)
)))(mod)(mod((
))(mod))(mod((
122
211





ppcbax
pcpbax
21, pp – неприводимые полиномы n-й степени, а 21,,,, xxcba - полиномы
степеней, меньших n.
21 xx 

табличнозаданыxyxy
неизвестныdcbaxppp
GFнадполиномыыепроизвольнdcbax
GFнад
полиномынеравныепопарноыенеприводимppp
pdpcxsxy
pbpaxsxy
)(),(
,,,,,,,
)(,,,,
)(
,,
)2(
)(mod))(mod)(()(
)(mod))(mod)(()(
21
321
321
312
211










)(mod)()(mod)(
:
)2(
)(mod))(mod)(()(
)(mod))(mod)(()(
11
312
211
pcxsиpaxs
междуьзависимостлинейнуюнайтиЗадача
pdpcxsxy
pbpaxsxy







cиaнайтинеобходимоxyиxyданнымпоЗадача
p
dqpdcxs
q
p
bqpbaxs
q
p
cxs
q
p
axs
q
qpdqpdcxsxy
qpbqpbaxsxy
pdqpcxsxy
pbqpaxsxy
)()(:
')(
;
)(
;
)(
';
)(
)4(
')()(
)()(
)3(
)(mod)')(()(
)(mod))(()(
21
3
11
3
2
11
2
1
1
1
1
33112
22111
3112
2111





 





 





 





 











RLWE?

Усложним формулу (2)
(5)
)(mod)...)(mod))(mod)((...()(
)(mod)...)(mod))(mod)((...()(
)()()0(
3
)0(
12
)()()0(
2
)0(
11





k
v
k
k
u
k
pdpdpcxsxy
pbpbpaxsxy
)()( 
jppi

  )!2,2min(:Сложность
2)1(2 nkn 

Теория хаоса в криптографии
✓Goce Jakimoski and Ljupˇco Kocarev, Chaos and Cryptography: Block Encryption Ciphers Based
on Chaotic Maps. IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS—I: FUNDAMENTAL THEORY
AND APPLICATIONS, VOL. 48, NO. 2, FEBRUARY 2001
✓Asim, M., Jeoti, V.: Efficient and simple method for designing chaotic S-boxes. ETRI Journal
30(1), 170–172 (2008)
✓Mona Dara and Kooroush Manochehri, A Novel Method for Designing S-Boxes Based on Chaotic
Logistic Maps Using Cipher Key. World Applied Sciences Journal 28 (12): 2003-2009, 2013
✓Christopher A. Wood, Chaos-Based Symmetric Key Cryptosystems
✓Dragan Lambić and Miodrag Živković, COMPARISON OF RANDOM S-BOX GENERATION
METHODS. PUBLICATIONS DE L’INSTITUT MATHÉMATIQUE Nouvelle série, tome 93 (107) (2013)

Создание S-box-ов с помощью
хаотических отображений
✓Хорошие криптографические свойства по
результатам целого ряда исследований
✓Простые алгоритмы
✓Случайность отображений в сочетании с
хорошими криптографическими свойствами
повышает уровень безопасности

Коды с максимальной дистанцией.
MDS-матрица
MDS-матрица (Maximal Distance Separable matrix) – проверочная
матрица линейного блокового кода с максимальной дистанцией
◦ Обеспечивает максимальное рассеивание за счёт своей структуры
◦ Используется при создании SPN-шифров в качестве линейных
рассеивающих преобразований
◦ Интересные типы матриц:
◦ Матрица Вандермонда
◦ Инволютивная матрица (одна и та же MDS-матрица для шифрования и
расшифрования)
◦ Матрица Коши
◦ Циркулярная матрица (как в Rijndael)

Матрица Коши
✓Является MDS-матрицей
✓Лёгкий алгоритм создания независимо от размерности
✓Свойство циркулярности не принципиально для white-box-реализации
✓Свойство инволютивности вредно для white-box-реализации
✓Следовательно, выбираем матрицу Коши
   k
ijjijijiij GFayxnjmiyxyxa 2,,;0;0;0;
1



Раунд блочного SPN-шифра
Нелинейная часть (S-box-ы)
Добавление раундового ключа
Линейная часть (MDS-матрица + сдвиги)

Раунд SPN-шифра и T-box-ы
(на примере AES-128)

Хаотичный асимметричный
white-box-шифр
✓Таблицы подстановок (8x8 бит) создаются хаотически для каждого из
входных байтов каждого раунда
✓MDS-матрица (16x16 байт) создаётся хаотически (матрица Коши)
✓Для white-box-реализации используется реализация SPN-шифра с
помощью T-box-ов
✓Линейная зависимость между элементами T-box-ов скрывается с
помощью вышеописанного метода сокрытия линейной зависимости
✓Набор модифицированных таблиц (T-box-ов) – открытый ключ
шифрования. По ним сложно восстановить закрытый ключ – набор таблиц
для расшифрования

Раунд шифра
)6(
))(((
...
))(((
))(((
...
))(((
...
))(((
))(((
))(((
...
))(((
))(((
...
)15(
1
)15()15,315()15(
)15(
1
)15()15,1()1(
)15(
1
)15()15,0()0(
)1(
1
)1()1,15()15(
)1(
1
)1()1,1()1(
)1(
1
)1()1,0()0(
)0(
1
)0()0,15()15(
)0(
1
)0()0,1()1(
)0(
1
)0()0,0()0(
)15(
)1(
)0(





































































jjjj
jjjj
jjjj
jjjj
jjjj
jjjj
jjjj
jjjj
jjjj
j
j
j
j
ystmix
ystmix
ystmix
ystmix
ystmix
ystmix
ystmix
ystmix
ystmix
y
y
y
Y
(i)
j-y 1 -байт выходных данных из предыдущего раунда. Если 0j , то (i)
j-y 1 - байт исходного
сообщения. )(k
js - это таблица подстановок, соответствующая каждому входному байту.
)(l,k
jt - умножение на элемент строки соответствующей MDS-матрицы в )GF( 8
2 . )k(
jmix -
запутывающие преобразования на базе метода сокрытия линейной зависимости

Маскировка линейной зависимости
между элементами T-box-а
)7(
)(mod)...)(mod))(mod)(((...(
..........................................................................
)(mod)...)(mod))(mod)(((...(
)(mod)...)(mod))(mod)(((...(
)(mod)...)(mod))(mod)(((...(
)(mod)...)(mod))(mod)(((...(
]['
),(),()1,()1,()0,()0,()(
3
),3(),3()1,3()1,3()0,3()0,3()3(
2
),2(),2()1,2()1,2()0,2()0,2()2(
1
),1(),1()1,1()1,1()0,1()0,1()1(
0
),0(),0()1,0()1,0()0,0()0,0()0(
33
22
11
00


























n
kn
i
kn
i
n
i
n
i
n
i
n
i
n
i
k
i
k
iiiiii
k
i
k
iiiiii
k
i
k
iiiiii
k
i
k
iiiiii
i
valpbpbpbat
valpbpbpbat
valpbpbpbat
valpbpbpbat
valpbpbpbat
aT
nn
)( j
it - элемент T-box-а до применения запутывающих преобразований (mix), ),( uj
ib –
случайно выбранный полином в )2( h
GF , ),( uj
ip – случайно выбранный неприводимый
полином h-й степени над )2(GF
),(),1(),0(
... vn
i
v
i
v
i ppp 

EVHEN. Хаотичный асимметричный
white-box-шифр
✓Назван в честь двух величайших математиков: Эвариста Галуа и Анри
Пуанкаре
✓Обладает скоростью симметричного шифра
✓Позволяет и шифровать, и подписывать
✓Размер открытого ключа: 640 Кб
✓Низкие требования к вычислительным ресурсам: один раунд – 16
операций сложения по модулю 2 16-и байтовых чисел. Нужно всего 3
операции: выборка из памяти, сложение по модулю 2 и запись в память

Применение
✓IoT
✓DRM
✓Везде, где нужна быстрая и не
требовательная к вычислительным
ресурсам асимметричная криптография

Спасибо за внимание
Исходный код реализации EVHEN:
https://github.com/dmschelkunov/EVHEN
Блог автора: http://dschelkunov.blogspot.com
E-mail автора: d.schelkunov@gmail.com

�ݺ�ߣ

EVHEN. Асимметричный SPN-шифр на базе white-box-криптографии и хаотических отображений

More Related Content

EVHEN. Асимметричный SPN-шифр на базе white-box-криптографии и хаотических отображений