Explanation of the self-healing property of CBC (Cipher Block Chaining)
Wikipedia :
CBC mode is self-healing: if one encryption block is changed, the error propagates to no more than two blocks.
Example:
Let the block size be 64 bits. Original plaintext:
3231343336353837 3231343336353837 3231343336353837 • • •
Correct encryption text:
ef7c4bb2b4ce6f3b f6266e3a97af0e2c 746ab9a6308f4256 • • •
If the ciphertext is damaged, the byte '0x4b'
changed to '0x4c'
:
ef7c4cb2b4ce6f3b f6266e3a97af0e2c 746ab9a6308f4256 • • •
Then it stands for:
efca61e19f4836f1 3231333336353837 3231343336353837 • • •
Question:
I am having a hard time understanding the self-healing property of CBC (Cipher Block Chaining), I thought the example given might help, but now I am more confused. Any help would be great.
source to share
Personally, I find the decryption graphics very helpful for such issues. From Wikipedia (public domain image) :
Now add some damage:
Red dots represent partial faulty inputs and the solid red line represents complete block damage.
Some notation before we start . I will specify the original plaintext blocks as p1
via p3
, corrupted as p1'
via p3'
, correct ciphertext blocks as c1
via c3
, and damaged as c1'
via c3'
:
3231343336353837 3231343336353837 3231343336353837 • • •
p1 p2 p3
ef7c4bb2b4ce6f3b f6266e3a97af0e2c 746ab9a6308f4256 • • •
c1 c2 c3
ef7c4cb2b4ce6f3b f6266e3a97af0e2c 746ab9a6308f4256 • • •
c1' c2'=c3 c3'=c3
efca61e19f4836f1 3231333336353837 3231343336353837 • • •
p1' p2' p3'=p3
There are also a few IV
that you did not include in your example.
Let's look at the first block : three bits at the input of the block cipher are changed ( 0x4b ^ 0x4c = 0x07 = 4+2+1
). Since the block cipher is designed for pseudo-random permutation, that is, the bijective function is indistinguishable from a random function (without knowing the key k
) - we get a completely (pseudo) random block as the output of the decryption function
dec( c1 ,k) = p1 XOR IV
<=> dec(ef7c4bb2b4ce6f3b,k) = 3231343336353837 XOR IV
dec( c1' ,k) = p1' XOR IV
<=> dec(ef7c4cb2b4ce6f3b,k) = efca61e19f4836f1 XOR IV
As the next step, IV is XORed, so we get
dec( c1 ,k) XOR IV = p1
<=> dec(ef7c4bb2b4ce6f3b,k) XOR IV = 3231343336353837
dec( c1' ,k) XOR IV = p1'
<=> dec(ef7c4cb2b4ce6f3b,k) XOR IV = efca61e19f4836f1
which shows that the entire block has been destroyed (full red block at the bottom).
Now, in the second block : we start over by decrypting the ciphertext block, which works great since no damage occurred in the block:
dec( c2 ,k) = p2 XOR c1
<=> dec(f6266e3a97af0e2c,k) = 3231343336353837 XOR ef7c4bb2b4ce6f3b
^
Note that this formula uses intact blocks everywhere. Recall that this block was generated in this way during encryption:
c2 = enc( p2 XOR c1 ,k)
<=> f6266e3a97af0e2c = enc(3231343336353837 XOR ef7c4bb2b4ce6f3b,k)
The next step is to XOR again with the previous block (this time not IV, but c1 '). This previous block c1 'is corrupted:
dec( c2 ,k) XOR c1' = p2 XOR c1 XOR c1'
<=> dec(f6266e3a97af0e2c,k) XOR ef7c4cb2b4ce6f3b = 3231343336353837 XOR ef7c4bb2b4ce6f3b XOR ef7c4cb2b4ce6f3b
Now we can actually compute c1 XOR c1'
(error) how c1 XOR c1' = 0000007000000000
and replace this everywhere:
dec( c2 ,k) XOR c1' = p2 XOR 0000007000000000
<=> dec(f6266e3a97af0e2c,k) XOR ef7c4cb2b4ce6f3b = 3231343336353837 XOR 0000007000000000
Finally, simplify p2 XOR 0000007000000000 = p2'
:
dec( c2 ,k) XOR c1' = p2'
<=> dec(f6266e3a97af0e2c,k) XOR ef7c4cb2b4ce6f3b = 3231333336353837
You can see that the original damage ( 0x07
) for the first ciphertext block is c1'
passed verbatim to the second plaintext block p2'
, but it remains otherwise intact (as rendered mostly white block in the graphics, with one square being red). This peculiar property of CBC can lead to attacks on real world systems such as oracle indentation .
The third block is boring as hell: No decryption and XOR inputs have changed, so p1=p1'
everything is fine there too .
source to share
When decrypting in CBC mode, the block is decrypted by first decrypting the block in question with the key and then XORing the previous block in the ciphertext. Take a look at the CBC mode on the wiki
Since you only need the current and previous block to decrypt in CBC mode, the effect of the changed byte in the ciphertext will only affect its block and the next block (if it exists).
source to share