Improving Security: Cipher Block Chaining
12 Nov 2018
↪ Background
One of the caveats regarding block ciphers I mentioned in my DES article was “Encrypting identical input blocks”. The actual problem here is that redundant input blocks will always result in the same output block when encrypted. Encrypting data, holding recurring structure or metadata, with a so called Electronic Codebook Block Cipher (ECB) could make the resulting ciphertext vulnerable to watermark or replay attacks. Together with confusion, diffusion is the main goal in Cryptography, so having even the slightest evidence of the initial plaintext is contrary.
To demonstrate the situation, the following example reads 512 bytes from /dev/zero (which returns 0), encrypts it with DES and converts the binary output to base64.
% dd if=/dev/zero bs=512 count=1 | ./run | base64 -b 64
1+0 records in
1+0 records out
512 bytes transferred in 0.000023 secs (22139007 bytes/sec)
ybOrqUBosr7Js6upQGiyvsmzq6lAaLK+ybOrqUBosr7Js6upQGiyvsmzq6lAaLK+
ybOrqUBosr7Js6upQGiyvsmzq6lAaLK+ybOrqUBosr7Js6upQGiyvsmzq6lAaLK+
ybOrqUBosr7Js6upQGiyvsmzq6lAaLK+ybOrqUBosr7Js6upQGiyvsmzq6lAaLK+
ybOrqUBosr7Js6upQGiyvsmzq6lAaLK+ybOrqUBosr7Js6upQGiyvsmzq6lAaLK+
ybOrqUBosr7Js6upQGiyvsmzq6lAaLK+ybOrqUBosr7Js6upQGiyvsmzq6lAaLK+
ybOrqUBosr7Js6upQGiyvsmzq6lAaLK+ybOrqUBosr7Js6upQGiyvsmzq6lAaLK+
ybOrqUBosr7Js6upQGiyvsmzq6lAaLK+ybOrqUBosr7Js6upQGiyvsmzq6lAaLK+
ybOrqUBosr7Js6upQGiyvsmzq6lAaLK+ybOrqUBosr7Js6upQGiyvsmzq6lAaLK+
ybOrqUBosr7Js6upQGiyvsmzq6lAaLK+ybOrqUBosr7Js6upQGiyvsmzq6lAaLK+
ybOrqUBosr7Js6upQGiyvsmzq6lAaLK+ybOrqUBosr7Js6upQGiyvsmzq6lAaLK+
ybOrqUBosr7Js6upQGiyvsmzq6lAaLK+ybOrqUBosr4=
Even though it is still very (very!) hard to reconstruct the plaintext without knowing the key, the example shows the attacker that we are encrypting redundant data.
↪ Cipher Block Chaining
A very efficient way to diffuse the ciphertext is the so called Cipher Block Chaining Mode (CBC): We just XOR the input block with the previous output block before running the encryption function. Here comes the example from above, with the identical encryption key and the same input data, but this time we added CBC support to our algorithm:
% dd if=/dev/zero bs=512 count=1 | ./run | base64 -b 64
1+0 records in
1+0 records out
512 bytes transferred in 0.000023 secs (22139007 bytes/sec)
zQXj4N3dNXEFx6EL/ajFbVx+mkMqusaf267esAGkQ8aZg73WbVCH1u9w8Ji0NYAu
iZ2LB7b9vxeSnJcFf7VJD98iShMSidLjiXPzDoq75FycohOAS8LDF08tVEdGrNL0
SIiekZ78ZdZTJdQrwu5BK3Yz6KLAzTi6Z/fOYXW5EbMuLaxBjRExKEui4VpQPSvh
zUwJ8y187kuCPad4Y0Wx4opz5zKfmv0ZILk2f36wHMMQp4mwgFIbX8Jh5Yki9u61
YSZDCc1xsiXdMG4CCgE5RIrWxG89//RGO4Xw2KVPayzHiMO+23fHQtKbQcXfdY38
AjGJUw5Q0lWvmVoQe1ALPFX7iUAqeBdp3bRZVdLWbXOvmvzFMDIk551J2l01YWr5
+fjnP8JDGpHku2KMDRluzkF+p2CxswLFxGMtOPrh6NG+ZcDzJP6412ITFiSkdlS4
DIX2bh37hfE1zT81O+YmUl3tLzdWHfUYkdMGRAUoao/cTCWlHBybDhr2UoDKQ+zy
OJ6RHhTyKp8juaPbhcTBH1vbKoCSjB5LhNhk7unQ5ziagkBVc+k9xAPB8MPjyygI
I1UZZRqktDef5OyKqz2Lcy6oXJbErZ3cKEub8+6176p6jqxXEOR66xpLjyuajH8c
g3gjaNi2iiAVH/2PEpCn+ZLTiq3LBT/djOxLW9M9bEs=
You can see that the redundancy is gone completely and there is no obvious trace of the identical input blocks anymore.
↪ Initialization Vector
Since we do not have a factor to XOR the input in the first run we need to introduce an additional shared secret: the Initialization vector (IV). The IV has to have the identical size of the input block we are encrypting. For DES this is 64bit, for AES 128bit. It also has to be known both at the enciphering and the deciphering end and becomes an additional part of our private key.
↪ Performance
The following examples reads and encrypts 320MB 0-bytes with DES (identical keys). The output goes directly to /dev/null to skip any disk interaction.
↪ ECB Mode:
% dd if=/dev/zero bs=1M count=320 | ./run | dd of=/dev/null
320+0 records in
320+0 records out
335544320 bytes (336 MB, 320 MiB) copied, 116.105 s, 2.9 MB/s
655359+1 records in
655359+1 records out
335544318 bytes (336 MB, 320 MiB) copied, 116.128 s, 2.9 MB/s
↪ CBC Mode:
% dd if=/dev/zero bs=1M count=320 | ./run | dd of=/dev/null
320+0 records in
320+0 records out
335544320 bytes (336 MB, 320 MiB) copied, 115.432 s, 2.9 MB/s
655359+1 records in
655359+1 records out
335544318 bytes (336 MB, 320 MiB) copied, 115.456 s, 2.9 MB/s
We can see that the runtimes are (almost) identical, the additional XOR steps do not show any measurable difference in our tests. Source Code The source code of the examples above can be found here: https://gogs.gfuzz.de/oliver.peter/DES/src/master/main.c
By utilizing the CIPHER_BLOCK_CHAINING macro definition, CBC can be enabled/disabled during compile time.
↪ Lessons learned
- CPUs XOR pretty fast :-)
- Cryptography still remains a tough topic, while playing around with CBC I found out that my DES implementation was not working correctly at all. Missing brackets while using a macro lead to passing half of the plaintext unaltered through the function.