<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN" "http://www.w3.org/TR/REC-html40/loose.dtd"> <html><body> <span id="mailbox-conversation"><div>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.*</div> <div><br></div> <div>(Message-length is one of the parameters that a high-throughput packet filter can filter on; it is often directly exposed by transport protocols.)</div> <div><br></div> <div>*Worst choice:* No padding. Obviously never desirable.</div> <div><br></div> <div>*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.</div> <div><br></div> <div>(It's bad because any padding rule which costs O(k)-space asymptotically leaks an unbounded amount of information.)</div> <div><br></div> <div>*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.</div> <div><br></div> <div>(Goldreich discusses this somewhere in his books. It might be an exercise or footnote...)</div> <div><br></div> <div>There are better choices, but they require some prior knowledge of the (unpadded) message-length distribution $p(length)$.</div> <div><br></div> <div>*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.)</div> <div><br></div> <div>*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?)</div> <div><br></div> <div>Questions:</div> <div><br></div> <div>Q1. Does any publicly available messaging cryptosystem use exponential padding?</div> <div><br></div> <div>Q2.Are there any good publications on adversarial models for message padding? </div> <div><br></div> <div>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))$.)</div> <div><br></div> <div>- David</div> <div><br></div> <div><div>*Here, by padding I mean extra bytes in wire form that are indistinguishable from the encrypted message, however generated.</div></div></span><div class="mailbox_signature">—<br>Sent using alpine: an Alternatively Licensed Program for Internet News and Email</div> </body></html>