Cryptography筆記10 - Exhaustive Search Attack on DES

Exhaustive Search Attack

定義: 藉由獲得n pairs of PT and CT，找出加密這些pairs的block cipher key k。

不過首先我們怎麼確定這些pairs是同一個key k加密來的?

如果我們先假設DES是一個完美的加密，則每個key in key space K (56bits)都是一個random invertible function，總共有2^56個(unique) random functions:

所以每一個PT/CT pair，極可能只能搭配一個unique DES function達成，key unique的機率 >0.995。
怎麼證明上面的statement?

我們相當於要證明存在k' != k 使得兩者都能對同一個message m加密後得出c的機率很小。

探討所有key k' in K(從000...00 到 111...11)，則對某固定key k in K來說，因為cipher text是64 bits，且ciphertext可以說是隨機分布的(uniformly distributed in 64 bits cipher text space)，所以某k' 丟入DES(k',m)剛好得出與DES(k,m)同樣結果的可能性 <= 1/(2^64)，又此k'可能有2^56種可能，所以對某固定k來說，存在k' != k 使得兩者都能對同一個message m加密後得出c 的機率 <= 2^56 * 1/(2^64) = 1/256，意即有兩個key可以把m map成同一個c的機率為1/256

所以反過來說，c = DES(k,m)且k為unique的機率 = 1 - 1/256 ~= 99.5%，這是對理想的DES來說，對不完美的DES當然此機率更大了。

如果獲得2個pairs of PT/CT，則此key unique的機率可以證明 非常靠近於1。

注意以上的證明也對AES適用。

所以要破解DES只要搜索2^56種key可能就好，對硬體突飛猛進來說，這太容易被破解了。exhaustive search on DES key 比攻擊AES簡單多了，主要原因在於DES key space太小，才56 bits。現在DES可以簡單幾天內就被exhaustive key search破解。

目前看來，key至少要90 bits才能避免這類攻擊。

3DES - 加強版DES

利用3個key來加密，所以key space = 2^168 bits (56*3)，不過加密時間也變成DES的三倍，但至少是能避免exhaustive key search。

為何不用2DES? 時間縮短成DES兩倍。因為會有另一個攻擊稱為meet-in-the-middle attack，所以2DES 安全性等於 DES，沒有改進。

Encryption scheme如果等式兩邊同時apply decryptor，可以改寫成以下:

這樣exhaustive search的時間降了一半的key space!!! 因為我們現在只要進行兩個56bits search運算量，而非112 bits search:

可以先把所有的E(k2,m)都找出來，這個只會有2^56可能，如果加上sorting的話，就是2^56 * log(2^56)，接這從右至左一 一嘗試D(K1,c)，是否能找出matching m，如果找到那就等於找到了兩組加密的keys。

實際analysis:

DESX

另外一個課程中有提到的加強版DES，可以抵擋exhaustive key search attack，有興趣可以了解一下。