Tell me more ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.
up vote 0 down vote favorite
1

Let $E_k$ : {0,1}$^l$ be a block cipher encryption function with block-size $l$ and key-length $n$.

In class, we saw that a double encryption with two independent keys $E{}'_{k_1k_2}(x)$ = $E_{k_1}(E_{k_2}(x))$,

can be brute-forced in $O(2^n)$ time and $O((l + n)2^n)$ space using the meet-in-the-middle attack:

create a table with $2^n$ entries mapping keys of length $l$ to entries of length n by encrypting the known plain text $x$ with all possible keys $k_2$, then search the table by decrypting the corresponding cipher text $c$ using all possible keys $k_1$.

Suppose you only have $O((l + m)2^m)$ space (where $m < n$), Give an algorithm to break the double encryption in time $O(2^{2n-m})$.

I am stuck for days, can't figure out the trick that will allow such an efficient algorithm.

Any ideas? Tips? Hints?

This is homework of course(Tag not exists for some reason).

ADDED:

Is it sufficient to show that if we choose smaller $n$ the encryption will be broken with non neglect-able probability? Or I must show an algorithm that ALWAYS brake the encryption?

share|improve this question
1  
Are you sure about the $O(2n)$ time in your given algorithm? Shouldn't this be $O(2·2^n) = O(2^n)$? – Paŭlo Ebermann♦ Jan 6 at 12:48
The reason for the homework tag not existing were discussed in Asking homework questions. – Paŭlo Ebermann♦ Jan 6 at 12:50
Correct, fixed :) – Yoni Hassin Jan 6 at 12:50
1  
If you can't fit a full table, why not try using a smaller table? – Antimony Jan 7 at 7:29
1  
@YoniHassin, I think the info you added needs to be asked to the professor. – mikeazo♦ Jan 7 at 14:24
show 3 more comments

1 Answer

up vote 3 down vote accepted

Hint: suppose someone told you $n-m$ bits of $k_2$; how much time/space would a meet-in-the-middle attack take then?

share|improve this answer
It will take $O(2^{2n-m})$ but with low (non neglectable) probability, while using $n$ entries will have very high probability (almost 1). – Yoni Hassin Jan 7 at 16:23
1  
Go through it again: if you know $n-m$ bits of the key, it'll take less than $O(2^{2n-m})$ time; how much exactly? How much space? And, once you have that, how do you extend that observation to the case where you weren't given the hint? – poncho Jan 7 at 16:27
1  
Again, do the exercise: if $k_1$ has $n$ unknown bits, and $k_2$ has $m$ unknown bits, how much time would it take to recover the unknown bits? How much space? Once you have answered that question, it should be simple to use that as a black-box to solve the case where both $k_1$ and $k_2$ has $n$ unknown bits. – poncho Jan 7 at 18:45

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.