定時測量對洩漏的資訊論界限
我正在通過定時測量尋找關於洩漏的資訊理論界限。我假設攻擊者
- 想從黑匣子裡洩露一個秘鑰 $ k $ 秘密注入黑匣子的比特；
- 已經編寫了黑匣子的程式碼（它可以讀取密鑰並採取相應的行動），並且可以製作該程式碼以選擇黑匣子執行的功能的持續時間 $ n $ 等間隔的持續時間 $ t_j=t_0+j/(n-1) $ , $ 0\le j<n $ ( $ t_j $ 以時鐘週期為單位），與 $ t_0 $ 已知；
- 可以不確定地測量該函式的持續時間 $ u $ 根據一些分佈 $ U $ ， 和 $ |u|<1/2 $ 除非另有說明，否則在每次執行該功能時。
我正在尋找洩漏整個密鑰的定時測量數量的嚴格上限（這樣我就可以確定一些 $ k $ 如果我們低於該界限，則仍然是秘密）。
最多執行一次洩漏 $ \log_2(n) $ 通過定時測量獲得比特價值的資訊，因此至少 $ \lceil k/\log_2(n)\rceil $ 需要定時測量才能通過該唯一平均值完全提取密鑰。如果攻擊者進一步有 $ \big\lceil\log_2\big(\lceil k/\log_2(n)\rceil\big)\big\rceil $ 黑盒中的永久儲存位在函式執行後仍然存在，並且最初為零（草圖：我們編寫密鑰 $ k $ 在基地 $ n $ , 並且永久儲存器用於計數器告訴哪個數字 $ k $ 被洩露）。
更新：我意識到上述界限 $ \lceil k/\log_2(n)\rceil $ 如果攻擊者可以選擇黑盒的輸入並讓程式碼採取相應的行動，則測量也適用；這使得 Q1 和 Q2 下面的相關性大大降低。
Q1：如果攻擊者的程式碼沒有任何永久儲存，只有黑盒內部的真隨機數生成器怎麼辦？甚至有什麼合適的方法來表徵洩漏密鑰所需的測量次數？
Q2：如果在 Q1 的情況下，攻擊者在每次定時測量之外還獲得了一些大的隨機輸入或輸出的黑盒，攻擊者的程式碼也可以使用？
Q3：如果攻擊者的不確定性分佈怎麼辦 $ U $ 變得重要？也許，考慮到 $ U $ 是離散均勻分佈 $ [0\dots m-1] $ ; 或者 $ U $ 是高斯的；或者介於兩者之間的東西，比如 $ U $ 是兩個或三個離散均勻分佈的總和 $ [0\dots m-1] $ .
理由：我的真正目標（希望我們可以在 Q2 的條件下回答 Q3 ）是評估智能卡中定時攻擊的對策的可證明有效性（假設同步執行），包括在敏感操作後插入隨機暫停，和第三季度一樣。攻擊者編寫程式碼的假設當然是最壞的情況，精心設計是為了獲得洩漏的上限（必要測量次數的下限）。
之所以問 Q2，是因為在攻擊者沒有編寫程式碼的真實情況下，有理由相信攻擊者無法使用永久儲存，但輸入（或輸出）對時序具有確定性影響。Q1 是對 Q2 的介紹，沒有那種數據依賴性。
如您所說，如果測量準確，則設備可能會洩漏 $ log_2(n) $ 每次呼叫的資訊位。如果它缺少內部儲存，那麼它就無法跟踪它已經洩露了密鑰的哪些部分。它可以做的是洩漏一組隨機位，但接收者必須知道它們是哪些位。我看到兩種方法。
如果定時通道是唯一的通信，那麼 $ m = log_2(n) $ 位必須結合兩個關鍵數據（ $ d $ 位）和位置（ $ p $ 位）。如果位置指示哪一組 $ d $ 我們正在洩漏的位，然後 $ p >= log_2(k/d) $ . 因此，對於 256 位密鑰，此方案要求您一次能夠洩漏至少 9 位：8 位表示密鑰位置，1 位表示該密鑰位。位置位將隨機生成。
另一種方法是以不同的方式傳達位置：如果您的威脅模型包括攻擊者看到的，您可以使用密文中的數據，而不是使用 RNG 來選擇位置並將其包含在洩露的數據中。你可以使用第一個 $ p $ 用於選擇/指示我們正在洩漏哪些密鑰位的密文位，其中 $ p = log_2(k/m) $ .
在這兩種情況下，解決所有洩漏需要多長時間 $ k $ 密鑰的位由Coupon Collector’s Problem給出，即 $ O(n log n) $ . 在第二個例子中，這應該是 $ O(k/m log(k/m)) $ . 當然，您不必等待收集所有部分。特別是對於低頻寬通道，盡快開始暴力破解是有意義的。
對於 Q1，您可以使用噴泉碼之類的東西（在概念上類似於秘密共享方案）來有效地洩露密鑰。
例如，您可以將鍵映射到多項式的係數 $ p $ 在有限域上 $ F $ （大小合適），在隨機點進行評估 $ a \in F $ （或者 $ a \in S $ 對於某個子集 $ S \subset F $ )，並洩漏 $ a $ 和 $ p(a) $ （或可能有幾個這樣的對）。一旦洩漏的不同點的數量等於 $ p $ , 插值應該允許重建 $ p $ .
對於 Q2，您可以得出隨機點 $ a $ 從已知的輸入。這使您不必洩漏它們，從而允許您每次執行洩漏（最多）兩倍的有用位。
Q3 似乎是一個編碼理論問題。基本上，將時序測量視為雜訊通道，您希望選擇盡可能接近通道香農容量的編碼。
請注意，上面為 Q1 建議的編碼方案已經提供了一種隱式錯誤檢測和糾正機制：如果您提取的數據點比嚴格需要的數據點多，並根據所有這些點對多項式進行插值，則可以判斷是否存在由於所得到的多項式（以高機率）的次數高於預期這一事實而導致的任何錯誤。如果錯誤的數量很少，甚至可以通過測試點的哪個子集產生正確的重建來檢測哪些點是錯誤的。也就是說，特別是對於更高的錯誤率，您可能還想在噴泉編碼之上簡單地應用傳統的糾錯碼。