Random data CBC padding scheme? When using AES in CBC mode, padding is required when the last plaintext block has not the length required by the cipher. Let's say $k$ mode bytes would be required to fill the block. My idea was to pad the last block with $k-1$ random bytes followed by one byte that corresponds to the integer value of $k$ (or $k-1$). That is, it tells how much padding was added. When decrypting, the previous decrypted block is held back, until it is clear that it was not the second to last block. If it was, the padding is removed accordingly and the full plain text is obtained.
Is this a secure way to pad a message?
More generally, are there problems that may arise from this method of padding, or can an incorrect padding scheme compromise the cipher?
Padding is dangerous. CBC mode with padding is secure against chosen-plaintext attacks, where the adversary can convince the legitimate party to encrypt messages and obtain the ciphertexts. But it is usually not secure against chosen-ciphertext attacks, where the adversary can craft ciphertexts and obtain information about the corresponding plaintext. Specifically, padding tends to be vulnerable to padding oracle attacks, where the adversary sends specially-crafted ciphertexts and does not obtain the corresponding plaintext, but finds out whether the padding in the ciphertext is valid. The adversary might find out, for example, because the decryptor emits an error message if the ciphertext is invalid, or because the decryptor does not carry out the action that it would carry out on a valid message, or because the decryptor takes a different amount of time to process messages with valid or invalid padding.
How devastating padding oracle attacks are depends on the nature of the padding and how much partial plaintext the adversary is likely to know. A well-known example is the Lucky Thirteen attack, where the conjunction of allowing up to 256 bytes of padding, and having 13 bytes of known plaintext in a message header, leads to a practical attack to fully decrypt a TLS connection against an unprotected implementation in many realistic scenarios.
In your case, the opportunities are more limited for the attacker, but the scheme is still vulnerable. Suppose the adversary knows or can guess the first 15 bytes of plaintext in a block and would like to know the last byte. The adversary can send that block to be decrypted as a 16-byte message, and learn at least whether the last byte is a valid value (1 to 16). This is not a complete breach of confidentiality, but it is a breach of confidentiality.
Padding oracle attacks depend on the adversary learning whether the padding is correct. A defense is to not have any invalid padding. An easy tweak to your scheme has this property: make the top 4 bits of the last byte random as well. This way no padding is invalid and therefore no padding oracle attack is possible as such. However, the adversary may still be able to learn the length of the plaintext (for example by measuring very precisely how long it takes to process), and if the ciphertext was one crafted by the adversary, this length could be in fact a confidential byte of the message.
To have an actual secure cipher, you need to use authenticated encryption. Authenticated encryption is not vulnerable to chosen-ciphertext attacks because the attacker cannot forge a superficially valid ciphertext: all valid ciphertexts include an authentication tag which cannot be calculated without the secret key. You can build authenticated encryption by taking unauthenticated ciphertexts and adding a MAC (“encrypt-then-MAC”), and that works even if the encryption part is padded CBC. On this topic, see Should we MAC-then-encrypt or encrypt-then-MAC?. However, CBC has no advantage over streaming mode, and all common proper authenticated encryption modes use CTR mode for the encryption part.