這個簡單的記憶困難功能好嗎？
我正在嘗試為工作量證明系統提出一個簡單的記憶硬函式來防止垃圾郵件。下面的安全嗎？
對於消息 M，附加一個隨機數 R。重複直到找到 R1、R2 使得 sha256(M++R1) 和 sha256(M++R2) 共享至少 d 個二進制數字。R1、R2 是工作量證明，隨消息一起發送。將 sha256 替換為您想要的任何加密雜湊函式。
我假設這個函式很難記憶，因為你想儲存所有 R 和它們相應的散列來增加匹配的可能性。如果您不將它們全部儲存，則會降低匹配的機率，從而節省記憶體，但平均需要更多的 cpu 時間。此外，僅儲存散列的一部分，例如每個散列的前半部分，應該可以節省記憶體，但可以將匹配的機率降低幾個數量級。
這個算法有明顯的缺陷嗎？這是一個已知的算法嗎？是否有一個標準算法大致與實現一樣簡單？
TL;DR：不，這不是記憶困難，甚至可能不像你想像的那樣計算密集。
假設我們有一個雜湊函式 $ H:{0,1}^\to{0,1}^n $ ，例如 SHA-256。現在我們可以構造 $ H’:{0,1}^\to{0,1}^n:m\mapsto H(M\parallel m) $ 對於一些固定的、預定義的消息 $ M $ 和在哪裡 $ \parallel $ 表示連接。注意如何 $ H’ $ 是一個普通的雜湊函式。
現在的任務是尋找 $ r_1\neq r_2 $ 這樣 $ \Delta (H’(r_1),H’(r_2))\leq n-d $ 對於一些工作因素 $ d $ 和 $ \Delta(\cdot,\cdot) $ 表示漢明距離。如果你有這樣的 $ r_1,r_2 $ ，這稱為接近碰撞，差異為 $ k:=n-d $ .
現在請注意，對於 $ d=n $ 這等於必須在 $ H’ $ , 可以及時完成 $ 2^{n/2} $ 以微不足道的記憶。用於此的算法是 Floyd 的循環查找（以查看它實際上可以用可忽略的記憶體完成）和 Pollard- $ \rho $ （這是最先進的，並且描述可以在Bernstein 的這個 PDF中找到，儘管它主要談論經典碰撞發現如何優於基於量子的發現）。另請參閱應用密碼學手冊 (PDF) 的第 9.7 節。
現在可以進行的第一個明顯優化是只考慮第一個 $ d $ 位 $ H’ $ 並嘗試在它們身上找到碰撞，即嘗試在它們身上找到碰撞 $ H’’:{0,1}^*\to{0,1}^d $ 在哪裡 $ H’’(m) $ 是第一個 $ d $ -位 $ H’(m) $ . 現在我們可以使用 $ 2^{d/2} $ 代替 $ 2^{n/2} $ 操作和沒有記憶。
現在，如果我們想進一步優化時間，我們可以注意到基本上所有的 $ H’ $ 是取值的獨立隨機變數 $ 0,1 $ 每個都有 50% 的機率，並且幾乎彼此獨立。所以我們基本上得到 $ d/2 $ 免費！此外，我們可以應用二項分佈的數學來估計2nd-pre-images所需的樣本量。此答案中對此進行了詳細說明，但 TL;DR 是 $ l:=\frac{2^n}{\sum_{i=0}^k\binom{n}{i}} $ 固定消息的第二個預映像需要消息，並且 $ \sqrt l $ “簡單”接近碰撞的消息。當然，這需要您希望的儲存空間，但可能比預期的要少。複雜性 $ \sqrt l $ 實際上在下面的第二篇論文中被證明為引理 1。
現在，如果我們想離開“簡單”策略的土地到這裡，有學術研究關於如何找到這樣的接近碰撞與Inna Polak 和Adi Shamir似乎是最新的貢獻（它也使用了一點記憶體），Mario Lamberger、Florian Mendel、Vincent Rijmen 和 Koen Simoens 的“Memoryless Near-Collisions via Coding Theory”（PDF）有點老。這些論文的算法的複雜性很難估計，但它提出了 $ n=160,k=33,d=127 $ 是用一台 PC 進行的。