Editing Padding (cryptography) (section)

==Traffic analysis and protection via padding==

Even if perfect cryptographic routines are used, the attacker can gain knowledge of the amount of traffic that was generated. The attacker might not know what [[Alice and Bob]] were talking about, but can know that they ''were'' talking and ''how much'' they talked. In some circumstances this leakage can be highly compromising. Consider for example when a military is organising a secret attack against another nation: it may suffice to alert the other nation for them to know merely that there ''is'' a lot of secret activity going on.

As another example, when encrypting [[VOIP|Voice Over IP]] streams that use variable bit rate encoding, the number of bits per unit of time is not obscured, and this can be exploited to guess spoken phrases.<ref>{{cite journal|title=Uncovering Spoken Phrases in Encrypted Voice over IP Conversations|first1=Charles V.|last1=Wright|first2=Lucas|last2=Ballard|first3=Scott E.|last3=Coull|first4=Fabian|last4=Monrose|first5=Gerald M.|last5=Masson|date=1 December 2010|journal=ACM Transactions on Information and System Security |volume=13|issue=4|pages=35|doi=10.1145/1880022.1880029|citeseerx=10.1.1.363.1973|s2cid=9622722}}</ref> Similarly, the burst patterns that common video encoders produce are often sufficient to identify the streaming video a user is watching uniquely.<ref>{{cite conference|url=https://www.usenix.org/conference/usenixsecurity17/technical-sessions/presentation/schuster|title=Beauty and the Burst: Remote Identification of Encrypted Video Streams|first1=Roei|last1=Schuster|first2=Vitaly|last2=Shmatikov|first3=Eran|last3=Tromer|conference=USENIX Security Symposium|conference-url=https://www.usenix.org/conference/usenixsecurity17|date=August 2017}}</ref> Even the ''total size'' of an object alone, such as a website, file, software package download, or online video, can uniquely identify an object, if the attacker knows or can guess a known set the object comes from.<ref>{{cite conference|chapter=Fingerprinting Websites Using Traffic Analysis|first1=Andrew|last1=Hintz|title=Privacy Enhancing Technologies |series=Lecture Notes in Computer Science |conference=International Workshop on Privacy Enhancing Technologies|date=April 2002|volume=2482 |pages=171–178 |doi=10.1007/3-540-36467-6_13|isbn=978-3-540-00565-0 }}</ref><ref>{{cite conference|chapter=Statistical Identification of Encrypted Web Browsing Traffic|first1=Qixiang|last1=Sun|first2=D.R.|last2=Simon|first3=Yi-Min|last3=Wang|first4=W.|last4=Russell|first5=V.N.|last5=Padmanabhan|first6=Lili|last6=Qiu|title=Proceedings 2002 IEEE Symposium on Security and Privacy |conference=IEEE Symposium on Security and Privacy|date=May 2002|pages=19–30 |doi=10.1109/SECPRI.2002.1004359|isbn=0-7695-1543-6 }}</ref><ref name="pets19">{{cite journal|url=https://petsymposium.org/2019/files/papers/issue4/popets-2019-0056.pdf|title=Reducing Metadata Leakage from Encrypted Files and Communication with PURBs|first1=Kirill|last1=Nikitin|first2=Ludovic|last2=Barman|first3=Wouter|last3=Lueks|first4=Matthew|last4=Underwood|first5=Jean-Pierre|last5=Hubaux|first6=Bryan|last6=Ford|journal=Proceedings on Privacy Enhancing Technologies (PoPETS)|volume=2019|issue=4|pages=6–33|doi=10.2478/popets-2019-0056|year=2019|arxiv=1806.03160 |s2cid=47011059|doi-access=free}}</ref>  The [[Side-channel attack|side-channel]] of encrypted content length was used to extract passwords from [[HTTPS]] communications in the well-known [[CRIME]] and [[BREACH]] attacks.<ref>{{cite report|url=https://tools.ietf.org/html/rfc7457|title= Summarizing Known Attacks on Transport Layer Security (TLS) and Datagram TLS (DTLS)|first1=Y.|last1=Sheffer|first2=R.|last2=Holz|first3=P.|last3=Saint-Andre|date= February 2015}}</ref>

Padding an encrypted message can make [[traffic analysis]] harder by obscuring the true length of its payload.  The choice of length to pad a message to may be made either deterministically or randomly; each approach has strengths and weaknesses that apply in different contexts.

===Randomized padding===

A random number of additional padding bits or bytes may be appended to the end of a message, together with an indication at the end how much padding was added.  If the amount of padding is chosen as a uniform random number between 0 and some maximum M, for example, then an eavesdropper will be unable to determine the message's length precisely within that range.  If the maximum padding M is small compared to the message's total size, then this padding will not add much [[Overhead (computing)|overhead]], but the padding will obscure only the least-significant bits of the object's total length, leaving the approximate length of large objects readily observable and hence still potentially uniquely identifiable by their length.  If the maximum padding M is comparable to the size of the payload, in contrast, an eavesdropper's uncertainty about the message's true payload size is much larger, at the cost that padding may add up to 100% overhead ({{math|2×}} blow-up) to the message.

In addition, in common scenarios in which an eavesdropper has the opportunity to see ''many'' successive messages from the same sender, and those messages are similar in ways the attacker knows or can guess, then the eavesdropper can use statistical techniques to decrease and eventually even eliminate the benefit of randomized padding.  For example, suppose a user's application regularly sends messages of the same length, and the eavesdropper knows or can guess fact based on fingerprinting the user's application for example.  Alternatively,  an active attacker might be able to ''induce'' an endpoint to send messages regularly, such as if the victim is a public server.  In such cases, the eavesdropper can simply compute the average over many observations to determine the length of the regular message's payload.

===Deterministic padding===

A deterministic padding scheme always pads a message payload of a given length to form an encrypted message of a particular corresponding output length.  When many payload lengths map to the same padded output length, an eavesdropper cannot distinguish or learn any information about the payload's true length within one of these length ''buckets'', even after many observations of the identical-length messages being transmitted.  In this respect, deterministic padding schemes have the advantage of not leaking any additional information with each successive message of the same payload size.

On the other hand, suppose an eavesdropper can benefit from learning about ''small'' variations in payload size, such as plus or minus just one byte in a password-guessing attack for example.  If the message sender is unlucky enough to send many messages whose payload lengths vary by only one byte, and that length is exactly on the border between two of the deterministic padding classes, then these plus-or-minus one payload lengths will consistently yield different padded lengths as well (plus-or-minus one block for example), leaking exactly the fine-grained information the attacker desires.  Against such risks, randomized padding can offer more protection by independently obscuring the least-significant bits of message lengths.

Common deterministic padding methods include padding to a constant block size and padding to the next-larger power of two.  Like randomized padding with a small maximum amount&nbsp;''M'', however, padding deterministically to a block size much smaller than the message payload obscures only the least-significant bits of the messages true length, leaving the messages's true approximate length largely unprotected.  Padding messages to a power of two (or any other fixed base) reduces the maximum amount of [[Entropy (information theory)|information]] that the message can leak via its length from {{math|''O''(log ''M'')}} to {{math|''O''(log log ''M'')}}.  Padding to a power of two increases message size overhead by up to 100%, however, and padding to powers of larger integer bases increase maximum overhead further.

The PADMÉ scheme, proposed for [[PURB (cryptography)|padded uniform random blobs or PURBs]], deterministically pads messages to lengths representable as a [[IEEE 754|floating point number]] whose mantissa is no longer (i.e., contains no more significant bits) than its exponent.<ref name="pets19" />  This length constraint ensures that a message leaks at most {{math|''O''(log log ''M'')}} bits of information via its length, like padding to a power of two, but incurs much less overhead of at most 12% for tiny messages and decreasing gradually with message size.