id: Гость   вход   регистрация
текущее время 22:13 28/03/2024
Автор темы: Гость, тема открыта 10/06/2010 23:24 Печать
Категории: криптография, симметричное шифрование, атаки
http://www.pgpru.com/Форум/Криптография/ДифференциальныйКриптоанализ
создать
просмотр
ссылки

Дифференциальный криптоанализ


Здравствуйте, все! Вот читаю (пытаюсь, ибо английский) – Бихам, Шамир, Differential cryptanalysis of des-like systems. Т.к. вокруг нету того кто бы мог помочь, то прошу консультации тут.


На стр.9 они пишут, если я правильно понял, о том, как можно определить 6 битов ключа.


Sk=Se+Si, где Sk-биты ключа, Se – входные биты, Si – биты на входе s-блока.


Далее, имеется табл 2. 34->D


(модераторы, извините, не понял как сделать таблицу, мб при нажатии на кнопку добавите пример, тиипа столбец1, столбец2, ячейка там ну и т.д.)



А теперь вопрос.


Что это за таблица, как получаются их значения (я не понял параграф)? Я предположил, что перебираются все возможные варианты 2^6 и они складываются поочередно то с Se, то с Se*. Если где-то получились одинаковые значения, то это возможные значения ключа?


 
Комментарии
— Гость (10/06/2010 23:30)   <#>
Хоть бы страницу скопировал сюда, или думаешь все обязаны знать ту книгу по странично?)
— Гость (11/06/2010 00:12)   <#>
это статья, а не книга

fileскачать_здесь
— unknown (11/06/2010 10:45)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
(модераторы, извините, не понял как сделать таблицу, мб при нажатии на кнопку добавите пример, тиипа столбец1, столбец2, ячейка там ну и т.д.)

документация Wiki.

Что-то не совпадают ни страницы, ни номера таблиц. У публикации могли быть разные версии. Та, которую привели по ссылке выше — от 19 июля 2000 года, 106 страниц.

Там в таблице 2 приведена сокращённая таблица распределений входных/выходных XOR-разностей для блока S1. Результат 34x -> 4x действительно имеет самый высокий коэффициент 16 (не считая тривиального случая 0x -> 0x). Вероятность 16 из 64 возможных пар блока S1 — это 1/4, что намного больше других вариантов.

А вот 34x -> 2x имеет малое значение 2. Всего таких может быть только 2 пары { S1I , S1*_I } и { S1*_I , S1I } соответственно.

Все возможные входные значения для пар представлены в таблице 5, где рассматривается только один вход S1'I = 34x из которой выбирается для примера однозначная пара 13x, 27x, которая и даёт только два варианта, что сответствует выходам 6x, 2x.

Таблица 6 показывает возможные ключи для выхода 34x -> Dx при входе 1x, 35x. В таблице 5 она показана как {06, 10, 16, 1C, 22, 24, 28, 32} -> D. Т.е. пары вида {34x} • {1x, 35x} -> Dx дают возможные ключи при условии, что соблюдается значение XOR на выходе S1'O = Dx
— crazyhorse (12/06/2010 21:42)   <#>
Результат 34x -> 4x действительно имеет самый высокий коэффициент 16


А вот 34x -> 2x имеет малое значение


наоборот
— Гость (12/06/2010 21:46)   <#>
а вот 34x -> 5x, я так понимаю, невозможный дифференциал?
— Гость (13/06/2010 00:30)   <#>
я вот прочитал, что в DES S-блоки нелинейны и безопасность определяется только ими.

в ГОСТ 28147 для смешения с ключом исп-ся операция сложения по модулю 2^32. она слабо нелинейна => влияет на стойкость. как она учитывается при дифф. криптан-зе? для нее составляется отдельная характеристика?
— crazyhorse (13/06/2010 16:40)   <#>
что-то я не совсем понял.

в документе по ссылке выше в примере №6

вольный перевод:

Эти пары дуальны. Если первая пара S1i,S1*i, то вторая S1*i,S1i. Посмотря на таблицу 5 мы видим что эти входы равны 13х и 27х чьи соответветствующие выходы 6х и 2х


Если S1i=13x, a S1o=6x, то должно выполняться S1o=S1(S1i), т.е. 6x=S1(13x), что не так. Или я чего-то не допонял?
— unknown (13/06/2010 19:05, исправлен 13/06/2010 19:09)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Результат 34x -> 4x действительно имеет самый высокий коэффициент 16
А вот 34x -> 2x имеет малое значение

наоборот

Совершенно верно. Спасибо, что сразу заметили и поправили очевидный ляп.
И дата у работы конечно 1990 год, а не 2000 :)


а вот 34x -> 5x, я так понимаю, невозможный дифференциал?

Согласно "Example 4". Для входа 34x возможны только выходы 1x 2x 3x 4x 7x 8x Dx Fx. Что доказывает неравномерность распределения:

Examples 3 and 4 demonstrate that for a fixed input XOR, the possible output XORs do not have uniform distribution

Это свойство S-блока, его нужно ещё распространить на свойства раунда, затем строятся межраундовые характерстики. Т.е. по крайней мере это кандидат.


в ГОСТ 28147 для смешения с ключом исп-ся операция сложения по модулю 2^32. она слабо нелинейна => влияет на стойкость. как она учитывается при дифф. криптан-зе? для нее составляется отдельная характеристика?

То что именно так влияет — точно. По крайней мере были опубликованы работы с доказательным отличием вариантов сложения ключа и XOR в пользу сложения. Как именно там учитывалось нужно искать и смотреть. Вполне может использоваться какое-то упрощение, чтобы составить сокращённую общую таблицу с учётом сложения, возможны и разные подходы, но конкретику надо искать в публикациях.


Общий смысл DF в том, что если пропустить много разных пар, но с заданной подобранной разностью, то фрагменты ключа будут появляться в таблице кандидатов с разной, неравномерной вероятностью. Те фрагменты, которых будет больше (при необходимом числе пар, т.к. атака вероятностная), то те скорее всего и будут истинными.


Если S1i=13x, a S1o=6x, то должно выполняться S1o=S1(S1i), т.е. 6x=S1(13x), что не так. Или я чего-то не допонял?

Может там для входов 13x и 27x должно выполняться 6x и 4x по таблице 2? Маловероятно конечно, что опечатка, тут действительно какой-то неясный момент.

— crazyhorse (15/06/2010 02:05)   <#>
все ясно. проблема в работе s-блоков.

на вход S-блока поступает 6-битовый вектор. Первый и последний биты определяют номер строки, а средние – столбец.
— Гость (17/06/2010 01:11)   <#>
По крайней мере были опубликованы работы с доказательным отличием вариантов сложения ключа и XOR в пользу сложения. Как именно там учитывалось нужно искать и смотреть.


не могли бы вы привести название работы?
— unknown (17/06/2010 09:14, исправлен 17/06/2010 09:15)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Ну если искать и смотреть, то вот:


IJCSNS International Journal of Computer Science and Network Security, VOL.7 No.6, June 2007


Modified S-box to Archive Accelerated GOST


George S Oreku1 Jianzhong Li2 Tamara Pazynyuk3 and Fredrick J. Mtenzi 4,

Department of Computer Science and Engineering
Harbin Institute of Technology, Foreign Student Building
A13 Room 601, P.O.Box 773, 92 Xi Dazhi Street,
Nangang District, Harbin 150001 China
Dublin Institute of Technology, Dublin 8, Ireland


Часть: 3. Security argument


THE ATTACK ON 20 ROUNDS OF GOST-XOR.Suppose
again that the round sub-key is XORed instead of being
added, (we will denote this variant of GOST as GOST-XOR).
Here we show an application of sliding with a twist which
results in an attack on the last 20 rounds of GOST-XOR.

Ещё немного затрагивается тема в


Preprint 11/1997 July 30, 1997
Mathematical Institute
Slovak Academy of Sciences,
Central Cryptographic Authority
Ministry of Interior
Bratislava
Otokar Groz'ek, Karol Nemoga, Marcel Zanechal
Why use bijective S-boxes in GOST-algorithm
PREPRINT SERIES

Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3