論文閱讀：Dude, is my code constant time?

論文連結
dudect Github

Introduction

Side-channel attack 是一種利用系統實作上的特性，而不是用密碼學演算法本身的攻擊，其中 Timing attacks 是其中一種很常見的手法，可以透過演算法的執行時間進而破解，舉例來說，一個判斷密碼是否正確的算法是從第一個字母開始逐一比對，一遇到不一樣的就馬上返回錯誤，那我們就可以透過多次嘗試，並觀察時間來判斷輸入是否正確。

現今也有一些評估的工具了，像是 Valgrind 的延伸 ctgrind，還有 ctverif 透過靜態的程式分析，但是有一些共同的缺陷是這些方法需要對硬體建模，但是困難的是 CPU 製造商通常不會給太多細節的資訊。

這篇論文的貢獻是，透過自己開發的 dudect，一個透過統計分析的程式判斷程式是否是 constant-time 在給定的平台之下。與其他工具透過靜態分析的手法不同，dudect 是透過 timing leakeage detection tests 對執行時間的統計分析，就可以避開底層硬體的限制，不侷限某特定 CPU 硬體平台。

A. Step 1: Measure execution time

• a) Classes definition:
  • 給定兩種不同類別的輸入資料，重複對方法進行測量，最常見的就是 fix-vs-random tests
  • 第一種資料是固定一個常數的值，第二種資料則是每次測量都隨機產生。
  • 第一種資料通常會給定一個特別的值，來觸發 corner-case(such as low-weight for arithmetic operations)
• b) Cycle counters:
  • 現今的 CPU 提供的 cycle counters 可以很精準的獲得執行的時間。
• c) Environmental conditions:
  • 為了減少環境的差異，每次測量都會對應隨機的輸入值分類。

B. Step 2: Apply post-processing

在統計分析之前需要做一些後處理。

• a) Cropping:
  • 典型的時間分布會呈現正偏態(positive skew)，可能是 OS 或是外部活動導致測量誤差(measurement artifacts)，可以透過裁減(crop)掉一些超過 threshold 的測量結果。
    
  • b) Higher-order preprocessing:
    • 統計測試可以透過 high-order preprocessing 得到更加的分析結果。例如 centered product 、mimicking higher-order DPA attacks。

C. Step 3: Apply statistical test

運用統計學試著推翻虛無假說 (null hypothesis)，這邊的虛無假說就是「兩個時間分布是相同的」，底下參考 WeiCheng14159。

• Hypothesis Testing 簡介：
  • Null hypothesis (H0) 是我們想要測定的假說
  • Alternative hypothesis (H1) 是 H0 的反面
  • 結果的判定：
    • Reject Null Hypothesis 代表我們在統計上有足夠的證據，證明 H0 是錯的，故 H1 是對的
    • Fail to reject Null Hypothesis 代表在統計上沒有足夠的證據，證明 H0 是錯的
• a) t-test:
  • 一個很簡單方便實作的是 Welch’s t-test，這個統計測試兩個平均數是否相同，
• b) Non-parametric tests:(無母數統計分析)
  • 一個很常見的方法是 Kolmogorov-Smirnov，好處是其依賴比較少關於底層分布的假設，缺點是可能收斂的比較慢或是需要更多樣本。
• Welch’s t-test
  • 先簡介 Student's t-test 就是抽樣下的常態分佈，常用來比較兩組樣本的平均值是否有差異。
  • Welch's t-test 則是在兩個樣本的變異數不相等的情況下會更加的準確。
  • 定義：
    • ${\mu }_1$：class 1 真正的執行時間的平均值（未知）
    • ${\mu }_2$：class 2 真正的執行時間的平均值（未知）
    • ${\sigma }_1$：class 1 採樣的執行時間的標準差（已知）
    • ${\sigma }_2$：class 2 採樣的執行時間的標準差（已知）
    • $n_1$：class 1 的樣本數（已知）
    • $n_2$：class 2 的樣本數（已知）
    • ${\overline{x}}_1$：class 1 採樣的的執行時間的平均值（已知）
    • ${\overline{x}}_2$：class 2 採樣的的執行時間的平均值（已知）
    • $H_0$：
      ${\mu }_1-{\mu }_2=0$ 假設class 1 和class 2 的平均執行時間相等，亦為 『兩個 class 的執行時間分佈是相同的』
    • $H_1$：
      ${\mu }_1-{\mu }_2\ne 0$ 假設class 1 和class 2 的平均執行時間並不相等，亦為 『兩個 class 的執行時間分佈是不同的』
  • 計算檢定統計量
    $t=\frac{{\overline{x}}_1-{\overline{x}}_2}{\sqrt{\frac{{\sigma }_1^2}{n_1}+\frac{{\sigma }_2^2}{n_2}}}$
    • $t$ 越接近 0 代表兩組數據的差異越小
    • lab0 實作上只有到這裡，然後直接檢查
      $t$ 是否大於 t_threshold_moderate

實作細節

lab0-c 的 Welch’s test 測試項目有兩個:

• is_insert_tail_const(): 用來測試將字串加到 Queue 尾端的執行時間是否能在常數時間完成。
• is_size_const(): 用來測試取得 Queue 大小時間是否能在常數時間完成。

每個測項又細分兩個階段:

• Pre-processing: 主要測量待測物 (給定的程式碼) 的執行時間 (CPU cycle)，其步驟如下:
  • 兩種產生 Queue 方式 (即對照 Welch’s Test 所需兩組取樣資料):
    • Queue 大小 = 0
      $\to$ 論文提及的 fix class
    • Queue 大小 = n (隨機產生)，並插入 n 個相同的隨機字串至 Queue 開頭 (字串長度=7bytes, 加上結束字元 '\0' 則為 8bytes)
      $\to$ 論文提及的 random class
• 執行待測物 (is_insert_tail_const() 或 is_size_const())，並記錄執行時間 (CPU cycles)
• Statistical test: 將所記錄的CPU執行時間 (CPU cycles) 套用如下 Welch’s test 公式，用以計算t value。可對照 lab0-c 原始碼的 t_push() 與 t_compute()。其所計算得出 t value 就可用來判斷測試項目是否在常數時間完成。

在 fixture.c 當中可以看到，最後會根據 t 值大小來判定是否為 constant time。

/* threshold values for Welch's t-test */
#define t_threshold_bananas                                                  \
    500                         /* Test failed with overwhelming probability \
                                 */
#define t_threshold_moderate 10 /* Test failed */

if (max_t > t_threshold_bananas) {
    return false;
} else if (max_t > t_threshold_moderate) {
    return false;
} else { /* max_t < t_threshold_moderate */
    return true;
}