id: Гость   вход   регистрация
текущее время 02:17 29/03/2024
Владелец: 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 католического университета Лёвен, Бельгия.


 
— Гость (19/07/2013 11:03)   <#>
Может существует спец.машинка для генерации s-box?
Интересно, для ГОСТ используются теже критерии?
— unknown (19/07/2013 12:21)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Насчёт критериев ГОСТ — очевидно нет, хотя они официально так до сих пор вообще и не опубликованы. Т.к. у ГОСТ блоки 4x4, то хотя бы часть критериев должна отличаться.

Насчёт машинки — интересно. Забавнее будет, что если для DES додумались сконструировать алгебраический S-блок (как в AES), который подошёл по всем критериям, но скрыли формулу.
— Гость (19/07/2013 12:23)   <#>
Значит ли это, что АНБ опережает гражданскую криптографию на 40 лет? Можно ли предположить, что АНБ способно на криптоанализ AES?
— unknown (19/07/2013 12:48, исправлен 19/07/2013 12:52)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Ну как бы кое-что у них в загашниках есть, особенно, когда дело касается собственных разработок. Опять же, про дифференциальный анализ при разработке DES знали, а про линейный — получается нет. Или делали вид, что не знают. Почва для спекуляций про тайные знания?


АНБ, например предложила SHA-0 в 1993 году, но быстро внесла мелкий фикс, исправляющий уязвимость, до SHA-1 без объяснения причины. Только с 1998 по 2005 годы гражданские криптографы смогли разобраться в чём там было дело.



В то время не было никакой гражданской криптографии. Это практически дата её зарождения. Так что, сравнивать успехи не с чем. IBM выполняла разработку DES совместно с АНБ для НБС (нынешний НИСТ) по контракту и стандарт никогда не должен был быть опубликован, а существовать только в виде закрытых микросхем. Произошла непреднамеренная (если отбросить возможность конспирологии) утечка и стандарт по ошибке опубликовали при передаче документации в НБС. АНБ признала это своей самой большой ошибкой, благодаря которой и зародилась свободная гражданская криптография.



На основании доступных данных — нет. АНБ демонстративно отказалось от разработки и криптоанализа кандидатов AES и проверяло кандидатов только по эксплуатационным характеристикам. Формула для S-блока AES выбрана открыто из малого числа доступных полиномов, обоснована (из всех полиномов выбрали самые малозатратные в реализации), никаких магических констант не содержит. Показано, что если выбрать другие возможные полиномы для этого поля, то стойкость альтернативных вариантов S-блоков AES не изменится.

— Гость (21/07/2013 09:02)   <#>
Показано, что если выбрать другие возможные полиномы для этого поля, то стойкость альтернативных вариантов S-блоков AES не изменится.
Где это можно посмотреть?
— unknown (21/07/2013 11:00, исправлен 21/07/2013 11:00)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

К сожалению, статью потерял, названия не помню и ничего не нагугливается. Может вам больше повезёт?


Называлось как-то наподобие "256 ways to implement Rijndael" или "256 ways to implement S-box for AES". Один из авторов вроде даже Шамир. В конце работы были приведены все 256 вариантов S-блоков. Вроде даже рекомендовалось как один из вариантов шифрования для защиты от утечек по побочным каналам (timing и differrential power атаки) — когда при шифровании совместимость с AES неважна, можно случайно выбирать один из 256 равностойких S-блоков, тем самым мешая противнику понять для какого искать ключ. Если замена производится динамически и часто, то это выравнивает статистику утечки данных.

— Гость (21/07/2013 18:07)   <#>
Возможно речь идет о статье "How many ways you can write Rijndael"? В конце (раздел 9 и acknowledgements) что-то похожее упоминается www.iacr.org/archive/asiacrypt2002/25010159/25010159.ps
— unknown (21/07/2013 22:27, исправлен 21/07/2013 23:02)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Похоже. Возможно читал другую версию работы, там в приложении было просчитано 255 S-блоков. Был ещё ряд каких-то работ по генерации похожих S-блоков.


Наилучшее описание прозрачности выбора параметров Rijndael дано в работе Сюзан Ландау filePolynomials in the Nation’s Service: Using Algebra to Design the Advanced Encryption Standard:


Daemen and Rijmen had an unstated goal in their algorithm design: transparency. The two designers wanted no suspicion of trapdoors. The polynomial defining the field is the first entry in Lidl and Niederreiter’s table of irreducible polynomials of GF(28) [25]. In using a public list to pick their parameters, Rijndael’s designers showed there was nothing up their sleeves. The simplicity of x8 + 1 and x4 + 1 is another demonstration of the lack of hidden parameters.

— Гость (22/07/2013 07:25)   <#>
Похоже. Возможно читал другую версию работы, там в приложении было просчитано 255 S-блоков.

К упомянутой выше статье нашлось и приложение: "The book of Rijndaels", filehttps://eprint.iacr.org/2002/158.ps.gz

Кстати, критерии и мотивы выбора полиномов, констант, числа раундов и т.д. можно найти и у авторов Rijndael в работе, представленной ими на драфт (раздел 7):
filehttp://csrc.nist.gov/archive/a.....ijndael-ammended.pdf
— unknown (22/07/2013 09:40)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Спасибо, всегда полезно обратиться к первоисточникам.
— стоматолог (07/08/2013 03:58)   <#>
Просто IBM провела больше ручной работы с конкретными блоками, с индивидуальным подходом к каждому испытуемому блоку. А ручная работа исследователей свелась к написанию программы, которая тупо перебирала блоки по общему шаблону. Никакого секрета.
— unknown (07/08/2013 12:29)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Непонятно, как это? Что конкретно тупо перебирала программа, а что разбирали вручную?
— стоматолог (07/08/2013 22:45)   <#>
Программа видимо перебирала все блоки подряд но из ограниченного множества (редукция к 4-битным перестановкам) и отсеивала не подходящие по критериям. А IBM-щики эвристически подбирали "хорошие" затравочные блоки не претендуя на полный перебор, а затем вручную многоэтапно улучшали каждый испытуемый блок учитывая его индивидуальные свойства.
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3