7
$\begingroup$

I was trying to understand cryptography from the book Information Security by Mark Stamp and I am confused by something.

Suppose that Alice has a secure block cipher, but the cipher only uses an 8-bit key. To make this cipher "more secure," Alice generates a random 64-bit key K, and iterates the cipher eight times, that is, she encrypts the plaintext P according to the rule

$$C = E(E(E(E(E(E(E(E(P, K_0), K_1), K_2), K_3), K_4), K_5), K_6), K_7)$$

where $K_0,...,K_7$ are the bytes of the 64-bit key $K$.

  1. Assuming known plaintext is available, how much work is required to determine the key $K_1$?
  2. Assuming a ciphertext-only attack, how much work is required to break this encryption scheme?

Here I believe that the author is trying to explain the meet in the middle attack, but how does this attribute to it? As far as I have understood things, by using a MIM attack, the answer will be $2^7$ for each block do is $2^7*8$, and ciphertext I believe there are no ciphertext shortcuts so is should be $2^{64}$?

Am I right or I am thinking in the wrong direction?

Is encrypting 8 times with 8-bit key beneficial?

$\endgroup$
1
  • 3
    $\begingroup$ Meet-in-the-middle will break this with cost $2^{64/2}=2^{32}$, which is feasible with a single PC. $\endgroup$ Sep 18, 2013 at 7:03

2 Answers 2

9
$\begingroup$

For a meet-in-the-middle attack with known plaintext, you break all $K_i$ at the same time. The goal is to split the work into multiple sides, trading off some exponential work for some exponential space and some linear work.

Split the encryption and decryption sides evenly. You need $(2^8)^4 \times 2 = 2^{33}$ block cipher calls, because you need 4 layers of $2^8$ encryption calls and 4 layers of $2^8$ decryption calls. (The work for both sides combines linearly, rather than exponentially, which is where the power of MITM lies.) When a match in the middle is found (the more known plaintext the better, since false positives are possible), you retrieve the key that was used to generate the mid-state matches from both sides, combine the two halves, and get the full $K$.

There's a shortcut for that analysis: Double-layering a cipher using different keys attempts to build a key of length $2n$, but an MITM attack can reduce it back to an effective key length of $n+1$. So for the question at hand, pretend we actually had a cipher with a 32-bit key (it iterates the original cipher 4 times internally) and that hypothetical cipher itself was iterated twice. We take the hypothetical 32-bit key, double it to a 64-bit key, then MITM reduces it to a 33-bit key.

A work factor of $2^{33}$ to recover all of $K$ is much less than the attempted strength of $2^{64}$. At almost half the length, it's a break.

(Side note: Splitting the work in the middle of the layers is the most efficient, but, for fun, you could split it elsewhere. Consider doing the MITM split at, say, $K_1$ and $K_2$. It would require $(2^8)^6 + (2^8)^2 = 2^{48} + 2^{16}$ calls to the block cipher, as you need 6 layers of $2^8$ encryptions, and 2 layers of $2^8$ decryptions. To conceptualize how MITM works, it may help to think of brute-force as a special-case MITM with 0 rounds on one of the sides, resulting in $(2^8)^8 + 0 = 2^{64}$ work, which is the full key space.)

That uses just one encryption/decryption split, also known as one-dimensional MITM. For ciphers layered more than twice, there are multi-dimensional MITM attacks, which apply an encryption and decryption split at each layer. It's more complicated, but it enhances the attack even more.

$\endgroup$
3
  • $\begingroup$ So what If the attacker only has cipher text? Is brute force the only option? (He knows nothing about plain text, but knows that Alice is using the technique) $\endgroup$ Sep 18, 2013 at 17:37
  • 1
    $\begingroup$ For ciphertext only, aside from algorithm-specific properties/weaknesses, I don't know of anything better than brute-force. $\endgroup$
    – B-Con
    Sep 18, 2013 at 18:30
  • $\begingroup$ Is it still considered a break if you make the key twice as long as the security level you want? Say that you want 64-bit security, so you repeat the 8-bit algorithm 16 times instead of only 8. $\endgroup$
    – user253751
    Mar 9, 2020 at 17:11
0
$\begingroup$

You haven't specified anything about the cipher's block size. Bear in mind that if the block size is smaller than 64 bits, a chosen plaintext attack or chosen ciphertext attack is faster than brute-forcing the 64-bit key. And a block size of less than 32 bits speeds up the MITM attack.

$\endgroup$
1
  • 1
    $\begingroup$ Could you elaborate a bit? The terms "chosen plaintext attack" and "chosen ciphertext attack" are names for general attack models (i.e. they tell what the attacker can do), not specific attacks which can be used to break a cipher. $\endgroup$ Oct 7, 2013 at 11:46

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.