lord-feistel/power_analysisArduino（Atmega328P）上の脆弱なRSA実装に対する電力解析サイドチャネル攻撃を実証する概念実証であり、詳細なハードウェアセットアップと測定手法を含む。
最近、Stackoverflowのこのトピックのように、Arduino用の暗号を自作している人を目にしました：
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年に発表されました（Paar & Pelzl, 2010）。
これは、インターネット上でデータを安全に送信するための最も安全な方法の1つであり続けています。
RSAのセキュリティの基盤の1つは、大きな合成数をその素因数に分解することの難しさにあります（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 - 実験で使用した電源。
オームの法則は、電気工学と物理学の分野における基本原則です。
これは、2点間の導体を流れる電流は、2点間の電圧に比例し、それらの間の抵抗に反比例することを述べています（Boylestad, 2015）。
図4は、回路とオームの法則を示しています。
図4 - オームの法則の図解。
オームの法則は、導体の両端の電圧を上げると、抵抗が一定であれば電流も増加することを意味します（Johnson & Hilburn, 2013）。図5は、回路の電流を求めることを目的としたオームの法則の適用例を示しています。
図5 - オームの法則の例。
キルヒホッフの電圧則（KVL）は、電気工学と物理学における基本原則です（Boylestad, 2015）。
これは、任意の閉じたネットワークまたはループにおけるすべての電位差（電圧）の総和がゼロであると述べています（Boylestad, 2015）。
図6は、キルヒホッフの電圧則を図解しています。
図6 - キルヒホッフの法則の図解。
図7に、抵抗R1とR2にかかる電流を求めるためのキルヒホッフの法則の適用例を示します。
図7 - キルヒホッフの法則の例。
分圧器はキルヒホッフの電圧則（KVL）の結果であり、抵抗R1とR2の間の電圧であるVoutを計算する方法を示します。
分圧器の公式は図8に示されています。
分圧器の適用例は図9に示されています。
図8 - 分圧器の図解。
図9 - 分圧器の例。
シャント抵抗は、回路の電源と直列に配置される低抵抗値の抵抗で、回路に流れる電流を測定するために使用されます。
シャントを使用して電流を測定することは、現代のマルチメータで使用される技術の1つです（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 - 電力測定。
よりよく観察するには、ビデオ1をご覧ください。LEDがオンのときの電圧降下を示しています。
ビデオ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 - 重い計算における消費電力。
べき乗演算の従来の方法は、基数を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進数） | 操作 | 結果 |
|-----------|--------------|----------------------------|-----------|---------------------------|
| 初期 | 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); }
### 結果
暗号化および復号化操作において、鍵は指数であるため、指数を発見することでRSA鍵が露呈します。先述のハードウェアを用いると、**図14**および**図15**に示すように、オシロスコープで消費電力のスペクトルを観測できます。
電圧が長時間降下する期間は、鍵のビット`1`が処理されていることを意味し、そうでなければビット`0`です。なお、指数が偶数の場合、追加の乗算が1回発生するため、エネルギー降下が長くなり、鍵情報が露呈しやすくなります。
**ビデオ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**. Retrieved from [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.
| 指数 (b) | 2進数 (b) | 従来のべき乗計算の演算数 | 高速べき乗計算の演算数 |
|---|
| 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 |