Suppose Dr. Smart has designed a 4DES cipher which encrypts data m in the follow

Question

Suppose Dr. Smart has designed a 4DES cipher which encrypts data m in the following way: c= Dk4(Dk3(Ek2(Ek1(m)))), where E and D denote the encryption and decryption operation of DES. To break this cipher and learn the key pair <k1,k2,k3,k4> from <m,c> pair, a brute-force method is to try all possible combinations of <k1,k2,k3,k4>, but this requires about 2^224 trials which is too much. Design a more practical attack for finding the paor of keys used with significantly less effort. You can assume that the attacker is able to obtain a few <m,c> pairs.

Explanation / Answer

Let’s say for concreteness that our DES has a 56-bit key K, operating on blocks of 64 bits,
although that nowadays would not give a secure enough hash. Let’s chop our plaintext P
(that we want to hash) into blocks of 64 bits, P1, P2, . . . , Pm. Set a block C0 of 64 bits in some
arbitrary way, say, all zeros. Then let Ci := EK(Ci1 Pi) for i = 1, 2, . . . ,m, recursively,
where EK is the DES encryption function with the key K, and is bitwise addition (mod
2). Finally, h(P) := Cm is the output of the hash. (The CBC mode of operation does the
same, except that there the resulting ciphertext is all of C1,C2, . . . ,Cm.)
(This is fast to compute because DES is fast to compute. It’s one-way and strongly collision
free because of the good cryptographic properties of DES, namely that it resists even a
known plaintext attack. Here we ignore the fact that the 56-bit key is actually too short
nowadays.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.