Методика оценки алгоритмов блочного симметричного шифрования

Размещено на http://www.allbest.ru/

Методика оценки алгоритмов блочного симметричного шифрования

Головашич С.О.

Постановка проблемы в общем виде и анализ литературы. Бурное развитие в последние годы вычислительных возможностей коммуникационных и компьютерных систем выдвигает новые требования к надежности и производительности систем защиты обрабатываемой информации. Основным и наиболее эффективным механизмом криптографической защиты в таких системах являются методы блочно-симметричного шифрования данных (БСШ). Проведенный анализ [1- - 6] показал, что системы защиты, построенные на основе симметричных криптоалгоритмов наряду с высокой скоростью преобразований и простотой практической реализации позволяют обеспечивать высокую степень устойчивости к различным методам криптографического анализа [2, 5, 6].

Исследования [1 - 6] используемых в современных системах защиты стандартов БСШ показали, что большинство наиболее распространённых алгоритмов уже устарели и не обеспечивают требуемой криптостойкости и производительности, в то время как новые алгоритмы требуют тщательного исследования и стандартизации [2, 3].

Так в Украине до сих пор нет своего национального стандарта на симметричный алгоритм шифрования, что вынуждает в системах защиты внутриплатежных банковских систем, коммуникационных и компьютерных системах госучреждений использовать устаревший стандарт бывшего СССР - блочно-симметричный алгоритм ГОСТ 28147-89 [2].

Наиболее распространённым подходом предварительного (экспресс) анализа современных криптоалгоритмов в целом, и БСШ в частности, является оценка трёх показателей: устойчивости алгоритма к известным криптоаналитическим атакам, производительности программной реализации алгоритма на современных персональных компьютерах и “статистической безопасности” (формирование уникальных псевдослучайных последовательностей). Однако данный подход оказывается недостаточным, если требуется создание/выбор алгоритма, претендующего на роль национального стандарта, а значит предполагающего его массовое внедрение в различных сферах применения. В таком случае, третьим (иногда вторым) по значимости критерием, после криптостойкости и производительности, становится “стоимость” реализации алгоритма на различных программно-аппаратных платформах [2, 3].

Целью данной статьи является анализ основных требований и характеристик проектирования, предъявляемых к алгоритмам-претендентам блочно-симметричного шифрования на роль национального стандарта, методики оценки характеристик БСШ на основе анализа эффективности их проектирования.

Методика оценки характеристик эффективности проектирования БСШ. Под эффективностью проектирования БСШ понимается комплексная оценка алгоритма БСШ, отражающая обоснованность и оптимальность выбранных авторами конструкций для решения задачи проектирования БСШ, т.е. минимизации аппаратных “затрат”, необходимых для обеспечения устойчивости алгоритма к известным атакам криптоанализа [1 - 4].

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

Таким образом, абсолютная оценка эффективности проектирования, на практике, является достаточно сложной, за исключением случаев, когда в конструкции алгоритма присутствуют очевидные ошибки проектирования. С другой стороны, относительная или сравнительная оценка эффективности проектирования может быть выполнена достаточно просто, особенно когда рассматриваются несколько алгоритмов, одинакового назначения и удовлетворяющих единой системе требований. Поэтому целью методики оценки БСШ является формирование сравнительной оценки эффективности проектирования алгоритмов-претендентов [2, 3].

В качестве опорных характеристик для оценки эффективности проектирования предлагается использовать:

1) уязвимость к известным криптоаналитическим атакам (показатель - положительно/отрицательно);

2) количественные характеристики каждого из необходимых аппаратных ресурсов (показатель - перечисление характеристик);

3) конструктивные особенности построения БСШ, приводящие к избыточным накладным расходам некоторого из ресурсов вычислителя, и при этом не обоснованные повышением уровня криптостойкости алгоритма (показатель - количество и перечень «избыточных» конструкций) [2, 3].

Как показывает анализ проведенных конкурсов по криптоалгоритмам [5 - 6], в современных симметричных криптосистемах показателем фактической криптостойкости является факт отсутствия известных аналитических атак со сложностью меньшей, чем полный перебор ключа, т.е. “силовая атака”. Таким образом, задачу проектирования БСШ, как и любого другого симметричного криптоалгоритма, можно свести к задаче поиска наименее ресурсоёмкого преобразования, обеспечивающего сложность поиска секретного ключа не проще чем полный перебор ключевого пространства.

Анализ характеристик для оценки эффективности проектирования БСШ. Для точного анализа, данные характеристики необходимо рассматривать в совокупности, и оценивать алгоритмы, учитывая все оценки, полученные в результате тестов. Рассмотрим основные характеристики к алгоритмам-претендентам подробнее.

Уязвимость к известным криптоаналитическим атакам.

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

Рассмотрим задачу дифференциального криптоанализа: используя свойства алгоритма, в основном свойства S-box, определить подключ раунда. Конкретный способ дифференциального криптоанализа зависит от рассматриваемого алгоритма шифрования [2].

Если в основе алгоритма лежит сеть Файстеля, можно считать, что блок m состоит из двух половин - m0 и m1. Дифференциальный криптоанализ рассматривает отличия, которые происходят в каждой половине при шифровании. (Для различных алгоритмов “отличия” определяются с помощью булевых операций). Выбирается пара незашифрованных текстов с фиксированным отличием. Затем анализируются отличия, получившиеся после шифрования одним раундом алгоритма, и определяются вероятности различных ключей. Если для многих пар входных значений, имеющих одно и то же отличие Х, при использовании одного и того же подключа одинаковыми (Y) оказываются и отличия соответствующих выходных значений, то можно говорить, что Х влечет Y с определенной вероятностью. Если эта вероятность близка к единице, то можно считать, что подключ раунда найден с данной вероятностью. Так как раунды алгоритма независимы, вероятности определения подключа каждого раунда следует перемножать. Считается, что результат шифрования данной пары известен. Результаты дифференциального криптоанализа используются как при разработке конкретных S-box, так и при определении оптимального числа раундов [2].

Другим способом криптоанализа является линейный криптоанализ, который использует линейные приближения преобразований, выполняемых алгоритмом шифрования. Данный метод позволяет найти ключ, имея достаточно большое число пар (незашифрованный текст, зашифрованный текст). Рассмотрим основные принципы, на которых базируется линейный криптоанализ [2, 3].

Обозначим:

P[1], … , P[n] - незашифрованный блок сообщения.

C[1], … , C[n] - зашифрованный блок сообщения.

K[1], … , K[m] - ключ.

A[i, j, …, k] = A[i]A[j] …A[k].

Целью линейного криптоанализа является поиск линейного уравнения вида:

P[б1, б2, …, бa]C[в1, в2, …, вb ] = K[г1, …, гc].

Выполняющееся с вероятностью р ? 0,5 бi, вi и гi - фиксированные позиции в блоках сообщения и ключе. Чем больше р отклоняется от 0,5, тем более подходящим считается уравнение [2].

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

Как следует из приведенного метода, уравнения составляются следующим образом. Вычисляются значения левой части для большого числа пар соответствующих фрагментов незашифрованного и зашифрованного блоков. Если результат оказывается равен нулю более чем в половине случаев, то полагают, что K[г1, …, гс] = 0. Если в большинстве случаев получается 1, полагают, что K[г1, …, гс] = 1.

Таким образом, получают систему уравнений, решением которой является ключ [2].

Количественные характеристики каждого из необходимых аппаратных ресурсов.

Задачу проектирования практического алгоритма БСШ следует рассматривать как задачу минимизации “затрат” на реализацию криптопреобразования, обеспечивающего необходимые показатели криптостойкости [4]. симметричный шифрование линейный криптоанализ

Следует отметить, что под “затратами” будем понимать перечень и объём ресурсов целевой аппаратной платформы, необходимых для реализации на ней анализируемого алгоритма БСШ. Нас будут интересовать следующие аппаратные ресурсы [2]:

- вычислительные ресурсы (единица измерения - количество тактов либо микроопераций вычислителя, необходимых для обработки единицы информации; в случае БСШ - это шифрование одного блока данных или “разворачивания” одного пользовательского ключа) - отражают производительность;

- ресурсы оперативной памяти (RAM, единица измерения - байт или КБайт) - необходимы для хранения, используемого в процессе вычислений, ключевого материала и промежуточных данных;

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

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

В приведенном выше списке ресурсы расположены в порядке убывания ценности» (для большинства аппаратных платформ).

Учитывая, что в настоящий момент не принято окончательное решение о том должны ли таблицы подстановок быть сменным параметром алгоритма или нет, и если - да, то в каком виде (“только S-блоки” или “S-блоки + MBN-полином”, выбор значений таблиц подстановок будет допустим из полного пространства или заранее ограниченного и т.д.), их учитывают как константные значения (т.е. в составе ресурса ROM). С одной стороны, использование фиксированных подстановок позволяет существенно снизить стоимость реализации, т.к. для них не требуется EEPROM и, в зависимости от реализации, возможно сокращение времени “установки ключа”. С другой стороны, в методике остаётся возможность оценить затраты EEPROM, в случае применения сменных таблиц подстановок. Однако оценка таблиц подстановок как фиксированных параметров, позволит нам исключить из остальных расчётов ресурс EEPROM, т.к. размеры исходных (пользовательских) ключей определяются требованиями к алгоритмам [2, 3].

При анализе требуемого объёма ресурсов, необходимо выполнить оценку для каждого класса аппаратных платформ, на которых может потребоваться реализация заданного криптоалгоритма.

Основные программно-аппаратные платформы, получившие широкое распространение сегодня можно разделить на три класса:

- 8/16-битные микроконтроллеры и смарт-карты;

- 32-битные микропроцессоры и микроконтроллеры (ARM, IA-32);

- 64-битные процессоры общего назначения (AMD64, Intel 64).

Таким образом, реализация алгоритма БСШ на микроконтроллере узкоспециализированного назначения, как правило, накладывает ограничения на все перечисленные выше ресурсы. Так, наиболее технически защищённая и удобная аппаратная платформа массового применения - бесконтактная смарт-карта, обладает предельно ограниченными ресурсами [3]. Наиболее современные представители (по состоянию на 2010 год) характеризуются следующими показателями:

- CPU: 8/16 bit, с частотой до 30 MHz;

- RAM: 4-8 KB;

- ROM: 100-250 KB;

- EEPROM: 8-80 KB.

Однако следует отметить, что применение защищённой
SoC-технологии (System-on-Chip) позволяет обеспечить наибольшую степень защиты секретных ключей. Это достигается за счёт поддержки полного жизненного цикла секретных ключей исключительно в памяти чипа, интегрирующего в себе: CPU, RAM, EEPROM, FLASH/ROM и TRNG (сертифицированный физический датчик случайных чисел), и при этом технологически защищенного от пассивных и активных атак класса Side-Channel. Чипы смарт-карт получили широкое распространение в сфере финансовых услуг и персональных систем контроля доступа широкого назначения. Поэтому возможность эффективной реализации разрабатываемого алгоритма на смарт-карте является необходимым условием его массового применения.

Примечание: на сегодняшний день практически все смарт-карты для финансового сектора имеют аппаратную поддержку Triple-DES, и даже AES (чипы NXP) [2].

Конструктивные особенности построения БСШ, приводящие к избыточным накладным расходам некоторого из ресурсов вычислителя, и при этом не обоснованные повышением уровня криптостойкости алгоритма.

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

Анализ показал, что эффективность конструкции БСШ можно оценить соотношениями:

- “противодействие криптоаналитическим атакам” - “расходы на реализацию”;

- “противодействие криптоаналитическим атакам” - “быстродействие”.

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

Выводы

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

Перспективным направлением дальнейших исследований является применение данной методики при оценке алгоритмов-участников конкурса БСШ Украины.

Список литературы

1. Кузнецов А. А., Москвиченко И. В. Разработка предложений по совершенствованию симметричных средств защиты информации перспективной системы критического применения. // Комп'ютерні системи та інформаційні технології. - Харьков. - 2008 р. С. 94 - 100.

2. Головашич С. А. Анализ эффективности проектирования алгоритмов-участников конкурса БСШ Украины. // Отчет. - Харьков: ООО «КРИПТОМАШ». - 2009 г. - С. 70.

3. Головашич С. А. Анализ эффективности проектирования алгоритмов участников конкурса БСШ Украины. // ХI Международная научно-практическая конференция «Безопасность информации в информационно-телекоммуникационных системах». Киев. 2008 г. - C. 31.

4. Долгов В. И. Подстановочные конструкции современных симметричных блочных шифров. / В. И. Долгов, Р. В. Олейников, И. В. Лисицкая, Р. В. Сергиенко, Е. В. Дроботько, Е. Д. Мельничук. - Харьков, Радиотехника, выпуск 6 (40), 2009 - С. 89 - 93.

5. Preneel B. Final report of European project number IST-1999-12324, named New European Schemes for Signatures, Integrity, and Encryption. / B. Preneel, A. Biryukov, C. De Canni`ere1, S. B. Ors, E. Oswald, B. Van Rompay1, - Berlin, Springer-Verlag, April 19, 2004 - Version 0.15 (beta) - pp. 836.

6. Nechvatal J. Report on the Developmentof the Advanced Encryption Standard (AES). / J. Nechvatal, E. Barker, L. Bassham, W. Burr, M. Dworkin, J. Foti, E. Roback, - Computer Security Division, Information Technology Laboratory, National Institute of Standards and Technology, Technology Administration, U.S. Department of Commerce, October 2, 2000 - pp. 116.

Размещено на Allbest.ru