What kind of padding should AES use?

Question

I have implemented the AES encryption (homework), but I stumble upon the problem of padding the messages.

If my messages are arrays of bytes as such:

public byte[] encrypt(byte[] message) {
    int size = (int) Math.ceil(message.length / 16.0);
    byte[] result = new byte[size * 16];
    for (int i = 0; i < size; i++) {
        if ((i+1) * 16 > message.length){
            //padding here????
        } else {
            byte[] block = Arrays.copyOfRange(message, i * 16, (i + 1) * 16);
            byte[] encryptedBlock = encryptBlock(block);                
            System.arraycopy(encryptedBlock, 0, result, i*16, 16);
        }
    }
    return result;
}

How can I pad such a message?

I cannot use Zero Padding because the each byte could be zero, and it might affect such a message with trailing zeros.

I cannot find any reference to how is this done not even here (the paper describing the AES encryption)

Solution

There are a number of methods you can use, from simple to advanced. Bruce Schneier suggests two rather simple methods:

One is to pad the last block with n bytes all with value n, which is what Alex Wien suggested. This has issues (including restricting you to block sizes that are less than 256 bytes long). This padding mode is known as PKCS#7 padding (for 16 byte blocks) or PKCS#5 padding (for 8 byte blocks).

The other is to append a byte with value 0x80 (a byte with value 1000 0000 in binary) followed by as many zero bytes as needed to fill the last block. This method is known as ISO padding, which is short for ISO/IEC 9797-1 padding method 2. The padding itself is bit-level padding, a single bit valued 1 is added, and then add 0 valued bits until you reach the block size.

As for how to know whether a message is padded, the answer is a message will always be padded: even if the last chunk of the message fits perfectly inside a block (i.e. the size of the message is a multiple of the block size), you will have to add a dummy last block.

If you are interested in researching some of the more advanced methods, look up a technique called ciphertext stealing on wikipedia: http://en.wikipedia.org/wiki/Ciphertext_stealing