GF(2^8) 中的常數時間乘法

我正在嘗試在 C 中實現 AES；我想讓它抵抗側通道攻擊，但我無法在恆定時間內實現乘法。我目前的程式碼：

static uint8_t GF28_Mult (uint8_t Poly0, uint8_t Poly1) {
   uint8_t Result = 0;

   for (uint8_t Shift = 0; Shift < 8; Shift++) {
       if (Poly1 & 0x01)
           Result ^= Poly0;

       if (Poly0 & 0x80)
           Poly0 = (Poly0 << 1) ^ 0x1b;
       else
           Poly0 <<= 1;

       Poly1 >>= 1;
   }

   return Result;
}

如果 GF28_Inverse 在恆定時間內，是否真的需要在恆定時間內擁有它？

在 C 中，域中的乘法 $ \operatorname{GF}(2^8) $ 用歸約多項式 $ x^8+x^4+x^3+x+1 $ 可以編碼為以下三個功能等效函式之一：

uint8_t mult1B_compact(uint8_t a, uint8_t b) {
   uint8_t r = 0, i = 8;
   while(i)
       r = (-(b>>--i & 1) & a) ^ (-(r>>7) & 0x1B) ^ (r+r);
   return r;
}

uint8_t mult1B_fast(uint8_t a, uint8_t b) {
   uint8_t r;
   r = (-(b>>7    ) & a);
   r = (-(b>>6 & 1) & a) ^ (-(r>>7) & 0x1B) ^ (r+r);
   r = (-(b>>5 & 1) & a) ^ (-(r>>7) & 0x1B) ^ (r+r);
   r = (-(b>>4 & 1) & a) ^ (-(r>>7) & 0x1B) ^ (r+r);
   r = (-(b>>3 & 1) & a) ^ (-(r>>7) & 0x1B) ^ (r+r);
   r = (-(b>>2 & 1) & a) ^ (-(r>>7) & 0x1B) ^ (r+r);
   r = (-(b>>1 & 1) & a) ^ (-(r>>7) & 0x1B) ^ (r+r);
return (-(b    & 1) & a) ^ (-(r>>7) & 0x1B) ^ (r+r);
}

uint8_t mult1B_shift8(uint8_t a, uint8_t b) {
   uint16_t r,s;
       r  = (-((s = b+b)&256))>>8 & a; r += r; r ^= (-(r&256))>>8 & 0x1B;
       r ^= (-((s += s )&256))>>8 & a; r += r; r ^= (-(r&256))>>8 & 0x1B;
       r ^= (-((s += s )&256))>>8 & a; r += r; r ^= (-(r&256))>>8 & 0x1B;
       r ^= (-((s += s )&256))>>8 & a; r += r; r ^= (-(r&256))>>8 & 0x1B;
       r ^= (-((s += s )&256))>>8 & a; r += r; r ^= (-(r&256))>>8 & 0x1B;
       r ^= (-((s += s )&256))>>8 & a; r += r; r ^= (-(r&256))>>8 & 0x1B;
       r ^= (-((s += s )&256))>>8 & a; r += r; r ^= (-(r&256))>>8 & 0x1B;
return r ^( (-((s +  s )&256))>>8 & a);
}

線上嘗試！前兩個版本廣泛使用了一種通用技術，適用於許多其他語言：

• 使用右移將感興趣的位移動到字節的低位>>
• & 1必要時將其隔離，
• 應用一元運算符-更改1為0xFF…FF（保持0不變），
• 然後將結果用作字節遮罩。

對於大多數平台，這會生成不受數據相關時序變化影響的程式碼¹。我知道沒有例外，但仍然應該檢查，例如通過檢查生成的程式碼，並在理論上呼叫/驗證有關影響每個目標 CPU 上指令執行時間的因素的考慮。

在許多平台上，mult1B_fast（可能是製造inline的）接近於最快的可移植 C 程式碼，沒有與數據相關的時序變化。然而，特別是在缺少桶形移位器的 CPU 上，可能值得嘗試這種mult1B_shift8變化，它只移位一個完整字節：上述技術應用於高字節 16 位變數，因此& 1變為&256. 彙編語言通常允許進一步的收益，包括直接訪問進位位。

注意：這些技術使其他側通道敞開，特別是功率分析。

注意：在一些非編譯語言中證明不存在數據相關的時序變化是非常困難的。理論上關於執行時環境的最細微的細節都需要考慮在內；比如，Java JITC使用什麼啟發式方法。

注意：關於*«一元減號運算符應用於無符號類型，結果仍然無符號»*的錯誤編譯器/工具警告可以被靜音，也許通過改變-(to的出現0-(。添加括號以滿足任何強制約定。

---

如果 GF28_Inverse 在恆定時間內，是否真的有必要在恆定時間內擁有（此欄位乘法程式碼）？

不，因為不需要全域乘法（另見註釋¹）。除了 S-box 的計算，AES 加密²的自然實現（包括 CTR 模式下的 AES 解密）只需要欄位乘以欄位元素 $ x $ ，編碼2。使用與上述相同的技術，可以將其編碼為以下之一：

inline uint8_t mul1B_x(uint8_t a) {
   return (-(a>>7) & 0x1B) ^ (a+a);
}

inline uint8_t mul1B_x_shift8(uint8_t a) {
   uint16_t r = a+a;
   return ((-(r & 256))>>8 & 0x1B) ^ r;
}

---

¹ 出於安全考慮，我們不需要恆定時間程式碼，這在許多現代計算平台上幾乎是不可能實現的，因為存在各種記憶體和後台中斷活動。可能存在的任何時序變化與所處理的數據無關就足夠了。

² 就是這樣一種自然的實現方式。當兩個 256 字節表與 256 字節邊界對齊時，它通常不會在沒有數據記憶體的 CPU 上不受數據相關時序變化的影響。其中一個表可以替換為mul1B_x，另一個是 S-box。

必須讓所有組件在恆定時間內保持無旁通道；更重要的是，時間並不是實現必須考慮的唯一附帶渠道。

從有限域乘法開始，我嘗試讓我的實現側通道免費：

static inline uint8_t xtime(uint16_t x)
{
   x = ((x << 1) & 0x00ff) - ((x << 1) & 0x0100);
   return (uint8_t)(x ^ ((x >> 8) & 0x1b));
}

static inline uint8_t gmul(uint8_t a, uint8_t b)
{
   register uint8_t x = 0;

   for(int i=0; i<8; a=xtime(a),i++)
       x ^= ~((1 & (b >> i)) - 1) & a;

   return x;
}

為了解釋我做了什麼讓它“恆定時間”，我用

1. “&”按位與和“>>”移位運算符獲得單個位整數值 0 或 1。
2. 減去步驟 1 中的值以獲得全位為零或全位為一個的字作為遮罩。
3. 使用帶有按位與運算符的遮罩有條件地應用第二個操作數以避免使用三元條件運算符。

您可能還對如何在恆定時間內實現 sbox感興趣。

引用自：https://crypto.stackexchange.com/questions/82095