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
_______________________________________________
Messaging mailing list
[email protected]
https://moderncrypto.org/mailman/listinfo/messaging
