Способы криптоанализа симметричных шифров

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

• аналитические атаки;
• статистические;
• силовые.

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

Класс аналитических атак можно разбить на два подкласса:

• методы анализа управляющей последовательности;
• методы анализа процедуры ключевой инициализации/реинициализации.

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

Класс статистических атак делится на два подкласса:

• методы анализа статистических свойств управляющей последовательности;
• методы анализа сложности последовательности.

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

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

Рассмотрим  аналитические атаки как один из основных видов атак, применяемых к ПШ. Все аналитические атаки осуществляют при условии, что аналитику известно описание генератора (образующие полиномы, вид нелинейного преобразования), он обладает открытым и соответствующим ему закрытым текстом. Атаки данного класса эквивалентны атакам по известному открытому тексту. Задачей аналитика является определение применяемого ключа (начального заполнения).

Если  для блочных шифров нет «канонической» теории их синтеза и анализа, то для поточных шифров теория построения методов «взлома» сформировалась; также установлен набор требований, которым должны удовлетворять «хорошие» схемы. В идейном плане методы взлома поточных шифров сводятся к одному из следующих двух подходов:

• использование статистических связей (корреляционные атаки);
• линеаризация (сведение задачи поиска ключа к решению системы линейных уравнений).

Соответственно, от стойких поточных схем требуется:

• большие периоды выходных последовательностей;
• хорошие статистические свойства выходных последовательностей («постулаты Соломона-Голомба»);
• нелинейность (точнее, высокая линейная сложность) выходных последовательностей.

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

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

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

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

5. Криптоанализ по побочным каналам

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

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

Рисунок 2. Источники  побочных каналов утечки информации.

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

Атаки по побочным каналам классифицируются по следующим трём типам:

• по контролю над вычислительным процессом: пассивные и активные.
• по способу доступа к модулю: агрессивные (invasive), полуагрессивные (semiinvasive) и неагрессивные (non-invasive).
• по методу, применяемому в процессе анализа: простые – simple side channel attack (SSCA) и разностные – differential side channel attack (DSCA).

На  сегодняшний день выделено более  десяти побочных каналов. Атаки различаются по виду используемого побочного канала: атаки по времени исполнения (Timing Attacks), атаки по энергопотреблению (Power Analysis Attacks), атаки по ошибкам вычислений (Fault Attacks), атаки по электромагнитному излучению (ElectroMagnetic Analysis), атаки по ошибкам в канале связи (Error Message Attacks). Существуют более изощренные виды атак: атаки по кэш-памяти (Cache-based Attacks), акустические атаки (Acoustic Attacks), атаки по световому излучению (Visible Light Attacks).

1. Атака по времени

Атака по времени – способ получения  какой-либо скрытой информации путем точного измерения времени, которое требуется пользователю для выполнения криптографических операций. Это – самая первая из атак по побочным каналам, появившаяся в гражданской криптографии. Зачастую время обработки данных в криптосистемах немного изменяется в зависимости от входных значений (например, открытого текста или шифротекста). Это является следствием оптимизации производительности и широкого круга иных причин. Атака по времени основана на измерении времени, необходимого модулю шифрования для выполнения операции шифрования. Эта информация может вести к раскрытию информации о секретном ключе. Например, тщательно измеряя время, требуемое для выполнения операций с секретным ключом, атакующий может найти точное значение экспоненты в алгоритме Diffie-Hellman.

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

2. Атаки по мощности

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

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

Атака по мощности может быть разделена  на простую (Simple Power Analysis, SPA) и разностную (Differential Power Analysis, DPA). Целью SPA является получение информации о конкретных выполняемых инструкциях в системе и о конкретных обрабатываемых данных. В общем случае SPA может дать как сведения о работе устройства, так и информацию о ключе.

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

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

3. Атаки по ошибкам вычислений

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

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

• Точность, которую нарушитель может достичь при выборе времени и места, где появляется ошибка во время работы криптографического модуля.
• Длина данных, на которые влияет ошибка; например, только один бит.
• Постоянство ошибки; является ли ошибка кратковременной или постоянной.
• Тип ошибки; такие как изменение одного бита; изменение одного бита, но только в одном направлении (например, с 1 на 0); изменение бита на случайное значение и др.