Hiding the Lengths of Encrypted Messages via Gaussian Padding

Secure network protocols like TLS, QUIC, SSH and IPsec allow for additional padding to be used during encryption in order to hide message lengths. While it is impossible to conceal message lengths completely, without drastically degrading efficiency, such mechanisms aim at causing as much frustration as possible to the prospective attacker. However, none of the protocol specifications provide any guidance on how to select the length of this padding. Several works have highlighted how the leakage of message lengths can be exploited in attacks, but the converse problem of how to best defend against such attacks remains relatively understudied. We make this the focus of our work and present a formal treatment of length hiding security in a general setting. Prior work by Tezcan and Vaudenay suggested that sampling the padding length uniformly at random already achieves the best possible security. However we show that this is only true in the limited setting where only a single ciphertext is available to the adversary. If multiple ciphertexts are available to the adversary, then sampling the padding length according to a Gaussian distribution yields quantifiably better security for the same overhead. In fact, in this setting, uniformly random padding turns out to be among the worst possible choices. We confirm experimentally the superior performance of Gaussian padding over uniform padding in the context of the CRIME/BREACH attack.