id: Гость   вход   регистрация
текущее время 00:12 07/12/2019
Владелец: unknown (создано 18/07/2013 12:11), редакция от 19/07/2013 12:25 (автор: unknown) Печать
Категории: криптография, алгоритмы, симметричное шифрование
http://www.pgpru.com/Новости/2013/МеханизмСозданияS-блоковДляDESДоСихПорОстаётсяЗагадкой
создать
просмотр
редакции
ссылки

18.07 // Механизм создания S-блоков для DES до сих пор остаётся загадкой


С момента публикации алгоритма блочного шифрования DES в 1977 американским бюро стандартов, он был сразу окружён подозрениями. Во-первых, возникло недовольство из-за слишком короткой длины ключа в 56 бит, которая была недостаточна против прямого перебора высокооснащённым противником. Во-вторых, хотя детали алгоритма и были опубликованы, была раскрыта только часть критериев разработки, что породило спекуляции о том, что DES содержит скрытую уязвимость безопасности или потайную отмычку. В 1993 году Винер указал на эффективный проект компьютера стоимостью 1 миллион долларов США, который мог бы восстановить ключ DES за 3.5 часа, что указывало, на то, что власти США могли восстанавливать ключи DES методом полного перебора ещё в конце 1970-х годов. В 1989 Бихам и Шамир продемонстрировали атаку против DES, которая получила название дифференциального криптоанализа; в ответ на это IBM ответила, что эта атака была известна разработчикам DES и включена в критерий разработки S-блоков. В 1994 году Копперсмит, один из разработчиков DES, представил список из восьми критериев, использованный для создания восьми оригинальных S-блоков DES. Это должно было уладить вопросы по поводу возможных закладок. Несмотря на это, роль АНБ в разработке DES и в частности S-блоков осталась неясной, так как публичные заявления IBM и АНБ в этой области не полностью согласуются между собой.


В 1982 году Мейер и Матиас (два других участника из команды разработки DES в IBM) обсуждали выполнение S-блоков и в особенности необходимое количество минтермов. Они утверждали, что в ранних разработках были получены S-блоки с количеством минтермов между 40 и 48. По мере добавления новых критериев разработки распределение минтермов сдвинулось к диапазону от 52 до 59. Левая граница распределения была выбрана с целью минимизации размера выполнения DES в микросхемах.


Исследователи Lauren De Meyer, Begul Bilgin и Bart Preneel попытались воспроизвести процесс создания S-блоков на основании доступной информации и получили неожиданные результаты: при помощи современных алгоритмов и оборудования, которое превосходит имевшееся в наличии в 1970-е годы по вычислительной мощности в 25 миллионов раз, сгенерировать S-блоки оказалось крайне трудоёмкой задачей.


Критерии Копперсмита выглядят так:


(S-1) Каждый S-блок имеет шесть входящих и четыре исходящих бита.


(S-2) Никакой исходящий бит S-блока не должен быть слишком близок к линейной функции входящих битов (так, если выбрать любое исходящее положение бита и любое подмножество из шести входящих битовых позиций то доля входов, для которых этот выход равен XOR-значению этих битов, не должна быть близка ни к 0, ни к 1, а должна быть близка к 1/2).


(S-3) Если зафиксировать самый левый и самый правый входящие биты в S-блоке и менять четыре средних бита, то каждый возможный 4-битовый выход получается только один раз по мере прохождения четырьмя входными битами всех 16 вариантов.


(S-4) Если два входа в S-блок отличаются по крайней мере в одном бите, то выход должен отличаться по крайней мере в двух битах (Если │ΔIi,j│ = 1, то │ΔOi,j│ ≥ 2, где │x│ — число единичиных бит в количестве x).


(S-5) Если два входа в S-блок отличаются в точности на два средних бита, то и выход должен отличаться минимум на два бита. (Если ΔIi,j = 001100, то │ΔOi,j│ ≥ 2).


(S-6) Если два входа в S-блок отличаются в первых двух битах и идентичны в последних двух битах, то два выхода не должны быть равны друг другу. (Если ΔIi,j = 11xy00, то │ΔOi,j│ ≠ 0 ; x и y — произвольные биты).


(S-7) Для каждой ненулевой разницы между входами ΔIi,j, не может быть более 32 пар входов ΔIi,j, которые показывают одно и тоже значение разницы выхода ΔOi,j.


(S-8) По аналогии с (S-7), но по более строгому ограничению в случае ΔOi,j = 0 в случае трёх активных S-блоков на раунде i.


Каждый из 6x4 S-блоков может быть разделён на строки по четырём 4x4 S-блоков, в которых оставшиеся левые и правые входящие биты большого блока управляют выбором одного из четырёх малых S-блоков. Однако, при таком рассмотрении не все критерии одинаково подходят для больших и малых S-блоков. Примечательно, что критерий (S-3) включает в себя требование того, что каждый 4x4 S-блок был 4-битовой перестанвкой, что облегчает их поиск.


Первоначально современные исследователи DES хотели сгенерировать случайным образом все малые 4x4 S-блоки и расширить их комбинации до 6x4 в соответствии с критериями. Однако, количество таких комбинаций составляет 16! x (4! / 4) = 125 536 739 328 000 ≈ 246.8, что слишком велико. Алгоритм построения пришлось заменить на основе афинных эквивалентностей, имеющих такие же алгебраические и дифференциальные свойства, что и перестановки в DES.


На основе афинных эквивалентностей удалось построить 635 S-блоков, аналогичных S-блокам DES. При этом количество минтермов (от 52 до 55) оказалось чуть выше, чем в результатах Матиаса-Мейера (от 52 до 53), что может указывать на использование разработчиками DES более сильных механизмов минимизации. Более ранний вариант, в котором не соблюдалась часть критериев с количеством минтермов от 40 до 48 по Мейеру-Матиасу удалось достичь только отказавшись от критерия нелинейности (S-2).


Итак, что же удалось выяснить исследвателям? Ранний дизайн Матиаса-Мейера может быть достигнут только путём случайных комбинаций 4-битовых перестановок, что приводит к крайне слабому алгоритму и не мог бы быть всерьёз принят IBM. В более реалистичном последнем варианте современным исследователям удалось приблизиться к параметрам S-блоков от IBM, но тесты Колмогорова-Смирнова показывают отличие в распределениях минтермов в пользу IBM, что не может быть явно объяснено сокрытием каких-то параметров разработки, а возможно лишь при использовании более сильного минимизатора.


Остаётся загадка, которая заключается в вопросе: как, даже при возможных финансовых затратах IBM на два или три порядка превосходящих доступные современным исследователям, но при доступных на тот период времени вычислительных мощностях в десятки миллионов раз меньше, чем доступны сейчас, команде IBM при помощи АНБ удалось сконструировать такие S-блоки для DES, к параметрам которых едва смогли приблизиться современные исследователи?


Источник: fileКафедра электротехники, исследовательская группа по компьютерной безопасности и промышленной криптографии, кафедра перспектив здравоохранения iMind католического университета Лёвен, Бельгия.


 
Много комментариев (13) [показать комментарии/форму]
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3