Question

Consider the following proposal to prevent DES from exhaustive key search under a known-plaintext attack. The secret key is k=k{1,k2}, where k1 is in (0,1) ^56 and k2 is (0,1) ^64. Let m be in (0,1) ^64 be the plaintext message. Encryption is defined as follows Ek(m)=DESk1(m) XOR k2

(a) Show that this proposal does not increase the work needed to break the encryption scheme E using brute force (exhaustive) search (that is, approximately 2^56 DES operations are still sufficient). You may assume that you have a few plaintext ciphertext pairs (m1,c1), (m2,c2), (m3,c3),...

(b) Now suppose the encryption algorithm is changed to Ek(m)=DESk1(m XOR k2)

Show that this scheme is again no more secure that DES.

Explain with equations.

Answer 1

k = { k₁ , k₂ }

C is Ciphertext and M = Plaintext

a.) C = E_k( M ) = DES_k1,k2 ( M ) = DES_k1 ( M ) XOR k₂ , where k₁ , k₂ are keys used for symmetric encryption and M is plaintext

Lets assume we have a few pairs of Plaintext-Ciphertext - (M₁ , C₁) and (M₂ , C₂)

C₁ = DES_k1 ( M₁ ) XOR k₂

C₂ = DES_k1 ( M₂ ) XOR k₂

If we do C₁ XOR C₂,

C₁ XOR C₂ = DES_k1 ( M₁ ) XOR k₂ XOR DES_k1 ( M₂ ) XOR k₂ ( a XOR a = 0 )

C₁ XOR C₂ = DES_k1 ( M₁ ) XOR DES_k1 ( M₂ ) ---- eq (1)

since we have C₁, C₂, M₁, M₂, we just need to do a brute force attack, using all possible combinations of

key k₁ and check whether eq(1) is satisfied or not. This is same as a brute force attack against DES.

On finding the key k₁ using brute force attack,

k₂ = C₁ XOR DES_k1 ( M₁ )

k₂ = DES_k1 ( M₁ ) XOR k₂ XOR DES_k1 ( M_1​​​ ) = k₂ ( a XOR a = 0)

since we have found both the keys k₁ and k₂, now any plaintext can be excrypted, and any ciphertext can be decrypted.

b.) C = E_k( M ) = DES_k1,k2 ( M ) = DES_k1 ( M XOR k₂ ) , where k₁ , k₂ are keys used for symmetric encryption and M is plaintext

Lets assume we have a few pairs of Plaintext-Ciphertext - (M₁ , C₁) and (M₂ , C₂)

C₁ = DES_k1 ( M₁ XOR k₂ )

C₂ = DES_k1 ( M₂ XOR k₂ )

If we perform a Bruteforce attack and try to Decrypt C₁ and C₂ using all possible keys k₁, and XOR them

D_k1( C₁ ) XOR D_k2( C₂ ) , then for the correct key k₁, this would be equal to,

= M₁ XOR k₂ XOR M₂ XOR k₂ = M₁ XOR M₂ , hence we can find out the key k₁, using a brute force attack,

Then, for k₂,

D_k1( C₁ ) = M₁ XOR k₂

Therefore D_k1( C₁ ) XOR M1 = M₁ XOR k₂ XOR M₁ = k₂ ,

since we have found both the keys k₁ and k₂, now any plaintext can be excrypted, and any ciphertext can be decrypted.