lord-feistel/power_analysisДоказательство концепции, демонстрирующее атаку по побочному каналу анализа мощности на уязвимую реализацию RSA на Arduino (Atmega328P), с подробным описанием аппаратной установки и методологии измерений.
Недавно я наблюдал, как люди самостоятельно реализуют криптографию для Arduino, как описано в этой теме на Stackoverflow:
https://stackoverflow.com/questions/39189065/rsa-encryption-decryption-functions-for-arduino
Несколько из них можно найти в интернете, некоторые, кстати, находятся в хорошо известных библиотеках.
Я решил сделать эту небольшую PoC (Proof of concept — доказательство концепции), чтобы показать, почему важно не изобретать свой собственный криптографический алгоритм, но также использовать надежную реализацию таких алгоритмов.
Эта PoC выполняет атаку по побочным каналам (атаку по анализу мощности) против плохой реализации вспомогательной процедуры, используемой в реализации RSA (быстрое возведение в степень).
Атака по побочным каналам — это метод компрометации криптографической системы путем использования косвенной утечки информации, а не прямой атаки на сам криптографический алгоритм или протокол.
Такой тип утечки может возникать из различных источников, таких как временная информация, энергопотребление, электромагнитное излучение или даже звук.
Такие атаки могут быть весьма эффективными для компрометации криптографических систем, таких как RSA, не требуя от злоумышленника решения основных математических задач, обеспечивающих безопасность криптографической схемы (Kocher, Jaffe, & Jun, 1999).
В данной статье будет выполнена атака по анализу мощности на широко известную уязвимость в реализации алгоритма RSA в прошивке для Arduino (Atmega328P).
Примечание: я делал это наспех, пожалуйста, простите меня за опечатки / грамматические ошибки, которые вы, возможно, найдете.
Атаки по анализу мощности включают измерение энергопотребления устройства во время криптографических операций.
Дифференциальный анализ мощности (DPA) включает статистический анализ паттернов энергопотребления при нескольких криптографических операциях для извлечения секретов, что делает его более сложным, чем простой анализ мощности (SPA), который напрямую связывает колебания мощности с конкретными криптографическими операциями для вывода секретов.
Дифференциальный анализ мощности (DPA) и простой анализ мощности (SPA) могут использоваться для извлечения закрытых ключей путем анализа паттернов энергопотребления во время вычислений RSA.
Эти атаки могут раскрыть закрытый ключ, выявляя различные паттерны энергопотребления, связанные с различными битами ключа (Kocher, Jaffe, & Jun, 1999).
RSA (Rivest-Shamir-Adleman) — широко используемый алгоритм шифрования с открытым ключом, названный в честь его изобретателей: Рона Ривеста, Ади Шамира и Леонарда Адлемана, которые представили его в 1977 году (Paar & Pelzl, 2010).
Он остается одним из самых безопасных методов для передачи данных через интернет.
Одна из основ безопасности RSA заключается в сложности разложения больших составных чисел на простые множители (Menezes, van Oorschot, & Vanstone, 1996).
Эта проблема, известная как задача факторизации, заключается в нахождении простых чисел, которые при перемножении дают заданное большое число.
Шифрование RSA опирается на предположение, что эта задача факторизации является вычислительно достаточно сложной, чтобы сделать взлом шифрования путем факторизации модуля на простые множители практически невозможным (Menezes, van Oorschot, & Vanstone, 1996).
На Рисунке 1 показан процесс шифрования и дешифрования RSA на простом примере.
Рисунок 1 — Пример RSA.
Обратите внимание, что в данном случае 3 и 33 являются открытыми. Число 7 в примере является закрытым ключом.
Функция Phi(N), функция Эйлера, вычисляет все взаимно простые числа в интервале от 1 до 33.
Значение 33 получается умножением P и Q; в данном случае 11 умножается на 3.
Результат функции Phi получается умножением (P-1) на (Q-1); в данном случае 10 умножается на 2.
Операция e<sup>-1</sup> mod 20 обозначает операцию модульного обратного (Menezes, van Oorschot, & Vanstone, 1996).
Примечание: Если вы хотите глубже изучить RSA, что необязательно для понимания данной статьи, в этом репозитории есть файл number_theory.md с кратким введением в эти основные операции теории чисел. Это объяснение может улучшить ваше понимание работы RSA.
В эксперименте использовался осциллограф DS1102 (представлен на Рисунке 2) производства Rigol.
Руководство пользователя осциллографа можно найти в ссылках (RIGOL Technologies, Inc., 2017).
Также использовался универсальный блок питания (представлен на Рисунке 3).
Рисунок 2 — Осциллограф, использованный в эксперименте.
Рисунок 3 — Блок питания, использованный в эксперименте.
Закон Ома — фундаментальный принцип в области электротехники и физики.
Он гласит, что ток, протекающий через проводник между двумя точками, прямо пропорционален напряжению между этими точками и обратно пропорционален сопротивлению между ними (Boylestad, 2015).
На Рисунке 4 показана схема и закон Ома.
Рисунок 4 — Иллюстрация закона Ома.
Закон Ома подразумевает, что если увеличить напряжение на проводнике, ток также увеличится, при условии, что сопротивление остается постоянным (Johnson & Hilburn, 2013). На Рисунке 5 представлен пример применения закона Ома, целью которого является нахождение тока в цепи.
Рисунок 5 — Пример закона Ома.
Закон напряжения Кирхгофа (ЗНК) — фундаментальный принцип в электротехнике и физике (Boylestad, 2015).
Он гласит, что сумма всех разностей электрических потенциалов (напряжений) в любом замкнутом контуре или петле равна нулю (Boylestad, 2015).
На Рисунке 6 проиллюстрирован закон напряжения Кирхгофа.
Рисунок 6 — Иллюстрация закона Кирхгофа.
На Рисунке 7 приведен пример применения закона Кирхгофа для нахождения тока через резисторы R1 и R2.
Рисунок 7 — Пример закона Кирхгофа.
Делитель напряжения является следствием закона напряжения Кирхгофа (ЗНК) и описывает способ расчета Vout, то есть напряжения между резисторами R1 и R2.
Формула делителя напряжения представлена на Рисунке 8.
Пример применения делителя напряжения показан на Рисунке 9.
Рисунок 8 — Иллюстрация делителя напряжения.
Рисунок 9 — Пример делителя напряжения.
Шунтирующий резистор — это резистор с низким сопротивлением, включаемый последовательно с источником питания цепи для измерения тока, протекающего через цепь.
Использование шунта для измерения тока — одна из техник, применяемых в современных мультиметрах (Boylestad, 2015).
Измеряя падение напряжения на шунтирующем резисторе и зная его сопротивление, можно рассчитать ток по закону Ома.
Для измерения потребляемого тока устройства Arduino необходимо разместить шунтирующий резистор последовательно с VCC (положительный контакт).
Способ подключения показан на Рисунке 10.
Примечание 1: Обратите внимание, что в PoC вместо платы Arduino Uno в качестве цели (микроконтроллер atmega328p) используется отдельная макетная плата, как показано на Рисунке 11. Это позволяет легче манипулировать выводами микроконтроллера без необходимости пайки.
Примечание 2: Если вы не знаете, как это сделать, моя предыдущая статья о том, как работает глитчинг, объясняет это и доступна по адресу https://github.com/lord-feistel/hardware_hacking_lab
Рисунок 10 — Шунт с Arduino.
Рисунок 11 — Схема шунта на макетной плате.
Чтобы продемонстрировать измерение потребления тока с помощью шунтирующего резистора, к GPIO микроконтроллера будет подключен светодиод (Sedra & Smith, 2014) (Рисунок 12), а осциллограф будет использоваться для наблюдения за тем, как это влияет на потребление мощности на шунтирующем резисторе в ситуациях, когда светодиод включен или выключен.
Обратите внимание: для извлечения ключа или наблюдения эффекта нагрузки на потребление мощности не обязательно использовать закон Ома для получения тока, достаточно только падения напряжения (Johnson & Hilburn, 2013).
Рисунок 12 — Измерение мощности.
Чтобы лучше это увидеть, пожалуйста, посмотрите Видео 1, которое показывает, как изменяется падение напряжения при включенном светодиоде.
Видео 1 — Падение напряжения из-за потребления светодиода.
Следующий код использовался для мигания светодиода. Он также находится в этом репозитории.```C const int PIN_CHARGE = 9 ; void setup() { pinMode(PIN_CHARGE, OUTPUT);
}
void loop() {
digitalWrite(PIN_CHARGE, HIGH);
delay(10);
digitalWrite(PIN_CHARGE, LOW);
delay(10);
}
Важно отметить, что это падение напряжения также происходит при выполнении сложных вычислений (Kocher, Jaffe, & Jun, 1999).
Следующий код вызывает падение напряжения, представленное на **Рисунке 13**
``````C
void setup() {
}
void loop() {
volatile unsigned long i = 0;
i = ((i + 1) * (i - 1) + (i * i) - (i / 2) * (i % 3) + (i * i * i * i)) * ((i + 2) * (i - 2) + (i * i) - (i / 3) * (i % 5) + (i * i * i * i));
delayMicroseconds(100);
}
Если падение напряжения отражает вычисления, то его можно использовать для определения обрабатываемых данных.
Рисунок 13 – Потребление энергии при тяжелых вычислениях.
Обычный способ выполнения операции возведения в степень – умножение основания n раз.
Предположим, 23 даст 2*2*2, поскольку 2 – это основание, а 3 – n.
Это работает очень хорошо, но недостаточно эффективно, чтобы сделать RSA реализуемым.
Для достижения такой реализации используется алгоритм быстрого возведения в степень.
Быстрое возведение в степень, также известное как возведение в квадрат, – это эффективный метод возведения числа в степень.
Далее можно найти псевдокод для быстрого возведения в степень.```C
function fast_exponentiation(a, b): result = 1 base = a exponent = b
while exponent > 0:
if (exponent % 2 == 1): // If exponent is odd
result = result * base
base = base * base // Square the base
exponent = exponent // 2 // Divide exponent by 2
return result
.
.
Шаги быстрого возведения в степень числа 2<sup>4</sup> можно найти в **Таблице 1**
| Итерация | Базовое значение | Экспонента в двоичном виде | Операция | Результат |
|----------|-----------------|----------------------------|----------|-----------|
| Начало | 2 | 100 | Старт | 1 |
| 1 | 4 | 010 | Возведение в квадрат | 1 |
| 2 | 16 | 001 | Возведение в квадрат | 1 |
| 3 | 256 | 000 | Умножение | 16 |
| Конец | - | - | Конец | 16 |
**Таблица 1** — Итерации быстрого возведения в степень числа 2<sup>4</sup>.
Далее объясняется процесс:```
- **Initialization:**
Start with base = 2 , exponent = 4 ( binary 100) , result = 1.
- **Iteration 1:** exponent = 4 (binary 100, even)
Square base to get 4 .
result remains 1.
- **Iteration 2:** exponent = 2 (binary 010, even)
Square base to get 16 .
result remains 1.
- **Iteration 3:** exponent = 1 (binary: 001, odd)
Multiply result by a = 16 to get 16.
result becomes 16.
- **Final:** n = 0 (binary: 000)
The loop ends with result = 16.
Note that for smaller numbers nothing change or it will get worser, however for big numbers it obtains a significant achievement in the efficiency.
It reduces the number of multiplicative operations compared to the naive approach, which is particularly useful for large exponents.
Table 2 shows a comparsion of the iterations for such a number using the naive exponentiation and the fast exponentiation.
Fast exponentiation is critical in RSA for both encryption and decryption processes, as these processes involve raising large numbers to large powers modulo some other large number (Paar & Pelzl, 2010).
As presented in the RSA example section the key is the exponent and usualy it will be a very large number.
Table 2 - Comparsion of effiency between conventional exponentiation and fast exponentiation.
An fast exponentiation was implemented in the arduino and uploaded in the atmega328p. As it is a PoC we implemented it in the easiest way to be visualized.
For instance, usually it is utilized shift operation over an integer variable, but we implemented the exponent as an array to be better understood.
Note the exponent representing the key is the array {0, 1, 0, 1, 0, 1, 0, 1} which will create a pattern in the meansure acquired by the osciloscope as a proof of that it works.```C
#include <Arduino.h>
volatile long long dumb_vulnerableExponentiation(volatile long long base, const volatile int* exponentArray, volatile int arrayLength, volatile long long modulo) { volatile long long result = 1; base %= modulo;
for (volatile int i = 0; i < arrayLength; ++i) {
result = (result * result) % modulo;
if (exponentArray[i] == 1) {
result = (result * base) % modulo;
}
}
return result;
}
void setup() { }
void loop() { volatile long long base = 3; volatile long long modulo = 1000000007; const volatile int exponentArray[] = {0, 1, 0, 1, 0, 1, 0, 1}; volatile int arrayLength = sizeof(exponentArray) / sizeof(exponentArray[0]); delay(2); volatile long long result = dumb_vulnerableExponentiation(base, exponentArray, arrayLength, modulo); }
### Результаты
Как было показано в начале, для операций шифрования и дешифрования ключом является экспонента, поэтому, обнаружив экспоненту, ключ RSA оказывается скомпрометирован.
Используя упомянутое ранее оборудование, можно увидеть спектр энергопотребления на осциллографе, как показано на **Figure* 14* и **Рисунок 15**
Периоды, когда напряжение падает на длительное время, означают, что обрабатывается бит `1` ключа, в противном случае — бит `0`.
Обратите внимание, что когда экспонента чётная, выполняется одно дополнительное умножение, что заставляет спад энергии длиться дольше, раскрывая информацию о ключе.
**Видео 2** показывает захват ключа. Чтобы понять, как регулировать период и амплитуду, обратитесь к руководству осциллографа.
**Рисунок 14** - Захват ключа
**Рисунок 15** - Отображение 0 и 1 ключа с помощью осциллографа
[](https://youtu.be/MBZ1abtTN_k)
**Видео 2** - Захват ключа с помощью осциллографа.
Такая атака может быть использована в сценарии, когда микроконтроллер использует известную библиотеку, но прошивка заблокирована, не позволяя злоумышленнику получить ключ напрямую из памяти.
Этот вид атаки также может быть использован против аппаратного обеспечения.
### Заключение
Реализация собственной системы шифрования RSA (Rivest-Shamir-Adleman) крайне не рекомендуется по нескольким критическим причинам, особенно из-за уязвимости к сложным атакам, таким как атаки по анализу энергопотребления.
Шифрование RSA, хотя математически надёжно при правильной реализации, требует тщательного внимания к деталям реализации для обеспечения безопасности.
Даже незначительные ошибки или упущения в реализации могут непреднамеренно раскрыть информацию о закрытом ключе, ставя под угрозу всю безопасность системы.
Кроме того, устоявшиеся криптографические библиотеки и фреймворки проходят тщательную проверку и тестирование со стороны сообщества безопасности, что гарантирует их устойчивость к известным атакам и уязвимостям. Использование этих проверенных библиотек не только экономит время и усилия, но и значительно снижает риск непреднамеренного внесения уязвимостей в систему.
### Ссылки
1. Понимание криптографии - Paar, C., & Pelzl, J. (2010). **Понимание криптографии**. Springer.
2. Справочник по прикладной криптографии - Menezes, A. J., van Oorschot, P. C., & Vanstone, S. A. (1996). **Справочник по прикладной криптографии**. CRC Press.
3. Дифференциальный анализ энергопотребления - Kocher, P., Jaffe, J., & Jun, B. (1999). **Дифференциальный анализ энергопотребления**. Proceedings of CRYPTO '99, Lecture Notes in Computer Science, vol 1666. Springer, Berlin, Heidelberg. DOI: 10.1007/3-540-48405-1_25.
4. Технический паспорт осциллографа DS1102 - RIGOL Technologies, Inc. (2017). **Технический паспорт цифрового осциллографа серий DS1000E, DS1000D**. Получено из [RIGOL Datasheet](https://beyondmeasure.rigoltech.com/acton/attachment/1579/f-03b8/1/-/-/-/-/DS1000E_DS1000D_DataSheet_EN.pdf)
5. Введение в анализ цепей - Boylestad, R. L. (2015). **Введение в анализ цепей** (13-е изд.). Pearson.
6. Основы электрических цепей - Johnson, D., & Hilburn, J. L. (2013). **Основы электрических цепей**. McGraw-Hill Education.
7. Микроэлектронные схемы - Sedra, A. S., & Smith, K. C. (2014). **Микроэлектронные схемы** (7-е изд.). Oxford University Press.
| Exponent (b) | Binary (b) | Conventional Exponentiation Operations | Fast Exponentiation Operations |
|---|
| 1 | 1 | 1 | 1 |
| 2 | 10 | 1 | 1 |
| 4 | 100 | 3 | 2 |
| 8 | 1000 | 7 | 3 |
| 16 | 10000 | 15 | 4 |
| 32 | 100000 | 31 | 5 |
| 64 | 1000000 | 63 | 6 |
| 128 | 10000000 | 127 | 7 |
| 256 | 100000000 | 255 | 8 |
| 512 | 1000000000 | 511 | 9 |
| 1024 | 10000000000 | 1023 | 10 |