3
$\begingroup$

There is some intriguing things about DES and 3DES. Now, I know that DES is weak and 3DES was an attempt to construct a more secure block-cipher from a deprecated one.

Having this in mind, what about the composition of two independent instantiations of block-cipher (t.i.t.s with two independent keys) having a reduced number of rounds. Take the example of AES (with key of 128-bit) which has 10 rounds (and consider that the last round is complete, in the sense that it contains all the operations add-roundkey, mixcolumns, shiftrows and subbytes). If we consider a reduced version of AES with 5 complete rounds, denoted $AES^r$, and we construct a new block cipher in the following way:

$$AES'_{k_1,k_2}(.)=AES^r_{k_1}(AES^r_{k_2}(.))$$

Is this block cipher as secure as the original version of AES ? It seems to me that it does, since the keys are independant, but I need confirmation.

Edit: Is the following composition also secure ?

$$AE''_{k_1,k_2}(.)=AES^r_{k_1}({AES^{r}}^{-1}_{k_2}(.))$$

where ${AES^r}^{-1}_{k_2}(.)$ denotes the decryption operation.

Thank you.

Improve this question
$\endgroup$
7
  • $\begingroup$ @fgrieu Actually, the key material is far weaker than twice the original key size. I believe a meet in the middle attack will recover $k_1$ and $k_2$ in time complexity $O(2^{k + 1})$ and space complexity $O(2^k)$. But overall it would seemingly still be as secure as the original version from a black-box perspective. That said 5-round AES would seem to be within the realm of practical cryptanalysis, so I imagine there could be a weakness there. $\endgroup$
    – Thomas
    Jun 6, 2013 at 13:56
  • $\begingroup$ @Thomas: I am assuming $k_1$ and $k_2$ are 128-bit each, and independent. In that setup, meet-in-the-middle does not apply. $\endgroup$
    – fgrieu ♦
    Jun 6, 2013 at 14:09
  • $\begingroup$ @fgrieu I think you are mistaken. MITM applies here, just on 128-bit keys. So there aren't 256 bits of entropy here. You are correct it does not make it less secure than the original version, but it doesn't make it more secure either from a key material perspective. $\endgroup$
    – Thomas
    Jun 6, 2013 at 14:12
  • $\begingroup$ @fgrieu There seems to be a slight miscommunication. I was talking about your statement that "the key has twice as much entropy". The effective key space of $AES'$ is not 256 bits (but still at least 128 bits). $\endgroup$
    – Thomas
    Jun 6, 2013 at 14:22
  • 3
    $\begingroup$ @Thomas: I agree with poncho's answer, and, reading them again, your comments. Meet-in-the-middle applies in the theoretical sense that a 256-bit-key cipher is theoretically broken with about $2^{129}$ (half) encryptions and $2^{135}$ bits of RAM. That's so huge that I took the questionable step to sum it up as "does not apply". $\endgroup$
    – fgrieu ♦
    Jun 6, 2013 at 14:26

2 Answers 2

Reset to default
5
$\begingroup$

Well, whether $AES'$ is as secure as $AES$ depends on the length of $k_1, k_2$.

If they are both 128 bit, then what you effectively have is a standard 128-bit AES, except that prior to round 6, you replace the running key with an independent key (and you tweaked the last round, but that's cryptographically harmless). Now, it is never a good idea to do random tweaks on ciphers, however, this appears reasonable to conjecture that this one is harmless; that the security of the cipher does appear unlikely to depend on the relationship of the subkeys in round 5 and round 6 of standard AES. This, of course, assumes that we are interested solely in the standard attacks (chosen-plaintext, chosen-ciphertext); if we are allowed to consider related-key attacks, this construction may well be weaker.

On the other hand, if $k_1, k_2$ are each 64 bits (with the $AES^r$ subkey derivation process being somehow modified to take a 64 bit key), then what we have is definitely weaker than standard AES (even though $AES'$ takes a 128 bit key); even against a known-plaintext scenario.

This is due to a standard meet-in-the-middle attack, where to find the values $k_1, k_2$ that solve the equation:

$AES'_{k1,k2}(P) = AES^r_{k1}(AES^r_{k2}(P)) = C$

for some known plaintext/ciphertext blocks, the attacker just computes:

$F(k_1) = AES^r_{k2}(P)$

$G(k_2) = {AES^r_{k1}}^{-1}(C)$

for all $2^{64}$ values of $k_1, k_2$, and searches the lists to find a pair $F(k_1) = G(k_2)$. This gives him solutions for $AES'_{k1,k2}(P) = C$ in $O(2^{64})$ time.

Improve this answer
$\endgroup$
3
$\begingroup$

This is not a complete answer but it seems to me that it cannot be more secure than the original AES since otherwise it would mean that there is a serious weakness in the AES key schedule

As far as being as secure there's at least one application in which it's a weakness : when you use AES inside a Davies-Meyer construction. An attacker has then more power since he can choose keys again after 5 rounds which allows his to build better differential trails

Improve this answer
$\endgroup$

Your Answer

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

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