[messaging] Padding

[David Leon Gil]

Something I haven't seen discussed here (though perhaps I missed something while skimming the huge archive), but consider critical in designing messaging protocols to counter mass surveillance: message-length padding.*


(Message-length is one of the parameters that a high-throughput packet filter can filter on; it is often directly exposed by transport protocols.)


*Worst choice:* No padding. Obviously never desirable.


*Bad choice:* Fixed-block-size padding. (But see infra.) How bad this is depends on the block-length. At typical block-cipher lengths of 16-64 bytes, it's pretty bad for human-readable messages. At, e.g., Clef's detachment block size, it's bad mostly for largish files.


(It's bad because any padding rule which costs O(k)-space asymptotically leaks an unbounded amount of information.)


*Min-entropy choice:* Exponential-padding, i.e., padding to the next-highest power of some constant, c. This asymptotically leaks a bounded amount of information. And it only costs O(n) space. I am puzzled why this is not the default for most messaging systems.


(Goldreich discusses this somewhere in his books. It might be an exercise or footnote...)


There are better choices, but they require some prior knowledge of the (unpadded) message-length distribution $p(length)$.


*Best choice, if you know $max(p)$:* Pad all messages to max(d). (But this is *not* a good choice if your $p$ is not the true distribution and users can substitute rate for length. For some applications -- I am thinking IRC-like systems -- a fixed message size and rate is plausible, however.)


*Best choice, if you know a good approximation to $p(length)$:* Choose a distribution which majorizes $p$ and draw random padded-message-lengths from that. (Question: For a logspace adversary equipped with an oracle for $p(padded)$ is it sufficient to simply reject lengths that are too short for a given message and draw again from the same distibution?)


Questions:


Q1. Does any publicly available messaging cryptosystem use exponential padding?


Q2.Are there any good publications on adversarial models for message padding? 


Q3. Has any work been done on padding-scheme interoperability? (E.g., it's fairly clear that it is undesirable to count an ephemeral public key against message length in a system that provides multiple curves unless $len(k_1, k_2) <<< len(min(d))$.)


- David


*Here, by padding I mean extra bytes in wire form that are indistinguishable from the encrypted message, however generated.

—
Sent using alpine: an Alternatively Licensed Program for Internet News and Email
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20140607/1b2cf226/attachment.html>