標籤與加密的任務不同
認證標籤讓接收者檢查訊息是否符合雙方共享的秘密密鑰,但它不一定隱藏訊息。我們研究一個刻意簡化的一次性實驗,證明精確的替換成功概率,並看清假設的重要性。
定義 11.1.1
(一次性仿射標籤方案)
令 為質數,以 表示訊息、標籤與密鑰分量的集合。發送者和接收者共享均勻隨機的秘密對 ,且它與固定訊息 獨立。發送者在這次使用中公開 及
接收者恰在 時接受聲稱的訊息與標籤 。所有運算都在 中進行。兩個密鑰分量都從整個域選取,包括零。
攻擊模型讓攻擊者看到一個真實對 ,然後對不同訊息進行一次驗證嘗試;同一密鑰下沒有更早的觀察或驗證回饋。
一次嘗試的精確界
定理 11.1.2
(替換成不同訊息)
觀察 後,攻擊者選擇任意 及標籤 ,其選擇可依賴觀察結果及與密鑰獨立的私人隨機性。接收者接受 的概率恰為 。
證明
(以觀察到的標籤為條件)
固定觀察到的 。對 的每個選擇,恰有一個 產生該觀察。由於原來 個密鑰對均勻,剩下的 個密鑰等可能。對固定的 ,
差 非零,因而可逆,所以 遍歷整個域時,此表達式恰好取遍每個標籤值一次。在觀察結果條件下, 的正確標籤均勻分佈。因此任何提出的 成功概率都是 。上述論證適用於每個觀察結果及由它選出的不同 ;再對攻擊者的獨立隨機選擇取平均即可。
證明有兩個要素,使用結果之前值得把它們分開。
證明透視
觀察後甚麼仍是隨機的?
均勻且與 獨立,這個假設只用了一次:它使符合觀察的 個密鑰等可能,而且只由 參數化。公開標籤消去密鑰的一個自由度,另一個自由度則完全未受影響。
關鍵一步是改寫 ,把未知的目標標籤寫成唯一剩下的未知量的函數。假設 正是在這裏與 為質數一起使用:域中非零元素可逆,所以 是 的雙射,把均勻的 送到均勻的標籤。若改在 中而 ,則 只取 與 兩個值,各有概率 ,偽造成功概率便是 而非 。
論證逐點收結:界對每個觀察及由它選出的每個 都成立,所以只要攻擊者的隨機性與密鑰獨立,取平均後任何自適應或隨機的 選擇都受同一界限制。
例題 11.1.3
(小域與觀察到的標籤)
取 ,假設密鑰為 、。對 ,真實標籤為 。只看到 的觀察者不能確定 :對每個 ,密鑰 都符合觀察。若替換訊息為 ,其有效標籤是 ;當 遍歷整個域,它取遍七個值。猜一個標籤的成功概率為 。此處列出密鑰值僅為檢查算術;真正的密鑰是秘密。
例題 11.1.4
(照抄觀察到的標籤)
仍取 及觀察 。偽造者可能提交新訊息 並沿用舊標籤 。若 ,訊息 的正確標籤是 ,而
因為 在模七下可逆。在七個等可能的相容密鑰 中,只有 接受照抄的標籤,所以成功概率為 ,與定理一致。邊界情況 正是標籤與訊息無關的密鑰;定義容許它,而這個策略押注的就是它。
定義容許 取零。排除零看似只是讓每個標籤都依賴訊息的無害做法,但它會改變精確界。
例題 11.1.5
(禁止零密鑰分量)
改設 在 上均勻, 在 上均勻且兩者獨立,共有 個密鑰。觀察到 後,每個 仍恰有一個相容的 ,所以 在 個非零值上均勻。對 ,目標標籤 取遍除 以外的每個值,各有概率 。提交任何 的偽造者成功概率為 ,大於 ;當 時為 。照抄標籤此時必定失敗,但最佳攻擊反而改進了。
重用破壞此實驗
反例模式
兩對數據透露密鑰
假設同一密鑰為不同訊息 產生標籤 ,而兩對數據都被觀察到。則
因為訊息不同,分母可逆。對上述例子,第二對真實數據 給出模七下 、。觀察者便可計算每個域訊息的標籤,例如訊息 的標籤是 。一次觀察的定理不適用於這個兩次觀察實驗。
常見錯誤
(把此界當作防重播或防重複猜測的保證)
定理只涉及對訊息 的一次嘗試。重播真實對 會以概率 被接受,所以此方案不保證新鮮性。多次驗證嘗試也在結論之外:每次被拒絕都告訴攻擊者哪些密鑰已被排除,需要另行分析。
訊息是公開的,沒有加密。真正系統需要安全密鑰建立、防重播、適當密鑰處理與經審核的認證方案;這個小例子並非實現建議。
習題
快速檢查
(若 、、,求訊息 和 的標籤。)
計算 並模七約化。
解答 · 答案
,,所以模七下標籤分別是 和 。
快速檢查
(已觀察一對 ,還有多少個可能密鑰 ?對每個可能的 , 是甚麼?)
從 解出 。
解答 · 答案
有 個等可能密鑰:對每個 ,觀察迫使 。
快速檢查
(為甚麼證明要求 ?)
看目標標籤中乘以 的因子。
解答 · 答案
這時 非零且可逆,所以 變化時目標標籤 均勻。若 ,目標標籤就是攻擊者已知的觀察值 。
快速檢查
(若同一密鑰產生的兩對不同訊息與標籤都公開,情況有何改變?)
把兩條標籤方程相減。
解答 · 答案
相減得 ;由於 可逆,這確定 ,再由任一對確定 ,攻擊者便可計算每個訊息的標籤。
延伸閱讀
MIT 通用雜湊講義 討論兩兩獨立的仿射映射。加州大學柏克萊分校訊息認證講義 討論更廣泛的認證構造。