Side-channel атаки. Взлом COMP128

, аспирант кафедры, безопасных информационных технологий СПб НИУ ИТМО, mikhail. *****@***com

, доцент кафедры Безопасных Информационных Технологий НИУ ИТМО, *****@

Аннотация

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

Введение

В последние 20 лет активно развивается новое направление криптоанализа, называемое Side Channel Attacks (SCA), или атаки по побочным каналам[1-9]. Основная идея данного подхода заключается в том, что шифрующее устройство рассматривается не только как математический аппарат, но и как конкретная его реализация на практике. Классический криптоанализ рассматривает криптоалгоритм с точки зрения математики - как некоторую функцию от входных данных, на выходе которой зашифрованный текст. Новая концепция рассматривает криптоалгоритм вместе с его материальной реализацией, обладающей определенными физическими свойствами, такими как время выполнения алгоритма, потребляемая при шифровании мощность, электромагнитное излучение от шифрующего устройства и другие.

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

В данной статье будет рассмотрена одна из таких атак по побочным каналам - распределенная атака на COMP128 (алгоритм аутентификации в GSM-стандарте).

Распределенная атака на COMP128

В мае 2002 года сотрудники IBM Watson Research Center Josyula R. Rao, Pankaj Rohatgi и Helmut Scherzer совместно с Stephane Tinguely из Swiss Federal Institute of Technology опубликовали статью “Partitioning Attacks: Or How to Rapidly Clone Some GSM Cards” (Распределенные атаки или как быстро клонировать GSM-карты), в которой рассказали, как можно реализовать атаку по потребляемой мощности (Simple Power Analysis - SPA) на SIM-карту [6]. Данная атака позволяет получать секретный ключ всего за пару минут. При этом авторы использовали около 1000 случайных запросов и доказали, что можно использовать всего 255 заранее подготовленных запросов (атака с выбором открытого текста). Более того, атаку можно еще усовершенствовать до 8 приспосабливающихся запросов, что позволяет проводить вскрытие секретного ключа за несколько секунд. Предыдущая известная атака на COMP128 - BGW (Briceno, Goldberg, Wagner - по фамилиям авторов) - требовала примерно 150000 запросов.

Авторы распределенной атаки воспользовались тем фактом, что на первом раунде шифрования используется замена по таблице T0, которая содержит 512 элементов. Т. е. для индексации по ней необходимо использовать 9-битовые значения, в то время как в SIM-карте используется лишь 8-битовая архитектура. Тогда авторы предположили, что таблица должна быть разбита на 2 подтаблицы размером по 256 элементов. Анализируя энергопотребление SIM-карты при различных запросах, исследователи смогли определить, к какой части таблицы T0 был адресован запрос. Таким образом, замеряя энергопотребление запросов при изменении входных данных, им удалось вычислить секретный ключ.

Комбинированные атаки

Атаки по побочным каналам имеют большое многообразие. Как уже упоминалось ранее, можно использовать такие побочные каналы, как время шифрования[1], мощность потребления[2], электромагнитное излучение от шифратора[3,4]. Помимо этого можно использовать яркость света, излучаемого монитором и отраженного от стены[5]. Можно достать секретную информацию даже по звукам, издаваемым внутренними компонентами электронного шифратора[7]. Существуют также различные атаки, которые воздействуют на шифратор и создают в нем ошибки, по которым потом восстанавливается ключ[8,9].

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

Варианты комбинированных атак на COMP128

Распределенная атака на COMP128, разработанная в 2002 году, является простой атакой по потребляемой мощности (SPA). Чтобы улучшить ее результаты, нужно скомбинировать эту атаку с какой-то другой. Рассмотрим атаку по времени (TA), атаку на основе зондирования (PA) и атаку на основе генерируемых ошибок (FIA).

Комбинация с атакой по времени

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

Однако на алгоритм COMP128 такую атаку провести довольно сложно, поскольку в нем используются операции, не подверженные атаке по времени.

Комбинация с атакой на основе зондирования

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

В COMP128 можно наблюдать за последними 16 байтами на каждом из 8-ми раундов, а не только на первом. Это даст выигрыш в скорости в 8 раз.

Комбинация с атакой на основе генерируемых ошибок

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

Аналогично предыдущей атаке, хотелось бы вносить ошибку в начале каждого раунда в последние 16 байт. COMP128 записывает в эти 16 байт перемешанные биты, полученные на предыдущем раунде шифрования. Если бы удалось внести ошибку, которая позволяла бы записывать в последние 16 байт нужные нам значения, то и замеры по потребляемой мощности удалось бы проводить не только на первом раунде шифрования. Например, если бы с каждым раундом в последние 16 байт записывалось значение RAND, увеличенное на 1, то количество необходимых запросов бы сократилось в 8 раз.

Заключение

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

Следует отметить, что противодействие комбинированным side channel атакам состоит в том, чтобы противодействовать составляющим атакам. Это является основным недостатком комбинированных SCA, поскольку сложность защиты от них равна сложности защиты от одной из составляющих атак, причем именно той, которой легче всего противодействовать.

Литература

1.  Paul C. Kocher. Timing attacks on implementations of Diffie-Hellmann, RSA, DSS, and other systems // Advances in Cryptology — CRYPTO '96 : сборник. — Springer, 1996. — С. 104—113 http://www. /public/pdf/TimingAttacks. pdf [дата просмотра: 02.04.2013]

2.  Paul Kocher, Joshua Jaffe, Benjamin Jun. Differential Power Analysis // Proc. of Advances in Cryptology (CRYPTO '99), LNCS : сборник. — 1999 — С. 388—397 http://www. /public/pdf/DPA. pdf [дата просмотра: 02.04.2013]

3.  Jean-Jacques Quisquater and David Samyde. ElectroMagnetic Analysis (EMA): Measures and Counter-measures for Smart Cards // E-SMART '01 Proceedings of the International Conference on Research in Smart Cards: Smart Card Programming and Security : сборник. — Springer-Verlag, 2001 — С. 200—210

4.  Karine Gandolfi, D. Naccache, C. Paar, Karine G. , Christophe Mourtel, Francis Olivier. Electromagnetic Analysis: Concrete Results // Proceedings of the Third International Workshop on Cryptographic Hardware and Embedded Systems : сборник. — Springer-Verlag, 2001. — С. 251—261 http://citeseerx. ist. psu. edu/viewdoc/download? doi=10.1.1.1.5990&rep=rep1&type=pdf [дата просмотра: 02.04.2013]

5.  Kuhn, M. G. Optical time-domain eavesdropping risks of CRT displays // Security and Privacy, 2002. Proceedings. 2002 IEEE Symposium on : сборник. — 2002. — С. 3—18. http://www. cl. cam. ac. uk/~mgk25/ieee02-optical. pdf [дата просмотра: 02.04.2013]

6.  J. Rao, P. Rohatgi, H. Scherzer, S. Tinguely, Partitioning Attack: Or How to Rapidly Clone Some GSM Cards // IEEE Symposium on Security and Privacy — 2002

7.  Adi Shamir, Eran Tromer Acoustic cryptanalysis: On nosy people and noisy machines — 2011 http://tau. ac. il/~tromer/acoustic/ [дата просмотра: 02.04.2013]

8.  D. Boneh, R. A. DeMillo, and R. J. Lipton. On the importance of checking cryptographic protocols for faults // Advances in Cryptology — EUROCRYPT '97 : сборник. — Springer, 1997. — С. 37-51. http://citeseer. ist. psu. edu/viewdoc/download? doi=10.1.1.48.9764&rep=rep1&type=pdf [дата просмотра: 02.04.2013]

9.  Eli Biham and Adi Shamir. Differential Fault Analysis of Secret Key Cryptosystems // Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology (CRYPTO '97) : сборник. — Springer-Verlag, 1997. — С. 513—525.