One Time Pad 被認為是選擇明文攻擊安全嗎？

如果我們正在考慮選擇明文攻擊設置，那麼攻擊者可以訪問加密 Oracle 權限，並且我們知道只有在我們只使用一次密鑰時才認為 OTP 是安全的。我們如何確保對手只使用一次密鑰？

或者對手如何使用加密預言機無關緊要，因為最終他們將看到與未查詢的明文相對應的密文，並且對手將無法解密它，因為他們不知道密鑰。使其成為 CPA-Secure。這第二條構想是在 CPA 設置中思考 OTP 的正確方法嗎？

謝謝！

注意：在這個答案中，我堅持一次性墊的定義，其中隨機墊僅使用一次；至少，我有它的名字作為支持！否則，眾所周知，即使是最弱的標準（具有冗餘的未知明文），由具有重複密鑰的 XOR 組成的OTP加密方案也是不安全的。

後期添加：此外，我堅持在標准文獻中為密碼給出的 IND-CPA 定義，並在下面引用。有關適用於 OTP 並得到滿足的不同定義，請參閱此其他答案。

選擇明文攻擊下的不可區分性適用於加密方案；不可能使 OTP 與加密方案的定義相匹配，因此IND-CPA 的正式定義不適用於 OTP。

具體來說，OTP 不符合 Jonathan Katz 和 Yehuda Lindell 的*《現代密碼學概論》*第一版（CRC Press，2008）中的定義 3.7：

私鑰加密方案是機率多項式時間算法的元組( $ \text{Gen} $ , $ \text{Enc} $ , $ \text{Dec} $ ）這樣：（..）

1. 密鑰生成算法 $ \text{Gen} $ 將安全參數作為輸入 $ 1^n $ 並輸出一個密鑰 $ k $ ; (..)
2. 加密算法 $ \text{Enc} $ 將密鑰作為輸入 $ k $ 和一條明文消息 $ m\in{0,1}^* $ ，並輸出密文 $ c $ . (..)
3. 解密算法 $ \text{Dec} $ 將密鑰作為輸入 $ k $ 和一個密文 $ c $ , 並輸出一條消息 $ m $ . (..)

要求對於每一個 $ n $ , 每個鍵 $ k $ 輸出 $ \text{Gen}(1^n) $ ，並且每個 $ m\in{0,1}^* $ , 它認為 $ \text{Dec}_k(\text{Enc}_k(m))=m $ .

在哪裡 $ {0,1}^* $ 是所有（有限長度）二進製字元串的集合。

OTP 無法適應這個框架：

• 如果我們嘗試同化隨機填充和鍵，我們會遇到上面定義中相同的問題 $ k $ 可用於多條消息（而且有些消息可能比密鑰大，但這是次要的）；OTP 不允許這樣做（由於OTP 的一次性要求）。
• 如果我們嘗試將隨機墊放入 $ \text{Enc} $ ，並且仍然保持 OTP 中的密文（包括與消息大小相同），那麼我們無法建構一個有效的 $ \text{Dec} $ .

注意：一些實際的加密方案使用的消息空間偏離 $ {0,1}^* $ ，就像所有字節串的集合一樣大小，甚至是固定大小的字節串，甚至可能比密鑰短（這在分組密碼中很常見）；並且可以接受扭曲加密方案的定義以允許這樣做。然而，任何加密方案的一個基本點是允許用給定密鑰加密的明文的總大小顯著增加超過密鑰的大小。同樣，OTP 不允許這樣做。

是的，一次性便箋模型提供了 IND-CPA 安全性的技術概念。 如果墊是均勻隨機的，則對手在 IND-CPA 遊戲中的優勢為零。這是一個標準——一旦你超越了定義，就變得微不足道了！——為像 Salsa20 或 AES-CTR 這樣的實用流密碼證明 IND-CPA 安全定理的引理。

當然，現實世界中的對手擁有像偽造這樣的能力，而不僅僅是竊聽，而且——撇開 pad 管理成本不談**——一次性 pad 模型無法防禦偽造！** 你真的想要一個經過驗證的密碼，甚至可能是一個抗隨機誤用的經過驗證的密碼。但這個問題僅與 IND-CPA 安全有關。

---

一次性墊模型。

1. 你和你的國際間諜夥伴共用一個很長的統一隨機墊 $ p $ 由一系列頁面組成 $ p_1, p_2, \dots, p_n $ ，為了交換一系列消息 $ m_1, m_2, \dots, m_n $ 關於推翻不方便的民選政府。
2. 發送消息 $ m_i $ , 你剝一頁 $ p_i $ 脫墊並貼上密文 $ c_i := m_i \oplus p_i $ 到鴿子的腿上。（因為鴿子不提供可靠的有序運輸，你可能想潦草地寫數字 $ i $ 在你貼在鴿子腿上的紙片上。）

你的外交夥伴，鴿子歸來，然後解密 $ c_i $ 通過剝離 $ p_i $ 關閉他們的墊子副本並恢復 $ m_i = c_i \oplus p_i $ . 3. 然後你吃掉你剛用過的墊子（或者如果你太嬌氣而不能像老電影中那樣成為真正的間諜，那就把它燒掉——完成後一定要把灰燼在一杯水中徹底混合）。

我們通過讓發送者和接收者保持關於他們使用了多少頁的狀態來對此建模：$$ \require{cancel}\cancel{!p_1!!}, \cancel{!p_2!!}, \cancel{!p_3!!}, \cancel{!p_4!!}, ,p_5, ,p_6, ,p_7, $$或者等價地記住這個數字 $ i $ 到目前為止已交換的消息。

旁白：使用像 Salsa20 這樣的流密碼，我們只需選擇 $ p_i := \operatorname{Salsa20}_k(i) $ 在哪裡 $ k $ 是發送者和接收者共享的統一隨機 256 位密鑰——其他一切都相同（密文為 $ c_i := m_i \oplus p_i = m_i \oplus \operatorname{Salsa20}_k(i) $ , 解密為 $ c_i \oplus \operatorname{Salsa20}_k(i) $ , 發送者和接收者必須記住 $ i $ , 不得重複 $ i $ 等），除了你不必用紙墊摸索或吃掉它們。

選擇明文攻擊（-CPA）。 在選擇明文攻擊設置中，我們假設對手可以學習他們選擇的明文的密文。我們通過為攻擊者提供一個稱為加密預言機的子程序來對此進行建模。當攻擊者向加密預言機查詢消息時，預言機返回消息的密文。

• 預言機可能是不確定的——它可能會擲骰子來決定返回許多有效密文中的哪一個，例如選擇一個 CBC 初始化向量。
• 預言機可能是有狀態的——它可能會記住對手過去送出的查詢、答案是什麼，或者到目前為止有多少查詢。

如果預言機是確定性和無狀態的，就像在具有固定隨機數的 AES-GCM-SIV 中那樣，那麼我們不能擁有密文本身不可區分性——充其量只有非重複消息的密文不可區分性。

（一些教科書只考慮非確定性情況，這很奇怪，因為當今地球上最流行的兩種流密碼，TLS 1.3 的 AES-GCM 和 ChaCha/Poly1305 密碼套件中使用的 AES-CTR 和 ChaCha，使用狀態！這個並不意味著 AES-GCM 和 ChaCha/Poly1305 無法提供 IND-CPA 安全性；它只是意味著教科書的定義是有限的——有狀態的 IND-CPA 概念在文獻中被廣泛使用。）

def ..._cpa_...(adversary):
   k = generate_key()
   i = [0]
   def encryption_oracle(plaintext):
       iv = random_iv()        # may be nondeterministic
       ciphertext = encrypt(k, iv, i)
       i[0] += 1               # may be stateful
       return ciphertext
   ... adversary(encryption_oracle) ...

區分遊戲或不可區分性 (IND-)。 在區分遊戲中，對手的目標是找到一對消息 $ \hat m_0 \ne \hat m_1 $ 這樣，如果我擲硬幣給出結果 $ b \in {0,1} $ 並返回消息的加密 $ \hat m_b $ , 對手可以以不可忽略的高於 1/2 的機率判斷硬幣朝哪個方向投擲 $ b $ 上來了。消息 $ \hat m_0 $ 和 $ \hat m_1 $ 可能取決於加密預言機給出的答案。

我們將正式將對手分為兩個階段：

• $ A_0 $ oradversary[0]給定一個加密預言機進行查詢，並返回一對消息 $ m_0 $ 和 $ m_1 $ 它想被挑戰；
• $ A_1 $ 或被adversary[1]賦予加密 $ m_b $ 秘密拋硬幣 $ b $ ，並返回關於什麼的猜測 $ b $ 曾是。

def ind_cpa_...(adversary):
   k = generate_key()
   i = [0]
   def encryption_oracle(plaintext):
       iv = random_iv()        # may be nondeterministic
       ciphertext = ..._encrypt(k, iv, i[0], plaintext)
       i[0] += 1               # may be stateful
       return ciphertext
   # First, give the adversary a chance to query encryption
   # oracle; let them pick two messages for the challenge.
   m0, m1 = adversary[0](encryption_oracle)
   # Choose which of the messages to challenge them with.
   b = flip_coin()
   mb = m1 if b else m0
   # Challenge the adversary to guess what b was.
   b_ = adversary[1](encryption_oracle(mb))
   # Return whether the adversary guessed right or not.
   return b == b_

對手的顯著優勢是他們猜對的機率和他們猜錯的機率之間的絕對差。用半正式的數學術語來說，

$$ \begin{equation} \operatorname{Adv}^{\operatorname{IND-CPA}}_E(A) := \left|\Pr[\operatorname{IND-CPA}_E(A) = 1] - \Pr[\operatorname{IND-CPA}_E(A) = 0]\right|. \end{equation} $$

這裡 $ E $ 表示加密方案 ( encrypt)， $ A $ 代表對手 ( adversary)，並且 $ \operatorname{IND-CPA}_E(A) $ 意味著玩 IND-CPA 遊戲 $ E $ ( ind_cpa_...) 對抗對手 $ A $ .

IND-CPA 遊戲，適用於一次性墊模型。 只需填寫空行：

def ind_cpa_otp(adversary):
   npages = 1000       # let's try to conserve paper
   pad = generate_pad(npages)
   i = [0]
   def encryption_oracle(plaintext):
       # multi-page messages left as exercise for reader
       ciphertext = plaintext ^ pad[i]
       pad[i[0]] = None        # om nom nom
       i[0] += 1               # next page, please
       return ciphertext
   m0, m1 = adversary[0](encryption_oracle)
   b = flip_coin()
   mb = m1 if b else m0
   b_ = adversary[1](encryption_oracle(mb))
   return b == b_

引理。 如果頁面 $ p_i $ 墊的 $ p $ 是獨立均勻隨機的，那麼$$ \operatorname{Adv}^{\operatorname{IND-CPA}}_{\operatorname{OTP}_p}(A) = 0. $$

證明。 假設對手送出 $ q $ 對加密預言機的查詢。那麼挑戰密文就是 $ m_b \oplus p_{q+1} $ . 的分佈 $ m_0 \oplus p_{q+1} $ 和分佈 $ m_1 \oplus p_{q+1} $ 都是一致的，並且獨立於所有先前的密文和 $ b $ ，所以對手答案的分佈與 $ b $ ; 因此 $ \Pr[A_1(m_b \oplus p_{q+1}) = b] = 1/2 $ 因此 $ \operatorname{Adv}^{\operatorname{IND-CPA}}_{\operatorname{OTP}_p}(A) = 0. $

當您通過選擇在實踐中實例化模型時 $ p_i = \operatorname{Salsa20}_k(i) $ 或者 $ p_i = \operatorname{AES}_k(i) $ 對於一個短的統一隨機密鑰 $ k $ ，對手在贏得 IND-CPA 遊戲時獲得了小幅優勢，但在將 Salsa20 或 AES 與統一隨機函式區分開來時，對手的優勢有限。

定理。 如果 PRF 對函式族的優勢 $ F_k $ 對於均勻隨機 $ k $ 由 $ \varepsilon $ ，則 IND-CPA 對上述一次性填充模型的優勢實例化為 $ p_i = F_k(i) $ 由 $ \varepsilon $ .

證明。**使用預言機與任何對手 進行 IND-CPA 遊戲 $ \mathcal O(i) $ 生成墊 $ p_i $ ( generate_pad)，作為 PRF 區分符 $ \mathcal O = F_k $ 對於一個統一的隨機密鑰 $ k $ 對比 $ \mathcal O = R $ 對於均勻隨機函式 $ R $ . 由於IND-CPA優勢當 $ \mathcal O = R $ 引理為零，IND-CPA 優勢在 $ \mathcal O = F_k $ 不能比界限更好 $ \varepsilon $ 關於 PRF 的優勢 $ F_k $ .

參見，例如，$$ 1 $$, 引理 12, 其中 $ p_i = R(i) $ 對於均勻隨機函式 $ R $ 在 $ \operatorname{CTR}[R] $ （相當於一次性墊型號）；和定理 13，其中 $ p_i = F_k(i) $ 對於偽隨機函式族 $ F $ 例如具有統一隨機密鑰的 Salsa20 $ k $ 在 $ \operatorname{CTR}[F] $ ——這是分組密碼“CTR 模式”安全性的標準參考。

這篇論文使用了一個稍微不同的遊戲，其中拋硬幣 $ b $ 預先發生，對預言機的所有查詢都是兩條不同的消息；結果是技術上稍強的定理，但實際結果基本相同。 *注意：*論文中的“異或”方案是不同的——它不是按順序（有狀態）通過 pad，而是為每條消息（具有不確定性）隨機均勻地選擇 pad 的頁面，因此存在碰撞的危險消息數量的二次方。引理 12 的證明比必要的更加迂迴，因為作者選擇首先證明一個關於“異或”方案的定理，這需要設置碰撞機率的界限。

如需更長的說明，請參閱 Goldwasser & Bellare 的講義$$ 2 $$, §§6.4–6.7.

---

這是 Salsa20 和 AES-CTR 等流密碼的設計靈感：您可以將所有精力集中在一種從短共享密鑰生成 pad的方法上，例如 Salsa20 或 AES，這些方法已經投入了數十年的工作。世界上最聰明的密碼分析員；然後漂亮而簡單的 xor 操作負責將 pad 與消息相結合，以使消息不被竊聽者保密。（例如，參見 Salsa20 設計文件$$ 3 $$，頁。4，“加密和解密應該不同嗎？”） Salsa20 和 AES-CTR 的安全使用規則源自一次性便箋簿的安全使用規則：就像您不能重複使用您的便箋簿的一頁一樣對於兩條不同的消息，您不得將具有相同密鑰的 Salsa20 或 AES-CTR 隨機數用於兩條不同的消息。

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