具有狀態更新功能的 PRNG
考慮狀態更新功能所在的（假設的）PRNG，但很容易找到一組原像（因此不是單向的）。也就是說，如果攻擊者獲得了系統的內部狀態，比如 state $ s_n, s_{n+1}, …, s_{n+m} $ ，“真實”的先前狀態 $ s_{n-1} $ 使用者獲得的可以是無限集合中的多個狀態中的任何一個 $ S $ . 所以攻擊者知道 $ s_{n-1} \in S $ , 但假設 $ |S| $ 是大的或無限的，所以攻擊者必須猜測“真” $ s_{n-1} $ 狀態。這樣的 PRNG 存在嗎？而且，可以將這樣的 PRNG 稱為“抗回溯”嗎？
我不確定的是，這樣的 PRNG 預設情況下是否是加密安全的：因為狀態更新功能已開啟，“真實”的先前狀態可能以相同的機率是 $ S $ ，因此之前的狀態幾乎是不可預測的，這意味著這樣的 PRNG 在密碼學上是安全的。我的邏輯在哪裡出錯了？
有狀態算法的狀態是它的“記憶”。一輪算法可以建模為一個函式 $ S \times I $ 至 $ S \times O $ 在哪裡 $ I $ 是一輪的輸入，並且 $ O $ 是一輪的輸出。對於 PRNG， $ I $ 要麼是一個單例（即沒有輸入，只是一個生成更多輸出的請求），要麼是少量資訊，例如請求的輸出大小，或者一些額外的熵注入。 $ O $ 是偽隨機輸出的塊。
回合前後的狀態大小是一樣的。所以對於給定的輸入，狀態更新函式是 on（滿射）當且僅當它是一對一的（內射的）。
如果您有一個狀態更新函式，但不是一對一的，這意味著您正在使用不同的模型，其中狀態的大小在每一輪中都會減小。您的 PRNG 將有一個有限的生命週期，因為大小最終會縮小到接近零（接近零是對手可以實際列舉可能狀態的任何大小）。這將限制它的用處。
在這種情況下，僅僅因為目前狀態的知識並不能讓攻擊者確定先前的狀態是什麼，並不能特別賦予任何安全性。安全不是合理的推諉。為了使系統安全，僅僅使對手無法毫無疑問地證明他們已經破壞了它是不夠的！你實際上需要使它實際上不可能被打破。對手擁有一些部分資訊而不僅僅是您關注的一項知識是很常見的。例如，假設在上一輪使用 PRNG 生成 32 個字節的數據，其中 16 個字節作為密鑰，16 個字節作為 IV，並且攻擊者已經能夠看到加密的消息，現在想要解密它。對手知道IV，即 他們知道 PRNG 輸出的一半，他們正在尋找另一半，這是關鍵。為了使 PRNG 具有回溯阻力，您需要確保了解目前 PRNG 狀態加上 IV 的知識不足以重構之前的 PRNG 狀態。也許僅了解目前 PRNG 狀態是不夠的，但在對手也知道一半輸出的實際場景中，這根本沒有幫助。
在現實世界的 PRNG 中，反轉狀態更新函式是微不足道的，即如果您知道目前狀態（可能還有相應的輸出），則可以找到先前的狀態。但根據定義，它們不是抗回溯的。