Cryptography
- cryptanalysis block-cipher meet-in-the-middle-attack
- Updated Sun, 26 Jun 2022 17:16:59 GMT
-
Break double encryption
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.
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?
Solution
Hint: suppose someone told you $n-m$ bits of $k_2$; how much time/space would a meet-in-the-middle attack take then?
Comments (3)
- +0 – It will take $O(2^{2n-m})$ but with low (non neglectable) probability, while using $n$ entries will have very high probability (almost 1). — Jan 07, 2013 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? — Jan 07, 2013 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. — Jan 07, 2013 at 18:45