Double encryption vs single encryption

Question

So I understand that double encryption would do no more than possibly double the time taken to break a single encryption, as the key size of double encryption would be 2k-bits and the size of single would be k-bits. But in terms of strength, is double encryption stronger than single encryption and is there a specific way to express how much stronger it is than single encryption? Thank you.

Answer 1

So I understand that double encryption would do no more than possibly double > the time taken to break a single encryption, as the key size of double encryption would be 2k-bits and the size of single would be k-bits.

Not exactly. While it is true that you need 2k bits for double encryption (you have two keys, each k bits in size), the strength of the encryption would be equivalent to k+1 bits.

That's because as you correctly deduced, the brute force time is going to be doubled; and that is equivalent to adding a single bit to the key. When bruteforcing, you would run 2^k with the k+1-th bit at 0, and 2^k attempts with the k+1-th bit at 1; this extra bit sort of represents whether you're bruteforcing the outer or the inner encryption.

Update (clarification)

The key factor here is the encryption architecture. More precisely, whether you have a way of telling whether the outer encryption has been successful or not.

For example, if we encrypt a ZIP file twice, and supply a bad password to the outer ZIP, this will either give us an error, or something which is not a ZIP file. So we don't need - or just can't - bruteforce the result, because we know it isn't going to end well.

When the decrypted ZIP file yields a valid encrypted ZIP file, then we know the bruteforce succeeded and now can start bruteforcing the new ZIP file thus obtained.

In this scenario, the above holds: the total run time is that of the outer bruteforce, plus that of the inner bruteforce.

The answer has been accepted, so I guess that's the scenario the OP had in mind too. But it's not the only possible scenario.

Suppose we run a low-level library AES encrypt of a string, giving just a block of apparently random bits with nothing even to say it's an AES encryption at all, and then we encrypt that block with AES again, yielding a different "outer" block of apparently random bits: no header, no signature, no checksum.

Now, testing any key with AES against the outer block will yield a block of random bits, but we don't know whether the decryption succeeded or not. We don't know this is the right block of random bits. To know this, we need to bruteforce the block, and see if the output block is a non-random, valid cleartext or not.

(The OTP code is "perfect" in that regard, since even after obtaining a plausible cleartext, you still can't know whether it is the correct cleartext: "ATTACK AT NIGHT" and "RETREAT AT ONCE" are both equally likely outcomes of a bruteforce. Not so with smaller keyspaces).

So we have to run 2^k outer decryptions, and each of them will require other 2^k inner decryptions, making the total time 2^k * 2^k, or 2^2k. In this scenario, 2-encryption with a k-key has the same strength of 1-encryption with a 2k-key.