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

Рис.1.2 Байтовая подстановка g

1.3.2.2 Битовая перестановка p и байтовое перемещение t

Как линейные преобразования, CRYPTON использует последовательную перестановку бита и перемещения байта. Бит-перестановка смешивает каждый столбец байта в массиве 4×4 байта и байт-перемещение перемещает результирующие столбцы байт в строки байт.

Сначала определяем четыре вектора маскировки (M3, M2, M1, M0) для извлечения бит, используемых в  как:

M0 = m3 || m2 || m1 || m0 = 0x3fcff3fc,

M1 = m0 || m3 || m2 || m1 = 0xfc3fcff3,

M2 = m1 || m0 || m3 || m2 = 0xf3fc3fcf,

M3 = m2 || m1 || m0 || m3 = 0xcff3fc3f, (1.3)

Где m0 = 0xfc, m1 = 0xf3, m2 = 0xcf, m3 = 0x3f. Чтобы сделать процес шифрования и расшифрования идентичными, используются два немного различных варианта перестановки; в нечетных раундах и e в четных раундах. Они определены следующим образом:

- байтовое перемещение o для нечетных раундов: B = o(A) определяется как:

B[0] ß (A[3] Ù M3) Å (A[2] Ù M2) Å (A[1] Ù M1) Å (A[0] Ù M0),

B[1] ß (A[3] Ù M0) Å (A[2] Ù M3) Å (A[1] Ù M2) Å (A[0] Ù M1),

B[2] ß (A[3] Ù M1) Å (A[2] Ù M0) Å (A[1] Ù M3) Å (A[0] Ù M2),

B[3] ß (A[3] Ù M2) Å (A[2] Ù M1) Å (A[1] Ù M0) Å (A[0] Ù M3). (1.4)

- Битовая перестановка e для четных раундов: B=e(A) определяется как:

B[0] ß (A[3] Ù M1) Å (A[2] Ù M0) Å (A[1] Ù M3) Å (A[0] Ù M2),

B[1] ß (A[3] Ù M2) Å (A[2] Ù M1) Å (A[1] Ù M0) Å (A[0] Ù M3),

B[2] ß (A[3] Ù M3) Å (A[2] Ù M2) Å (A[1] Ù M1) Å (A[0] Ù M0),

B[3] ß (A[3] Ù M0) Å (A[2] Ù M3) Å (A[1] Ù M2) Å (A[0] Ù M1). (1.5)

Битовая перестановка  просто перестраивает массив 4×4 байта, перемещая байт из (i, j)-ой позиции в (j, i)-ую позицию (См. Рисунок 1.3 для B=

Рис. 1.3 байтовое перемещение t

1.3.2.3 Добавление ключа s

В следующей операции цикловой ключ добавляется к состоянию посредством простого EXOR. Цикловой ключ вырабатывается из ключа шифрования посредством алгоритма выработки ключей (key schedule).

K = (K[3], K[2], K[1], K[0])t, B = (A) определяется как B[i] = A[i] Å K[i], где i = 0, 1, 2, 3.

1.3.2.4 Циклическое преобразование r

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

roK =  sK  ◦  t ◦ po ◦ g o

для r = 1, 3, ... etc.,(1.6)

reK  =  sK  ◦  t ◦ pe ◦ ge for r = 2, 4, ... etc.  (1.7)

1.3.3 Шифрование и расшифрование

Преобразование кодирования EK r-циклов CRYPTON под ключом K состоит из начального добавления ключа и r/2 повторений и e затем заключительное преобразование вывода. Кодирование и расшифровка могут быть выполнены тем же самым кодом, если применяются различные циклические ключи.

1.3.4 Формирование ключей

R-цикл CRYPTON требует общего количества 4 (r + 1) цикловых ключей 32-битной длины. Эти циклические ключи произведены от ключа пользователя 8k (k = 0,1, ..., 32) бит в два этапа: сначала нелинейное преобразование ключа пользователя в 8 расширенных ключей и затем генерируется необходимое количество циклических ключей от этих расширенных ключей, использующих простые операции.

1.4 Основные виды криптоанализа БСШ и определения надежности СЗИ

Криптология довольно четко делится на две части: криптографию (шифрование) и криптоанализ. Криптограф пытается найти методы обеспечения секретности и(или) аутентичности (подлинности) сообщений [18]. Криптоаналитик пытается выполнить обратную задачу, раскрывая шифр или подделывая кодированные сигналы таким образом, чтобы они были приняты как подлинные. Исходное сообщение, которому криптограф применяет свое искусство, называется открытым текстом, а результат его работы — шифрованным текстом сообщения — шифртекстом, или криптограммой. Для управления процессом шифрования криптограф всегда использует секретный ключ. Часто (но не всегда) он передает этот секретный ключ каким-либо надежным способом (например, в "дипломате", пристегнутом наручниками к руке курьера) человеку (или машине), которому он собирается позднее послать криптограмму, составленную с использованием этого ключа.

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

Системы и средства защиты информации (СЗИ) отличаются от "обычных" систем и средств тем, что для них не существует простых и однозначных тестов, которые позволяют убедиться в том, что информация надежно защищена[19]. Кроме того, эффективность СЗИ и просто их наличие никак не связываются на работоспособности основной системы. Поэтому задача эффективности СЗИ не может быть решена обычным тестированием. Например, для проверки работоспособности системы связи достаточно провести ее испытания. Однако успешное завершение этих испытаний не позволяет сделать вывод о том, что встроенная в нее подсистема защиты информации тоже работоспособна.

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

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

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

Принято различать криптоалгоритмы по степени доказуемости их безопасности [20]. Существуют безусловно стойкие, доказуемо стойкие и предположительно стойкие криптоалгоритмы. Безопасность безусловно стойких криптоалгоритмов основана на доказанных теоремах о невозможности раскрытия ключа. Примером безусловно стойкого криптоалгоритма является система с разовым использованием ключей (шифр Вернама) или система квантовой криптографии, основанная на квантовомеханическом принципе неопределенности. Стойкость доказуемо стойких криптоалгоритмов определяется сложностью решени хорошо известной математической задачи, которую пытались решить многие математики и которая является общепризнанно сложной. Примером могут служить системы Диффи-Хеллмана или Ривеста-Шамира- Адельмана, основанные на сложностях соответственно дискретного логарифмирования и разложения целого числа на множители. Предположительно стойкие криптоалгоритмы основаны на сложности решения частной математической задачи, которая не сводится к хорошо известным задачам и которую пытались решить один или несколько человек. Примерами могут криптоалгоритмы ГОСТ 28147-89, DES, FEAL.

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

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

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

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

Общая схема организации защищенной связи приведена на рисунке 1.11 [21].

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

Источник сообщений вырабатывает произвольную информацию (открытые тексты) с каким-то распределением вероятностей. Шифратор шифрует это сообщение на конфиденциальном (известном только отправителю и получателю) ключе Z и переводит открытый текст в шифрованный текст или шифрограмму (криптограмму, шифртекст).

Рис. 1.11 Общая схема организации защищенной связи

Ключи вырабатываются источником ключей и по безопасным каналам рассылаются абонентом сети связи. Дешифратор раскрывает принятую шифрограмму и передает получателю.

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

Операции шифрования и расшифрования можно описать так:

Y = E(X), X = D(Y)(1.16)

Для взаимной однозначности необходимо, чтобы DE было единичным преобразованием. В этом разделе будет предполагать наличие у отправителя и получателя общего секретного ключа Z. (На самом деле ключи у них не обязательно одинаковые, но знание одного ключа, например шифрования, позволяет легко вычислить другой. Поэтому рассматриваемые криптоалгоритмы иногда называют симметричными, или одноключевыми. Соответственно, и криптография, занимающаяся изучением таких алгоритмов, называется одноключевой). Данная схема применяется в том случае, если абоненты сети доверяют друг другу.

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

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

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

Обычно криптоалгоритмы разрабатывают так, чтобы они были стойкими по отношению к криптоанализу на основе специально выбранных открытых текстов.

Понятие "наилучшего алгоритма" раскрытия ключа в определении стойкости неконструктивно и допускает субъективное толкование (для кого- то из разработчиков наилучшим алгоритмом может быть простой перебор ключей). По-видимому, ни для одного из используемых криптоалгоритмов не определен наилучший алгоритм раскрытия ключа, то есть задача нахождени наилучшего алгоритма является чрезвычайно сложной. Поэтому на практике для оценки стойкости пользуются наилучшим известным или найденным в ходе исследований алгоритмом раскрытия. Таким образом, на практике никто не может помешать способному криптоаналитику снизить оценку стойкости, придумав новый, более эффективный метод анализа.

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