Monthly Archive for March, 2009

[ Sometimes the LATEX does not render properly. Just refresh the page and it should do. ]

In the cipher block chaining mode, each block of plain text is XORed with the previous cipher text block before being  encrypted. This was, each cipher text block is dependent on all the plain text blocks that have been processed up to  that point. Also to make each message unique, an initialization vector must be used in the first block.

CBC Encryption

CBC Decryption

CBC mode is as secure as the underlying block cipher against standard attacks. In addition any patterns in the plain text are concealed by the XORing of the previous cipher text blocks with the plain text block. Note also that the plain text cannot be directly manipulated except by removal of blocks from the beginning or the end of the cipher text. The initialization vector should be different for any two messages encrypted with the same key and is preferably randomly chosen. It does not have to be encrypted and it can be transmitted with (or considered as the first part of)  the cipher text.

If the first block has index $$1$$, the mathematical formula for CBC encryption is $$!C_i = E_K(P_i \oplus C_{i-1}), C_0 = IV$$ while the mathematical formula for CBC decryption is $$!P_i = D_K(C_i) \oplus C_{i-1}, C_0 = IV$$

Choosing the initial value $$c_0$$ at random prevents almost with certainty that the  same initial value $$c_0$$ is used for more than one encryption. This is important for security. Suppose for a moment that the same $$c_0$$ is used for two messages $$m$$ and  $$m^`$$ . Then, an eavesdropper can immediately detect whether the first $$l$$ blocks of $$m$$ and $$m^`$$ coincide, because in this case the first $$l$$ ciphertext blocks are the same.

The speed of encryption is identical to that of the block cipher, but the encryption process cannot be easily parallelized, although the decryption process can be.

In this mode, we have $$r = n$$. Encryption in the cipher-block chaining mode is implemented by the following algorithm

Algorithm:

bitStream cbcEncrypt(bitStream m)

select $$c_0 \in \{0, 1\}^n$$ at random

divide $$m$$ into $$m_1m_2…m_l$$

for $$i$$ $$\gets$$ $$1$$ to $$l$$ do

$$c_i \gets E_k(m_i \oplus c_{i-1})$$

return $$c_0c_1c_2..c_l$$

Decryption in cipher-block chaining mode is implemented by the following algorithm

Algorithm:

bitStream cbcDecrypt(bitStream c)

divide $$c$$ into $$c_0c_1c_2…c_l$$

for $$i$$ $$\gets$$ $$1$$ to $$l$$ do

$$m_i \gets {E_k}^{-1}(c_i) \oplus c_{i-1}$$

return $$m_1m_2…m_l$$

A transmission bit error in block $$c_i$$ affects the decryption of the blocks $$c_i$$ and $$c_{i+1}$$. The block recovered from $$c_i$$ will appear random (here we assume that even a small change in the input of a block cipher will produce a random looking output), while the plaintext recovered from $$c_{i+1}$$ has bit errors precisely where $$c_i$$ did. The block $$c_{i+2}$$ is decrypted correctly. The cipher block chaining mode is self synchronizing, even if one or more entire blocks are lost. A lost ciphertext block results in the loss of the corresponding plaintext block and errors in the next plaintext block.

In both the electronic codebook mode and cipher block chaining mode, $${E_k}^{-1}$$ is applied for decryption. Hence, both modes are also applicable with public key encryption methods, where the computation of $${E_k}^{-1}$$ requires the recipient’s secret, while $$E_k$$ can be easily computed by everyone.

[ This is a part of a series of post on Modes Of Encryption. I had to scribe a lecture as a requirement of a course on the Foundations Of Cryptology at the Indian Institute Of Technology. The scribe has been broken into smaller chunks so that it is easily readable. ]

Popularity: 2% [?]

[ Sometimes the LATEX does not render properly. Just refresh the page and it should do. ]

Often the length of message exceeds the block length. So, the block ciphers need some extension. Consider a block cipher of length $$n$$. We fix a key $$k$$, and denote the encryption function with this key as $$!E_k\colon \{0, 1\}^n \to \{0, 1\}^n$$
To encrypt a message $$m$$ that is longer than $$n$$, the message is decomposed into blocks of fixed size $$ r, m = m_1m_2…m_l$$. The individual blocks are encrypted iteratively.

The message block size $$r$$ need not equal $$n$$. In few modes of encryption, $$r$$ is smaller than $$n$$.

Also if the length of message $$m$$ is not an integral multiple of $$r$$, then we have to complete the last block. The last block of the message can be padded out with some bits and encrypted. After decryption, the receiver must remove the padding. Therefore he must know how many bits were padded. This can be achieved, for exmple, by storing the number of padded bits in the last byte of the last block.

[ This is a part of a series of post on Modes Of Encryption. I had to scribe a lecture as a requirement of a course on the Foundations Of Cryptology at the Indian Institute Of Technology. The scribe has been broken into smaller chunks so that it is easily readable. ]

Popularity: 1% [?]