[tahoe-dev] proposal: add padding

[Zooko O'Whielacronx]

On Tue, Jul 9, 2013 at 11:39 AM, Greg Troxel <gdt at ir.bbn.com> wrote:
>
> So I think before we add padding as a non-experimental features, we need
>
>   a paper analyzing the block-level-crypto vs encrypted files trade
>   space, and discussing the understand-file-size threat model

I hope such a paper comes out soon, but I kind of think this is at the
forefront of security or crypto research, so it is quite possible that
another decade may pass before the academic publication gatekeepers
begin to care about these issues. If that's the way it is going to go,
I don't want to be waiting for that before adding protection for our
users.

The two recent examples that seem relevant to me are the CRIME attack
by Rizzo and Duong (not published in a peer-reviewed paper AFAIK) and
the "Message-Locked Encryption" paper by Ristenpart et al.:

http://eprint.iacr.org/2012/631

>   a discussion of the threat model.  While it's easy to say "it would be
>   nice if an attacker couldn't understand file structure", if we really
>   mean "someone should not be able to guess if you are storing MP3s",
>   that's something else, and not fixed by padding to multiple of 512
>   bytes.

That's a good point. It related to something that someone said in
response to this on twitter… Let's see…

Bah, I can't find it, but someone pointed out that if someone uploads
many different files that are the same size, an observer would be able
to deduce that they are all the same size, and what size they are,
from the distribution of padded-sizes.

Please also see the comments left by nickm on the ticket. Nickm is a
lead developer on Tor and has been studying and working on closely
related problems for many years now. I have a high estimation of his
opinions on such things.

https://tahoe-lafs.org/trac/tahoe-lafs/ticket/2018# padding to hide
the size of plaintexts

See also comments from Marsh Ray, who is also a pro. (Marsh is one of
the few people who can put on their c.v. that they found a critical
security flaw in SSL.)

> Alternatively, one could look at things like bup, which do splitting based on rolling checksums and hash-level dedup.  By using bup and storing in tahoe, one probably gets most of the desired properties.

Yes, this is very interesting! I think there's potentially a lot of
value to be gained from this. Hm, actually I'm going to reply to this
in a separate reply.

Regards,

Zooko