One-Time-Pad

一次性填充隨機性是否有助於暴力攻擊?

  • January 21, 2017

我知道,嘗試暴力破解使用一次性密碼編碼的消息會導致生成每條可能的消息。Wikipedia 的範例是使用鍵“XMCKL”解碼“EQNVZ”會產生“HELLO”,但鍵“TQURI”會產生同樣合理的“LATER”。

然而,一個“更隨機”的一次性墊被認為比“不太隨機”的一次性墊更好。所以有一種方法可以比較兩個墊子的隨機性,對吧?

如果密鑰 TQURI 被“測量”為不如 XMCKL 隨機,那麼墊盡可能隨機的可能性是否意味著 HELLO 是更有可能的消息?

假設一條編碼消息僅包含簡單的英語。一條 50 個字元的消息可以使用相同數量的可能密鑰解碼成大量可能的消息。當我們逐個字元解碼時,我們可以丟棄任何不明顯的英語內容。這仍然會留下大量可能的消息(我不知道如何估計有多少),但我們會同時增加所謂的隨機密鑰的長度

如果一個可能的解碼使用 GJXWHELZYHWLXE 鍵在 DAWN 開始 ATTACK,而另一個解碼使用 AABBCCDDEEFFGG 鍵開始 SEND MONEY NOW,我們可能會丟棄後者,因為 pad 永遠不會使用這樣的重複鍵。

因此,規則是只保留“最隨機”鍵的英文解碼。(我不知道如何選擇這樣的截止點。)這可能會將潛在資訊減少到合理數量的候選人嗎?(我想更長的鍵可以讓你更自信地確定它們的隨機程度,但我不知道如何計算那種東西。)

另一種可能性是只保留解析得相當好的消息。BATALION ALPHA ATTACKS AT DAWN 是有道理的,但 SUNSET DOGGY COOKIE FLOOR 可能會被丟棄。

即使單個消息生成大量具有足夠隨機密鑰的解碼候選者,一系列消息似乎也會建立一個上下文,提示哪些解碼是有效的。例如,如果消息 1“平等地”(因為密鑰隨機性)解碼給候選

A. WHEN DO WE ATTACK
B. SHOES GREENER ARE
C. MASHED ROOF CARRY

並且消息 2 回复“同樣”解碼為

A. ATTACK AT DAWN
B. LEAVE PARLANCE
C. DOG ALPHA MODE

那麼似乎“對話”可能是我們何時攻擊/攻擊黎明。(當然,回復也會解碼為 ATTACK AT 0100、ATTACK AT 0200、ATTACK AT DUSK 等,但我們正在選擇具有“最隨機”鍵的解決方案。即使 ATTACK AT 0100 和 ATTACK 的鍵在 DUSK 以同等程度的隨機性捆綁在一起,知道攻擊迫在眉睫仍然很有用。)看起來你擁有的資訊越多,就越容易猜測(或應用一些人工智慧)正在討論的一般執行緒。

因此,修改後的蠻力方法將通過 (1) 丟棄消息中的無效和無意義的內容,(2) 丟棄不符合所需隨機性門檻值的密鑰的解碼,以及 (3) 丟棄不符合隨機性門檻值的解碼,來修剪可能但不太可能的解碼。 t 適合消息間上下文。必須在輸入每個新消息字元時進行修剪,以避免在無用的分支上浪費時間和空間。

這種方法還會留下天文數字的可能解碼嗎?或者它是否可以將候選人減少到一個足夠小的數量,以至於 NSA 電腦可能願意嘗試預測(以某種程度的可信度)一組編碼消息可能在談論什麼?

維基百科關於蠻力的條目說一次性攻擊

…最終會揭示每一個…可能的字元串,包括正確的答案——但在所有給出的答案中,沒有辦法知道哪個是正確的。

但似乎有些答案比其他答案更有可能被計算出來。是否可以將可能的答案集減少到一個合理的數量,尤其是在考慮到所需密鑰的隨機性時?

混淆可能來自使用術語“隨機性”而不是“密鑰使用 N 個不同字元的機率”。 一組可能的鍵使用的字元越多,隨機選擇的鍵往往具有的字元就越多。 換句話說,隨機選擇一個從 A 到 Z 的 14 個字元的鍵後,該鍵可能會使用大約 11 個不同的字元。密鑰中只有 1 或 2 個不同字元的情況很少見。

這是使用 A 到 Z 的 1000 萬個隨機 14 個字元的鍵:

每個鍵的字元

超過 300 萬個鍵使用了 11 個字元,而只有 56 個鍵使用了 5 個字元。沒有使用 4 個或更少字元的鍵。超過 130,000 個鍵沒有重複字元並且全部使用了 14 個。僅嘗試具有 10 到 12 個不同字元的鍵仍然可以得到超過 78% 的鍵。

因此,的,跳過最不可能的鍵將減少您的搜尋時間,並且可能不會跳過正確的答案。對於剩餘的情況,您仍然需要進行大量計算。

引用自:https://crypto.stackexchange.com/questions/43068