[messaging] Padding

[Guy K. Kloss]

On 27/06/14 06:57, Michael Rogers wrote:
> On 08/06/14 06:12, David Leon Gil wrote:
>> *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.

Triggered by this discussion I have just that implemented last week in
our multi-party encryption protocol. Thanks for the discussion, everyone!

> It seems to me that the information leak depends on the observer's
> prior knowledge about possible message sizes. For example, if the
> observer knows that the message is either "Yes" or "No" then padding
> to the next power of two does nothing to conceal the message size
> (which in turn reveals the content).

For that reason, I've looked at a certain base-line minimum message
size. Initially I was inspired by TXT/SMS messages and Tweets with 140
chars, that seem to capture a good portion of the average messages
already. And in an interactive chat, one tends to keep thoughts shorter
any way, and then rather send multiple messages. This led me to assume
128 characters (as a convenient power of two size) to be of a
sufficient/good size for English speakers.

To back this up, I have found some analysis of chat log dumps performed
on Yahoo messengers, which confirmed my assumptions [0]. So, in the end
I am padding every message up to that base-line size, and for messages
exceeding it, it will be a power-of-two multiple of that size.

Guy


[0] S. Gianvecchio, M. Xie, Z. Wu, and H. Wang.
    "Measurement and classification of humans and bots in internet
    chat."
    Proceedings of the 17th USENIX Security Symposium (Security 2008),
    San Jose, CA, July 2008.

http://usenix.org/event/sec08/tech/full_papers/gianvecchio/gianvecchio.pdf

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: OpenPGP digital signature
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20140627/07cc887c/attachment.sig>