Дипломная работа: Интегральная атака против блочного симметричного шифра Crypton

Создание новых эффективных методов раскрытия ключа или иного метода ослабления криптоалгоритма может давать осведомленным лицам большие возможности по нанесению ущерба пользователям, применяющим данный криптоалгоритм. Публикация или замалчивание этих сведений определяются степенью открытости общества. Рядовой пользователь системы бессилен помешать нарушителю в раскрытии его ключей.

Из изложенного следует, что понятие "наилучшего известного" алгоритма неабсолютно: завтра может появиться новый более эффективный алгоритм раскрытия, который приведет к недопустимому снижению стойкости криптоалгоритма. С развитием математики и средств вычислительной техники стойкость криптоалгоритма может только уменьшаться. Для уменьшения возможного ущерба, вызванного несвоевременной заменой криптоалгоритма, потерявшего свою стойкость, желательна периодическая перепроверка стойкости криптоалгоритма. Для снижения вероятности непредсказуемого "обвала" вновь разработанного криптоалгоритма необходимо проведение криптографических исследований.

Из рассмотренного выше следует, что понятие стойкости криптосистемы многогранно. Стойкость зависит не только от разработчика, но и от особенностей использования данного криптоалгоритма в системе управлении или связи, от физической реализации криптоалгоритма, а также от будущих успехов математики и вычислительной техники. Ведь криптосистема может эксплуатировать много лет, а необходимость сохранять в секрете в течение длительного времени переданную ранее по открытым каналам связи информацию может сделать необходимым прогнозировать развитие науки и техники на десятилетия.

Последние десятилетие характеризуется резким увеличением числа открытых работ по всем вопросам криптологии, а криптоанализ становится одной из наиболее активно развивающихся областей исследований. Многие криптосистемы, стойкость которых не вызывала особых сомнений, оказались успешно раскрытыми. При этом разработан большой арсенал математических методов, представляющих прямой интерес для криптоаналитика.

В начале 1970-х гг. была известна только классическая одноключевая криптография, но число открытых работ по этой тематике было весьма скромным. Отсутствие интереса к ней можно объяснить целым рядом причин. Во-первых, острой потребности в криптосистемах коммерческого назначения, по-видимому, еще не ощущалось. Во-вторых, большой объем закрытых исследований по криптографии обескураживал многих ученых, которым, естественно, хотелось получить новые результаты. И наконец, может быть, самый важный фактор заключается в том, что криптоанализ как научная дисциплина фактически по-прежнему представлял собой большой набор разрозненных "трюков", не объединенных стройной математической концепцией.

В 1970-х гг. ситуация радикально изменилась. Во-первых, с развитием сетей связи и повсеместным вторжением ЭВМ необходимость в криптографической защите данных стала осознаваться все более широкими слоями общества. Во-вторых, изобретение Диффи и Хелманном криптографии с открытым ключом создало благоприятную почву для удовлетворения коммерческих потребностей в секретности, устранив такой существенный недостаток классической криптографии, как сложность распространения ключей. По существу, это изобретение гальванизировало научное сообщество, открыв качественно новую неисследованную область, которая к тому же обещала возможность широкого внедрения новых результатов быстро развивающейся теории вычислительной сложности для разработки конкретных систем с простым математическим описанием. Ожидалось, что стойкость таких систем будет надежно опираться на неразрешимость в реальном времени многих хорошо известных задач и что, может быть, со временем удастся доказать принципиальную нераскрываемость некоторых криптосистем.

Но надежды на достижение доказуемой стойкости посредством сведения задач криптографии к хорошо известным математическим задачам не оправдалась, а, скорее, наоборот. Именно то обстоятельство, что любую задачу отыскани способа раскрытия некоторой конкретной криптосистемы можно переформулировать как привлекательную математическую задачу, при решении которой удается использовать многие методы той же теории сложности, теории чисел и алгебры, привело к раскрытию многих криптосистем. На сегодняшний день классическая лента однократного использования остается единственной, безусловно, стойкой системой шифрования.

Идеальное доказательство стойкости некоторой криптосистемы с открытым ключом могло бы состоять в доказательстве того факта, что любой алгоритм раскрытия этой системы, обладающий не пренебрежимо малой вероятностью ее раскрытия, связан с неприемлемо большим объемом вычислений. И хотя ни одна из известных систем с открытым ключом не удовлетворяет этому сильному критерию стойкости, ситуацию не следует рассматривать как абсолютно безнадежную. Было разработано много систем, в отношении которых доказано, что их стойкость эквивалентна сложности решения некоторых важных задач, которые почти всеми рассматриваются как крайне сложные, таких, например, как известная задача разложения целых чисел. (Многие из раскрытых криптосистем были получены в результате ослабления этих предположительно стойких систем с целью достижения большого быстродействия.) Кроме того, результаты широких исследований, проводившихся в течение последних десяти лет как в самой криптографии, так и в общей теории вычислительной сложности, позволяют современному криптоаналитику гораздо глубже понять, что же делает его системы нестойкими.

Проведение криптоанализа для давно существующих и недавно появившихся криптоалгоритмов очень актуально, так как вовремя можно сказать, что данный криптоалгоритм нестоек, и усовершенствовать его или заменить новым. Для того, чтобы выявлять нестойкие криптоалгоритмы необходимо все время совершенствовать уже известные методы криптоанализа и находить новые.

Направление криптоанализа могут быть различными, в соответствии с направлениями криптографии: это раскрытие ключа, навязывание ложной информации за счет нахождения слабостей в криптоалгоритме или протоколе, возможность бесконечного чтения зашифрованной информации и т.п.

Криптоалгоритм, как правило, должен быть стойким по отношению к криптоанализу на основе выбранных открытых текстов. Первое требование по существу означает, что рассекречивание некоторой информации, передававшейся по каналу связи в зашифрованном виде, не должно приводить к рассекречиванию другой информации, зашифрованной на этом ключе. Второе требование учитывает особенности эксплуатации аппаратуры и допускает некоторые вольности со стороны оператора или лиц, имеющих доступ к формированию засекреченной информации.

Криптоанализ может базироваться на использовании как общих математических результатов (например методов разложения больших чисел для раскрытия криптосистемы RSA), так и частных результатов, полученных для конкретного криптоалгоритма. Как правило, алгоритмы криптоанализа являются вероятностными.

Дифференциальный метод криптоанализа [21] (ДКА) был предложен Э.Бихамом и А.Шамиром в 1990 г. Дифференциальный криптоанализ - это попытка вскрытия секретного ключа блочных шифров, которые основаны на повторном применении криптографически слабой цифровой операции шифрования r раз. При анализе предполагается, что на каждом цикле используется свой подключ шифрования. ДКА может использовать как выбранные, так и известные открытые тексты .

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

В открытой печати линейный метод криптоанализа впервые был предложен японским математиком Мацуи. Метод предполагает, что криптоаналитик знает открытые и соответствующие зашифрованные тексты.

Обычно при шифровании используется сложение по модулю 2 текста с ключом и операции рассеивания и перемешивания. Задача криптоаналитика - найти наилучшую линейную аппроксимацию (после всех циклов шифрования)

Для раскрытия ключа шифра DES этим методом необходимо 247 пар известных открытых и зашифрованных текстов.

1.5 Выводы по разделу

Исходя из выше изложенного материала можно сделать вывод, что БСШ Crypton является эффективным и на программном и на аппаратном уровне: благодаря высокой степени паралельности и использованию очень простых логических операций ANDS/XORS, CRYPTON работает очень быстро на большинстве платформ, как в программном обеспечении, так и в аппаратных средствах. Анализ безопасности БСШ Crypton показывает, что 12-раундовый самозаменяемый шифр (с одинаковыми процессами для кодирования и расшифрования) с длиной блока 128 битов и длинной ключа до 128 битов обладает хорошей стойкостью к существующим атакам. Интегральная атака на 4-х раундовый БСШ Crypton является намного эффективнее, чем полный перебор по всему ключевому пространству.

Поэтому реализация интегрального алгоритма атаки на БСШ Crypton будет наиболее актуальной задачей.

2. ОСОБЕННОСТИ РЕАЛИЗАЦИИ ИНТЕГРАЛЬНОЙ АТАКИ НА ШИФР CRYPTON

2.1 Интегральные свойства БСШ Crypton

Crypton представляет собой блочный шифр. Длина ключа и длина блока 128 бит. Описание алгоритма атаки взято из [22].

Четыре преобразования работают с промежуточным результатом, называемым Состоянием (State). Состояние можно представить в виде прямоугольного массива из 16 байт , где . Обозначим  – столбец из четырех байт. Аналогично представлен ключ шифрования , где . Обозначим .

В шифре определено поле Галуа GF(28), элементами которого являются байты. Байты рассматриваются как многочлены над Z2:

,

где  i-й бит байта  (0 или 1).

Операция сложения "". При сложении байт соответствующие им многочлены складываются над Z2 (1+1=0).

Операция умножения. При умножении байт соответствующие им многочлены перемножаются над Z2 и результирующий многочлен берется по модулю простого многочлена

.

В процессе работы алгоритма ключ  расширяется (Key Schedule, Key Expansion). Первые 4 столбца (по 4 байта) массива являются исходным ключом (). Каждый последующий r-й набор из 4 столбцов вычисляется из предыдущего набора и используется для r-ого раунда, обозначим его . Раунд состоит из четырех различных элементарных преобразований, которые преобразуют состояние  в состояние :

1.  Замена байт – BS (Byte Substitution): применение перестановки S (также известной как S-блок, Sbox) ко всем байтам состояния независимо.  для .

2.  Сдвиг строк – SR (Shift Rows): циклический сдвиг байт по правилу .

3.  Замешивание столбцов – MC (Mix Columns): каждый столбец состояния изменяется линейным преобразованием . Преобразование  можно представить, как умножение столбца на матрицу слева:

Операция  обратима: .

4.  Добавление раундового ключа – KA (Key Addition): к текущему состоянию прибавляется раундовый ключ .

Финальный раунд не содержит операции MC. Составим 2 формулы, связывающие состояния Ar-1 и Ar:

 (1)

 (2)

2.2 Алгоритм реализации интегральной атаки на БСШ Crypton

В данном разделе описана специфичная для шифра Crypton интегральная атака [22]. Представлено математическое обоснование базовой атаки на 4 раунда.

Интегральная атака основана на возможности свободного подбора атакующим некоторого набора открытых текстов для последующего их зашифрования. Эта атака для 4-раундового шифра Crypton (стандарт Crypton включает в себя 12 раундов) эффективнее, чем полный перебор по всему ключевому пространству.

Введем определения.

Λ-набор – набор из 256 входных блоков (массивов State), каждый из которых имеет байты (назовем их активными), значения которых различны для всех 256 блоков. Остальные байты (пассивные) остаются одинаковыми для всех 256 блоков из Λ-набора. Т.е. : , если байт с индексом  активный и  иначе.

Λk – Λ-набор c k активными байтами.

Pr – множество состояний в конце раунда r.

Возьмем Λ-набор и проследим его изменение в течении нескольких раундов. После элементарных преобразований BS и KA блоки Λ-набора дадут в результате другой Λ-набор с активными байтами в тех же позициях, что и у исходного. Преобразование SR сместит эти байты соответственно заданным в ней смещениям. После преобразования MC Λ-набор в общем случае необязательно останется Λ-набором (т. е. результат операции может перестать удовлетворять определению Λ-набора). Но поскольку каждый байт  результата MC является линейной комбинацией (с обратимыми коэффициентами) четырех входных байт того же столбца , то столбец с единственным активным байтом на входе даст в результате на выходе столбец со всеми четырьмя активными байтами.

Рассмотрим шифрование Λ1-набора, во всех блоках которого активен только один байт. Т.е. значение этого байта различно во всех 256 блоках, а остальные байты одинаковы. Проследим эволюцию этого байта на протяжении трех раундов. В первом раунде преобразование MC преобразует один активный байт в столбец из 4 активных байт, т.е. P1 является Λ4. Во втором раунде эти 4 байта разойдутся по 4 различным столбцам в результате преобразования SR, P2 является Λ16. Преобразование MC следующего, третьего раунда преобразует эти байты в 4 столбца, содержащие активные байты. Этот набор все еще остается Λ-набором до того момента, когда он поступает на вход MC третьего раунда.

Основное свойство Λ-набора – поразрядная сумма по модулю 2 () всех байтов, находящихся на одних и тех же местах, по всему набору равна нулю, т.е. . Действительно, поразрядная сумма неактивных (с одинаковыми значениями) байт равна нулю по определению операции "" (т.к. ), а активные байты, пробегая все 256 значений, также при поразрядном суммировании дадут нуль.

Рассмотрим теперь результат преобразования MC в третьем раунде байтов входного массива данных A в байты выходного массива данных B. Покажем, что и в этом случае поразрядная сумма всех блоков выходного набора будет равна нулю, то есть:

Таким образом, P3 является Λ16, т.е. все данные на входе четвертого раунда сбалансированы (их полная сумма равна нулю). Этот баланс в общем случае нарушается последующим преобразованием BS. Ключ Kr также можно однозначно задать в L-представлении, которое строится следующим образом:

Зная Lr можно вычислить Kr, и обратно. Для проведения атаки потребуется множество Q4 состоящее из 256 состояний: . Множество Q4 можно получить из выходных данных шифра P4 применением 2 обратных преобразований SR-1 и MC-1 к каждому состоянию.

Схема базовой интегральной атаки на 4-раундовый Crypton.

Для всех

Для

Если , то

В этой схеме мы инвертируем 4-ый раунд шаг за шагом, чтобы получить сбалансированные байты P3. При  сумма  будет сбалансированной.

Если предполагаемое значение байта ключа было верно, то оно будет включено в возможные варианты на место . Большая часть неверных значений байта будет отсеяно. За счет того, что поиск может производиться отдельно (параллельно) для каждого байта ключа, скорость подбора всего значения раундового ключа весьма велика. Далее по значению можно найти , а потом и  – исходный ключ [22].

2.3 Описание программной реализации

Разработанный в рамках дипломной работы программный продукт представляет собой реализацию шифрования и расшифрования данных с использованием алгоритма Crypton и реализацию интегральной атаки. Системные требования - компьютер на базе Intel Pentium и выше, ОС - Windows 95 + IE 4.0 и выше.

Программный продукт выполняет следующие операции:

- зашифрование входных данных в криптограму;

- расшифрование криптограммы;

- нахождение 128 – битного ключа.

Операция зашифрования выполняется следующим образом:

1. Запускаем файл ENCRDECR.EXE получаем на экране Рис.2.1

2. Нажатием кнопки "0" выбираем функцию зашифрования;

3. Указываем путь к файлу который необходимо зашифровать и путь где разместить криптограму Рис. 2.2

Рисунок 2.1 Начало работы программы

Рисунок 2.2 Указание пути к файлу

4. По указаному пути мы получим криптограму.

Операция расшифрования выполняется следующим образом:

1.  Запускаем файл ENCRDECR.EXE получаем на экране Рис.2.1

2.  Нажатием кнопки "1" выбираем функцию расшифрования;

3.  Указываем путь к криптограме и путь где разместить расшифрованный файл Рис. 2.3

Рисунок 2.3 Операция расшифрования

5. По указаному пути мы получим исходные данные.

Операция нахождения ключа выполняется следующим образом:

1. Запускаем файл ENCRDECR.EXE получаем на экране Рис.2.1

2. Нажатием кнопки "2" выбираем функцию атаки;

3. Указываем путь к криптограме Рис. 2.4

Рисунок 2.4 Операция нахождения ключа.

В результате получим наш ключ Рис.2.5

3. БЕЗОПАСНОСТЬ ЖИЗНЕДЕЯТЕЛЬНОСТИ

3.1 Анализ условий труда

Дипломный проект выполнялся в помещении научно - исследовательской лаборатории (НИЛ). При разработке применялись ПЭВМ. В дальнейшем при разработке вопросов БЖД будем использовать источники и нормативные документы, регулирующие вопросы БЖД при эксплуатации ПЭВМ [23, 12, 16].

Исследовательские работы выполнялись в помещении НИЛ, размеры которой составляют 4х6х3 м (площадь 24м2). В помещении имеется 1 окно, площадью 6 м2. Рабочих мест 2 (2 программиста). Каждое рабочее место оборудовано ПЭВМ.

Помещение соответствует требованиям ДНАОП 0.00-1.31-99 - на одного работающего приходится 12 м2 площади и, 36 м3 объема при норме 6 м2 и 20 м3 соответственно.

Рассматривая НИЛ как систему "Человек-Машина-Среда" ("Ч-М-С"), можно выделить 2 подсистемы "рабочее место", в состав каждой из которых входят элементы "человек" (работник), "машина" (ПЭВМ). Элемент "среда" (производственная среда в помещении НИЛ) является общим для подсистем "рабочее место".

Элемент "человек" разделим на следующие функциональные части:

Ч1 – человек, выполняющий целенаправленные функции;

Ч2 – человек, рассматриваемый с точки зрения его влияния на "среду" за счет тепло-, влаговыделения и др.;

Ч3 – человек, рассматриваемый с точки зрения его психофизиологического состояния;

ПТ – предмет труда (проектирование программного продукта).

Элемент "машина" разделим на следующие части:

М1 – выполняет основную техническую функцию (программный продукт);

М2 – функции аварийной защиты (изоляция, предохранители);

М3 – управление окружающей средой (тепло, шум, электромагнитное излучение) (рисунок 1).

Рисунок 1. Система "Человек-Машина-Среда" для НИЛ

На рис. 1. приведены обозначения:

1 - (Ч1-М1) воздействие человека на управление машиной и ее настройки (программирование);

2 - (ПТ-М1) информация о состоянии предмета труда, управляемая машиной (исходные данные программы);

3 - (М1-ПТ) воздействие машины на предмет труда (компиляция программного кода);

4 - (Ч2-С) влияние "человека" на "среду" (теплообмен, шум) ;

5 - (С-Ч3) влияние "среды" на психофизиологическое состояние "человека" (утомление, перенапряженность анализаторов);

6 - (С-Ч1) влияние "среды" на качество работы "человека" (физическая и умственная активность);

7 - (М1-С) влияние "машины" на состояние "среды" (Эл.магн. излучение, тепло);

8 - (С-М1, С-М2, С-М3) влияние "среды" на качество работы "машины" (повышение температуры деталей компьютера);

9 - (Ч1-Ч3) связь выполняемой работы с психофизиологическим состоянием организма (утомление, умственная перенапряженность);

10 - (Ч1-Ч2) влияние характера труда на интенсивность обмена веществ ;

11 - (Ч3-Ч3) взаимодействие людей между собой ;

12 - (М1-Ч1) информация о состоянии машины, обрабатываемая человеком (программный код, изображенный на мониторе);

13 - (М1-М2) информационная связь между компьютером и защитной функцией;

14 - (М3-М1) аварийное управляющее воздействие.

Возникающие нецелевые (не связанные с выполнением работ) связи между элементами системы приводят к появлению опасных и вредных производственных факторов (ОВПФ). В таблице 1. перечислены, согласно [24] и ГОСТ 12.0.003-74 возможные ОВПФ с указанием их источника и последствий воздействия на человека. Помещение относится к классу помещений без повышенной опасности, поскольку нет признаков, свойственных особо опасным помещениям и помещениям с повышенной опасностью. Можно выделить следующие ОВПФ в помещении НИЛ.

Страницы: 1, 2, 3, 4, 5