Question

5.1 (Double encryption). Let E = (E,D) be a cipher. Consider the cipher E2 = (E2, D2), where E2(k,m) = E(k, E(k,m)). One would expect that if encrypting a message once with E is secure then encrypting it twice as in E2 should be no less secure. However, that is not always true. (a) Show that there is a semantically secure cipher E such that E2 is not semantically secure. (b) Prove that for every CPA secure ciphers E, the cipher E2 is also CPA secure. That is, show that for every CPA adversary A attacking E2 there is a CPA adversary B attacking E with about the same advantage and running time.

Answer 1

With only the hypothesis that AA and BB are secure block ciphers sharing block size and key size, we can't conclude that the compound block cipher GG defined by c-Gk(m)-Ak (Bk (m))c-Gk (m)-Ak(Bk(m)) is secure. An extreme example is that GG could be the identity function (e.g. BB could be AES-256 encryption, and AA AES-256 decryption) And we can't make a rigorous exception for that case: AA and BB can interact badly in nany ways to that 6G is weak when AA and BB are secure (e.g BB could be AES-25 encryption except for a modified S-box in the first SubBytes, and AA straight AES-256 decryption, so that GkGk is a transformation with no diffusion between bytes of a block, and quite a weak transformation of each byte) On the other hand, there are (overwhelmingly many) cases where GG is more resistant to attack than either AA or BB is (e.E. BB could be AES-256 encryption reduced to the initial AddRoundkey and first 7 rounds, and AA AES-256 encryption reduced to the last 7 rounds, so that GG is the full AES-256). Thus we can't hope for general attacks working against GG