РегистрацияДифференциальный криптоанализ
Здравствуйте, все! Вот читаю (пытаюсь, ибо английский) – Бихам, Шамир, Differential cryptanalysis of des-like systems. Т.к. вокруг нету того кто бы мог помочь, то прошу консультации тут.
На стр.9 они пишут, если я правильно понял, о том, как можно определить 6 битов ключа.
Sk=Se+Si, где Sk-биты ключа, Se – входные биты, Si – биты на входе s-блока.
Далее, имеется табл 2. 34->D
(модераторы, извините, не понял как сделать таблицу, мб при нажатии на кнопку добавите пример, тиипа столбец1, столбец2, ячейка там ну и т.д.)
А теперь вопрос.
Что это за таблица, как получаются их значения (я не понял параграф)? Я предположил, что перебираются все возможные варианты 2^6 и они складываются поочередно то с Se, то с Se*. Если где-то получились одинаковые значения, то это возможные значения ключа?
комментариев: 9796 документов: 488 редакций: 5664
документация 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
наоборот
в ГОСТ 28147 для смешения с ключом исп-ся операция сложения по модулю 2^32. она слабо нелинейна => влияет на стойкость. как она учитывается при дифф. криптан-зе? для нее составляется отдельная характеристика?
в документе по ссылке выше в примере №6
вольный перевод:
Если S1i=13x, a S1o=6x, то должно выполняться S1o=S1(S1i), т.е. 6x=S1(13x), что не так. Или я чего-то не допонял?
комментариев: 9796 документов: 488 редакций: 5664
Совершенно верно. Спасибо, что сразу заметили и поправили очевидный ляп.
И дата у работы конечно 1990 год, а не 2000 :)
Согласно "Example 4". Для входа 34x возможны только выходы 1x 2x 3x 4x 7x 8x Dx Fx. Что доказывает неравномерность распределения:
Это свойство S-блока, его нужно ещё распространить на свойства раунда, затем строятся межраундовые характерстики. Т.е. по крайней мере это кандидат.
То что именно так влияет — точно. По крайней мере были опубликованы работы с доказательным отличием вариантов сложения ключа и XOR в пользу сложения. Как именно там учитывалось нужно искать и смотреть. Вполне может использоваться какое-то упрощение, чтобы составить сокращённую общую таблицу с учётом сложения, возможны и разные подходы, но конкретику надо искать в публикациях.
Общий смысл DF в том, что если пропустить много разных пар, но с заданной подобранной разностью, то фрагменты ключа будут появляться в таблице кандидатов с разной, неравномерной вероятностью. Те фрагменты, которых будет больше (при необходимом числе пар, т.к. атака вероятностная), то те скорее всего и будут истинными.
Может там для входов 13x и 27x должно выполняться 6x и 4x по таблице 2? Маловероятно конечно, что опечатка, тут действительно какой-то неясный момент.
на вход S-блока поступает 6-битовый вектор. Первый и последний биты определяют номер строки, а средние – столбец.
не могли бы вы привести название работы?
комментариев: 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
Ещё немного затрагивается тема в
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