幫助對海綿排列進行密碼分析
我一直在研究和研究雜湊函式。到目前為止，我的研究使我進入了海綿結構。似乎海綿中用來攪動狀態的排列或多或少是安全的核心，以及容量/速率。因此，我一直在製作和打破玩具排列以更好地理解它們。我已經設法整理出一個我想要幫助或密碼分析指針的排列，因為我或多或少地沒有想法。
排列如下：
一個狀態被初始化為
(45 + sum(input_bytes)) * input_byte_length * 2對於列舉輸入字節中的每個索引和字節：
- 生成一個偽隨機字節：
(251 ** (state xor byte) % 257) % 256- 放
input_byte[index % input_byte_length] = psuedorandom_byte ^ (counter % 256)在蟒蛇中：
def permute_state(_bytes): byte_length = len(_bytes) state = (45 + sum(_bytes)) * byte_length * 2 for counter, byte in enumerate(_bytes): psuedorandom_byte = pow(251, state ^ byte, 257) % 256 _bytes[counter % byte_length] = psuedorandom_byte ^ (counter % 256) return _bytes我發現它似乎有一個相對於輸入字節的長度很長的周期。遞歸置換 1 個空字節的初始狀態在 255 個應用程序後循環，2 個空字節的初始狀態在 30 個幾千個應用程序後循環，我沒有等待初始狀態 3 個空字節完成，所以我不知道早在它循環之前。
有沒有辦法計算這種排列的周期？它似乎因初始化狀態的魔術表達式而有很大差異；在嘗試了各種表達式組合後，我發現了此處呈現的狀態，但不明白它在遞歸置換時如何/為什麼會影響循環長度。
當輸入大小為單字節時，我能夠反轉排列。但是，我嘗試將相同的策略應用於更長的長度是沒有幫助的。我最終得到了一個可能產生輸出字節的 256 個狀態/字節對的列表。我反轉 1 個字節排列的策略如下：
- 第一個輸出字節可以通過找到提供給模冪運算步驟的狀態 xor 字節的組合來反轉；
- 狀態是一個相對較小的搜尋空間，但是當輸入字節的長度為 時，猜測是有效的
1；狀態等於90 + input_byte_value- 循環遍歷 256 個字節並找到產生輸出的字節
但是，當我嘗試將這些步驟應用於輸入大小 > 1 的排列時，我發現我最終猜測狀態和輸入字節是相互獨立的，因此最終得到了 256 個不同的字節 + 狀態組合，這沒有什麼可做的對我來說。
我已經看到了像這樣的很棒的問題和答案，並且想知道是否有一種更具統計性的方法來對排列的狀態/輸入字節進行逆向工程。
這裡的排列公式讓我想起了線性同餘發生器或線性回饋移位寄存器等。這種排列是否適合任何具有特定已知弱點的通用算法？如果是這樣，我可以利用哪些弱點來恢復狀態或反轉排列？有什麼方法可以彌補上述弱點嗎？
編輯
到目前為止，在我的任何研究中，我都沒有考慮過平台字節序。順便說一句，我的平台是小端的。
在“狀態”或輸入的排列內部沒有應用填充。
請注意，每個置換函式呼叫初始化的“狀態”不是雜湊函式的內部狀態；散列函式的內部狀態是這種排列將操作的狀態，這裡提到的“狀態”是臨時的，可以更好地命名（如果有的話，歡迎提出建議）。“密鑰”可能是一個更準確的術語，儘管它是生成的而不是提供給呼叫的。
編輯 2
通過在生成偽隨機字節時包含下一個字節，我在遞歸應用時進行了更長周期的修改。我不確定這是否也解決了 CodesInChaos 指出的錯誤，但它增加了循環長度，這是我很好奇的事情：
psuedorandom_byte = pow(251, state ^ byte ^ (_bytes[(counter + 1) % byte_length] * counter), 257) % 256編輯 3
在進一步考慮 1 字節狀態的最簡單範例後，我意識到，對於 1 字節狀態，該函式基本上會產生相同的雜訊波。函式的不同輸入等效於在波形上選擇不同的起點，遞歸呼叫只是一次循環向前遍歷波形。
初始狀態可以通過記錄 2 ** 8 個輸出或整個循環來確定。從技術上講，對於一個字節的狀態，只知道一個輸出就可以讓您知道前一個輸出，並通過擴展了解之前的所有輸出。
但是，我不確定這種構想是如何擴展到多字節輸入狀態的。我不確定是否生成了相同的波，不同之處在於它開始的位置，或者不同的雜訊波是否由不同的字節組合產生。我推測後者，因為輸入字節的某些組合沒有相同的周期長度。我也不確定如何將這個想法擴展到擷取所有輸出字節並找到哪個種子產生了該特定順序。
我繪製了一個字節週期的雜訊波，如果有人好奇的話：
排列解釋（如評論區所述）：
我認為沒有辦法在不實際計算的情況下檢查這樣一個序列的周期。話雖如此，在密碼學中，這樣的長時間是不可取的。
偽隨機排列是可逆的。所提出的算法這一事實並不意味著它更接近於偽隨機函式，然後是偽隨機排列。
但是，我說“更接近”，因為偽隨機函式會在明顯小於之後進入一個循環 $ 2^N $ 應用程序。具有如此長的循環長度的行為將函式與隨機函式區分開來。
呈現的函式會產生有偏差的輸出。理想情況下，適當的散列函式應該將其輸出均勻地分佈在所有可能字節的空間中。意思是，如果您採集足夠的樣本，對於每個輸出索引，您應該會看到每個索引出現 256/256 個不同的符號。使用提供的函式對海綿執行我的指標會產生嚴重的偏差輸出：
Testing for byte bias... Byte bias: 32 [256, 90, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4]第一個數字表示輸出大小（32 字節）。下面的列表顯示了在每個索引處出現了多少不同的可能字節值。理想情況下，所有數字都應為“256”——這裡提供的函式除了第一個索引外，其他所有數字都有困難。
我將此歸咎於追求不必要的要求以產生一個在遞歸應用時循環遍歷所有輸入的函式。優先考慮這個不必要的“功能”是以犧牲其他實際必要的功能為代價的。
由 251/257 模冪創建的 s-box 的機率為 128/256 微分 (xor: 128 -> 253)。這是非常糟糕的，而且對於對稱基元來說，模冪運算很慢。差分密碼分析的框架可以應用於雜湊函式，如果設計更強大，這就是我的建議。然而，在這裡打擾它可能有點過頭了。
現在是（相對）優點。該函式本身實現了第一個原像電阻- 給定輸出，很難找到產生它的特定輸入。請注意，海綿結構本身將通過“壓縮”輸出時不輸出的容量字節來實現此效果。
然而，第二原像抗性，即找到可以產生給定輸出的任何輸入的能力，更難獲得，並且可以說是一個更重要的要求。但是，即使是經過深思熟慮的良好設計，只要通過一次數據傳遞，這可能是一項難以實現的壯舉。許多現實世界的雜湊函式利用數十輪來幫助實現這一目標。
狀態變數類似於遞歸擴散層，並且負責設計確實擁有的許多優點。我個人現在選擇異或和而不是加法，並通過將狀態字節添加到目標字節來產生非線性效應（混合異或/模加法會產生非線性效應）。
理想情況下，計數器就像一個隨機數，可以分解一個相同的字節串（即 0000000…0）。正如偏置輸出所證明的那樣，它在這裡並不是特別有用。但這仍然是一個很好的技術，需要牢記。