雞/雞蛋問題：文件內部散列（包括散列）！可能？

事情是我有一個文件，有元數據的空間。我想在其中存儲一個用於完整性驗證的散列。問題是，一旦我存儲散列，文件和散列一起改變。雞/雞蛋問題：文件內部散列（包括散列）！可能？

我完全理解這是由md5/sha這樣的單向加密散列方法定義不可能的。

我也意識到存儲驗證數據的容器的可能性與作爲zip & co的內容分開。

我也意識到可以單獨計算哈希值並將其與文件一起發送，或者將其追加到末尾或客戶端計算哈希時忽略它的地方。

這不是我想要的。

我想知道是否有一個算法，它可能從散列本身的結果包含在其中的數據中獲得結果散列。

它不需要加密或滿足很多標準。它也可以基於一些啓發式方法，即在現實的時間量之後提供期望的結果。

我真的不是那麼喜歡數學，但是不可能有一些真正先進的指數模數多項式循環反向引用devision的東西，使這成爲可能？

如果不是，什麼（如果有）證明反對它？

我需要這個tis的原因是因爲我想（最終）存儲散列和MP4文件一起。其複雜的，但其他解決方案並不容易實施，因爲該文件走過一個糟糕的設計生產管道...

來源

2010-12-13 The Surrican

回答上述問題至少和這一個一樣難：[是否有MD5固定點，其中md5（x）== x？]（http://stackoverflow.com/questions/235785/is-there- an-md5-fixed-point-where-md5x-x） – 2010-12-13 19:30:14

@Greg：reread。 OP意識到這對MD5和SHA來說是不可能的。 – 2010-12-13 19:31:52

它不是重複的，因爲它處理一個特殊的加密散列，問題是不同的，因爲它需要與它本身的功能相同。我的問題是關於更多的算法，還有非crypticals以及包含該散列的數據。本身並不是干涉哈希。 – 2010-12-13 19:33:46

以某種方式可以用CRC來做到這一點。我過去所做的是在文件中留出4個字節作爲CRC32的佔位符，並填充零。然後我計算文件的CRC。

然後可以通過計算CRC多項式的伽羅瓦域中的數字來填充佔位符字節以使文件的CRC等於任意固定常數。。

（另外的可能，但此時沒有合適的細節你基本上需要計算（CRC_desired - CRC_initial）* 2 ^{-8 * byte_offset字節}在伽羅瓦域，其中byte_offset字節是字節的佔位符字節的數量和在文件的結尾）

注：按@ KeithS的評論這個解決方案不是防止對故意篡改。我們在一個項目中使用它作爲將嵌入式系統中的元數據與用於編程的可執行文件綁定在一起的手段 - 嵌入式系統本身並不直接瞭解用於對其進行編程的文件，因此無法計算出CRC或哈希本身 - 來檢測嵌入式系統和用於編程的文件之間的意外不匹配。（在後來的系統中，我剛剛使用了UUID。）

來源

2010-12-13 19:31:00

哇！ crc並不那麼辛苦，在考試期間在紙上做了一次：D讓我認爲通過... crc也是理想的（良好的錯誤檢測），並且在思考這個問題時我想到了+1 – 2010-12-13 19:34:16

catch是crc32是79,228,162,514,264,337,593,543,950,336比md5糟糕的一個散列。 32位校驗和很容易碰撞。 – 2010-12-13 19:40:39

它更糟，我意識到這一點。但它仍然是一個相當不錯的完整性檢查器，如果這是唯一的要求 – 2010-12-13 19:42:33

不，不可能。你要麼是一個單獨的散列ala md5sum文件，要麼嵌入散列僅用於文件的「數據」部分。

來源

2010-12-13 19:29:12

我知道這聽起來不合邏輯，否則可能會有。但你有什麼證據/理由嗎？ - 編輯：Jason S的回答暗示否則 – 2010-12-13 19:32:04

哈希需要完整的文件知識，幷包含在文件中。因此，您創建文件，創建不包含散列的文件的散列，然後將散列添加到更改其內容的文件中，從而再次散列文件會產生不同的散列。哈希將用作校驗和來證明文件沒有被篡改，所以在散列之後篡改文件（通過添加散列）將在給定適當的散列算法的情況下在接收端重新散列失敗。 – KeithS 2010-12-13 19:38:07

這取決於您對「散列」的定義。正如你所說的，顯然對於任何僞隨機哈希來說，這是不可能的（在合理的時間內）。

同樣顯而易見的是，你可以做到這一點當然有一些微不足道的「哈希」。例如，具有設置爲1的奇數比特的數據散列爲00，並且偶數個1的散列值爲11。散列不會修改1位的奇數/偶數，因此當包含散列時文件散列相同。

來源

2010-12-13 19:35:45 patros

是的，我在我的腦海中做了一個非常確切的例子，並且想到是否有可能將邏輯擴展到某種其他方式的證明，但沒有得到太多的結果：D – 2010-12-13 19:39:33

有無數的散列函數工作。有多少有用的是另一個問題... – patros 2010-12-13 20:46:24

方式the nix package manager做到這一點是通過計算你假裝哈希的內容在文件中的散列時就像20 x的一些固定的值，而不是文件的哈希值，然後你寫了這20 x哈希當你檢查散列時，你會讀到並忽略它假裝散列時只是固定值20 x的散列時

他們這樣做是因爲安裝包的路徑取決於散列如果散列是固定長度的，他們將其設置爲一些固定值，然後將其替換爲真正的散列值，並且在驗證時忽略它們放置的值並假裝它是固定值

，但如果你不使用這樣的方法是不可能

來源

2010-12-13 19:36:10

是的，這基本上發送散列分開，但在同一個文件中...我意識到這種可能性，但不幸的是不能做到這一點。我不確信它是不可能的，看看Jason S所說的。聽起來符合我的邏輯。 – 2010-12-13 19:40:51

所以這真的歸結爲找到一個固定點'H（h || m）= h'，至少在正常操作期間至少不應該有這樣一個固定點，但這是堆棧溢出，它根據定義異常確切地是異常的 – 2010-12-13 19:43:48

。 +1，尤其是最後一部分;） – 2010-12-13 19:47:55

我記得那是能夠在一個文本文件，該文件的CRC值嵌入一個老的DOS程序。但是，只有使用簡單的哈希函數纔有可能。
雖然理論上你可以創建任何類型的散列函數（給定足夠的時間或正確的算法）這樣的文件，攻擊者將能夠使用完全相同的方法。更重要的是，他會選擇：使用你的方法來獲得這樣的文件，或者只是爲了擺脫支票。

這意味着現在你有兩個問題，而不是一個，並且都應該以相同的複雜性來實現。這取決於你決定是否值得。

編輯：你可以考慮散列一些中間結果（如RAW解碼輸出，或某些特定於你的編解碼器）。通過這種方式解碼器可以擁有它，但是對於另一個程序來說，計算起來會更困難。

來源

2010-12-13 20:38:12 ruslik

很酷。這就是我需要的。事情是不會有攻擊者，文件通過生產管道處理，只有文件被傳輸，我將不得不在每一步都更新它，以傳遞一個長長的哈希來完整性。我只是想確保文件不會被損壞。 – 2010-12-13 22:09:27

當然，這是可能的，以多種方式。但是，它不能防止有意篡改。

例如，讓

hash(X) = sum of all 32-bit (non-overlapping) blocks of X modulo 65521.

讓

Z = X followed by the 32-bit unsigned integer (hash(X) * 65521)

然後

hash(Z) == hash(X) == last 32-bits of Z

這裏的想法只是，任何32位整數全等0模65521將有對X的散列沒有影響。然後，由於65521 < 2^16，hash has ar ange小於2^16，並且至少有2^16個值小於2^32與0模65521一致。所以我們可以將散列編碼爲不影響散列的32位整數。你實際上可以使用任何小於2^16的數字，65521恰好是最大的這種素數。

來源

2010-12-13 23:14:16

雞/雞蛋問題：文件內部散列（包括散列）！可能？

回答

相關問題