# 2019q1 Homework3 (review)
contributed by <`Shengyuu`>

## 2019q1 第 3 週測驗題（上） 測驗 1
### 題目：

考慮到 memecmp 一種實作如下：

#include <stdint.h>
#include <stddef.h>
int memcmp(const uint8_t *m1, const uint8_t *m2, size_t n) {
    for (size_t i = 0; i < n; ++i ) {
        int diff = m1[i] - m2[i];
        if (diff != 0) return (diff < 0) ? -1 : +1;
    }
    return 0;
}

為了避免承受 information leakage 的風險，將上述程式碼的迴圈數固定，且避免使用 conditional branching 一類指令，從而避免 side-channel attack

#include <stdint.h>
#include <stddef.h>
int memcmp(const uint8_t *m1, const uint8_t *m2, size_t n) {
    for (size_t i = 0; i < n; ++i ) {
        int diff = m1[i] - m2[i];
        if (diff != 0) return (diff < 0) ? -1 : +1;
    }
    return 0;
}

### 題目解析：
在原始的程式碼中

for (size_t i = 0; i < n; ++i ) {
    int diff = m1[i] - m2[i];
    if (diff != 0) return (diff < 0) ? -1 : +1;
}

會將字串 `m1`, `m2` 從第一個字元開始逐一比較，只要發現一個字元不一樣，程式就會終止並回傳比較結果。
這樣的作法會導致每次程式執行的時間不相同，當輸入字串 `m2` 從 `m2[0]` 開始有越多的連續字元和 `m1` 相等，程式執行的時間就會越長，導致 information leakage 。
[Linux Programmer's Manual](http://man7.org/linux/man-pages/man3/memcmp.3.html)也有提到相關問題
>Do not use memcmp() to compare security critical data, such as cryptographic secrets, because the required CPU time depends on the number of equal bytes. Instead, a function that performs comparisons in constant time is required.
>
另外，conditional branch 也同樣會有 information leakage 的風險，所以新版的 memcmp 把用到 conditional bracnch 的地方都替換掉。
### 解題思路：

程式碼的前三行是變數宣告的部份

const uint8_t *pm1 = (const uint8_t *) m1 + n;
const uint8_t *pm2 = (const uint8_t *) m2 + n;
int res = 0;

其中變數 `pm1` 、 `pm2` 用來紀錄字串 `m1`、`m2` 最後一個字元的位置，也因為用來紀錄字串，所以變數型態宣告為 `uint8_t`

在第三個變數宣告的地方卡了一下，看不懂 `res` 是什麼單字的英文縮寫，無法猜測這個變數是拿來做什麼的，但可以發現 `return` 的部份只跟 `res` 這個變數有關，所以先來看看 `return` 的部份

return ((res - 1) >> 8) + (res >> 8) + 1;

又題目告訴我們此段程式碼是由 `(res > 0) - (res < 0)` 替換過來的，我們可以先從替換前的程式碼來探究 `res` 這個變數再做什麼，以下是推論

- res > 0
`return 1`
- res < 0
`return -1`
- res == 0
`return 0`
由上面的推論以及原始版 `memcmp` 的邏輯可以得知，當 `m1`、`m2` 字串相等時，`res` 的值必須為 `0` ， 將 `m1` 和 `m2` 第一個不一樣的字元做相減，如果相減的值大於 `0` 則 `res > 0` ，反之

了解變數所代表的含意後再來看看程式主要的 `while` 回圈

if (n) {
do {
int diff = *--pm1 - *--pm2;
res = (res & ((X & ~diff) >> 8)) | Y;
} while (pm1 != m1);
}

在這裡可以看到終止條件是當 `pm1 == m1` 的時候，每次迴圈都會做 `--pm1` 的動作，所以在字串比較中若 `n` 相同，所執行的迴圈數會相同，這裡改善了原始版 `memcmp` 可能執行不同次數迴圈的缺陷

最後來看看題目問的 `X`、`Y` 所在的程式碼

res = (res & ((X & ~diff) >> 8)) | Y;

我們已經知道當 `m1`、`m2` 字串全等的時候 `res` 的值會是 `0` ，由這點可以推測 `Y` 的值一定要是 `diff` 或 `0` ，然而 `Y` 如果是 `0` 就沒有寫的意義了，所以我們大膽推測 `Y` 的答案就是 `diff` 。

再來我們看看 `X` 的選項，這裡我們可以把 `0`、`diff`、`1` 都刪除，前兩者經過運算之後的值一定都是 `0` ，而後者經運算之後就相當於 `~diff` ，這三者在程式碼中都沒有存在的意義所以直接刪除，最後剩下 `diff + 1`、`diff - 1` 兩個選項，也是這題最困難的部份。

---

#### 解析 `res`

為了探究 `X` 的值，我們需要對 `res` 有透徹的了解。還記得整個函式的目的是為了判斷 `m1`、`m2` 是否相等，若不相等則要判斷 `m1`、`m2` 離字首最近不相等的字元的大小關係，所以當字串不相等時，`res` 這個變數要紀錄的應該是離字首最近的相異字元的大小關係。

而字串檢查的順序是從最後一個字元開始檢查，因此每次的迴圈若發現 `m1`、`m2` 的字元不相等，這時候我們就該改變 `res` 的值，否則就保留。

當 `diff` 的值為非 `0` 的時候

(res & ((X & ~diff) >> 8))

的值為 `0` ，使得

res = Y;

`diff` 的最大值為 `255` ，`(diff + 1 & ~diff) >> 8` 的值有可能不是 `0` ，可推出 `X = diff - 1`

###### tags: `Linux 核心設計 2019`