1
$\begingroup$

It's my understanding that Electronic Code Book (ECB) produces similar cypher text for similar plaintext inputs which is not a good thing. To get around that, Cypher Block Chaining (CBC) can be used to increase diffusion within the encrypted message. For example an algorithm could take the previous block's cypher text and XOR that with next block's plaintext. My question is, doesn't that make the beginning of a message easier to decrypt? In my mind it seems like the 1st block of an encrypted message has a closer relationship to the original message (less mathematical permutations involved) than subsequently encrypted blocks?

$\endgroup$
  • 1
    $\begingroup$ We expect you to do a significant amount of self-study and research before asking, including consulting standard resources (like Wikipedia and/or standard textbooks). This helps you craft a better question, and sometimes enables you to answer your question on your own. In this case, see e.g. en.wikipedia.org/wiki/Block_cipher_mode_of_operation#CBC. Look at the diagrams there. Why do you think the first block has fewer "permutations" or a closer relationship to the original message? The diagram looks identical for the first block.... $\endgroup$ – D.W. Mar 11 '15 at 18:18
  • 4
    $\begingroup$ @D.W The OP described the two modes of operation correctly, which suggests he has already consulted standard sources. Not everyone can figure stuff out on their own, nor can they ask good questions all the time. Your entire comment was aimed at helping the OP, but only the last two sentences do so. This question is OK. $\endgroup$ – rath Mar 11 '15 at 19:29
  • $\begingroup$ @D.W I'm not trying to make a fuss, but I know that efforts to maintain a high standard on content can dissuade newer users from participating further. This is my main concern, and this is why I write this to you $\endgroup$ – rath Mar 11 '15 at 19:31
6
$\begingroup$

In the first block, the IV provides the "randomness", and in subsequent blocks you just use the previous block of ciphertext instead. Based on the assumption, that the cipher is not weak and behaves like a pseudorandom permutation, this is basically the same: You XOR something unpredictable on the plaintext, and then encrypt.

As long as the IV is chosen randomly (and therefore, it should never be the same), there is no weak beginning. If you disregard the randomness and always start with the same value for a new message, then yes, the first block can be considered weaker. Because then you can distinguish, if two messages have the same beginning.

$\endgroup$
  • $\begingroup$ It seems like the 1st block only depends only on the IV, key, and plaintext. The second block depends on the previous block output (which depends on the IV, key, plaintext), key, and plaintext. I could abstract away the previous blocks output as just another randomly chosen IV, but in reality there is some sort of stateful information contained in there isn't there? $\endgroup$ – Joel B Mar 11 '15 at 16:28
  • 1
    $\begingroup$ The second block depends on the key, plaintext, and previous ciphertext block. But the previous ciphertext block is known to an attacker, just like the IV is for the first block. Hypothesize that an attacker somehow know the first block of plaintext (say it's attacker-controlled). It's clear that this provides no additional information that could be used to break the second ciphertext block; the only input to the second encryption block that depends on that is the IV (the previous ciphertext block), but the attacker already knows it. $\endgroup$ – Stephen Touset Mar 11 '15 at 17:39
  • $\begingroup$ Related: crypto.stackexchange.com/questions/5421/… $\endgroup$ – Ilmari Karonen Mar 11 '15 at 18:38
  • $\begingroup$ @StephenTouset - Thanks. That the attacker already knows the entire cyphertext is the part that I wasn't considering. $\endgroup$ – Joel B Mar 11 '15 at 18:59
  • 1
    $\begingroup$ The only possible problem arises, if the attacker can somehow control the previous ciphertext. But under the assumption, that the cipher behaves like a pseudorandom permutation, he can't control the the first ciphertext, even if he can know or manipulate the first plaintext. The only property the "random input" (IV or previous ciphertext) requires, is that it does not repeat. Confidentiality is not needed, it is even public. Basically, you could just use alternatively an increasing counter. This would be similar to the difference between OFB and CTR. $\endgroup$ – tylo Mar 12 '15 at 11:11
3
$\begingroup$

As long as the IV is chosen correctly, every individual block of the encrypted output will be uniformly random over the set of all bit-patterns of the given size. Each block is independent from the clear text, but they are not independent from each other.

The first block contains the IV itself, which by construction is uniformly random and independent from the clear text message. Once this block is XOR-ed with the first clear text block, the resulting block is again uniformly random and independent from the clear text.

The output of the XOR is fed through the cipher. Since the cipher performs a permutation of all the possible bit strings of the specific length, it preserves the uniformly randomness. (A permutation of a uniformly random distribution is still uniformly random.) Moreover since the key doesn't depend on the clear text, this step couldn't introduce any correlation with the clear text, so it remains independent from the clear text.

Now you can simply repeat the same steps to see that every individual output block is indeed uniformly random and independent of the clear text.

Another way to see it is, that you can produce the cipher text by randomly choosing any single block instead of the IV. From this single block you can encrypt your way forwards to the end of the clear text to produce all cipher blocks after the randomly chosen block. You can also work your way backwards to produce the preceding cipher blocks using an approach very similar to CFB mode.

In the end the probability distribution of cipher texts are identical regardless of which of the blocks you chose first. In certain scenarios choosing the middle block rather than the first block makes sense as a way of parallelizing the encryption across two CPUs.

$\endgroup$
2
$\begingroup$

This is why we use random initialization vectors (IVs) for all such algorithms.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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