Side-channel криптоанализ

Введение

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

«Классический» криптоанализ рассматривает криптографические примитивы с первой точки зрения. Второй подход используется в side-channel («обходной путь») криптоанализе. Side-channel криптоанализ [5] использует особенности реализации, чтобы узнать секретные параметры, используемые в вычислениях. Следовательно, он обладает меньшей общностью — он работает только для заданной реализации, однако, при этом он зачастую значительно более мощный, чем «классический» аналог.

Классификация side-channel атак

Side-channel атаки, обычно классифицируют по двум признакам:

• инвазивные - неинвазивные
• активные - пассивные

инвазивные - неинвазивные атаки

Для инвазивных атак нужен прямой доступ к компьютеру или его компонентам (жучки). Неинвазивные атаки пользуются только информацией доступной извне компьютера (нежелательное, непредусмотренное излучение, например, от power supply или clock).

активные - пассивные атаки

Активные атаки пытаются мешать должному функционированию оборудования ( fault-induction attacks пытаются внести ошибки в вычисления). Пассивные атаки, напротив, просто наблюдают за работой устройства, не нарушая его.

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

Типы side-channel атак

• Probing attacks
• Fault-induction attacks
• Timing attacks
• Power analysis attacks
• Electromagnetic analysis attacks

---

Probing attacks

Инвазивная, пассивная атака. Для получения информации компьютер вскрывается и исследуется каждый провод по которому идут данные, или же с помощью микроскопа исследуется состояние ячеек памяти. Используется оборудование: зондирующая установка, включающая в себя микроскопы (вплоть до ионных и электронных) и микроманипуляторы для установки щупов на поверхности чипа. Порядок стоимости — 10000$. Чтобы упростить наблюдение криптоаналитик обычно замедляет clock. [6],[7]

---

Fault-induction attacks

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

Типы ошибок

Ошибки характеризуются определенными параметрами:

• постоянные — переменные

Постоянные наносят устройству постоянный вред ( «замораживание» ячейки памяти с присвоением ей определенного значения, обрыв провода). Переменные, напротив, меняются со временем (радиактивный обстрел).

• место расположения
• время возникновения

Естественно, имеет смысл на заданную систему наводить только такие ошибки, которые дадут о ней какую-то неизвестную информацию. Таким образом fault-induction криптоанализ распадается на две ветви: первая изучает какие ошибки следует наводить на оборудование, вторая — как эти ошибки наводить на оборудование. Примеры fault-induction криптоанализа: 1) Атака на RSA-систему, использующую китайскую теорему об остатках [8],[9], 2) дифференциальный криптоанализ DES (Biham and Shamir) [10], 3) дифференциальный криптоанализ систем, основанных на эллиптических кривых [11].

---

Timing attacks

Оказывается, для некоторых реализаций криптосистем время исполнения программы реализации может дать информацию о секретных параметрах. При многократном измерении времени отклика системы на разные начальные данные эта информация может оказаться исчерпывающей. Идея впервые была высказана Kocher [12] и впервые применена на практике против системы RSA использующей алгоритм Монтгемери [13]. В [14] описывается timing attack на AES (Rijndael) открывающая ключ за 4000 измерений.

---

---

Power analysis attacks

Дополнительную информацию может дать также и зависимость энергопотребления во время исполнения программы. Например, на рисунке изображена зависимость энергопотребления компьютера, выполняющего шифрование DES. Явно просматриваются (верхняя линия) начальная стадия инициализации, 16 раундов шифрования и завершающая стадия. Более детальный анализ может дать информацию о порядке конкретных операций (нижняя линия — увеличенный фрагмент верхней, отвечающий 2 и 3 раунду). [15]

---

Electromagnetic analysis attacks

Любое движение зарядов вызывает вокруг себя електромагнитное поле. Наблюдение за этим полем может дать достаточную информацию о секретных параметрах системы. Ярким примером этого вида атак является ван Эйковский перехват. [16],[17],[18]

Перехват ван Эйка

В 1985 году вышла статья Вима ван Эйка «Электромагнитное излучение от мониторов: опасность подслушивания» [3]. В этой статье подробно описывается как с помощью оборудования суммарной стоимостью не больше 100 долларов, можно перехватить изображение с монитора с расстояния нескольких десятков метров.

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

Рис.2. Перехват сигналов с электронного оборудования

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

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

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

Рис. 4. Формирование кадра на мониторе.

Если ограничиться рассмотрением ЭЛТ дисплеев, то излученное поле будет содержать две основные компоненты: 1)излучение сигнала синхронизации (внутренних часов clock) 2)излучение видеосигнала Вим ван Эйк обнаружил, что любая спектральная компонента излученного видеосигнала очень напоминает телевизионный сигнал. Это позволило эму восстановить картинку с ЭЛТ монитора с помощью обыкновенного черно-белого телевизора и телевизионной антены.

Дальнейшее развитие этой темы нашло в работах Маркуса Куна ([1],[2]), которому в 2004 году удалось осуществить ван Эйковский перехват для ЖК мониторов, Osama Takizawa, Akihiro Yamamuro ([4]) и многих других.

Злоумышленнику зачастую может оказаться проще подсмотреть секрет пользователя, нежели чем «честно» перехватывать зашифрованные сообщения, искать ключи и т.д. Таким образом, с точки зрения критпографии в цепи защиты информации появляется ещё одно звено — защита от подслушивания, которое вполне может оказаться самым слабым. С точки криптоанализа ван Эйковский перехват представляет неивазивную, пассивную side-channel electromagnetic analysis attack. Из его очевидных достоинств, можно выделить то, что засечь перехват невозможно (он не оставляет следов). Из недостатков же, можно выделить необходимость физической близости к объекту подслушивания и использование дополнительного оборудования.

Пути решения проблемы перехвата.

Проблема перехвата состоит в том, что: 1)цифровое оборудование излучает сильные сигналы 2)злоумышленник знает, как эти сигналы интерпретировать.

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

Источники

• [1 Markus G. Kuhn. Electromagnetic Eavesdropping Risks of Flat-Panel Displays.] (англ.). — Статья о ван Эйковском перехвате для ЖХ мониторов.. Проверено 14 декабря 2008.

• [2 Markus G. Kuhn. Security Limits for Compromising Emanations.] (англ.). — Статья о проблемах безопасности мониторов.. Проверено 14 декабря 2008.

• [3 Wim van Eck. Electromagnetic Radiation from Video Display Units An Eavesdropping Risk.] (англ.). — статья о ван Эйковском перехвате.. Проверено 14 декабря 2008.

• [4 Osama Takizawa, Akihiro Yamamuro. A Trial of the Interception of Display Image using Emanation of Electromagnetic Wave.] (англ.). — статья описывает попытку японских ученых перехватить изображение с ЖК мониторов.. Проверено 14 декабря 2008.

• [5 Jean-Jacques Quisquater, Francois Koeune. Side Channel Attacks.] (англ.). — статья, классифицирующая side-channel атаки.. Проверено 14 декабря 2008.

Ссылки

[6] Anderson, Security engineering, Wiley & Sons, New York, 2001.

[7] Olivier KÄommerling and Markus G. Kuhn, Design principles for tamper-resistant smartcard processors, Proc. of USENIX Workshop on Smartcard Technology (Smartcard '99), 1999.

[8] D. Boneh, R.A. DeMillo, and R.J. Lipton, On the importance of checking cryptographic protocols for faults, Advances in Cryptology — EUROCRYPT '97, Konstanz, Germany (W. Fumy, ed.), LNCS, vol. 1233, Springer, 1997, pp. 37–51.

[9] Marc Joye, Arjen K. Lenstra, and Jean-Jacques Quisquater, Chinese remain-dering based cryptosystems in the presence of faults, Journal of cryptology 12 (1999), no. 4, 241-245.

[10] E. Biham and A. Shamir, Diferential fault analysis of secret key cryptosystems, Proc. Of Advances in Cryptology { Crypto '97 (Berlin) (Burt Kaliski, ed.), vol. 1294, Springer-Verlag, 1997, Lecture Notes in Computer Science Volume 1294, pp. 513–525.

[11] I. Biehl, B. Meyer, and V. Muller, Di®erential fault attacks on elliptic curve cryptosystems, Advances in Cryptology - CRYPTO 2000 (M. Bellare, ed.), Lectures Notes in Computer Science (LNCS), vol. 1880, Springer-Verlag, 2000.

[12] P. Kocher, Timing attacks on implementations of Di±e-Hellman, RSA, DSS, and other systems, Advances in Cryptology - CRYPTO '96, Santa Barbara, California (N. Koblitz, ed.), LNCS, vol. 1109, Springer, 1996, pp. 104–113.

[13] J.-F. Dhem, F. Koeune, P.-A. Leroux, P. Mestr¶e, J.-J. Quisquater, and J.-L. Willems, A practical implementation of the timing attack, Proc. CARDIS 1998, Smart Card Research and Advanced Applications (J.-J. Quisquater and B. Schneier, eds.), LNCS, Springer, 1998.

[14] W. Schindler, J.-J. Quisquater, and F. Koeune, Improving divide and conquer attacks against cryptosystems by better error detection correction strategies, Proc. of 8th IMA International Conference on Cryptography and Coding, December 2001, pp. 245–267.

[15] P. Kocher, Ja®e J., and B. Jub, Di®erential power analysis, Proc. of Advances in Cryptology { CRYPTO '99 (M. Wiener, ed.), LNCS, vol. 1666, Springer-Verlag, 1999, pp. 388–397.

[16] Jean-Jacques Quisquater and David Samyde, A new tool for non-intrusive analysis of smart cards based on electro-magnetic emissions: the SEMA and DEMA methods, Eurocrypt rump session, 2000.

[17] Jean-Jacques Quisquater and David Samyde, Electromagnetic analysis (EMA): measures and countermeasures for smart cards, Smart cards programming and security (e-Smart 2001), Lectures Notes in Computer Science (LNCS), vol. 2140, Springer, 2001, pp. 200–210.

[18] K. Gandol¯, C. Mourtel, and F. Olivier, Electromagnetic analysis: Concrete results, Proc. of Cryptographic Hardware and Embedded Systems (CHES 2001) (C»etin Kaya Ko»c, David Naccache, and Christof Paar, eds.), Lecture Notes in Computer Science, vol. 2162, Springer, 2001, pp. 251–261.