Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

2 Answers 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.

share|improve this answer

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.

share|improve this answer
    
you are talking about something else, I wanted to know if my answers are correct or not ? :) Thanks –  alaamub Jan 28 '12 at 21:39
    
I provided the answer to your second question. First one is right. –  Jalaj Jan 28 '12 at 21:42
    
Great Thank you Jalaj :) –  alaamub Jan 29 '12 at 9:41

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.