8
$\begingroup$

Is there any way to hide message length from adversary in symmetric key cryptography?

Suppose we want to hide message length from active and efficient adversaries.

$\endgroup$
  • $\begingroup$ Coincidentally, I answered a very similar question recently with crypto.stackexchange.com/questions/59098/…. It's a proven technique for an established communications channel that relies on continuous transmission of mainly fake data/noise. $\endgroup$ – Paul Uszak May 12 '18 at 20:39
6
$\begingroup$

Yes, you can pad the message. As long as you can retrieve the location of the message inside the padded plaintext then you can hide the exact message length.

Note that statistical methods can still be applied; you will have to always create a message size of $N$ if you want to full hide the length of messages of $0$ to $N$ in length - excluding normal padding that may be required for block modes of encryption. Obviously, you still leak the information that the message is lower than $N$. But that cannot be avoided; an encrypted message of size $N$ cannot be created for all messages larger than $N$.

Just adding a padding of random length may not be good enough as you will still leak some data about the message size if you average things out. This paper by Cihangir Tezcan and Serge Vaudenay makes it clear that providing random padding cannot practically hide enough information when a minimum amount of security is required. It still depends on the use case if random (sized) padding is sufficient for a use case, but it should be avoided.


There are several ways of padding that are independent of the message contents, that allow for deterministic unpadding:

  • include (prefix) the message length with the size, then use any kind of padding behind the message up to the size N of the input plaintext, note that you must be able to parse the length encoding (having a single ASN.1 / DER encoded structure is a special case of this);
  • perform bit padding, putting a single bit valued 1 and then add zero's untile you reach size N (or, for byte oriented protocols, use a byte valued 0x80 or 0x01 depending on the bit order within the bytes - usually big endian / 0x80 is used);
  • end the padding with a padding length indicator, retrieve it and remove the bytes (possibly validating the intermediate bytes, depending on the scheme).

The advantage of using the length of the message is that you can skip decryption of the last part of the ciphertext. But note that this doesn't work for authenticated encryption with one authentication tag, and that not decrypting the last part may leak the size of the plaintext through side channel attacks.

The disadvantage of bit padding is that you may need to go all of the decrypted bytes until you find the set bit (or the byte with the single bit set), starting at the end of the decrypted bytes.


Note that you'd need at least one bit or byte for the bit padding method or space enough to store the length encoding. It is impossible to create a deterministic unpadding method where the size of the message M is identical to N and the message itself cannot be used to determine the size.

|improve this answer|||||
$\endgroup$
  • 1
    $\begingroup$ Bit padding makes it very easy to "retrieve the location of the message inside the padded plaintext". $\hspace{.44 in}$ $\endgroup$ – user991 May 18 '14 at 18:25
  • $\begingroup$ @RickyDemer Yes, or including the length of the plaintext within the message and adding zero's, for instance using ASN.1. I like bitpadding. It does not have a maximum padding length and it does not require byte boundaries either. Finally, it is an extremely simple mechanism. It also poses on question less than PKCS#7 padding: "Should I check the values between the plaintext and the final byte value?" $\endgroup$ – Maarten Bodewes May 18 '14 at 20:40
  • $\begingroup$ @RickyDemer I made substantial edits on that article in Wiki actually, check for "Owlstead" in the history :) $\endgroup$ – Maarten Bodewes May 18 '14 at 20:43
  • 2
    $\begingroup$ I read abstract of this paper and it explains more about this issue:cihangir.forgottenlance.com/papers/lengthhiding-corrected.pdf $\endgroup$ – abdolahS May 19 '14 at 15:00
  • $\begingroup$ That paper nicely backs up that first-to-last paragraph with a slightly more scientific explanation :) $\endgroup$ – Maarten Bodewes May 12 '18 at 18:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.