Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
2  
Meet-in-the-middle will break this with cost $2^{64/2}=2^{32}$, which is feasible with a single PC. –  CodesInChaos Sep 18 '13 at 7:03
add comment

2 Answers

up vote 8 down vote accepted

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.

share|improve this answer
    
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) –  chettyharish Sep 18 '13 at 17:37
1  
For ciphertext only, aside from algorithm-specific properties/weaknesses, I don't know of anything better than brute-force. –  B-Con Sep 18 '13 at 18:30
    
Thanks a lot :) –  chettyharish Sep 19 '13 at 1:29
add comment

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.

share|improve this answer
1  
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. –  Paŭlo Ebermann Oct 7 '13 at 11:46
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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