使對密碼雜湊的攻擊不那麼經濟
考慮到記憶體與執行時之間的權衡，也許是一個關於復雜性的抽象問題，我想知道是否有可能只限制任一極端方法以達到最佳效率，從而使對雜湊的攻擊不那麼經濟。
背景
我參加了關於最近出版的研討會，Scrypt is Maximally Memory-Hard 1，作者專注於 scrypt，這是一個由 Percival 設計的簡單候選記憶硬函式 (MHF)，並在 RFC 7914 中進行了描述。
從摘要：
我們證明了 scrypt 是最佳的記憶硬，即它在並行隨機預言模型中的累積記憶複雜度 (cmc) 是 $ \Omega(n^2 \cdot w) $ ， 在哪裡 $ w $ 和 $ n $ 分別是底層雜湊函式的輸出長度和呼叫次數。
另外在介紹中：
在這項工作中，在第 5 節中，我們還證明了一個最優的 $ \Omega(n^2 \cdot w) $ 抽象scrypt評估的遊戲的並行累積 pebbling 複雜度的下限：我們考慮長度路徑 $ n $ ，並且對手必須鵝卵石 $ n $ 該圖上隨機選擇的節點，其中第 i 個挑戰節點僅在挑戰節點出現時才顯示 $ i − 1 $ 是鵝卵石的。這已經給出了一個最佳的 $ \Omega(n^2 \cdot w) $ 下限 $ cc_{mem} $ 對於只允許儲存整個標籤但不能儲存其任何功能的對手的scrypt 。
據我了解，攻擊者有可能製定一種策略，在記憶體和執行時復雜性之間進行適當的折衷，例如 $ X_0, X_1, \dots , X_{n−1} $ 僅儲存偶數 $ i $ ，因此將最壞情況下的記憶體使用量減半，同時也具有最壞情況下的執行時間，但總記憶體·時間成本與以前相同。
問題
對於單個系統，我想說硬體成本與 CPU 性能或板載記憶體大小是非線性的，即代表任一頻譜極端的組件可能會成倍地昂貴。因此，為了降低迴報率或增加攻擊者期望的必要資本投資，我們可能希望降低中端硬體的可用性，否則這些硬體將是最經濟的使用。
為了視覺化我的基本想法，我在下麵包含了一個粗略的圖表，其中 x 和 y 軸是記憶體和時間使用情況。在綠點處與紫色線相交的橙色矩形的體積表示任何配置的總記憶體·時間成本，例如，如果您有足夠的記憶體，則可以在 $ \frac{1}{2} $ 時間單位。我想知道是否可以製定一個問題，使記憶體·時間成本遵循紅色曲線，從而將對手進一步推向硬體極端，以實現最佳的記憶體·時間成本，同時損害硬體成本。
也許你們中的一些人可能知道從經濟角度觸及最佳有效結果的研究，即考慮硬體投資、運營成本、每個解決方案的預期回報。我想這聽起來像是使用需要工作證明的加密貨幣時的礦工優化問題，但我對激勵攻擊者或詐騙者的經濟學更感興趣。
@misc{cryptoeprint:2016:989, author = {Jo\"el Alwen and Binyi Chen and Krzysztof Pietrzak and Leonid Reyzin and Stefano Tessaro}, title = {Scrypt is Maximally Memory-Hard}, howpublished = {Cryptology ePrint Archive, Report 2016/989}, year = {2016}, note = {\url{https://eprint.iacr.org/2016/989}}, }基本上
是否有任何函式可以使記憶體或執行時方法的線性組合效率低於僅致力於記憶體或計算速度優化，從而總是使中端硬體不適合有利可圖的攻擊？
我一直在思考這個問題，但沒有一個令人滿意的答案：這似乎是一個從未在文獻中真正考慮過的問題（至少，在理論密碼學社區中沒有）。
順便說一句，我今天早上剛剛檢查了 ePrint 檔案，偶然發現了今天添加到檔案中的這篇論文，它完全關注你的問題。它引入了一種新的複雜性度量，它解釋了時間-記憶體權衡不會相對於硬體成本線性擴展的事實。我還沒有詳細閱讀它（我打算），但作者是記憶硬函式方面的主要研究人員之一（作者的子集開發了分析 MHF 的理論模型，描述了對 Argon 和 Balloon 的最著名的攻擊，給出了新的結構，並證明了 Scrypt 的最大記憶硬度）。應該值得一讀。