--- tags: Optimization --- # 論文閱讀：Dude, is my code constant time? ::: warning 閱讀此篇論文主要為學習目的，然而由於我對於密碼學/系統領域/統計都不是很擅長(~~直接一點就是我甚麼都不會~~)，文中可能不乏錯誤的解釋或者引用，如果有疑問或者發現問題都歡迎直接告知！ ::: [Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf) ## Abstract 論文中提出了工具**dudect**，可以用來檢測一段程式是否constant time執行。 ## Introduction [Time attack](https://en.wikipedia.org/wiki/Timing_attack)是一種side-channel attacks，攻擊者可以通過分析執行加密算法所花費的時間來嘗試破壞密碼系統。 舉一個簡單的例子: 假如有個比對輸入與密碼的演算法是從第一個字母開始依序比對，如果字母相同則往下比較，直到輸入和真實密碼有差異或者輸入等同密碼之後結束。那麼攻擊者可以透過輸入不同的密碼得到不同的運行時間(假如比對的越久，表示輸入與真實密碼的前面部份相同的越多)，回推真實密碼的長度，這就產生了資安的疑慮。 即使在此篇論文已經有許多的評估工具，如ctgrind、ctverif等。他們的共同的缺點是這些方法針對hardware建立模型必須建模。令一個困難點是，CPU製造商透露關於CPU如何運作的細節總是很些微。也可能受到某些改變(如[micro code](https://en.wikipedia.org/wiki/Microcode))的影響。 因此論文提出了dudect工具，避免了使用[靜態程式分析(static analysis)](https://zh.wikipedia.org/wiki/%E9%9D%9C%E6%85%8B%E7%A8%8B%E5%BA%8F%E5%88%86%E6%9E%90)，而是使用對於時間的統計分析(statistical analysis)。藉此避免測量時間的方法對於硬體的dependency。 ## Timing Leakage Detection 實驗的理論是基於對執行時間的[leakage detection test](https://link.springer.com/chapter/10.1007/3-540-45472-1_12)。透過兩個不同的測資，檢驗其執行時間的distribution是否有顯著的差異。 ### A. Step 1: Measure execution time 首先，反複測量兩個不同"class"的input在加密函式上的執行時間。 a) Classes definition: leakage detection test的類型有數種，其中大多數的差異在於input data classes的定義方式不同。論文中使用比較經典的fix-vs-random leakage detection test，即兩個類型的資料:一種為固定測資、另一種是隨機測資的集合。其中固定的測資被用來觸發某些特殊情況(例如算術運算) b) Cycle counters: 現代的CPU中都有cycle counter可以精準的計算運行時間。在低端處理器中 則可以使用高分辨率計時器，或者使用外部設備。 c) Environmental conditions: 為了最小化運行環境對測試結果的影響，每個測量都對應一個隨機的class ### B. Step 2: Apply post-processing 得到執行時間，在進行統計檢定之前，可以先進行某些處理。 a) Cropping: 對於較長的執行時間，一般的時間分佈都是呈[positive skewed](https://zh.wikipedia.org/wiki/%E5%81%8F%E5%BA%A6)，這可能是由於測量的誤差(measurement artifacts)，主要的測量函式會受到OS或者外部的程式影響。這種情況下，可以裁剪測量值(去除掉大於某個threshold的測量值) ![](https://i.imgur.com/RTkKyrp.png) b) Higher-order preprocessing: 統計檢驗可以透過high-order preprocessing得到更加的分析結果。例如scentered product 、mimicking higher-order DPA attack ::: danger 對這些統計名詞毫無概念，詳細請參閱論文reference ::: ### C. Step 3: Apply statistical test 最後，是透過統計檢驗試圖反證null hypothesis“兩個時間分佈相等”。有幾個可用的檢驗方式: a) t-test: 採用[Welch’s t-test](https://en.wikipedia.org/wiki/Welch%27s_t-test)。當t-test 拒絕假說(無法證明平均值的差異)，表示執行時間為constant time。 :::info :bell: **t-test** 一般提及的t-test又稱為[Student's t-test](https://zh.wikipedia.org/wiki/%E5%AD%B8%E7%94%9Ft%E6%AA%A2%E9%A9%97)，是指當虛無假設成立時，任一檢定統計有[Student's t-distribution](https://zh.wikipedia.org/wiki/%E5%AD%A6%E7%94%9Ft-%E5%88%86%E5%B8%83)的統計假說檢定。 而論文中使用的Welchs t-test則是Student's t-test的修改，其在兩個samples的變異數不同，或者sample大小不同時會來得更加可靠。 ::: b) Non-parametric tests: 可以透過 Non-parametric tests檢驗，例如Kolmogorov-Smirnov。其優點是這些測試通常對於distributions的假設較少;缺點是他們可能收斂較慢，需要更多樣本。 ## Results [tool連結](https://github.com/oreparaz/dudect) 往後是針對不同的案例，透過論文方法驗證是否為constant time的結果。詳細內容請直接參考論文。