如何計算無序集的雜湊
假設我有一組元素，具有已知的散列（例如 SHA-2）。如何計算集合的雜湊？我的意思是一個無序的集合，所以元素的順序是不確定的，並且在確定集合的散列時不會起任何作用。
從理論上講，應用於雜湊的任何交換操作都應該沒問題，但我有強烈的感覺，將它們全部異或在一起是非常不安全的。攻擊者可以將一個元素添加到集合中以產生雜湊衝突，儘管找到具有所需雜湊的元素與破壞整個集合的雜湊一樣困難。
有什麼比將元素排序到列表中、計算它們的散列然後計算散列列表的散列的簡單解決方案更好的解決方案嗎？
如果 Merkle 樹基於某種元素的排序，我認為它們在這裡無濟於事。
在給定元素的雜湊值的情況下，形成無序集的雜湊值的一種眾所周知的技術是按字典順序對雜湊值進行排序，按此順序連接它們，然後對結果進行雜湊處理。原始集合中元素的順序不會影響結果，這顯然繼承了散列的屬性（抗碰撞、抗原像、ROM 中的安全性）。讀者可以自行決定這是否是對元素進行排序的簡單方法。這有嚴重的缺點：必須儲存雜湊值；這不是線上算法。
這可以通過對集合元素的散列進行異或來解決，但是（正如問題中所推測的那樣）這給出了一個弱散列。特別是，如果雜湊是 $ b $ -位，然後在多一點之後 $ b $ 我們可能會找到的元素 $ b $ 線性獨立的散列（按位異或），然後通過對其中一些散列進行異或運算，我們可以形成所需的任何值；這是第一原像攻擊。
更新：Meir Maor 的評論指出了這篇非常相關的論文：Dwaine Clarke、Srinivas Devadas、Marten van Dijk、Blaise Gassend、G. Edward Suh，增量多集散列函式及其在記憶體完整性檢查中的應用，在AsiaCrypt 2013的會議記錄中。它為多重集建構散列函式，它們的結果直接應用於集合，它們是多重性限制為的多重集 $ {0,1} $ .
基於他們的 MSet-Mu-Hash 結構，以下工作不需要排序，並且可以使用常量記憶體計算，因為集合元素的雜湊可用於線上算法：
- 選擇一個不折不扣的 2049 位公共素數 $ p $ 和 $ (p-1)/2 $ 也是素數，例如 $ p=\lfloor2^{2047}\pi+494382\rfloor $ ; 我們假設離散對數模 $ p $ 很難，大約與破壞 SHA-256 抗碰撞性一樣多。
- 展開每個給定的 SHA-256 雜湊 $ H_i $ 將集合中的一個元素轉換為 2048 位位串 $ S_i $ ，例如作為 $ S_i=\operatorname{H}(H_i|K_1)|\operatorname{H}(H_i|K_2)|\operatorname{H}(H_i|K_3)|\operatorname{H}(H_i|K_4) $ 在哪裡 $ \operatorname{H} $ 是 SHA-512 和四個 $ K_j $ 是短的不同的公共任意常數。
- 計算積模 $ p $ 的 $ S_i $ （根據大端約定轉換為整數）；這可以與上一步一起完成。該產品將 $ 1 $ 為空集。
- 使用 SHA-256 對產品進行雜湊處理（根據 big-endian 約定轉換為 2056 位字元串）以生成最終結果。
注意：為了避免在某些假設的工作量證明協議（見此）中的某些攻擊，無論是在排序時還是在使用模乘組合時，在初始散列之上使用的一個或兩個散列應該是不同的（例如使用不同的初始常數）。