block cipher algorithm

Question

Consider a block cipher algorithm with the properties: - Input, output block length is 64 bits and key size is 56 bits. - Given a key K, the key scheduling requires 2 microseconds. - After the key scheduling produces all subkeys, the encryption or decryption of a single 64-bit block requires 0.5 microseconds.

1. Compute the total time (in microseconds) required to encrypt 1 megabytes of data ?
2. Given two known values C and M such that C = EK(M) under an unknown key K, how many years (at most) are required to crack the cipher on a single computer (runs at 3 GHz)? Notes: 1 microseconds is 10^-6 seconds. 1 megabytes is 2^20 bytes.

---

My answer: 64-bit requires 0.5 ms (2^-1) ==> then 1-bit requires 2^-1/2^6 = 2^-7 .

now we need 2^-7 for each bit, how many for 1 megabytes of data:

1 megabytes = 2^23 bit ==> so 2^23 * 2^-7 = 2^16 + 2 microseconds.

now for the second part, consider the unknown key, 2^56 / 2 = 2^55

---

I'm wondering if my answers are correct ? could anybody please advice ?

Thanks - Alaa

Answer 1

I guess you are implementing $\mathsf{DES}$ algorithm. In that case, there is no provable security guaranteed. The security for all symmetric key algorithms have heuristic arguments and rely on the fact that there has been no successful attack on them. Otherwise, they are seen in ideal-cipher model, which is equivalent to random oracle model and hence prone to same issues.

So for the second question, I assume a perfectly secure encryption scheme in the Shannon's sense. Now you are trying to perform a chosen ciphertext attack, then the number of attempts you need to do is $2^{56}$ attempts which is the key size.

Answer 2

Thanks for using the homework tag.

This is certainly a description of DES, as Jalaj noted. The teacher here is asking you to compute the time required to break DES via exhaustive key-search. Given that you asked this question 7 months ago, I am going to assume the homework was already turned in and therefore I can give more info than I normally would for a homework question.

(1) If DES encrypts 8 bytes at a time, in 0.5 usec, then 1 Mbyte is $2^{20}$ bytes so we need $2^{20}/2^3 = 2^{17}$ encryptions. This therefore takes $2^{16}$ usec, which is a fraction of a second.

(2) Now we must try exhaustive key-search. There are $2^{56}$ possible DES keys, and you would need to try an expected $2^{55}$ of them on average, but in the worst case you would have to try all $2^{56}$. (This ignores speed-ups like key-complementation which reduces search-time by half.) Let's say you need to do $2^{55}$ key trials, each requiring the schedule to be run (2 usec), followed by a test-encryption to see if the key was right (0.5 usec). So $2^{55} \times 2.5 /10^6 \approx 90071992547$ secs, which is about 2800 years.

Of course we can go faster with specialized hardware, and we can parallelize this, and in fact we have. DES is therefore considered broken and should not be used for serious applications.