MAC協議的完美否認
我試圖提出一個滿足這些安全要求以及 MAC 的正常安全要求的協議
一次性 MAC
- Alice 和 Bob 預先共享一個 $ n^2 $ OTP 位， $ k $ （生成的位與您在此處滿足所有要求的 OTP 相同）
- 愛麗絲打破 $ k $ 進入 $ n $ 長度的字元串 $ n $ ，讓我們稱呼他們 $ k_1, k_2, …, k_n $
- 對於每個 $ k_i $ 愛麗絲計算 $ b_i = \bigoplus_{j=0}^{n}(m \oplus k_i) $
- 每個 $ b_i $ 是通過 xoring 中的所有位計算得出的位 $ m \oplus k_i $
- 愛麗絲發送 $ m||b $ 在哪裡 $ b = b_1||b_2||…||b_n $
- Alice 和 Bob 銷毀 k
證明
One-Time MAC 是一種 MAC，因為任何不知道密鑰的人只能以可忽略的機率修改流。如果有人試圖翻轉消息中的位，那麼他們將需要翻轉 MAC 中的一些未知位，反之亦然。他們只會用機率正確猜測 $ 2^{-n} $ .
現在是完美的否認部分。
如果夏娃帶著 $ m $ 和 MAC（ $ m $ ) = 一次性 MAC( $ m $ ) 那麼 Alice 就可以生成 $ n $ 隨機的 $ n $ 位字元串檢查他們 $ b_i $ 值並對它們重新排序，以便它們創建一個“有效”鍵。（注意她可能需要產生超過 $ n $ 如果鍵的數量 $ b_i = 0 $ 與數量不符 $ 0 $ ‘在 MAC( $ m $ )，但很有可能她不需要產生超過 $ 2n $ 隨機字元串）
問題與思考
我覺得有義務發布有關此協議的問題。
- 非常大的鍵（ $ n^2 $ )
- 與 OTP（密鑰管理等）類似的問題
- 可以用作 OTP 的 MAC，並為消息提供完美的保密性和完美的可否認性，而不會被篡改
問題
這是否滿足 MAC 的屬性？
這是否滿足這個定義？
這可以用更小的鑰匙來完成嗎？
對於長消息，您可以將其分解為較小的消息並單獨使用 MAC 以使用更少的密鑰嗎？
- 我會假設你會失去安全感，因為 $ n $ 會更小
這是否滿足 MAC 的屬性？
不，它沒有，但是對其進行調整。
問題是翻轉一點 $ m $ 總是改變 MAC 的每一位（如果 $ n $ 是奇數），或者沒有位（如果 $ n $ 甚至）; 因此，攻擊者修改消息並調整 MAC 是微不足道的。
你真正的意思是 $ b_i = \bigoplus_{j=1}^{n}(m \wedge k_i) $ （在哪裡 $ \wedge $ 是按位和運算。這仍然需要一些調整（因為全 0 消息；要麼在消息中包含人工 1 位，要麼更便宜，對另一個進行最終異或 $ k $ 向量進入決賽 $ b $ 結果）。
這種方法相當於隨機選擇一個 $ (n \times n) $ 矩陣 $ GF(2) $ ，然後對消息進行矩陣乘法以形成輸出；這是一種眾所周知的通用雜湊方法。
這是否滿足這個定義？
通過上述調整，是的。
這可以用更小的鑰匙來完成嗎？
當然。我懷疑大多數通用雜湊方法都可以做到這一點。這是一種使用相當小的密鑰的方法（多項式雜湊）。
讓我們選擇一個整數 $ z $ , 和一個欄位表示 $ GF(2^z) $ （實際上，任何這種大小的欄位都可以工作）。
然後，對於我們的一次性密鑰密鑰，我們隨機選擇兩個 $ z $ 位值 $ h $ 和 $ c $ .
然後，我們劃分我們的 $ n $ 位消息 $ m $ 進入 $ z $ 位大小的塊 $ m_{i-1}, m_{i-2}, …, m_0 $ （在哪裡 $ i = \lceil( n / z ) \rceil $ ，我們計算：
$$ MAC = m_{i-1} h^{i+1} + m_{i-2} h^{i} + … + m_0 h^2 + i h + c $$ 上面的計算是在 $ GF(2^z) $
這也是一個安全的 MAC（對消息和標籤的任何修改最多將通過檢查 $ (i+1)2^{-z} $ ; 我們可以選擇 $ z $ 使這個任意小），它也符合您的要求（偽造一個 MAC，我們可以選擇任意一個 $ h $ 併計算什麼 $ c $ 價值必須是）；總共使用 $ 2z $ 每條消息的 OTS 位數。