lord-feistel/power_analysis취약한 RSA 구현(Arduino Atmega328P)에 대한 전력 분석 부채널 공격을 시연하는 개념 증명과 상세한 하드웨어 설정 및 측정 방법론.
최근에 저는 사람들이 Arduino를 위해 직접 암호화를 구현하는 것을 관찰했습니다. 예를 들어 stackoverflow의 이 주제에서 언급된 것과 같습니다:
https://stackoverflow.com/questions/39189065/rsa-encryption-decryption-functions-for-arduino
그 중 몇 가지는 인터넷에서 찾을 수 있으며, 일부는 잘 알려진 라이브러리에 있습니다.
저는 왜 자신만의 암호화 알고리즘을 발명하지 말아야 하는지, 그리고 그러한 알고리즘의 강력한 구현을 사용하는 것이 중요한지 보여주기 위해 이 작은 PoC (개념 증명)를 수행하기로 결정했습니다.
이 PoC는 RSA 구현에 사용되는 보조 루틴 (빠른 거듭제곱)의 잘못된 구현에 대해 부채널 공격 (전력 분석 공격)을 수행합니다.
부채널 공격은 암호화 알고리즘 또는 프로토콜 자체를 직접 공격하는 대신 간접적인 정보 누출을 이용하여 암호 시스템을 손상시키는 방법입니다.
이러한 누출은 타이밍 정보, 전력 소비, 전자기 방출 또는 소리와 같은 다양한 출처에서 발생할 수 있습니다.
이러한 공격은 RSA와 같은 암호 시스템을 손상시키는 데 매우 효과적일 수 있으며, 공격자가 암호 체계의 보안을 보장하는 기반이 되는 수학적 문제를 해결할 필요가 없습니다 (Kocher, Jaffe, & Jun, 1999).
이 논문은 Arduino (Atmega328P)용 펌웨어에서 RSA 알고리즘 구현의 잘 알려진 취약점에 대한 전력 분석 공격을 수행할 것입니다.
참고: 급하게 작성했기 때문에 발견될 수 있는 맞춤법/문법 오류는 양해 부탁드립니다.
전력 분석 공격은 암호화 작업 중 장치의 전력 소비를 측정하는 것을 포함합니다.
차등 전력 분석 (DPA)은 여러 암호화 작업에 걸친 전력 소비 패턴에 대한 통계적 분석을 통해 비밀을 추출하는 방법으로, 전력 변동을 특정 암호화 작업과 직접적으로 연관시켜 비밀을 추론하는 단순 전력 분석 (SPA)보다 더 정교합니다.
차등 전력 분석 (DPA)과 단순 전력 분석 (SPA)은 RSA 계산 중 전력 소비 패턴을 분석하여 개인 키를 추출하는 데 사용될 수 있습니다.
이러한 공격은 서로 다른 키 비트와 관련된 뚜렷한 전력 사용 패턴을 식별하여 개인 키를 드러낼 수 있습니다 (Kocher, Jaffe, & Jun, 1999).
RSA (Rivest-Shamir-Adleman)는 1977년에 발명자인 Ron Rivest, Adi Shamir, Leonard Adleman의 이름을 딴 널리 사용되는 공개 키 암호화 알고리즘입니다 (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 연산에 대한 이해를 높일 수 있습니다.
실험에는 Rigol에서 제조한 오실로스코프 DS1102 (그림 2에 제시)를 사용했습니다.
오실로스코프의 매뉴얼은 참고문헌에서 찾을 수 있습니다 (RIGOL Technologies, Inc., 2017).
일반 전원 공급 장치도 사용되었습니다 (그림 3에 제시).
그림 2 - 실험에 사용된 오실로스코프.
그림 3 - 실험에 사용된 전원 공급 장치.
옴의 법칙은 전기 공학 및 물리학 분야의 기본 원리입니다.
이는 두 점 사이의 도체를 통해 흐르는 전류가 두 점 사이의 전압에 정비례하고 그 사이의 저항에 반비례한다는 것을 나타냅니다 (Boylestad, 2015).
그림 4는 회로와 옴의 법칙을 보여줍니다.
그림 4 - 옴의 법칙 설명.
옴의 법칙은 저항이 일정하게 유지된다면 도체 양단의 전압을 증가시키면 전류도 증가한다는 것을 의미합니다 (Johnson & Hilburn, 2013). 그림 5는 회로의 전류를 찾는 것이 목표인 옴의 법칙 적용 예를 보여줍니다.
그림 5 - 옴의 법칙 예제.
키르히호프의 전압 법칙 (KVL)은 전기 공학 및 물리학의 기본 원리입니다 (Boylestad, 2015).
이는 모든 폐쇄 네트워크 또는 루프에서 모든 전위차(전압)의 합이 0임을 나타냅니다 (Boylestad, 2015).
그림 6은 키르히호프의 전압 법칙을 설명합니다.
그림 6 - 키르히호프 법칙 설명.
그림 7에는 저항 R1과 R2에 흐르는 전류를 찾기 위한 키르히호프 법칙의 적용 예가 있습니다.
그림 7 - 키르히호프 법칙 예제.
전압 분배기는 키르히호프의 전압 법칙 (KVL)의 결과로, 저항 R1과 R2 사이의 전압인 Vout을 계산하는 방법을 제시합니다.
전압 분배기의 공식은 그림 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 - 브레드보드의 션트 회로.
션트 저항을 사용하여 전류 소비 측정을 시연하기 위해, LED (Sedra & Smith, 2014)를 마이크로컨트롤러의 GPIO에 연결하고 (그림 12), 오실로스코프를 사용하여 LED가 켜지거나 꺼진 상황에서 션트 저항의 전력 소비에 미치는 영향을 관찰합니다.
키를 추출하거나 전력 소비에 대한 충전 효과를 관찰하기 위해 전류를 얻기 위해 옴의 법칙을 사용할 필요는 없으며, 전압 강하만으로도 충분합니다 (Johnson & Hilburn, 2013).
그림 12 - 전력 측정.
자세히 관찰하려면 LED가 켜졌을 때 전압 강하가 어떻게 되는지 보여주는 비디오 1을 확인하십시오.
비디오 1 - LED 소비로 인한 전압 강하.
LED를 깜박이기 위해 다음 코드가 사용되었습니다. 이 코드는 이 저장소에서도 찾을 수 있습니다.```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 - 무거운 계산 시 전력 소비.
거듭제곱 연산을 수행하는 전통적인 방법은 밑(base)을 n번 곱하는 것입니다.
23을 예로 들면, 2가 밑이고 3이 n이므로 2*2*2가 됩니다.
이는 매우 잘 작동하지만, RSA를 실현할 만큼 효율적이지는 않습니다.
이러한 구현을 위해 빠른 거듭제곱(fast exponentiation) 알고리즘이 사용됩니다.
빠른 거듭제곱(제곱에 의한 지수법)은 숫자를 거듭제곱하는 효율적인 방법입니다.
다음에서 빠른 거듭제곱에 대한 의사 코드를 찾을 수 있습니다.```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.
작은 숫자의 경우에는 변화가 없거나 오히려 나빠질 수 있지만, 큰 숫자의 경우 효율성이 크게 향상됩니다.
이는 단순한 방식에 비해 곱셈 연산 횟수를 줄여주며, 특히 큰 지수에 유용합니다.
표 2는 단순 지수 연산과 고속 지수 연산을 사용한 그러한 숫자의 반복 횟수를 비교한 것입니다.
고속 지수 연산은 RSA의 암호화 및 복호화 과정 모두에서 중요합니다. 이 과정들은 큰 숫자를 다른 큰 숫자 모듈로 큰 거듭제곱으로 올리는 것을 포함하기 때문입니다 (Paar & Pelzl, 2010).
RSA 예제 섹션에서 살펴본 바와 같이, 키는 지수이며 일반적으로 매우 큰 숫자입니다.
표 2 - 일반적인 지수 연산과 고속 지수 연산의 효율성 비교.
고속 지수 연산이 Arduino에 구현되어 Atmega328p에 업로드되었습니다. PoC이므로 시각화하기 가장 쉬운 방식으로 구현했습니다.
예를 들어, 일반적으로 정수 변수에 대한 시프트 연산을 사용하지만, 더 이해하기 쉽도록 지수를 배열로 구현했습니다.
키를 나타내는 지수는 배열 {0, 1, 0, 1, 0, 1, 0, 1} 이며, 이는 오실로스코프로 측정한 값에 패턴을 생성하여 작동한다는 증거가 됩니다.```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); }
### 결과
암호화 및 복호화 연산에서 키는 지수(exponent)이며, 따라서 지수를 발견하면 RSA 키가 노출된다는 점을 앞서 설명했습니다.
앞서 언급한 하드웨어를 사용하면 오실로스코프에서 전력 소비 스펙트럼을 볼 수 있으며, 이는 **그림 14**와 **그림 15**에 나와 있습니다.
전압이 오랫동안 떨어지는 구간은 키의 비트 `1`이 처리되고 있음을 의미하며, 그렇지 않은 경우는 비트 `0`입니다.
지수가 짝수일 때는 추가 곱셈이 한 번 더 발생하여 에너지 강하 시간이 길어져 키 정보가 노출된다는 점에 유의하십시오.
**비디오 2**는 키 캡처 과정을 보여줍니다. 주기와 진폭을 조정하는 방법을 이해하려면 오실로스코프 매뉴얼을 참조하십시오.
**그림 14** - 키 캡처
**그림 15** - 오실로스코프를 사용하여 키의 0과 1 노출
[](https://youtu.be/MBZ1abtTN_k)
**비디오 2** - 오실로스코프로 키 캡처
이러한 공격은 마이크로컨트롤러가 잘 알려진 라이브러리를 사용하는 시나리오에서 사용될 수 있지만, 펌웨어가 잠겨 있어 공격자가 메모리에서 직접 키를 얻을 수 없는 경우에도 가능합니다.
이러한 공격은 하드웨어에 대해서도 사용될 수 있습니다.
### 결론
자체 RSA(Rivest-Shamir-Adleman) 암호화 시스템을 구현하는 것은 여러 중요한 이유, 특히 전력 분석 공격과 같은 강력한 공격에 취약하기 때문에 매우 권장되지 않습니다.
RSA 암호화는 올바르게 구현될 경우 수학적으로 강력하지만, 보안을 보장하려면 구현 시 세부 사항에 세심한 주의가 필요합니다.
사소한 구현 결함이나 실수라도 의도치 않게 개인 키에 관한 정보를 유출하여 시스템의 전체 보안을 손상시킬 수 있습니다.
또한, 확립된 암호화 라이브러리와 프레임워크는 보안 커뮤니티의 엄격한 검토와 테스트를 거쳐 알려진 공격과 취약점에 대한 복원력을 보장합니다. 이러한 검증된 라이브러리를 사용하면 시간과 노력을 절약할 뿐만 아니라 실수로 시스템에 취약점을 도입할 위험을 크게 줄일 수 있습니다.
### 참고 문헌
1. Understanding Cryptography - Paar, C., & Pelzl, J. (2010). **Understanding Cryptography**. Springer.
2. Handbook of Applied Cryptography - Menezes, A. J., van Oorschot, P. C., & Vanstone, S. A. (1996). **Handbook of Applied Cryptography**. CRC Press.
3. Differential Power Analysis - Kocher, P., Jaffe, J., & Jun, B. (1999). **Differential Power Analysis**. Proceedings of CRYPTO '99, Lecture Notes in Computer Science, vol 1666. Springer, Berlin, Heidelberg. DOI: 10.1007/3-540-48405-1_25.
4. DS1102 Oscilloscope Datasheet - RIGOL Technologies, Inc. (2017). **DS1000E, DS1000D Series Digital Oscilloscope Datasheet**. 에서 검색됨: [RIGOL Datasheet](https://beyondmeasure.rigoltech.com/acton/attachment/1579/f-03b8/1/-/-/-/-/DS1000E_DS1000D_DataSheet_EN.pdf)
5. Introductory Circuit Analysis - Boylestad, R. L. (2015). **Introductory Circuit Analysis** (13th ed.). Pearson.
6. Fundamentals of Electrical Circuits - Johnson, D., & Hilburn, J. L. (2013). **Fundamentals of Electrical Circuits**. McGraw-Hill Education.
7. Microelectronic Circuits - Sedra, A. S., & Smith, K. C. (2014). **Microelectronic Circuits** (7th ed.). 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 |