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.

+3


source to share


2 answers


Personally, I find the decryption graphics very helpful for such issues. From Wikipedia (public domain image) :

Original CBC decryption

Now add some damage:

Corrupted CBC decryption

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 .

+10


source


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).

+1


source







All Articles