No, not cryptanalysis (although that would be such a nice name for it). This is an encryption mode, or rather a tweak to an encryption mode. And it's actually quite safe -- you even get back the ciphertext at the end.
The CBC mode of operation for block ciphers only works on a whole number of blocks. Thus padding the message is required. Some modes -- e.g. CTR -- can be used without such padding. Ciphertext "stealing" or CTS is a hack which allows CBC mode without padding.
- Length of plaintext is at least 1 block.
- Length of plaintext is known (e.g. by passing it at the start of the message)
Note that the second assumption is anyway required for minimal security
(or an adversary
can tack garbage
onto the end
of the decrypted
message by tacking on anything at the end of the encrypted
When the message length isn't a whole number of blocks, what we'd like to do is truncate the last block. But CBC doesn't let us do that, because we must know all bits of a block to decrypt. The sneaky idea behind ciphertext stealing is to "steal" the appropriate number of bits from the penultimate ciphertext block!
To encrypt in CBC mode with ciphertext stealing, pretend to pad the last plaintext block with 0s, to fill it up to a whole block size:
... aaaaaaaa bbbbbbbb ccc00000
Now CBC encrypt the whole thing:
... AAAAAAAA BBBBBBBB CCCCCCCC
(note that we cannot assume anything about the "last" bits of
; in particular, they're very probably not zero
Then the encrypted blocks are:
BBBBBBBB = EK(bbbbbbbb⊕AAAAAAAA)
CCCCCCCC = EK(ccc00000⊕BBBBBBBB)
So if we know all
, we can decrypt it to get the last bits of
-- we XOR
ed them with 0's. Bearing this in mind, we transmit
... AAAAAAAA CCCCCCCC BBB
The first thing to notice is that we transmitted only as many bits as were in the message -- we transmitted the same number of full blocks, and as many bits of the penultimate ciphertext block
BBBBBBBB as there were bits of the last plaintext block
To decrypt, we decrypt all blocks up to
AAAAAAAA (inclusive) as usual for CBC. We now decrypt the last block-and-a-bit:
DK(CCCCCCCC) = ccc00000⊕BBBBBBBB = xxxBBBBB
ccc????? = DK(CCCCCCCC)⊕BBB?????
We get the last bits of the plaintext by XOR
with the partial last ciphertext block
; this gives us the partial last plaintext block
. The remaining bits are exactly
the bits missing
from the ciphertext block
. So we put them together to get the full block, and compute
DK(BBBBBBBB) = AAAAAAAA⊕bbbbbbbb
bbbbbbbb = DK(BBBBBBBB)⊕AAAAAAAA
Ciphertext stealing lets us pass a partial final block, securely (note that no proof was given here!) and without increasing the message size. You still need to authenticate the message to avoid tampering (i.e. use some MAC). And you still need to specify the message length. The implementation is more complex, for a relatively small saving of space -- even for AES, at most 15 bytes will be saved. And you still cannot transfer really short messages, which fit in less than one full block.
Is it worth it? Usually not. But if your application requires it -- say if you have many messages of length between 1 block and 2 blocks -- it might be worth remembering this hack.