Stream cipher padding

Question

Problem example

Let's say I have a plaintext with length of 50 bytes. I want to encrypt it using a stream encryption algorithm ChaCha20-Poly1305.

Poly1305 generate a 128 bit hash (16 bytes), so encrypted message will be of length 50 + 16 = 66... If I append nonce to it (12 bytes), it'll be 78 bytes.

But... When I add for example 1 more byte to a plain text, cipher text will be of a length 79 bytes (+1).

What I need

I need to hide a real plaintext length. I heard about oracle padding attack, so if I use some padding, or create my own padding scheme (until plaintext length will be divisible by 16), will this attack affect me?

My question is: It is safe to use a padding to an authenticated stream cipher, like ChaCha20-Poly1305?

Answer 1

Is it safe to use padding with an authenticated stream cipher like ChaCha20-Poly1305?

Yes, assuming you authenticate the padding so it can't be tampered with. Applying the padding before encryption solves this problem and is the typical approach. Alternatively, padding could be authenticated using the associated data.

I don't want people to know the "correct" plaintext length.

Effective padding is very difficult, so any simple or custom scheme (e.g. padding to a fixed block size) will likely either reveal the approximate length still or incur massive overhead (e.g. double the length of the message).

Fortunately, there are two padding schemes for this purpose:

1. PADMÉ is a deterministic scheme designed to limit length leakage with minimal overhead. It was created for encoding padded uniform random blobs (PURBs).
2. Covert's scheme provides random padding whilst ensuring a minimum fixed amount of padding for small messages. It was created for the Covert file encryption tool, and I'm now using it in Kryptor, my file encryption tool.

Note that these only calculate the amount of padding. You need to use something like ISO/IEC 7816-4 to apply the padding in a reversible manner without storing the amount.

Also, both have limitations:

• PADMÉ creates distinguishable file sizes and fails to hide the length of small messages as well as messages that vary on the border between two padding amounts. For example, messages 0-8 bytes long receive no padding, 9 bytes means 1 byte of padding, and so on.
• Covert's scheme won't protect against statistical attacks when an attacker can observe the same message padded many times, for example. It also leads to slightly more overhead and hasn't been formalised in a paper like PADMÉ.
• Implementations are rare. Few projects use either scheme, although few projects attempt to hide metadata like file lengths, largely due to complexity and performance/storage costs.

Implementations

• libsodium's ISO/IEC 7816-4
• ISO/IEC 7816-4 in C#
• PADMÉ in Go
• PADMÉ in Rust
• PADMÉ in C#
• PADMÉ in JavaScript
• Covert padding in Python
• Covert padding in C#