1
$\begingroup$

On reading the accepted answer to this question, I was wondering whether a Meet In The Middle attack could be applied to the suggested construction (below), and if not, then what is the effective key strength of combining two 256 bit ciphers in such a way? If I understand correctly, the Tahoe-Lafs 100 Year Cryptography project uses a similar construction.

$C=P\oplus K^1\oplus K^2$, where $C$ is the ciphertext, $P$ is the plaintext and $K^1$ is the key stream of one cipher and $K^2$ is the key stream of the other cipher (courtesy of Maarten Bodewes).

$\endgroup$
5
  • 2
    $\begingroup$ Surely this should work by brute-forcing and table'ing $P\oplus K^1$ and then checking for matches with brute-forced $C\oplus K^2$ (ie consider $E^1(M)=M\oplus K^1$ and $E^2(M)=M\oplus K^2$ as ciphers that are applied as $E^1(E^2(M))$) $\endgroup$
    – SEJPM
    Commented Jul 20, 2017 at 17:24
  • $\begingroup$ @SEJPM would you mind posting that as an answer? $\endgroup$
    – hunter
    Commented Jul 21, 2017 at 10:24
  • $\begingroup$ It's not really useful to discuss whether the security level of combined stream ciphers like that exceeds 256 bits: that security level is so high that anything beyond it is inconsequentially inconceivable. The real reason to use a composition like this is not to raise the security level, but to hedge against a cryptanalytic breakthrough in one of the stream ciphers. For example, if someone found a technique for breaking AES256-CTR, it is unlikely that the same technique would apply to Salsa20, which has a totally different design. [Adapted from a part of an otherwise wrong answer I wrote.] $\endgroup$ Commented Jul 22, 2017 at 4:01
  • $\begingroup$ @SqueamishOssifrage It is indeed useful for me in terms of learning about the practical consequences of MITM attacks - the example I gave uses a ubiquitous key size, but the question is generic and could be applied to any key size... I'm more interested in the implicatons of the construction. I'm well aware of just how ridicuously excessive a 256 key is, and the motivations for combining ciphers to mitigate against future breaks, but that's not what I was asking. $\endgroup$
    – hunter
    Commented Jul 22, 2017 at 11:30
  • $\begingroup$ Sure—that's why I downgraded to a comment. More on-topic, perhaps: Suppose $K^i = S_i(k_i)$ for some short key $k_i$, say 256 bits, and some PRG $S_i$, say AES256-CTR or Salsa20 with zero nonce. MITM needs time & space for $2^{256}$ encs & $2^{256}$ decs, so area*time cost is $2*2^{256}*2^{256}=2^{513}$. A parallel machine with $2^{256}$ AES circuits, $2^{256}$ Salsa20 circuits, and negligible memory takes $2^{256}$ time—also $2^{513}$ AT. For multi-target attacks, rainbow tables reduce cost of at least one success. Exercise: Can you adapt RTs to the MT MITM scenario to make it cheaper? $\endgroup$ Commented Jul 22, 2017 at 14:14

1 Answer 1

1
$\begingroup$

Let $K^1,K^2$ be the key-streams generated by $k_1,k_2$.

Now define $E^1_{k_1}(m):=m\oplus K^1$ and $E^2_{k_2}(m):=m\oplus K^2$.

Note that $E^1_{k_1}(E^2_{k_2}(m))=m\oplus K^1\oplus K^2$.

You now have a straight double encryption and can apply the standard meet-in-the-middle attack now.


The implementation would use a known-plaintext pair $(m,c)$. You would now tabulate all $E^1_{k_1'}(m)=m\oplus K^{1'}$ and then try all $D^2_{k_2'}(c)=c\oplus K^{2'}$ and look for matches between $E^1_{k_1'}(m)$ and $D^2_{k_2'}(c)$.

$\endgroup$
1
  • $\begingroup$ Thanks - upon seeing it broken down like that it's easier for me to digest. $\endgroup$
    – hunter
    Commented Jul 22, 2017 at 11:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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