[tahoe-dev] proposal: add padding

[Zooko O'Whielacronx]

Folks:

I think Tahoe-LAFS should automatically pad files when encrypting them
in order to hide the specific length of the file. Avi Freedman just
reminded me of this issue in private email conversation, so I finally
got around to writing up a proposal that has been nagging me for years
(ticket #2018):

-------

Even though LAFS keeps the contents of files secret from attackers, it
currently exposes the length (in bytes) of that content. This can be
useful information to an attacker in various ways. For one thing, an
attacker might be able to "recognize" specific files or kinds of files
from a pattern of file sizes. More subtle dangers may also exist,
depending on the circumstances, for example the famous "CRIME" attack
on SSL (​http://security.stackexchange.com/questions/19911/crime-how-to-beat-the-beast-successor/19914#19914)
which depends crucially on the attacker being able to measure the
exact size of certain encrypted output. Ticket #925 is about how
potentially interesting metadata about the LAFS filesystem itself can
be inferred from the byte-level granularity of exposed sizes.

I propose that LAFS automatically add a randomized number of padding
bytes to files when encrypting. Concretely, how about something like
this. With F as the file size in bytes,

    Let the "max padding", X, be 32 * log₂(F), rounded up to the
nearest multiple of 32.

    Choose a number of padding bytes, P, evenly from [0..X) as
determined by the encryption key. Note: this is important that the
number is deterministic from the key, so that multiple encryptions of
the same-keyed file will not pick different random numbers and allow
an attacker to statistically observe the padding's size.

    Append P bytes of padding (0 bytes) to the ciphertext before encryption.

https://tahoe-lafs.org/trac/tahoe-lafs/ticket/925# Information leak to
holders of a directory read cap, about whether each dir entry is
writeable and the length of its write cap
https://tahoe-lafs.org/trac/tahoe-lafs/ticket/2018# padding to hide
the size of plaintexts