2019q1 第 3 週測驗題 (上)

目的: 檢驗學員對 C 程式設計的認知

---

測驗 1

考慮到 memcmp 一種實作如下: (行為和 ISO C90 有出入)

#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 的風險，於是著手避免使用 conditional branching 一類的指令，從而避免 side-channel attack。

為了避免 conditional branch 指令的出現，我們可將 (res > 0) - (res < 0) 替換為 ((res - 1) >> 8) + (res >> 8) + 1。隨後我們實作下方功能等價但避免 branch 的 memcmp:

#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
• Re: [PATCH] crypto_memcmp: add constant-time memcmp

請補完程式碼。

作答區

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

延伸問題:

1. 解釋上述程式的原理，需要從機率統計的觀點分析;
   • 為何不能用事先計算好的表格呢？ (提示: cache 的影響)
   • 如何驗證程式正確以及 constant-time 呢？
2. 研讀下方論文並解說:
   • Remote timing attacks are practical
   • A Lesson In Timing Attacks (or, Don't use MessageDigest.isEquals)
3. 在 Linux 核心找到這類 constant-time 的操作程式碼，予以解說和設計實驗;

---

測驗 2

考慮以下計算平方根的程式:

#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)² = x² + 2ax + a² 漸進找出平方根。不過上面的程式僅能處理整數，我們引入 fixed point 來表達浮點數，改寫程式碼如下:

/* 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

延伸問題:

1. 解釋上述程式碼運作原理，並找出類似的開放原始碼程式;
2. 上述 sqrt_I2F 函式存在 overflow 風險，請提出修正方案並驗證;

---

測驗 3

考慮以下 linked list 程式:

#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 函式，功能等價但更簡潔，如下:

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;

延伸問題:
在 Linux 核心找出運用類似的手法的程式碼並解說

---