[tahoe-dev] combined ciphers in Tahoe-LAFS Re: Hashes in 100 year crypto

[Zooko O'Whielacronx]

Dear Jack:

Thanks a lot for bringing this issue up. Here are a few quick responses from me.

On Mon, Jul 19, 2010 at 4:42 PM, Jack Lloyd <lloyd at randombit.net> wrote:
>
>  - Figure out how to safely use Comb4P with different hash outputs
>   lengths, and use, say SHA-256 and SHA-512, or SHA-256 and Tiger, or
>   whatever.

-1 (uncertainty, complication, poor security/performance ratio)

>  - Scrap the idea of using Comb4P and use a different combiner. It's
>   possible that mere concatenation would be sufficient, in which case
>   our problem is much simpler in that we just have to choose two good
>   hashes, instead of two good hashes with identical output sizes.

+1

Have you seen my notes about this?

http://tahoe-lafs.org/pipermail/tahoe-dev/2010-June/004575.html

Oh, sorry, that might be illegible due to liberal use of non-ascii
bits. Um... Here:

http://pubgrid.tahoe-lafs.org/file/URI%3ACHK%3Agwx3rghewgci7u6dqhfq6euvqa%3Ahavl3aybdlbznne67geuiq6r4ampy5rccijjsutvqeto6t2e4hqq%3A3%3A10%3A67235/@@named=/Screen%20shot%202010-07-19%20at%2023.18.26-0600.png

>  - Choose a pair of 512-bit hashes already in Crypto++ and use those.

-1 (for the reasons you give)

>  - Choose a SHA-3 candidate (since they all support 256 bit outputs as
>   a condition of the contest) and use that paired with SHA-256.

+1 (there are several SHA-3 candidates I would be happy with)

>   Even after we've made a choice, we'd also have to get the SHA-3
>   candidate in question into Crypto++, write and test a wrapper for
>   pycryptopp, and then actually integrate it into the actual system.

Yes, there would be plenty of work to be done. Also we could consider
using Botan instead of or in addition to Crypto++. (I know, we're
opening up a whole bunch of possibilities here which may be a bit
overwhelming to Yu Xue at this stage!)

>  - The nuclear option: Nix hash combining for the current iteration of
>   100 year crypto. Have Yu Xue move on to other areas, such as tying
>   the AES/XSalsa20 combo into Tahoe proper, and/or working on digital
>   signature combinators

+2!

AES/XSalsa20 combining is well understood and Yu Xue has already
implemented the XSalsa20 wrappers (pycryptopp #40), and it is arguably
the most important part of the 100-Year-Crypto project!

That's because we can always upgrade our hash functions and digital
signature schemes year after year, and if in doing so we stay ahead of
the attackers then we can preserve our data integrity and our
unforgeability for one hundred years. But we cannot do the same for
encryption in order to preserve confidentiality for one hundred years
because an attacker could have stored our old ciphertexts for later
cryptanalysis.

Getting the combined AES/XSalsa20 deployed in Tahoe-LAFS would be the
"last 10% of the work" which takes 90% of the effort. We would require
strong backward-compatibility, testing, and packaging work. The first
version of Tahoe-LAFS to be released with this feature would have to
be able to read both old AES-encrypted and new AES/XSalsa20-encrypted
files and it would have to ''produce'' old AES-encrypted files by
default. It would have to be able to produce new
AES/XSalsa20-encrypted files if specifically configured to do so, and
of course it would have to somehow embed into the ciphertext or
capability the fact that it was using the new encryption scheme so
that downloaders could unambiguously decrypt it.

We would need to think about, document, and test what happens when an
older Tahoe-LAFS client (such as v1.7.1) finds itself faced with a
file encrypted with the new encryption.

We would want "quick start-up self-test" behavior, in the spirit of
http://tahoe-lafs.org/trac/pycryptopp/changeset/683/trunk/ , to detect
compilation bugs or other problems at run-time.

We would want to run some basic benchmarks such as the ones that
François ran on his ARM buildbot [1] just to be sure that this change
wasn't making Tahoe-LAFS go from "usable" to "unusable" on some
platform that someone cares about.

If Yu Xue could get a complete implementation of this finished and
contributed to Tahoe-LAFS I would be impressed. And very happy. :-)

(regarding digital signatures)
>  - though I think we still have open questions
>   there on what we would want to use here as well. Use RSA+ECDSA?
>   Move off RSA entirely and use DSA+ECDSA or ECDSA+ECNR? Or go for
>   ECDSA plus something exotic like McEliece or a hash-based scheme?

Yes, lots of questions. I'm currently still pretty interested in
trying to squeeze good performance out of hash-based digital
signatures (Generalized Merkle Signature System) [2]. I've had some
more ideas about that since the last time we talked on this list (take
advantage of the statefulness of the mutable file versioning scheme
which we rely on and require anyway).

> I would really like to see comments on these and other approaches.
> This seems like a tough problem with a lot of downsides no matter what
> we decide.

Now that we've had this little exchange I'm fairly enthusiastic about
Yu Xue concentrating on just seeing the combined cipher project all
the way through. Even if he can't finish the entire job in the
remaining weeks of summer, every step that he takes in that direction
will probably end up being a valuable contribution.

Dear Yu Xue: what do you think? :-)

Regards,

Zooko

P.S. Oh, and don't forget about yet another possibility: Samuel Neves
suggestion to use a hash function for encryption [3, 4, 5]. I suggest
that we remember this and then put it on the back burner for now and
focus on AES/XSalsa20.

http://tahoe-lafs.org/trac/pycryptopp/ticket/40# xsalsa20 wrapper

[1] http://tahoe-lafs.org/pipermail/tahoe-dev/2010-March/004150.html
[2] http://tahoe-lafs.org/pipermail/tahoe-dev/2010-July/004587.html
[3] http://tahoe-lafs.org/pipermail/tahoe-dev/2010-June/004487.html
[4] http://tahoe-lafs.org/pipermail/tahoe-dev/2010-June/004495.html
[5] http://tahoe-lafs.org/pipermail/tahoe-dev/2010-June/004515.html