Block ciphers and padding

A block cipher like AES can only do one thing: transform a fixed-size block into another block of the same size, under the control of a key. For AES, this block is 128 bits, i.e. 16 bytes. No more, no less.

The problem with real messages

A real message — an email, a file, an HTTPS request — is rarely exactly 16 bytes. So it has to be split into a sequence of 16-byte blocks, and then each block is encrypted.

Message clair (37 octets)
+----------------+----------------+-----+
| bloc 1 (16 o.) | bloc 2 (16 o.) | ... |
+----------------+----------------+-----+
                                     ^
                          5 octets seulement : trop court !

Almost always, the message size is not a multiple of 16. The last block is incomplete. What do we do with those missing bytes?

Padding

We fill out the last block with extra bytes: this is the padding. But we cannot put just anything: at decryption time, we need to know exactly how many bytes to remove, otherwise the message is corrupted.

The standard method is PKCS#7. Its rule is elegant: if k bytes are missing, we add k bytes each equal to k.

Il manque 3 octets -> on ajoute : 03 03 03
Il manque 1 octet  -> on ajoute : 01
Il manque 6 octets -> on ajoute : 06 06 06 06 06 06

At decryption time, we read the last byte: it gives the number of padding bytes to remove.

The tricky case: the already-aligned message

What happens if the message is already a multiple of 16 bytes? If we added nothing, the decryptor would read the last byte of the real data and wrongly believe it was padding.

The PKCS#7 solution: we always add padding, even in this case. An aligned message then receives a whole block of padding:

16 octets de padding = 10 10 10 ... 10  (16 fois la valeur 16, en hexadécimal)

There is therefore always between 1 and 16 bytes of padding. Decryption is never ambiguous.

Counting the blocks

For a message of L bytes with a block size B, the number of blocks after padding is:

nombre_de_blocs = plancher(L / B) + 1

The + 1 reflects the fact that there is always at least one byte of padding: even an aligned message gains a block.

In summary

• AES encrypts fixed-size blocks: 16 bytes (128 bits).
• A message is split into blocks; the last one is completed with padding.
• PKCS#7 adds k bytes each equal to k, and always adds padding — even a whole block if the message is already aligned.
• Decryption reads the last byte to know how many bytes to remove, without ambiguity.