# Linux 核心專題: dudect 研究和擴充
> 執行人: Mike1117
> [解說錄影](https://youtu.be/QM3bxolsHss)
### Reviewed by `rota1001`
下方在解讀 t-test 的結果中，使用「落在 1 以下」與「落在 1-2 之間」來描述結果，然而 t 值的大小單獨來看是沒有意義的，你是以什麼自由度與什麼顯著水準下在解讀這個結果的？
#### Reply by `Mike1117`
在 `dudect` 的設計中，`t_compute()` 僅回傳 `t-value` 本身，並未進一步查表取得 p-value，也未使用自由度進行傳統意義下的假設檢定：
```c
static double t_compute(ttest_ctx_t *ctx) {
double var[2] = {0.0, 0.0};
var[0] = ctx->m2[0] / (ctx->n[0] - 1);
var[1] = ctx->m2[1] / (ctx->n[1] - 1);
double num = (ctx->mean[0] - ctx->mean[1]);
double den = sqrt(var[0] / ctx->n[0] + var[1] / ctx->n[1]);
double t_value = num / den;
return t_value;
}
```
此外，論文中亦提及：
>A t value larger than 4.5 provides strong statistical evidence that the distributions are different.
可見作者採用的是經驗性門檻，而非傳統的顯著水準 $α$ 。
而在原實作中，`report()` 函式內也直接以 t 值門檻進行判斷：
```c
// threshold values for Welch's t-test
#define t_threshold_bananas 500 // test failed, with overwhelming probability
#define t_threshold_moderate \
10 // test failed. Pankaj likes 4.5 but let's be more lenient
...
static dudect_state_t report(dudect_ctx_t *ctx) {
...
if (max_t > t_threshold_bananas) {
printf(" Definitely not constant time.\n");
return DUDECT_LEAKAGE_FOUND;
}
if (max_t > t_threshold_moderate) {
printf(" Probably not constant time.\n");
return DUDECT_LEAKAGE_FOUND;
}
if (max_t < t_threshold_moderate) {
printf(" For the moment, maybe constant time.\n");
}
return DUDECT_NO_LEAKAGE_EVIDENCE_YET;
}
```
此處的門檻 `10` 較論文中的 `4.5` 更為寬鬆，以求更保守的判斷。
由此可見，`dudect` 採用的是非傳統統計檢定的流程，不基於某一自由度對應的臨界值，而是直接依據 t 值是否超過門檻來判斷 timing distribution 是否顯著不同，即是否有 Time leakage 的發生，故我此處直接以「落在 1 以下」與「落在 1-2 之間」來描述結果。
作者直接計算並比較 t 值，省略自由度的計算及查表取得 p-value 的步驟，我認為其考量有以下幾點：
- `dudect` 檢測時通常涉及極大的樣本數(數萬至數十萬次測量)，當樣本數非常大時， t-distribution 會收斂於標準常態分佈。對於一個遠離中心點的 t 值（如上述提及的門檻 4.5 或 10），其對應的 p-value 會趨近於零，遠小於任何傳統的顯著水準（如 0.05 或 0.01）。因此，額外計算精確的 p-value 並無實質意義，直接比較 t 值本身更為高效。
- 簡化檢測邏輯與加速測試。
### Reviewed by `fcu-D0812998`
dudect 檢測結果是否會被 CPU cache 和 branch prediction 的雜訊影響？如果會，該如何避免。
#### Reply by `Mike1117`
`dudect` 不對底層硬體進行建模，所以勢必會被 CPU cache 和 branch prediction 的雜訊所影響。
但同時， `dudect` 的每輪量測都會至少收集 10000 筆以上的資料，
根據中央極限定理，在如此大量的資料量下，隨機雜訊會被平均化，最終資料會趨近於常態分佈，如此會稀釋 CPU cache 和 branch prediction 等雜訊的影響。
此外，`dudect` 會對原始資料和多個 percentile 裁剪後數據（以及二階 centered-product 資料）分別執行 t-test，這會進一步降低極端 outlier 的干擾，從而輸出較為穩定的結果。
## 任務簡述
重新研讀〈[Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)〉論文，並運用 [lab0-c](https://github.com/sysprog21/lab0-c) 給定的程式碼探討常數時間偵測的議題，隨後從 Linux 核心選出若干應為常數時間的程式碼 (如密碼學，需要適度改寫)，應用 dudect 來檢測是否屬於常數時間的實作。
## 重新研讀〈[Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)〉論文
> 詳實紀錄你的認知和疑惑，務必誠實面對自己
在完全理解這篇論文之前，需要先具備以下提及的先備知識
### 假說檢定 Hypothesis Testing
假說檢定是推論統計中用於檢定現有資料是否足以支持特定假設的方法。
欲檢定統計上假設的正確性的為虛無假說(Null hypothesis，記為 $H_0$ )
- 對母體參數提出一個主張，假設此主張為真實
而相對於虛無假說的其他有關母數之論述是對立假說(Alternative hypothesis，記為 $H_a$ 或 $H_1$ )。
- 對立假設是相對於虛無假說所提出的另一個不同（相反）的假設或主張，必須有足夠的證據，才能說明此主張為真。
一個簡單的例子便是我們在法庭上，會預先假設被告為**無罪**(此為虛無假說 $H_0$ )，而檢察官需要提供足夠的證據來證明被告**有罪**(此為對立假說 $H_1$ )，若證據不足，那法官便會判被告無罪(但實際上不一定**無罪**，僅是證據不足)。
### T-test
>一般情況下所說的 T-test 指的便是由 William Sealy Gosset 以 Student 為筆名所提出的 Student's t-test ，而 Welch’s t-test 則是由 Bernard Lewis Welch 所提出的基於 Student's t-test 的一種變體 t-test 。
#### Student's t-test
由 William Sealy Gosset 於 1908 年提出的運用假設檢定評估一個或兩個母體平均數的工具。
t-test 可能會用於：
1. 評估一個群組是否偏離已知值 (One-sample t-test)
2. 兩個群組是否彼此不同 (Two-sample t-test)
3. 配對測量值是否有顯著差異 (The Paired t-test)。
| 類型 | 單樣本 t 檢定 (One-sample t-test) | 兩樣本 t 檢定 (Two-sample t-test) | 成對 t 檢定 (Paired t-test) |
|--------------|------------------------------------|-----------------------------------|-----------------------------|
| 變數數量 | 一 | 二 | 二 |
| 變數類型 | 連續測量資料 | 連續測量資料 + 群組類別變數 | 連續測量資料 + 配對群組變數 |
| 檢定目的 | 決定母體平均數是否等於特定值 | 決定兩個不同群組的母體平均數是否相等 | 決定配對測量的平均差是否為 0 |
| 範例 | 一群人的平均心率是否等於 65 | 兩群人的平均心率是否相等 | 一群人在運動前後的心率差是否為 0 |
| 母體平均數估計值 | 樣本平均數 | 各群組的樣本平均數 | 配對差異的樣本平均數 |
| 母體標準差 | 未知，使用樣本標準差 | 未知，使用各群組樣本標準差 | 未知，使用配對差異樣本標準差 |
| 自由度 | n – 1 | n₁ + n₂ – 2 | n – 1 |
#### Welch’s t-test
Student's t-test 的一種變體， Student's t-test 要求 Two sample t-test 時兩樣本之變異數要相同，
而 Welch’s t-test 則不要求變異數相等，因此在實務上更穩健，更為泛用。
其公式如下：
$$
t = \frac{\bar{X}_1 - \bar{X}_2}{\sqrt{\frac{s_1^2}{N_1} + \frac{s_2^2}{N_2}}}
$$
其中：
- $\bar{X}_1, \bar{X}_2$ 為兩組樣本的平均值
- $s_1, s_2$ 為樣本標準差
- $N_1, N_2$ 為樣本數
從這個公式我們可以看出，$t$ 值會隨著兩組樣本平均值 $\bar{X}_1$ 與 $\bar{X}_2$ 之間的差距增加而變大；同時，若樣本標準差 $s_1, s_2$ 增加或樣本數 $N_1, N_2$ 減少 ，則分母會變大，導致 $t$ 值變小。
這反映出 Welch's t-test 在比較平均數時，會同時考慮變異程度與樣本規模的影響。
### Fix vs. Random Testing
`Leakage detection` 方法的一種，最早由 Gilbert Goodwill 等人於論文 `A testing methodology for side channel resistance validation` 中提出，是一種將輸入資料的型態分成固定和隨機兩組，並使用統計檢定來判定這兩組資料所產生的輸出是否有顯著差異的方法。
### 論文本身
本篇論文基於以上提及的理論基礎，提出了一個簡單、小巧且無需依賴硬體建模的方法檢測某段程式碼能否在指定平台上以常數時間執行的工具，其過程如下：
1. 將輸入資料分為 Fix 以及 Random 兩組，分別進行時間量測。
2. 以第一輪的資料作為劃分 percentile 的依據。
3. 每次量測完後，依資料的分組更新平均數、平方差總和以及樣本數。
- 原實作設定之 `NUMBER_PERCENTILES` 為 100 ，故每次需更新
- 原始
- 依 percentile 劃分的 100 組
- 當樣本 > 10000 筆時，額外做的二階（centered-square）測試
- 共 102 組資料
4. 計算每次量測完後不同組別的 t 值，若量測次數不足則繼續量測，否則則以 t 值為依據檢查是否有洩露發生。
Reference:
1. [維基百科 - 假說檢定](https://zh.wikipedia.org/zh-tw/%E5%81%87%E8%AA%AA%E6%AA%A2%E5%AE%9A)
2. [JMP 統計知識入口 - t 檢定介紹](https://www.jmp.com/zh-hant/statistics-knowledge-portal/t-test)
3. [Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)
4. [國立臺北大學統計學教材 - 第十章：t 檢定](https://web.ntpu.edu.tw/~wtp/statpdf/Ch_10.pdf)
## 運用 [lab0-c](https://github.com/sysprog21/lab0-c) 給定的程式碼探討常數時間偵測的議題
> 解說為何之前會有偵測的疑慮，又如何運用統計學來分析
### 為什麼要做多次 T-test
```c
static void update_statistics(dudect_ctx_t *ctx) {
for (size_t i = 10 /* discard the first few measurements */; i < (ctx->config->number_measurements-1); i++) {
int64_t difference = ctx->exec_times[i];
if (difference < 0) {
continue; // the cpu cycle counter overflowed, just throw away the measurement
}
// t-test on the execution time
t_push(ctx->ttest_ctxs[0], difference, ctx->classes[i]);
// t-test on cropped execution times, for several cropping thresholds.
for (size_t crop_index = 0; crop_index < DUDECT_NUMBER_PERCENTILES; crop_index++) {
if (difference < ctx->percentiles[crop_index]) {
t_push(ctx->ttest_ctxs[crop_index + 1], difference, ctx->classes[i]);
}
}
// second-order test (only if we have more than 10000 measurements).
// Centered product pre-processing.
if (ctx->ttest_ctxs[0]->n[0] > 10000) {
double centered = (double)difference - ctx->ttest_ctxs[0]->mean[ctx->classes[i]];
t_push(ctx->ttest_ctxs[1 + DUDECT_NUMBER_PERCENTILES], centered * centered, ctx->classes[i]);
}
}
}
```
可以看到在原始實作中，共將 difference(執行時間) push 進了三種不同的組別，分別為：
1. 原始未經任何處理的 difference ， 被 push 進 `ctx->ttest_ctxs[0]`
2. 經由 100 組 percentile 篩選過的 difference ，若 difference 比當前所處的 percentile 大，則直接捨棄，否則 push 進 `ctx->ttest_ctxs[對應 percentile]`
3. 若當前量測的資料數已足夠，則計算 `centered-square` ，將其 `centered-square` push 進 `ctx->ttest_ctxs[101]`
最後會再計算三組共 102 筆資料的 t 值，檢測是否有 Leakage 發生。
那麼既然已經檢查了原始兩組比對的 t 值，為何還要再分為後面兩組再比對 t 值呢？
先從第二組 percentile 開始看起，
percentiles 意為 `百分位數`，參考[維基百科](https://zh.wikipedia.org/zh-tw/%E7%99%BE%E5%88%86%E4%BD%8D%E6%95%B0)：
>若將一組數據從小到大排序，並計算相應的累計百分點，則某百分點所對應數據的值，就稱為這百分點的百分位數。
而在原始實作中， percentile 是這樣決定的：
```c
#define DUDECT_NUMBER_PERCENTILES (100)
...
static int64_t percentile(int64_t *a_sorted, double which, size_t size) {
size_t array_position = (size_t)((double)size * (double)which);
assert(array_position < size);
return a_sorted[array_position];
}
static void prepare_percentiles(dudect_ctx_t *ctx) {
qsort(ctx->exec_times, ctx->config->number_measurements, sizeof(int64_t), (int (*)(const void *, const void *))cmp);
for (size_t i = 0; i < DUDECT_NUMBER_PERCENTILES; i++) {
ctx->percentiles[i] = percentile(
ctx->exec_times, 1 - (pow(0.5, 10 * (double)(i + 1) / DUDECT_NUMBER_PERCENTILES)),
ctx->config->number_measurements);
}
}
...
if (first_time) {
// throw away the first batch of measurements.
// this helps warming things up.
prepare_percentiles(ctx);
}
```
可以看到在執行完第一次量測後，會呼叫 `prepare_percentiles(ctx)` 來劃分 percentile 。
`prepare_percentiles` 會先將第一次量測的資料根據執行時間由小到大進行排序，並以
公式 $p_i = 1 - \left(0.5\right)^{\frac{10(i + 1)}{N}}$ 計算目前應的百分位數，最後呼叫 `percentile` 計算百分位數對應的 index ，取出當前百分位數對應的具體執行時間。
根據公式，0 - 100 組的分位點會如下所示：
可以看到分位點主要集中在 80 - 100 % 的範圍內，論文中提及：
>The upper tail may be more influenced by data-independent noise.
大多數的執行時間都會受到系統等因素的影響，進而導致拉長執行時間，最後造成肥尾分布( Fat-tailed distribution )，如果按照傳統線性切分 percentile ，就會導致在較前的百分位捨棄太多筆數的資料，進而導致結果的不穩定，所以作者此處選擇靠後的百分位數切分。
而以經不同 percentile 裁切後的資料做 t-test 是為了縮小離群值所帶來的影響，讓 t-test 更專注在非離群值的細小差異上。
第三組資料則是以 $(t_{執行時間} - μ_{平均執行時間})^2$ 來進行 t-test ，因為兩組資料可能在平均執行時間上沒有顯著差異，但可能在離散程度上存在差異，這個值可以很好的表現資料本身的離散程度。
回到問題本身，為什麼要做多次 t-test？我覺得主要有以下幾個原因：
1. 資料本身包含過多的雜訊，需要通過一定的 crop 來讓實際執行時間上的差異更顯著、更能被 t-test 所捕捉。
2. 兩組資料的平均值可能相同，但離散程度可能存在差異，需要將離散程度也列入考量。
### 修正 lab0 中的錯誤實作
在重新研讀論文以及 lab0-c 給定的程式碼後，我發現 lab0-c 的 dudect 部分有實作上的錯誤。
可以看到位於 `dudect/constant.c` 以及 `lab0-c/dudect/fixture.c` 中的兩個函式 `measure()` 以及 `update_statistics()`，
這兩個函式的作用分別為對特定函式量測其執行所需要的 CPU cycles 以及利用計算出的 CPU cycles 更新 t-test context 。
具體程式碼如下：
```c=
bool measure(int64_t *before_ticks,
int64_t *after_ticks,
uint8_t *input_data,
int mode)
{
assert(mode == DUT(insert_head) || mode == DUT(insert_tail) ||
mode == DUT(remove_head) || mode == DUT(remove_tail));
switch (mode) {
case DUT(insert_head):
for (size_t i = DROP_SIZE; i < N_MEASURES - DROP_SIZE; i++) {
...
before_ticks[i] = cpucycles();
dut_insert_head(s, 1);
after_ticks[i] = cpucycles();
...
}
break;
case DUT(insert_tail):
for (size_t i = DROP_SIZE; i < N_MEASURES - DROP_SIZE; i++) {
...
}
break;
case DUT(remove_head):
for (size_t i = DROP_SIZE; i < N_MEASURES - DROP_SIZE; i++) {
...
}
break;
case DUT(remove_tail):
for (size_t i = DROP_SIZE; i < N_MEASURES - DROP_SIZE; i++) {
...
}
break;
default:
for (size_t i = DROP_SIZE; i < N_MEASURES - DROP_SIZE; i++) {
...
}
}
return true;
}
static void update_statistics(const int64_t *exec_times,
uint8_t *classes,
int64_t *percentiles)
{
for (size_t i = 0; i < N_MEASURES; i++) {
int64_t difference = exec_times[i];
/* CPU cycle counter overflowed or dropped measurement */
if (difference <= 0)
continue;
/* do a t-test on the execution time */
t_push(ctxs[0], difference, classes[i]);
/* t-test on cropped execution times, for several cropping thresholds.
*/
for (size_t j = 0; j < NUM_PERCENTILES; j++) {
if (difference < percentiles[j]) {
t_push(ctxs[j + 1], difference, classes[i]);
}
}
}
}
```
可以看到，每次 `measure()` 都會將函式執行前後的 CPU cycles 存入 `before_ticks[i]` 以及 `after_ticks[i]` ，`i` 的範圍為 `DROP_SIZE` ~ `N_MEASURES - DROP_SIZE - 1`
這邊有必要釐清
- `N_MEASURES`： 根據註解，為 `Number of measurements per test`
- `DROP_SIZE`： `constant.h` 中並未給出具體定義，但根據原實作及論文，可以知道這是每次量測後需丟棄的資料大小
為什麼要丟棄一部分資料？根據原實作的註解及論文推測：
> /* discard the first few measurements */
此處丟棄的為開始量測後的數筆頭部資料，是為了排除系統處於 `warm-up` 階段時量測到的可能含有雜訊的資料。
故不難推斷 `DROP_SIZE` 同樣是為了定義需要丟棄的資料大小，不過相較於原實作只丟棄頭部資料， `lab0-c` 中的實作設計為還會丟棄尾部的資料。
而現有實作的缺陷非常明顯，正常實作的流程應為：
- 量測 → 在 `update_statistics` 時丟棄頭尾部資料
而目前 `lab0-c` 的實作為：
- 在量測時跳過前 `DROP_SIZE` 個 index ，開始量測後直接將資料存入 `DROP_SIZE` ~ `N_MEASURES - DROP_SIZE` → 在 `update_statistics` 時卻存取 `10 ~ N_MEASURES`
此舉頗有刻舟求劍的意味，很明顯是錯誤的實作，在 `update_statistics` 中加入 Debug 訊息，將 `exec_times[i]` 印出後會如下所示：
```c
i = 10 | class = 1 | exec_time = 0
i = 11 | class = 1 | exec_time = 0
...
i = 18 | class = 0 | exec_time = 0
i = 19 | class = 1 | exec_time = 0
i = 20 | class = 0 | exec_time = 1178
i = 21 | class = 1 | exec_time = 1140
i = 22 | class = 1 | exec_time = 1064
...
i = 127 | class = 1 | exec_time = 1064
i = 128 | class = 0 | exec_time = 1102
i = 129 | class = 1 | exec_time = 1064
i = 130 | class = 0 | exec_time = 0
i = 131 | class = 1 | exec_time = 0
...
i = 149 | class = 0 | exec_time = 0
```
可以看到不管是頭部亦或是尾部，都會有很多未經量測，`exec_time = 0` 的資料。
根據前述提及 `Welch’s t-test` 的公式，這些 `zero-filled` 的資料經 `update_statistics` 更新 `ctxs` 後，會導致平均數 $\bar{X}_1$, $\bar{X}_2$ 的減小，以及 $s_1^2$, $s_2^2$ 的增大，兩者都會導致 t 值變小，進而可能導致 `dudect` 的 Time Leakage 偵測失敗。
故應該做如下修改：
- 首先將每個量測 case 的 for 迴圈都作修改，使它們可以進行完整的量測：
```diff
- for (size_t i = DROP_SIZE; i < N_MEASURES - DROP_SIZE; i++) {
+ for (size_t i = 0; i < N_MEASURES; i++) {
```
- 更新 `update_statistics` ，使其可以正確丟棄頭/尾的量測資料：
```diff
- for (size_t i = 0; i < N_MEASURES; i++) {
+ for (size_t i = DROP_SIZE; i < N_MEASURES - DROP_SIZE; i++) {
```
如此即可完整量測資料，並在 `update_statistics` 時正確丟棄頭尾的資料。
也已提交對應的 [Pull requests](https://github.com/sysprog21/lab0-c/pull/296)
## 檢驗 Linux 核心部分常數時間的實作
> 從 Linux 核心選出若干應為常數時間的程式碼 (如密碼學，需要適度改寫)，應用 dudect 來檢測是否屬於常數時間的實作
### crypto_memneq
[原函數](https://github.com/torvalds/linux/blob/67a993863163cb88b1b68974c31b0d84ece4293e/lib/crypto/memneq.c#L67)如下：
```c
static inline unsigned long
__crypto_memneq_generic(const void *a, const void *b, size_t size)
{
unsigned long neq = 0;
#if defined(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS)
while (size >= sizeof(unsigned long)) {
neq |= get_unaligned((unsigned long *)a) ^
get_unaligned((unsigned long *)b);
OPTIMIZER_HIDE_VAR(neq);
a += sizeof(unsigned long);
b += sizeof(unsigned long);
size -= sizeof(unsigned long);
}
#endif /* CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS */
while (size > 0) {
neq |= *(unsigned char *)a ^ *(unsigned char *)b;
OPTIMIZER_HIDE_VAR(neq);
a += 1;
b += 1;
size -= 1;
}
return neq;
}
```
` __crypto_memneq_generic() `是於 Linux 核心中用來進行 constant-time 比較的一個實作。
主要目的是：在比較兩段記憶體是否相等時，不讓比較過程因為出現分支或資料相關而過早 return ，可以避免被 side-channel attack（例如 timing attack）觀察到敏感資訊。
於此將其改寫為如下形式：
```c
unsigned long __crypto_memneq_generic(const void *a, const void *b, size_t size) {
unsigned long neq = 0;
while (size > 0) {
neq |= *(unsigned char *)a ^ *(unsigned char *)b;
OPTIMIZER_HIDE_VAR(neq);
a += 1;
b += 1;
size -= 1;
}
return neq;
}
measurement part:
crypto_memneq_generic(a, fixed, CHUNK_SIZE);
```
此版本直接採用 `byte-by-byte` 的實作，先定義一固定的記憶體區塊 `fixed` ，在 measure 時會以隨機或固定的兩個 class 與 fixed 進行比對，即：
- crypto_memneq_generic(random-class, fixed, CHUNK_SIZE)
- crypto_memneq_generic(fixed-class, fixed, CHUNK_SIZE)
最終結果如下：
```c
...
measure: 0.01 M, max t: +1.18, max tau: 1.10e-02, (5/tau)^2: 2.07e+05.
measure: 0.01 M, max t: +1.30, max tau: 1.20e-02, (5/tau)^2: 1.74e+05.
measure: 0.01 M, max t: +1.25, max tau: 1.15e-02, (5/tau)^2: 1.88e+05.
measure: 0.01 M, max t: +1.26, max tau: 1.15e-02, (5/tau)^2: 1.88e+05.
measure: 0.01 M, max t: +1.27, max tau: 1.15e-02, (5/tau)^2: 1.88e+05.
measure: 0.01 M, max t: +1.24, max tau: 1.12e-02, (5/tau)^2: 1.98e+05.
Probably constant time
```
可以看到經過多輪 measurements 後， t 值均落在 1 - 2 之間，明顯為 constant time 的實作。
### sha256_block_generic
[原函式](https://github.com/torvalds/linux/blob/master/lib/crypto/sha256-generic.c#L72)如下：
```c
static void sha256_block_generic(u32 state[SHA256_STATE_WORDS],
const u8 *input, u32 W[64])
{
u32 a, b, c, d, e, f, g, h;
int i;
/* load the input */
for (i = 0; i < 16; i += 8) {
LOAD_OP(i + 0, W, input);
LOAD_OP(i + 1, W, input);
LOAD_OP(i + 2, W, input);
LOAD_OP(i + 3, W, input);
LOAD_OP(i + 4, W, input);
LOAD_OP(i + 5, W, input);
LOAD_OP(i + 6, W, input);
LOAD_OP(i + 7, W, input);
}
/* now blend */
for (i = 16; i < 64; i += 8) {
BLEND_OP(i + 0, W);
BLEND_OP(i + 1, W);
BLEND_OP(i + 2, W);
BLEND_OP(i + 3, W);
BLEND_OP(i + 4, W);
BLEND_OP(i + 5, W);
BLEND_OP(i + 6, W);
BLEND_OP(i + 7, W);
}
/* load the state into our registers */
a = state[0]; b = state[1]; c = state[2]; d = state[3];
e = state[4]; f = state[5]; g = state[6]; h = state[7];
/* now iterate */
for (i = 0; i < 64; i += 8) {
SHA256_ROUND(i + 0, a, b, c, d, e, f, g, h);
SHA256_ROUND(i + 1, h, a, b, c, d, e, f, g);
SHA256_ROUND(i + 2, g, h, a, b, c, d, e, f);
SHA256_ROUND(i + 3, f, g, h, a, b, c, d, e);
SHA256_ROUND(i + 4, e, f, g, h, a, b, c, d);
SHA256_ROUND(i + 5, d, e, f, g, h, a, b, c);
SHA256_ROUND(i + 6, c, d, e, f, g, h, a, b);
SHA256_ROUND(i + 7, b, c, d, e, f, g, h, a);
}
state[0] += a; state[1] += b; state[2] += c; state[3] += d;
state[4] += e; state[5] += f; state[6] += g; state[7] += h;
}
```
此函式是 SHA-256 (Secure Hash Algorithm 256-bit) 密碼學雜湊演算法的核心組成部分。其主要作用是實現該演算法所定義的壓縮函式。
在 SHA-256 演算法的 Merkle–Damgård 架構下，任意長度的輸入訊息會先經過預處理（填補與長度附加），然後被分割成一連串 512 bits（64 Bytes）的訊息區塊。`sha256_block_generic` 的職責就是對單一的 512 bit block 進行處理，將其資訊安全地壓縮並混入一個 256 位元的內部狀態中。
如果這個函式不是 Constant time ，會導致 SHA-256 的實作變為 Not constant time ，進而導致 side-channel attacking 。
將該函式引入 dudect 並補齊相關巨集進行測試，結果如下：
```c
...
measure: 0.01 M, max t: +0.06, max tau: 5.85e-04, (5/tau)^2: 7.32e+07.
measure: 0.01 M, max t: +0.24, max tau: 2.30e-03, (5/tau)^2: 4.71e+06.
measure: 0.01 M, max t: +0.36, max tau: 3.36e-03, (5/tau)^2: 2.21e+06.
measure: 0.01 M, max t: +0.41, max tau: 3.79e-03, (5/tau)^2: 1.74e+06.
measure: 0.01 M, max t: +0.59, max tau: 5.47e-03, (5/tau)^2: 8.36e+05.
measure: 0.01 M, max t: +0.43, max tau: 4.00e-03, (5/tau)^2: 1.56e+06.
measure: 0.01 M, max t: +0.48, max tau: 4.42e-03, (5/tau)^2: 1.28e+06.
measure: 0.01 M, max t: +0.44, max tau: 3.96e-03, (5/tau)^2: 1.60e+06.
measure: 0.01 M, max t: +0.40, max tau: 3.58e-03, (5/tau)^2: 1.95e+06.
Probably constant time
```
可以看到經過多輪 measurements 後， t 值均落在 1 以下，可以佐證其為 constant time 的實作。
Sign in with Wallet
Connect another wallet