模闆攻擊 - 天天看點

模闆攻擊是一種強大的側信道攻擊。它是“模組化類”攻擊(profiling attack)的一種，所謂模組化類攻擊，是指攻擊者會在目标裝置的同類型裝置或者其複制品上建立一個"profile"，随後利用這一"profile"快速恢複目标裝置的密鑰。

相較于CPA，模闆攻擊對攻擊者的要求更高。攻擊者需要對目标裝置的複制品具有完全的控制權，并且進行大量的前期工作以建立模闆，不過，一旦模闆建立，攻擊者能夠以很小的代價完成攻擊。在模闆足夠好的情況下（如模組化所用的能量迹數量足夠大），攻擊者僅需一條能量迹即可恢複密鑰。（下文中以“曲線”一詞替代“能量迹”）

模闆攻擊分為以下四步：

利用一個可以完全控制的目标裝置的複制品，使用不同的輸入（明文和密鑰）進行計算并采集曲線，確定采集的曲線足夠提供給攻擊者每一種密鑰猜測對應的資訊
建立模闆，模闆是一種POIs(points of interest)的多元分布
在目标裝置上，使用少量的不同明文加密擷取相應的曲線（目标裝置的密鑰不受攻擊者控制）
利用模闆進行攻擊，找到最可能正确的密鑰猜測值

本文譯自http://wiki.newae.com/Template_Attacks

信号、噪聲和統計學

開始讨論模闆攻擊的細節前，了解其涉及的統計學概念是非常重要的。所謂模闆就是一種描述曲線上關鍵點的多元分布。這一部分就是介紹何為多元分布以及它是如何在側信道這一背景下使用的。

噪聲分布

電信号是内在的噪聲。無論何時我們進行電壓測量，我們都不會看到一個完美、恒定的結果。例如，如果我們把萬用表接到一個5V的電源上并進行4次測量，得到的結果更可能是類似于(4.95、5.01、5.06、4.98)這樣，可以考慮用如下方式對這一電壓模組化:

\[\boldsymbol{X} = X_{actual}+\boldsymbol{N}

其中，\(X_{actual}\)代表無噪聲的電壓測量，\(\boldsymbol{N}\)代表額外的噪聲。在上面的例子中，\(X_{actual}\)為5V。\(\boldsymbol{N}\)為随機變量，每次測量的結果都不同。注：\(\boldsymbol{N}、\boldsymbol{X}\)加粗表示它們是随機變量。

高斯分布(即正态分布)是一種可以用來描述這些随機變量的模型。高斯分布的機率密度函數(PDF)是：

\[f(x) = \frac{1}{\sigma \sqrt{2 \pi}}e^{-(x-\mu)^2/2\sigma^2}

其中, \(\mu\)表示平均值、\(\sigma\)表示标準差。如在上面的例子中，如果均值為5，标準差為0.5，那麼它對應的機率密度函數為

我們可以利用機率密度函數來評估一個測量值出現的可能性，如：

由此可見，測量結果為7V的機率是極小的。我們将這一特點應用在模闆攻擊中，如果某一個密鑰猜測對應的機率密度值較小，那它極有可能是錯誤的。

多元統計

上面的例子告訴我們，對于一個值的測量來講一進制高斯分布能夠有很好的表現，但如果我們需要同時處理多個随機變量呢？

假設我們正在測量兩個夾雜着噪聲的電壓源，記為\(\boldsymbol{X}、 \boldsymbol{Y}\)，其中，\(\boldsymbol{X}\)符合正态分布，\(\boldsymbol{Y}\)符合另一種分布。然而，這不一定是有效的。如果二者遵循不同的分布，，那我們則認為這二者是獨立的，即當\(\boldsymbol{X}\)發生變化時，\(\boldsymbol{Y}\)不一定會随之變化。

多元分布能夠幫助我們對相關或不相關的多個随機變量進行模組化。在多元分布中，不再使用方差，而是使用一個協方差矩陣。例如，對三個随機變量(\(\boldsymbol{X}, \boldsymbol{Y}, \boldsymbol{Z}\))模組化，該協方差矩陣為：

相應地，這種分布要求每一個随機變量都有一個平均值：

多元分布的機率密度函數要更複雜一些：不再使用單個數作為參數，而是使用一個包含全部變量的向量\(\boldsymbol{x}=[x, y, z,...]^T\)。k個随機變量的機率密度函數為：

如果覺得這個公式太複雜了，不用擔心，python中的scipy科學計算包已經給我們提供了底層的實作。上一部分中我們将單個值輸入機率密度函數得到了對應的測量出現的可能性。換句話說，隻要将曲線上的點(POIs)放入\(\boldsymbol{x}\)中進行計算，那麼\(f(x)\)就能告訴我們這一密鑰猜測正确的可能性了。

建立模闆

模闆是多個機率分布的集合，每個機率分布描述了一個密鑰可能對應的曲線的樣子。也可以這麼說：“如果你使用了密鑰\(k\)，那麼你的能量曲線會符合\(f_k(\boldsymbol{x})\)。”利用這一性質，我們就可以區分能量曲線之間的細微不同，并作出準确的密鑰猜測。

曲線數量

模闆攻擊的一大缺點就在于在開始攻擊前攻擊者需要收集大量的曲線用于模組化階段。這是因為要對每一個可能的密鑰都能得到一個好的模型，就需要對每個可能的密鑰都收集足夠多的曲線用以模組化。例如，如果要攻擊AES-128的子密鑰（一次S盒操作用到的一個位元組），就需要對0-255這256個可能的值分别模組化。是以，往往我們需要上萬的曲線才能在模組化階段有一個好的結果。

當然，如果我們不對每個可能的密鑰值模組化，而是對密鑰的漢明重量模組化，同樣在AES-128的情況下，隻需要0-8共9個模型即可，需要的曲線數量大大減少。不過，這樣做缺點也很明顯，不再能使用單條曲線即可恢複密鑰，還需要一些其他的資訊。

Points of Interest

我們的目标是建立多元機率分布來描述每一個可能的密鑰對應的曲線。如果我們用這種方式對整個曲線(如有3000個點)模組化，那麼就需要一個3000維的分布。這是很誇張的，是以我們需要一種更好的方式來替代它。好消息是，并不是曲線上的每一個點對我們都有用，原因如下：

每個時鐘周期可能會取樣多次。是以我們可以從一個适當的點擷取大量的資訊而無需處理曲線上所有的點
私鑰不一定會影響整條曲線，它可能隻影響曲線的一些關鍵部位。找出這些部位，我們就可以舍棄掉無關的點

這兩點意味着我們可以從曲線中選擇最重要的3-5個點作為POIs(points of interest)，如果我們可以選出這些點，那麼就可以使用一個3維到5維的分布來描述曲線，相較于3000維這是一個非常大的提升。

如何選擇POIs

有很多種選擇POIs的方法，主要目标是找到在操作數不同(不同的密鑰或漢明重量)的曲線上差異較大的點。這裡介紹最簡單的方法--內插補點求和。

對于每一個操作數\(k\)對應的曲線上的第\(i\)個點求平均值\(M_{k,i}\)，例如當我們采集到使用密鑰\(k\)進行加密的\(T_k\)條曲線後，就會有\(M_{k,i} = \frac{1}{T_k}\sum_{j=1}^{T_k}{t_{j,i}}\)
求得每個\(k\)的均值後，兩兩作差，并對這些內插補點求和。這将會得到一條有尖峰的曲線（如下圖），尖峰處即為上面提到的差異大的點。計算方式為\(D_i = \sum_{k_1, k_2} |M_{k_1, i}, M_{k_2, i}|\)

尖峰位置即為重要的點，但考慮到上一部分中的第一條，相鄰很近的尖峰我們需要舍棄一部分。下面這個算法可以幫我們選擇最終的POIs：
- 選擇最高的尖峰，并将其索引選為一個POI
- 舍棄最近的N個點(N為POIs之間的最小距離)
- 重複前面兩個步驟直至選取足夠的POIs

分析資料

假設我們已經确定了I個POIs，記為\(s_i,(0<=i<I)\)。那麼我們下面的任務就是為每一個候選的子密鑰或者中間值的漢明權重求得一個均值和一個協方差矩陣，設共有K個候選項。

對一個單獨的候選項\(k\)而言，步驟如下：

擷取\(k\)對應的所有曲線，共\(T_k\)條，則\(t_{j，s_i}\)表示第\(j\)條曲線第\(s_i\) 個POI的值
計算每個POI的值的均值\(\mu_i\)

\[\mu_i = \frac{1}{T_k}\sum_{j=1}^{T_k}t_{j, s_i}

\]
計算每個POI的值的方差\(v_i\)

\[v_i = \frac{1}{T_k}\sum_{j=1}^{T_k}(t_{j, s_i}-\mu_i)^2

\]
計算每一個POI點對(\(i、i^*\))的協方差\(c_{i,i^*}\)

\[c_{i,i^*}=\frac{1}{T_k}\sum_{j=1}^{T_k}(t_{j, s_i}-\mu_i)(t_{j,s_i^*}-\mu_i^*)

\]
得到均值向量和協方差矩陣

模闆攻擊

模闆攻擊

對每個\(k\)都執行一遍上述操作，我們就完成了對\(K\)個候選者的模組化工作

使用模闆

模組化完成後，就可以開始進行攻擊了。完成攻擊需要若幹條曲線，設該值為\(A\)，那麼\(a_{j,s_i}，（1<=j<=A）\)就表示第\(j\)條曲線的第\(i\)個POI的值。

應用模闆

首先我們嘗試将上一節中建立的模闆應用在單條曲線上，目标是得到所有密鑰猜測的可能性。

将POIs的值放入向量，得到

模闆攻擊
計算每個密鑰猜測的機率密度函數(PDF)：\(p_{k,j} = f_k(a_j)\)
對每一條曲線重複上述步驟

這部分操作得到一系列的\(p_{k,j}\)，代表第\(j\)條曲線表示的候選者是\(k\)的機率

組合結果

最後一步就是根據所有的\(p_{k,j}\)判斷哪個密鑰猜測更可能是最終的答案。最簡單的方法就是：

\[P_k = \prod_{j=1}^Ap_{k,j}

例如，如果我們的一個密鑰猜測為0x00，并且三條曲線對應的機率密度為(0.9, 0.95, 0.8)，那麼計算結果會是0.684。隻要有一條曲線不符合模闆，就會使得最終值迅速下降，這非常有助于我們消除錯誤選項。最終，我們選擇\(P_k\)值最高的\(k\)作為攻擊結果。

這種将每條曲線的結果直接組合起來的方法容易出現精度問題。将很多數相乘後，最終得到的結果可能超出了浮點數的表示範圍，造成精度問題。一個非常簡單的解決方法就是使用對數。使用如下方法：

\[\log{P_k} = \sum_{j=1}^{A}\log{p_{k,j}}

代替直接計算\(P_k\)，使用對數結果即可作出正确且不存在精度問題的結論。