Increasing the parallelization of Triple-DES

Triple-DES encrypts with the first key, then the second key, then the third key. Two keys are sitting around waiting. Why not encrypt with all three keys at the same time?

You take 192 bits of plaintext (three 64-bit sub blocks) and run the entire 192 bits through an MDS-matrix as a pre-step. Afterwards, in parallel, you simultaneously encrypt the first block with the first key, the second block with the second key and the third block with the third key.

You repeat the 192 bit MDS-matrix. Afterwards, in parallel, you encrypt the third block with the first key, the first block with the second key and the second block with the third key.

You repeat the 192 bit MDS-matrix. Afterwards, in parallel, you encrypt the second block with the first key, the third block with the second key and the first block with the third key.

Block1 = Key1, Key2, Key3

Block2 = Key2, Key3, Key1

Block3 = Key3, Key1, Key2

Encrypting with the third key, second key, and then first key is no different than encrypting with the first key, second key, and then the third key, so there would be no loss in security. This would also be resistant to the 64 bit block size attack. How much actual performance increase would there be from encrypting with all three keys in parallel? Would it complicate implementation to an extent where it wouldn't be worth it?

Well, this is effectively a 192-bit block cipher; changing any one bit of the input would have an unpredictable effect on all 192 bits of output. Some notes:

• 192 is an odd-sized block cipher; if I was the designer, I'd be sorely tempted to add another lane and make it a 256 bit block cipher.

• The initial MDS is cryptographically pointless - it's a public operation, and so the cryptanalyst can easier factor it out.

• At first glance, it wouldn't appear you gain anything by rotating the keys between layer; the inputs to (say) a specific DES at layer two is a linear function of all three DES outputs at the previous layer. In some sense, all three DES functions at a specific layer are equivalent; I'd simplify it by making each level "key 1, key 2, key 3" (and possibly add "key 4" if you go with the 256 bit block idea above).

• "Encrypting with the third key, second key, and then first key is no different than encrypting with the first key, second key, and then the third key, so there would be no loss in security." - hold it right there, bucko - adding operations in the middle effects the security, and it can reduce it. It may be secure (that is, at least as secure as regular 3DES), however that's something that would need to be shown, not just assumed.

• The best attack that occurs to me (not that this is proof that there isn't a better one): a saturation-based approach (where you hold two of the input blocks constant, and cycle through all possibilities of the third block - yes, that's $2^{64}$ blocks of input); after the second MDS matrix, the sum over all $2^{64}$ blocks of the inputs to any of the last round DES blocks will be 0 - this would allow you to test a guess of a DES key, at the cost of circa $2^{64}$ trial decryptions, that is, $2^{112}$ decryptions to do a full search. It is unknown if you can do a more efficient attack.

As for performance, well, that'd be quite dependent on the hardware (performance always is) - obviously, if you have a software implementation that can do only one DES operation at a time, you're no faster than normal 3DES (and actually a bit slower; both because of the intermediate IP/FP operations, and the MDS operations). Assuming you had hardware that could do multiple DES operations in parallel, well, you might get some gain - however (to do a BOTE computation) encrypting 48 bytes would take 6 (3x parallel) DES operations; encrypting the same 48 bytes with AES would take 3 AES operations - I'd expect the latter to be faster.