# 2019q1 第 3 週測驗題 (上) :::info 目的: 檢驗學員對 C 程式設計的認知 ::: --- ### 測驗 `1` 考慮到 [memcmp](http://man7.org/linux/man-pages/man3/memcmp.3.html) 一種實作如下: (行為和 ISO C90 有出入) ```clike #include <stdint.h> #include <stddef.h> int memcmp(const uint8_t *m1, const uint8_t *m1, 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](https://en.wikipedia.org/wiki/Information_leakage) 的風險,於是著手避免使用 conditional branching 一類的指令,從而避免 [side-channel attack](https://en.wikipedia.org/wiki/Side-channel_attack)。 為了避免 conditional branch 指令的出現,我們可將 `(res > 0) - (res < 0)` 替換為 `((res - 1) >> 8) + (res >> 8) + 1`。隨後我們實作下方功能等價但避免 branch 的 `memcmp`: ```clike #include <stdint.h> #include <stddef.h> int cst_memcmp(const void *m1, const void *m2, size_t n) { const uint8_t *pm1 = (const uint8_t *) m1 + n; const uint8_t *pm2 = (const uint8_t *) m2 + n; int res = 0; if (n) { do { int diff = *--pm1 - *--pm2; res = (res & ((X & ~diff) >> 8)) | Y; } while (pm1 != m1); } return ((res - 1) >> 8) + (res >> 8) + 1; } ``` 注意: 在 Linux 核心內部的實作方式可見: * [[PATCH] crypto_memcmp: add constant-time memcmp](https://www.spinics.net/lists/linux-crypto/msg09542.html) * [Re: [PATCH] crypto_memcmp: add constant-time memcmp](https://www.spinics.net/lists/linux-crypto/msg09551.html) 請補完程式碼。 ==作答區== X = ? * `(a)` diff * `(b)` (diff + 1) * `(c)` (diff - 1) * `(d)` 1 * `(e)` 0 Y = ? * `(a)` diff * `(b)` (diff + 1) * `(c)` (diff - 1) * `(d)` 1 * `(e)` 0 :::success 延伸問題: 1. 解釋上述程式的原理,需要從機率統計的觀點分析; * 為何不能用事先計算好的表格呢? (提示: cache 的影響) * 如何驗證程式正確以及 constant-time 呢? 3. 研讀下方論文並解說: * [Remote timing attacks are practical](https://crypto.stanford.edu/~dabo/abstracts/ssl-timing.html) * [A Lesson In Timing Attacks (or, Don't use MessageDigest.isEquals)](http://codahale.com/a-lesson-in-timing-attacks/) 4. 在 Linux 核心找到這類 constant-time 的操作程式碼,予以解說和設計實驗; ::: --- ### 測驗 `2` 考慮以下計算平方根的程式: ```clike #include <stdint.h> /* The algorithm uses the property that computing x² is trivial compared to * sqrt. It will search the biggest x so that x² <= v, assuming we compute * sqrt(v). */ int32_t sqrt_I2I(int32_t v) { uint32_t r = v; // r = v - x² uint32_t b = 0x40000000; // a² uint32_t q = 0; // 2ax while (b > 0) { uint32_t t = q + b; // t = 2ax + a² q >>= 1; // if a' = a/2, then q' = q/2 if (r >= t) { // if (v - x²) >= 2ax + a² r -= t; // r' = (v - x²) - (2ax + a²) q += b; // if x' = (x + a) then ax' = ax + a², // thus q' = q' + b } b >>= 2; // if a' = a/2, then b' = b / 4 } return q; } ``` 該函式利用 (x + a)^2^ = x^2^ + 2ax + a^2^ 漸進找出平方根。不過上面的程式僅能處理整數,我們引入 [fixed point](http://www-inst.eecs.berkeley.edu/~cs61c/sp06/handout/fixedpt.html) 來表達浮點數,改寫程式碼如下: ```clike /* A fixed point is a 32 bit value with the comma between * the bits 15 and 16, where bit 0 is the less significant bit of the value. * FIXME: Larger numbers might cause overflow and rounding error. */ typedef int32_t fixed; fixed sqrt_I2F(int32_t v) { if (!v) return 0; uint32_t r = v; uint32_t b = 0x40000000; uint32_t q = 0; while (b > 0) { uint32_t t = q + b; if (r >= t) { r -= t, q = t + b; } Q; } if (r >= q) ++q; return q; } ``` 請補完程式。 ==作答區== Q = ? * `(a)` b >>= 2 * `(b)` r >>= 1 * `(c)` r <<= 1 * `(d)` b >>= 1 * `(e)` b <<= 1 * `(f)` r >>= 1, b <<= 1 * `(g)` r <<= 1, b >>= 1 :::success 延伸問題: 1. 解釋上述程式碼運作原理,並找出類似的開放原始碼程式; 2. 上述 `sqrt_I2F` 函式存在 overflow 風險,請提出修正方案並驗證; ::: --- ### 測驗 `3` 考慮以下 linked list 程式: ```clike #include <stddef.h> struct node { int data; struct node *next; } *head; void insert(struct node *newt) { struct node *node = head, *prev = NULL; while (node != NULL && node->data < newt->data) { prev = node; node = node->next; } newt->next = node; if (prev == NULL) head = newt; else prev->next = newt; } ``` 可透過以下 pointer to pointer 改寫 `insert` 函式,功能等價但更簡潔,如下: ```clike void insert(struct node *newt) { struct node **link = &head; while (*link && A) B; newt->next = *link; *link = newt; ``` 請補完程式碼。 ==作答區== A = ? * `(a)` *link->data < newt->data * `(b)` (*link)->data < newt->data * `(c)` **link->data < newt->data * `(d)` (link)->data < newt->data B = ? * `(a)` *link = *link->next * `(b)` (*link) = (*link)->next * `(c)` link = (*link)->next; * `(d)` link = &(*link)->next; :::success 延伸問題: 在 Linux 核心找出運用類似的手法的程式碼並解說 ::: ---