如何進行逆向工程算法？

Question

我想知道如何去顛倒一個算法，如用於存儲登錄名或密碼的算法。

可以說我有數據量，其中：

7262627 -> ? -> 8172 

5353773 -> ? -> 1132 

等，這僅僅是一個例子。或者說一個轉換成另一個的十六進制字符串。

&h8712 -> &h1283或類似的東西。

我該如何着手弄清楚算法是什麼？一個人從哪裏開始？

你會開始嘗試不同的班次，xors和希望有什麼突出的東西嗎？我確信有更好的方法，因爲這看起來像在黑暗中刺傷。

反向工程這種算法是否可行？

對不起，如果這是一個愚蠢的問題。感謝您的幫助/指示。

Answer 1

反向工程這種算法是否可行？

有可能與一個有缺陷的算法和足夠的加密/未加密的對，但一個精心設計的算法可以消除這樣它在所有的這種可能性。

Answer 2

也許，你不能。假設轉換功能是已知的，像

function hash(text): 
    return sha1("secret salt"+text) 

但「祕密鹽」不知道，是保密性強的（一個非常大的，隨機整數）。即使是非常大量的純文本crypttext對，也絕不能強制使用祕密鹽。實際上，如果使用的精確哈希函數是已知的兩個同樣強大的函數之一，那麼您甚至不可能在使用哪一個哈希函數之間得到一個好的猜測。

Answer 3

有一些東西的人嘗試：

• 獲取源代碼，或拆解的可執行文件。
• 猜測，基於其他人使用的散列函數。例如，由32個十六進制數字組成的哈希可能是MD5的一個或多個重複，並且如果您可以獲得單個輸入/輸出對，則很容易確認或反駁（儘管參見下面的「鹽」）， 。
• 統計分析大量輸入和輸出對，查找任何類型的模式或相關性，並將這些相關性與系統設計者可能使用的已知散列函數和/或可能操作的屬性相關聯。這超出了單一技術的範圍，並進入了通用密碼分析領域。
• 問問作者。安全系統通常不依賴於他們使用的哈希算法的保密性（如果他們使用哈希算法，通常不會保密）。然而，你給出的例子很小，密碼的安全散列總是涉及鹽，而你顯然不會。所以我們可能不會談論作者有信心這樣做的系統。

對於輸出僅爲4位十進制數字的散列，只需構建一個包含每個可能的7位輸入的表格及其散列值，即可對其進行攻擊。然後，您可以反轉該表，並進行（一對多）去散列操作。你永遠不需要知道散列是如何計算的。你如何獲得輸入/輸出對？那麼，如果外人可以以某種方式指定要散列的值，並查看結果，那麼就有了所謂的「選定明文」，並且依賴於此的攻擊是「選定的明文攻擊」。因此，如果以允許選擇明文攻擊生成大量輸入/輸出對的方式使用7位數字 - > 4位數字散列，則其實非常微弱。我意識到這只是一個例子，但它也只是扭轉它的一種技術的一個例子。

請注意，對散列進行逆向工程並實際反轉散列是兩件不同的事情。你可能會發現我使用的是SHA-256，但是這並不能幫助你將其反轉（即給出一個輸出，計算出輸入值）。沒有人知道如何完全反轉SHA-256，儘管當然總是有彩虹表（見上面的「鹽」）<conspiracy>至少沒有人承認他們這樣做，所以對你我都沒有用處。 </conspiracy>

Answer 4

在黑暗中刺傷會使你精神錯亂。有一些算法，根據目前的瞭解，你不可能希望推斷現在和宇宙[預測]結束之間的內部工作，而不知道確切的細節（可能包括私人密鑰或內部狀態）。當然，其中一些算法是現代密碼學的基礎。

如果你事先知道有一個要發現的模式，有時候有辦法解決這個問題。例如，如果數據集包含相差1多個輸入值，比較對應的輸出值：

 
7262627 -> 8172 
7262628 -> 819 
7262629 -> 1732 
... 
7262631 -> 3558 

這是相當清楚的（給定了幾分鐘，一個計算器），當加1，輸入增大輸出增加913模8266（即簡單的linear congruential generator）。

Differential cryptanalysis是用來分析密碼分組密碼的強度，依靠對於其中密碼算法是已知的類似但更復雜的想法比較現代的技術，但它承擔的私鑰不。考慮一個位彼此不同的輸入塊，並通過密碼來追蹤該位的影響，以推斷每個輸出位可能「翻轉」的可能性。

解決這類問題的其他方法是查看極值（最大值，最小值），分佈（導致frequency analysis），方向（數字總是增加？減少？）和（如果允許的話） ）考慮數據集被發現的上下文。例如，某些類型的PIN碼的總是包含重複的數字，使他們更容易記住（我不是說PIN碼可以一定是推斷從別的 - 只是一個重複的數字是一個少一位數字擔心！）。