2
$\begingroup$

Some block cipher modes of operation use only encryption processes, such as CFB, OFB and CTR.

If doing multiple encryptions using them, will these encipherment schemes be vulnerable to Meet-in-the-middle attacks?

I'm asking this because there is no decryption process in these modes, so I can't imagine a Meet-in-the-middle happening because an inverse process (decryption) is needed

$\endgroup$
1
  • $\begingroup$ Also, you can upvote comments, too. Unfortunately, there is no downvote for the comments. $\endgroup$
    – kelalaka
    Feb 5 at 22:56

1 Answer 1

3
$\begingroup$

Consider double encryption with the CTR mode;

The first layer outputs a stream $o$ of the encryption of the counter block per NIST definition of the CTR document.

$$o_i = \operatorname{AES-CTR}(k_1,counter_i)$$

The second layer outputs as stream $\bar o$

$$\bar o_i = \operatorname{AES-CTR}(k_2,counter_i)$$

This means $c_i = m_i \oplus o_i \oplus \bar o_i$ and assuming that we have known-plaintext than we have

$$v_i \oplus o_i = \bar o_i$$ where $v_i = c_i \oplus m_i$

Now, the meet-in-the-middle-attack executes as;

  • First, make a table of encryption of the first counter with the first key candidates
  • X-or each of the results with the message block $v_1$
  • Now, male a table of encryption of the first counter with the first key candidates. You can copy the first table before x-oring with $v_1$
  • Sort and match and test key candidates with additional known-plaintext-ciphertext pairs.

The above is the base of the attack, however, there will be dense possible keys. Instead one can form the tables containing 2 for AES-128 and 4 for AES-256 or more blocks so that the possible candidates will be much lower. This will increase the table size by 4 or 8 times.

$\endgroup$
7
  • $\begingroup$ @IlmariKaronen that will require the double of the table size and double the ecnryption size. Isn't storing one and comparing the false positives with additional pairs better than this? $\endgroup$
    – kelalaka
    Feb 4 at 14:47
  • $\begingroup$ Yes it is, if you can get the false positive rate reasonably low. But with your parameters most candidate keys will be false positives (and some will be multiple false positives). Although, come to think of it, even if you do end up testing on average one extra block for each candidate to rule out false positives, it still takes no more time that making the table entries one block longer in the first place, and saves memory. So I guess you do want to keep the length of the table entries (approximately) equal to the key length. $\endgroup$ Feb 4 at 15:44
  • $\begingroup$ @kelalaka Does keeping the IVs of the two layers of CTR encryption secret prevents the attack you mentioned above? $\endgroup$ Feb 5 at 22:46
  • 1
    $\begingroup$ If you keep the IV secret one cannot set up the tables. And the cost is multiplied with $2 \cdot len(IV)$, this is what I see at this moment. This should be larger than brute force. However, if you are setting your on the secrecy of the IV, you are on the wrong path $\endgroup$
    – kelalaka
    Feb 5 at 22:49
  • $\begingroup$ Well, in your case, you can derive them from the user's password with some good passwords. In this case, the security is bounded by the strength of the password. $\endgroup$
    – kelalaka
    Feb 5 at 23:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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