Алгоритмы шифрования для использования так или иначе должны быть реализованы в некоторой компьютерной программе или аппаратном шифраторе. И в том, и в другом случае у криптоаналитика появляются дополнительные возможности для атак на алгоритмы шифрования. Данные возможности проистекают из того факта, что любой шифратор в процессе своей работы дает криптоаналитику возможность для съема различной побочной информации. Причем интенсивность утечки такой информации и ее полезность для криптоаналитика зависят как от структурных особенностей самого алгоритма шифрования, так и от особенностей его программной или аппаратной реализации: насколько разработчик шифратора старался уменьшить возможность утечки информации и вообще учитывал возможность подобных атак.
Все атаки, использующие утечки данных по побочным каналам (side-channel attacks), можно разделить на две категории:
1) пассивные (passive) атаки, в процессе реализации которых криптоаналитик лишь пассивно «прослушивает» шифратор с целью получения необходимой информации для ее последующего анализа;
2) активные (active) атаки, для проведения которых криптоаналитик производит различные воздействия на шифратор с целью заставить его работать в нештатном режиме, вследствие чего шифратор может выдавать существенно больше полезной информации по побочным каналам.
Для начала рассмотрим пассивные атаки.
Начало подобным атакам положили работы Пола Кохера (Paul Kocher), в которых была представлена атака по времени выполнения (timing attack). Данная атака использует тот факт, что на некоторых аппаратных платформах определенные операции могут выполняться за различное число тактов процессора. Результат – различное время выполнения операций. Соответственно, криптоаналитик путем высокоточных замеров времени выполнения шифратором определенных операций может сделать какие-либо предположения о значении определенных фрагментов секретного ключа.
Существует следующая классификация используемых в криптоалгоритмах операций по степени их подверженности атакам по времени выполнения:
1) не подвержены атакам по времени выполнения (т. е. выполняются за одинаковое число тактов на всех платформах) операции табличной замены, сдвига и вращения на фиксированное число битов, а также логические операции;
2) в ряде случаев атаки по времени выполнения могут быть проведены против алгоритмов, в которых присутствуют операции сложения или вычитания;
3) наиболее проблемными с данной точки зрения являются операции умножения, деления, возведения в степень, а также сдвиги и вращения на переменное число битов.
Одним из наиболее показательных алгоритмов, против которых может быть проведена атака по времени выполнения, является алгоритм RC5. В раунде RC5 присутствуют операции вращения на переменное число битов, что приводит к появлению неких, зависящих от обрабатываемых данных и значения секретного ключа, временных характеристик. Это делает атаку на RC5 теоретически возможной. Среди других алгоритмов, подверженных данной атаке, Кохер упоминает такие известные алгоритмы, как IDEA, Blowfish и DES.
В качестве «противоядия» к атакам по времени выполнения Кохер предлагает следующее:
1. Обеспечить выполнение шифратором операций строго за одно и то же количество тактов процессора независимо от значений операндов. Однако, это сопряжено с техническими сложностями; кроме того, уменьшает быстродействие алгоритма, поскольку время выполнения операций в этом случае будет приведено к максимально возможному.
2. Различным образом маскировать время выполнения операций: использовать случайные временные задержки, выполнять произвольные зашумляющие операции, внедрять в алгоритм различные случайные величины и т. д. Все это также приводит к уменьшению быстродействия алгоритма, поэтому наилучшим вариантом противодействия данным атакам является отсутствие в алгоритме шифрования операций, время выполнения которых зависит от обрабатываемых данных.
Еще одна из пассивных атак предложена также Полом Кохером при участии ряда других сотрудников американской компании Cryptography Research: атака по потребляемой мощности (SPA – simple power analysis). Данная атака во многом похожа на предыдущую, однако, высокоточному замеру подлежит мощность, потребляемая шифратором в процессе выполнения криптографических преобразований.
В работе доказывается, что такой высокоточный замер мощности, достаточный для криптоанализа, вполне возможен. В качестве доказательства, в частности, приводится результат замера мощности, потребляемой шифратором в процессе выполнения раундов №№ 2 и 3 алгоритма DES (иллюстрация из работы Кохера и его коллег приведена далее).
На рисунке отчетливо видны операции вращения ключевых регистров процедуры расширения ключа DES: перед вторым раундом вращение выполняется на 1 бит, а перед третьим – на два бита (см. стрелочки на рисунке). Кроме того, отчетливо видны различия между данными раундами (например, см. выделенные рамками области) – эти различия могут проистекать, в том числе, из-за того, что в этих раундах используются различные биты ключа. Соответственно, они могут быть проанализированы криптоаналитиком с целью получения какой-либо информации о ключе шифрования.
В качестве противодействия SPA предлагаются различные методы зашумления – аналогично атакам по времени выполнения.
Усилением SPA является дифференциальный криптоанализ по потребляемой мощности DPA (differential power analysis). Данная атака является более эффективной, чем SPA, но и более сложно реализуемой на практике.
В 2000 г. была предложена атака, использующая высокоточные измерения электромагнитного излучения шифратора, возникающего в процессе шифрования. Аналогично SPA и DPA, рассматриваются два варианта такой атаки: SEMA (simple electromagnetic analysis) и DEMA (differential electromagnetic analysis). Авторы атаки в качестве атакуемых устройств избрали криптографические смарт-карты, реализующие алгоритмы DES, RSA и COMP128. Во всех трех случаях атака методом DEMA позволила вычислить значения ключей шифрования.
Еще одна атака основана на предположении, что шифраторы должны каким-либо образом сообщать о возникновении ошибочных ситуаций, которые могут возникнуть при расшифровании данных. Простейший вариант – попытка расшифрования неверным ключом. Сам факт ошибки расшифрования может в определенных случаях дать криптоаналитику некоторую полезную информацию (причем, в общем случае, сообщение шифратора об ошибке может быть достаточно развернутым и информативным). Практически реализуемая атака, основанная на сообщениях об ошибках (error message leakage), была предложена известным криптологом Сержем Воденэ (Serge Vaudenay).
Успех описанных атак зависит от множества различных факторов, в частности:
1) содержит ли атакуемый алгоритм операции, критичные с точки зрения утечек информации по побочным каналам;
2) насколько реализация алгоритма в программном или аппаратном шифраторе учитывает данные атаки и защищена от подобных утечек информации.
Наиболее часто атакуемыми оказываются криптографические смарт-карты, т. е. достаточно низкоскоростные шифраторы, работающие в условиях ограниченных ресурсов. В данном случае для проведения атаки нет необходимости в столь высокоточных замерах, какие были бы необходимы, например, для атаки на программный шифратор, работающий на современном персональном компьютере.
Информация, полученная с помощью атак с использованием утечек данных по побочным каналам, может использоваться криптоаналитиком в контексте других атак, например, для сужения области возможных значений ключа шифрования. Теоретически возможен и идеальный для криптоаналитика вариант: полное раскрытие алгоритма (т. е. вычисление ключа шифрования) только за счет пассивной side-channel-атаки.
Это фрагмент книги Сергея Панасенко «Алгоритмы шифрования. Специальный справочник».
Все атаки, использующие утечки данных по побочным каналам (side-channel attacks), можно разделить на две категории:
1) пассивные (passive) атаки, в процессе реализации которых криптоаналитик лишь пассивно «прослушивает» шифратор с целью получения необходимой информации для ее последующего анализа;
2) активные (active) атаки, для проведения которых криптоаналитик производит различные воздействия на шифратор с целью заставить его работать в нештатном режиме, вследствие чего шифратор может выдавать существенно больше полезной информации по побочным каналам.
Для начала рассмотрим пассивные атаки.
Атака по времени выполнения
Начало подобным атакам положили работы Пола Кохера (Paul Kocher), в которых была представлена атака по времени выполнения (timing attack). Данная атака использует тот факт, что на некоторых аппаратных платформах определенные операции могут выполняться за различное число тактов процессора. Результат – различное время выполнения операций. Соответственно, криптоаналитик путем высокоточных замеров времени выполнения шифратором определенных операций может сделать какие-либо предположения о значении определенных фрагментов секретного ключа.
Существует следующая классификация используемых в криптоалгоритмах операций по степени их подверженности атакам по времени выполнения:
1) не подвержены атакам по времени выполнения (т. е. выполняются за одинаковое число тактов на всех платформах) операции табличной замены, сдвига и вращения на фиксированное число битов, а также логические операции;
2) в ряде случаев атаки по времени выполнения могут быть проведены против алгоритмов, в которых присутствуют операции сложения или вычитания;
3) наиболее проблемными с данной точки зрения являются операции умножения, деления, возведения в степень, а также сдвиги и вращения на переменное число битов.
Одним из наиболее показательных алгоритмов, против которых может быть проведена атака по времени выполнения, является алгоритм RC5. В раунде RC5 присутствуют операции вращения на переменное число битов, что приводит к появлению неких, зависящих от обрабатываемых данных и значения секретного ключа, временных характеристик. Это делает атаку на RC5 теоретически возможной. Среди других алгоритмов, подверженных данной атаке, Кохер упоминает такие известные алгоритмы, как IDEA, Blowfish и DES.
В качестве «противоядия» к атакам по времени выполнения Кохер предлагает следующее:
1. Обеспечить выполнение шифратором операций строго за одно и то же количество тактов процессора независимо от значений операндов. Однако, это сопряжено с техническими сложностями; кроме того, уменьшает быстродействие алгоритма, поскольку время выполнения операций в этом случае будет приведено к максимально возможному.
2. Различным образом маскировать время выполнения операций: использовать случайные временные задержки, выполнять произвольные зашумляющие операции, внедрять в алгоритм различные случайные величины и т. д. Все это также приводит к уменьшению быстродействия алгоритма, поэтому наилучшим вариантом противодействия данным атакам является отсутствие в алгоритме шифрования операций, время выполнения которых зависит от обрабатываемых данных.
Атаки по потребляемой мощности
Еще одна из пассивных атак предложена также Полом Кохером при участии ряда других сотрудников американской компании Cryptography Research: атака по потребляемой мощности (SPA – simple power analysis). Данная атака во многом похожа на предыдущую, однако, высокоточному замеру подлежит мощность, потребляемая шифратором в процессе выполнения криптографических преобразований.
В работе доказывается, что такой высокоточный замер мощности, достаточный для криптоанализа, вполне возможен. В качестве доказательства, в частности, приводится результат замера мощности, потребляемой шифратором в процессе выполнения раундов №№ 2 и 3 алгоритма DES (иллюстрация из работы Кохера и его коллег приведена далее).
На рисунке отчетливо видны операции вращения ключевых регистров процедуры расширения ключа DES: перед вторым раундом вращение выполняется на 1 бит, а перед третьим – на два бита (см. стрелочки на рисунке). Кроме того, отчетливо видны различия между данными раундами (например, см. выделенные рамками области) – эти различия могут проистекать, в том числе, из-за того, что в этих раундах используются различные биты ключа. Соответственно, они могут быть проанализированы криптоаналитиком с целью получения какой-либо информации о ключе шифрования.
В качестве противодействия SPA предлагаются различные методы зашумления – аналогично атакам по времени выполнения.
Усилением SPA является дифференциальный криптоанализ по потребляемой мощности DPA (differential power analysis). Данная атака является более эффективной, чем SPA, но и более сложно реализуемой на практике.
Другие пассивные атаки
В 2000 г. была предложена атака, использующая высокоточные измерения электромагнитного излучения шифратора, возникающего в процессе шифрования. Аналогично SPA и DPA, рассматриваются два варианта такой атаки: SEMA (simple electromagnetic analysis) и DEMA (differential electromagnetic analysis). Авторы атаки в качестве атакуемых устройств избрали криптографические смарт-карты, реализующие алгоритмы DES, RSA и COMP128. Во всех трех случаях атака методом DEMA позволила вычислить значения ключей шифрования.
Еще одна атака основана на предположении, что шифраторы должны каким-либо образом сообщать о возникновении ошибочных ситуаций, которые могут возникнуть при расшифровании данных. Простейший вариант – попытка расшифрования неверным ключом. Сам факт ошибки расшифрования может в определенных случаях дать криптоаналитику некоторую полезную информацию (причем, в общем случае, сообщение шифратора об ошибке может быть достаточно развернутым и информативным). Практически реализуемая атака, основанная на сообщениях об ошибках (error message leakage), была предложена известным криптологом Сержем Воденэ (Serge Vaudenay).
Успех описанных атак зависит от множества различных факторов, в частности:
1) содержит ли атакуемый алгоритм операции, критичные с точки зрения утечек информации по побочным каналам;
2) насколько реализация алгоритма в программном или аппаратном шифраторе учитывает данные атаки и защищена от подобных утечек информации.
Наиболее часто атакуемыми оказываются криптографические смарт-карты, т. е. достаточно низкоскоростные шифраторы, работающие в условиях ограниченных ресурсов. В данном случае для проведения атаки нет необходимости в столь высокоточных замерах, какие были бы необходимы, например, для атаки на программный шифратор, работающий на современном персональном компьютере.
Информация, полученная с помощью атак с использованием утечек данных по побочным каналам, может использоваться криптоаналитиком в контексте других атак, например, для сужения области возможных значений ключа шифрования. Теоретически возможен и идеальный для криптоаналитика вариант: полное раскрытие алгоритма (т. е. вычисление ключа шифрования) только за счет пассивной side-channel-атаки.
Это фрагмент книги Сергея Панасенко «Алгоритмы шифрования. Специальный справочник».