SHA-256 初始 36 位及更多位的部分衝突

我很幸運，通過蠻力發現了兩條不同的消息，它們的SHA-256雜湊值在前 9 個 36 位十六進製字元中發生衝突，我們稱之為hash-prefix.

鑑於Birthday Problem，我必須將散列放在一起2^18，2^(36/2)以便成功找到具有散列前綴衝突的兩條消息的機會將增加到大約 50%。我確實是通過逐漸將每個雜湊的前綴與另一個進行比較來找到它們的。這個過程並沒有花太長時間，但這就是我幸運的原因。

我想找到 2 條不同的消息，這些消息在散列後碰撞超過 36 個初始位。在比較雜湊時，您能幫我想出一個更好的策略嗎？

這是我比較雜湊前綴的方法：

class FindPartialCollision {
private:
   ...

public:
   ...

   bool compare(vector<string> sv, int n_Hashes) {
       for (int i = 0; i < n_Hashes; i++) {
           for (int j = i + 1; j < n_Hashes; j++) {
               if (sv.at(i) == sv.at(j)) {
                   cout << "COLLISION FOUND." << endl;
                   return true;
               }
           }
       }
       cout << "No collision found." << endl;
       return false;
   }

   ...
}

請注意，它僅包含從每個消息的每個 SHA-256 雜湊中獲取vector<string> sv的初始字元字元串，其中是要比較的所需長度。x``x

例如，如果我要查找一對消息，其雜湊值在前 10 個十六進製字元中發生衝突，則n_Hashes傳遞給此方法的值將是16^(10/2) = 2^(40/2) = 2^20 = 1 048 576，這已經太大並且會導致巨大的時間複雜度。

非常感謝任何幫助，我很抱歉這個業餘問題。

實際上，這種程式問題更適合stackexchange。

但是，要回答您的問題，有兩種明顯的方法可以加快碰撞搜尋：

• 使用雜湊表；也就是說，不要將所有內容都放在一個大列表中，而是將它們劃分到（例如）1024 個不同的列表中（這樣您就知道兩個不同列表中的項目不是“匹配”）。而且，假設您知道 SHA256 已經很好地分佈，您可以（例如）使用 SHA256 雜湊值的前 10 位選擇放置特定雜湊的雜湊表條目；這樣，您將永遠不必顯式比較前 10 位不同的兩個雜湊值。這將您需要進行的比較次數減少了 99.9%。當然，您將根據您擁有的資源調整雜湊表的大小（即它包含多少條目）。
• 使用排序算法；即使用好的算法將雜湊值升序排序；這樣，任何“接近”的匹配都將是相鄰的，因此這是您需要進行的唯一比較。一個好的排序算法 $ N $ 元素可以在 $ O(N \log N) $ 時間，因此這比單獨比較每個元素要快得多。

我不知道在您的情況下哪個會更好；但是它應該給你一些思考。

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