Collision-Resistance
手動檢查雜湊函式時需要比較多少個十六進制數字？
我有時會在將大文件從一個地方傳輸到另一個地方後對大文件執行 sha256sum，然後只瀏覽雜湊輸出以驗證它是否正確。但是，我通常只看第一個/最後 5 或 6 個十六進制數字並稱其為足夠好。
我知道碰撞的機率大約是 1 / 2^64，但是“接近碰撞”的機率是多少？例如，只有一個或兩個十六進制數字不同。
作為一個相關主題，如果你有一個二進制序列並且只改變一個位，你會得到一個完全不同的雜湊，對嗎？那麼隨機錯誤是否有可能導致幾乎相同的雜湊？我知道 MD5 已被“破解”，因此惡意代理可以將任何必要的數據附加到文件中以使其具有相同的雜湊輸出——但這是否在任何合理的隨機發生的可能性範圍內？
編輯：這個話題在下面引發了一些討論，這些討論與我原來的問題的範圍一樣（如果不是更多的話！）資訊豐富。話雖如此 - 我只是指使用雜湊函式作為文件完整性檢查，而不是作為防止攻擊的保護。
手動檢查雜湊函式時需要比較多少個十六進制數字？
如果您確實希望應用散列函式的完整安全保證：所有這些。
我通常只看第一個/最後 5 或 6 個十六進制數字並稱其為足夠好。
這有效地將散列函式的安全性降低到僅輸出 10-12 個十六進制數字（即 40-48 位）的散列函式的安全性，我們可以很容易地在大約 $ 2^{24} $ 評估是很容易做到的。
“接近碰撞”的可能性有多大？例如，只有一個或兩個十六進制數字不同。
正如在這個答案中所討論的那樣，最多的機率 $ t $ 兩個雜湊之間的位差異 $ n $ 位輸出長度為
$$ p_t=\sum^t_{k=0}{n\choose k}2^{-n} $$這意味著你需要大約 $ \sqrt{1/p_t} $ 評估以得出所需的接近碰撞。可以在此答案中找到找到這些值的策略（包括低記憶體方法）。