[tahoe-dev] convergent encryption reconsidered

[zooko]

(This is an ASCII rendering of https://zooko.com/ 
convergent_encryption_reconsidered.html .)

                  Convergent Encryption Reconsidered

    Written by Zooko Wilcox-O'Hearn, documenting ideas due to Drew
    Perttula, Brian Warner, and Zooko Wilcox-O'Hearn, 2008-03-20.

   Abstract

    Convergent encryption is already known to suffer from a
    confirmation-of-a-file attack. We show that it suffers also
    from a learn-partial-information attack. The conditions under
    which this attack works cannot be predicted by a computer
    program nor by an unsophisticated user. We propose a solution
    which trades away part of the space savings benefits of
    convergent encryption in order to prevent this new attack. Our
    defense also prevents the old attack. The issues are presented
    in the context of the Tahoe Least-AUthority Grid File System, a
    secure decentralized filesystem.

   Background -- The Confirmation-Of-A-File Attack

    Convergent encryption, also known as content hash keying, was
    first mentioned by John Pettitt on the cypherpunks list in 1996
    [1], was used by Freenet [2] and Mojo Nation [3] in 2000, and
    was analyzed in a technical report by John Doceur et al. in
    2002 [4]. Today it is used by at least Freenet, GNUnet [5],
    flud [6], and the Tahoe Least-AUthority Grid File System [7].
    The remainder of this note will focus on the Tahoe LAUGFS
    filesystem. The use of convergent encryption in other systems
    may have different consequences than described here, because of
    the different use cases or added defenses that those systems
    may have.

    Convergent encryption is simply encrypting a file using a
    symmetric encryption key which is the secure hash of the
    plaintext of the file.

    Security engineers have always appreciated that convergent
    encryption allows an attacker to perform a
    confirmation-of-a-file attack -- if the attacker already knows
    the full plaintext of a file, then they can check whether a
    given user has a copy of that file.

    Whether this confirmation-of-a-file attack is a security or
    privacy problem depends on the situation. If you want to store
    banned books or political pamphlets without attracting the
    attention of an oppressive government, or store pirated copies
    of music or movies without attracting the attention of
    copyright holders, then the confirmation-of-a-file attack is
    potentially a critical problem. On the other hand, if the
    sensitive parts of your data are secret personal things like
    your bank account number, passwords, and so forth, then it
    isn't a problem. Or so I -- and as far as I know everyone else
    -- thought until March 16, 2008.

    I had planned to inform users of the current version of Tahoe
    -- version 0.9.0 -- about the confirmation-of-a-file attack by
    adding a FAQ entry:

      Q: Can anyone else see the contents of files that I have not
      shared?

      A: The files that you store are encrypted so that nobody can
      see a file's contents (unless of course you intentionally
      share the file with them). However, if the file that you
      store is something that someone has already seen, such as if
      it is a file that you downloaded from the Internet in the
      first place, then they can recognize it as being the same
      file when you store it, even though it is encrypted. So
      basically people can tell which files you are storing if they
      are "publically known" files, but they can't learn anything
      about your own personal files.

    However, four days ago (on March 16, 2008) Drew Perttula and
    Brian Warner came up with an attack that shows that the above
    FAQ is wrong.

   The Learn-Partial-Information Attack

    They extended the confirmation-of-a-file attack into the
    learn-partial-information attack. In this new attack, the
    attacker learns some information from the file. This is done by
    trying possible values for unknown parts of a file and then
    checking whether the result matches the observed ciphertext.
    For example, if you store a document such as a form letter from
    your bank, which contains a few pages of boilerplate legal text
    plus a few important parts, such as your bank account number
    and password, then an attacker who knows the boilerplate might
    be able to learn your account number and password.

    For another example, if you use Tahoe to backup your entire
    home directory, or your entire filesystem, then the attacker
    gains the opportunity to try to learn partial information about
    various files which are of predictable format but have
    sensitive fields in them, such as .my.cnf (MySQL configuration
    files), .htpasswd, .cvspass, .netrc, web browser cookie files,
    etc.. In some cases, files such as these will contain too much
    entropy from the perspective of the attacker to allow this
    attack, but in other cases the attacker will know, or be able
    to guess, most of the fields, and brute force the remainder.

    Designers of these systems -- MySQL, Apache, etc. -- know that
    user secrets are often guessable (increasingly often,
    nowadays), which is why such applications limit the rate at
    which clients can attempt to login and try passwords. From a
    cryptographer's perspective, using Tahoe with convergent
    encryption on all files allows an attacker to use off-line
    attacks instead of on-line attacks, which renders vulnerable
    some secrets which were formerly safe.

    The amount of information that the attacker can learn using
    this attack is upper-bounded by two things: first, by the
    attacker's computational capacity. If the attacker can perform
    no more than 2^64 computations, then he can learn no more than
    64 bits worth of information from any file. Note that he does
    not have to spend all of this computation attacking a single
    file owned by a single user -- instead he can attack many users
    and many files in parallel with the same computation. (He can
    also burn his resulting values into a rainbow table on DVD and
    sell it on the Web so that the buyer can attack other users
    using the result of the attacker's computation. This is
    currently done for hashed or encrypted passwords.)

    The second upper bound is the amount of entropy in the file
    from the attacker's perspective. If the file contains more
    entropy, from the attacker's perspective, than his
    computational capacity, then he learns nothing about the file
    (except that the file was not any of the things that he guessed
    that it might be). Note that the amount of entropy is relative
    to the attacker, not intrinsic to the file. You may think that
    a PDF file with millions of bytes in it would have a lot of
    entropy, but if it happens to be a form letter from your bank,
    and if the attacker happened to receive the same letter with
    only a few fields different, then it contains little entropy to
    him. This subtlety may underlie the failure of many, including
    myself, to understand this issue sooner. Observe also that it
    is not possible for a computer program to determine whether a
    given file has sufficient entropy -- the answer to that
    question depends on what the attacker knows and on how
    sophisticated and accurate is his model of the victim.

    (Note: ideas like this are often Obvious in Retrospect. If this
    one was Obvious in Forespect to anyone, I would appreciate
    references. I've scoured the citations mentioned in this note
    and found no hint of it.)

   Defense Against Both Attacks

    What can we do about this? Well, in Tahoe the application which
    uses the secure filesystem, or even the human user which uses
    the application, can choose to use convergent encryption or not
    on a per-file basis, and there is no backwards-compatibility
    problem (Tahoe v0.9.0 will be able read files which are written
    with or without convergent encryption).

    However, we can do better than that by creating a secret value
    and mixing that value into the per-file encryption key (so
    instead of symmetric_key = H(plaintext), you have symmetric_key
    = H(added_secret, plaintext), where "," denotes an unambiguous
    encoding of both operands). This idea is due to Brian Warner
    and Drew Perttula.

    The set of people who know this added secret is the set of
    people whose files can converge, and it is also the set of
    people who are able to perform either of the two attacks
    described above. This means that attackers with whom you do not
    share this added secret are prevented from performing either
    attack on your files.

    One policy which is easy to implement is for each user to keep
    the added secret to themselves. This would make successive
    uploads of the same file by the same user converge, but would
    not achieve convergence with any other user's files, and would
    fully protect the users against these two attacks.

    There are various possibilities for how to automatically decide
    whether or not to use convergent encryption on a given file or
    set of files -- heuristics based on file size, name or
    location, white lists or black lists of files, and perhaps ways
    that the user interface could make the alternatives apparent to
    the user. These ideas are out of the scope of this note (and,
    for now, of the Tahoe decentralized filesystem itself -- the
    application written atop Tahoe can decide).

    It should be noted that if the exact size of a file is divulged
    then this information can be used for a confirmation-of-a-file
    attack, if there are few likely files of that exact size.
    Adding padding to files before encryption can substantially
    reduce the effectiveness of that attack vector, as is already
    well known.

   A Comment About Space Savings

    One of the original motivations for convergent encryption, as
    expressed in Doceur's technical report, is to conserve storage
    space by coalescing identical files. That technical report
    cited an experiment by Doceur et al. at Microsoft in 2002 which
    showed that coalescing all files on a set of 585 Windows
    workstations resulted in a 50% space savings. My suspicion is
    that the gains available for modern uses are nowhere near that
    good -- I wouldn't be surprised if it were less than 5% for
    typical uses of the Tahoe Least-AUthority Grid File System.

    My reasoning is:
     1. The Doceur et al. test set was probably the ideal test set
        to highlight the advantages of coalescing: it was hundreds
        of workstations, which probably all followed the same
        Information Technology Department policies, which were
        probably homogeneous, and which were probably packed with
        many of the same software products (especially Microsoft
        products).
     2. Movies and music. In 2002, on Windows workstations in an
        office at Microsoft, there probably weren't any movies. For
        some of the probable use cases for Tahoe, movies and
        collections of music are the largest component. The
        presence of movie files, which are large, could increase or
        decrease the proportion of savings from coalescing files,
        depending on the degree to which those files are shared
        among multiple users, which brings us to the next point:
     3. The Long Tail; Today there seems to be a more diverse set
        of things taking up a bigger portion of the total.
     4. Personally-produced photos and movies. It seems like some
        of the files that people are most eager to back up and to
        share are the product of their own cameras. Such files will
        typically be shared by only one or a few users.

    The question of how much space is saved by convergence in a
    typical use of Tahoe remains open. Hopefully someone will
    perform empirical measurements to answer this question in the
    near future.

   Conclusions

    Convergent encryption renders user files vulnerable to a
    confirmation-of-a-file attack. We already knew that. It also
    renders user files vulnerable to a learn-partial-information
    attack in subtle ways. We didn't think of this until now. My
    search of the literature suggests that nobody else did either.

    The addition of an added secret to be mixed into the symmetric
    encryption key allows you to limit the scope of users with whom
    your files will converge. Attackers who are outside of this set
    of users cannot use the new learn-partial-information, nor can
    they use the old confirmation-of-a-file attack.

    The Tahoe Least-AUthority Grid File System will probably
    release v0.9.1, to succeed the current v0.9.0 release, which
    will add the feature of mixing in an added secret to the
    symmetric encryption key when doing convergent encryption,
    which will turn that feature on by default, and which will
    perhaps offer a way through the API and or UI to control that
    feature on a per-user and per-file basis.

     Citations

    [1] http://cypherpunks.venona.com/date/1996/02/msg02013.html

    [2]
    http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.10.4919

    [3]
    http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.59.9607

    [4]
    http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.8.7586

    [5] http://gnunet.org

    [6] http://flud.org

    [7] http://allmydata.org

     Zooko

    Last modified: Sat May 5 15:13:38 MDT 2007