[tahoe-dev] “On the limits of the use cases for authenticated encryption”

Wed Apr 25 12:50:07 UTC 2012

On Wed, Apr 25, 2012 at 1:00 PM, Zooko Wilcox-O'Hearn <zooko at zooko.com>wrote:

> Folks:
>
> I just wrote this essay and posted it on Google+ (which I am using
> somewhat like a blog, so this is sort of like a blog entry). A conversation
> I had with Shawn Willden on his G+ "blog" recently is one of the
> inspirations for this post.
>
> https://plus.google.com/108313527900507320366/posts/cMng6kChAAW
>
> *On the limits of the use cases for authenticated encryption*
>
> *What is authenticated encryption?*
>
> Authenticated encryption is getting a lot of attention among
> cryptographers and crypto programmers nowadays. Authenticated encryption is
> just like normal (symmetric) encryption, in that it prevents anyone who
> doesn't know the key from learning anything [*] about the text. The
> "authenticated" part is that it *also* prevents anyone who doesn't know
> the key from undetectably altering the text. (If someone who doesn't know
> the key does alter the text, then the recipient will cleanly reject it as
> corrupted rather than accepting the altered text.)
>
> It is a classic mistake for engineers using crypto to confuse encryption
> with authentication. If you're trying to find weaknesses in someone's
> crypto protocol, one of the first things to check is whether the designers
> of the protocol assumed that by encrypting some data they were preventing
> that data from being undetectably modified. Encryption doesn't accomplish
> that, so if they made that common mistake, you can attack the system by
> modifying the ciphertext. Depending on the details of their system, this
> could easily lead to a full break of the system, such that you can violate
> the security properties that they had intended to provide to their users.
>
> Since this is such a common mistake, with such potentially bad
> consequences, and because fixing it is not that easy (especially due to
> timing attacks against authentication schemes), cryptographers have studied
> how to efficiently and securely integrate both encryption and
> authentication into one package. The resulting schemes are called
> authenticated encryption schemes.
>
> In the years since cryptographers developed some good authenticated
> encryption schemes, they've started thinking of them as a "drop-in
> replacement" for normal old unauthenticated encryption schemes, and started
> suggesting that everyone should use authenticated encryption schemes
> instead of unauthenticated encryption schemes in all cases. There was a
> recent move among cryptographers, spearheaded by the estimable Daniel J.
> Bernstein, to collectively focus on developing new improved authenticated
> encryption schemes. This would be a sort of community-wide collaboration,
> now that the community-wide collaboration on secure hash functions—the
> SHA-3 contest—is coming to an end.
>
> Several modern cryptography libraries, including “Keyczar” and Daniel J.
> Bernstein's “nacl”, try to make it easy for the programmer to use an
> authenticated encryption mode and some of them make it difficult or
> impossible to use an unauthenticated encryption mode.
>
> When Brian Warner and I presented Tahoe-LAFS at the RSA Conference in
> 2010, I was surprised and delighted when an audience member who approached
> me afterward turned out to be Prof. Phil Rogaway, renowned cryptographer
> and author of a very efficient authenticated encryption scheme ("OCB
> mode"). He said something nice about our presentation and then asked why we
> didn't use an authenticated encryption mode. Shortly before that
> conversation he had published a very stimulating paper named
> “Practice-Oriented Provable Security and the Social Construction of
> Cryptography”, but I didn't read it until years later. In that fascinating
> and wide-ranging paper he opines, among many other ideas, that
> authenticated encryption is one of “the most useful abstraction boundaries”.
>
> So, here's what I wish I had been quick-witted enough to say to him when
> we met in 2010: authenticated encryption can't satisfy any of my use cases!
>
> *Tahoe-LAFS access control semantics*
>
> I'm one of the original and current designers of the Tahoe-LAFS secure
> distributed filesystem. We started out, in 2006, by choosing the access
> control semantics that we wanted to offer our users and that we knew how to
> implement. Here's what we chose:
>
> *There are two kinds of files: immutable and mutable. When you write a
> file to the filesystem you can choose which kind of file it will be in the
> filesystem. Immutable files can't be modified once they have been written.
> A mutable file can be modified by someone with read-write access to it. A
> user can have read-write access to a mutable file or read-only access to
> it, or no access to it at all.*
>
> *In addition to read-write access and read-only access, we implement a
> third, more limited, form of access which is "verify-only" access. You can
> grant someone the ability to check the integrity of your ciphertexts
> without also granting them the ability to decrypt it.*
>
> This is useful in the modern cloudy world, because with it you can
> delegate the job of auditing and repairing your files to a third party
> without becoming vulnerable to that party reading your files.
>
> (You can read a one-page summary of the Tahoe-LAFS design here:
> https://tahoe-lafs.org/trac/tahoe-lafs/browser/docs/about.rst , a more
> detailed explanation of the access control semantics here:
> https://tahoe-lafs.org/trac/tahoe-lafs/wiki/Capabilities , and a six-page
> paper about the way it is implemented with cryptography here:
> https://tahoe-lafs.org/~zooko/lafs.pdf .)
>
> *Can't be implemented with authenticated encryption!*
>
> This seems like a small, useful set of concepts which users can understand
> and employ. It doesn't do everything that everyone wants, but I think that
> it has a certain elegance, and also it has stood the test of time and has
> served many users well.
>
> Now, here are three consequences of the above design:
>
> 1. I can authorize you to check the integrity of a file (ciphertext)
> without authorizing you to read it.
>
> 2. I can authorize you to check the integrity of a file without
> authorizing you to change its contents.
>
> These two are necessary for the use case mentioned above: delegating the
> job of monitoring and repairing your data to some third party who is not
> allowed to read your data.
>
> 3. I can authorize you to read a file without authorizing you to change
> its contents.
>
> This one is necessary to implement both the immutability property of
> immutable files (nobody can change the contents, although verifiers and
> readers can check the integrity of the contents), and the authenticity
> property of mutable files (readers or verifiers can't change the contents,
> although they can verify the correctness of the contents).
>
> As far as I can tell, authenticated encryption cannot be used to implement
> these properties.
>

I really can;t work out why you say this. Or, alternatively, why it matters?

For case 1, presumably authenticated encryption can (and probably is) be
used as part of the protocols, so I don't get it.

For case 2, I guess you're saying authenticated encryption does not
directly provide the properties you want. So what? Are you saying that
authenticated encryption ought to be good for anything with the words
"authentication" and "encryption" in its description?

Or, are you saying that if you replace unauthenticated encryption with
authenticated encryption it actually breaks your system? If so, I'd like to
see examples....

>
> *What does this imply for other users of cryptography?*
>
> I'm not sure if the Tahoe-LAFS design is sort of the odd duck, and all the
> rest of the world should go ahead and upgrade from unauthenticated
> encryption to authenticated encryption, or if this mismatch is a warning
> sign. Maybe authenticated encryption isn't the most useful abstraction
> boundary after all.
>
> Maybe we should have a conversation about which abstractions benefit our
> users. I think it helps to work “top-down”, from use cases (e.g. one-to-one
> chat, group chat, file-sharing, web hosting, live file-editing
> collaboration, streaming video, voice, etc.) to desired semantics, and then
> to the security properties of protocols. So far I think the enthusiasm for
> authenticated encryption has been somewhat “bottom-up”—after we all
> witnessed the repeated mistake of relying on encryption for authentication,
> we invented a way to prevent that, and then started thinking that we should
> apply the solution to all uses.
>
> [*] Except they get to learn the length of it, depending on your padding.
> And of course they get to learn from where and to where it was transmitted,
> and when, depending on how your comms work. That's called "traffic
> analysis" and it is often the most valuable information to the attacker
> anyway.
>

BTW, IMO the "enthusiasm" for authenticated encryption comes from the fact
that we have needed and used it without having any actual definition of
what it is or basis for knowing when we've got it right. With the result
that we have got it wrong. I don't think the need for it has changed at
all, just the recognition that there are good ways to do it. And other ways.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://tahoe-lafs.org/pipermail/tahoe-dev/attachments/20120425/669063ed/attachment-0001.html>