[tahoe-dev] Hashes in 100 year crypto

[Jack Lloyd]

Part of the 100 year crypto project that our GSoC student Yu Xue is
working on is, instead of relying on just SHA-256, to combine two
different hashes in such a way that if even one of them stays strong
then Tahoe remains safe and sound.

For a combine, we're going to use Comb4P. This is a Fiestel scheme
with good properties - there are reasonably good proofs that, if even
one of the hashes used in it has certain good properties (such as
collision resistance, preimage resistance, or psuedo-randomness) then
the combined hash will also have this property, even if the other hash
does not. However, one limitation to Comb4P is that using it to
combine hash functions of different lengths seems at the least
unstudied and perhaps actually unsafe.

Thus, to use Comb4P successfully we need to identify two N-bit hashes,
both of which we think have a good chance of remaining secure for a
long time, or take some other approach.

Ideas I've had so far:

 - 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.

 - 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.

 - Use hashes of different lengths, but truncate to the shorter one
   (eg using SHA-256 plus SHA-512 truncated to 256 bits)

 - Choose a pair of 512-bit hashes already in Crypto++ and use those.
   I say this because the only 256 bit hash in Crypto++ that isn't
   SHA-256 seems to be RIPEMD-256, which is not particularly well
   studied (and Crypto++'s sources have a comment that "RIPEMD-256 is
   considered insecure, and should not be used unless you absolutely
   need it for compatibility." - I don't know what the specific
   attack/limitation might be though (I actually don't know that I've
   ever seen even a single paper looking carefully at the double-wide
   RIPEMD constructions)). But we could use, say, SHA-512 and
   Whirlpool - but SHA-512 is not particularly fast, especially on
   32-bit processors, and Whirlpool is downright slow.

   This has an additional limitation that then we are dealing with
   1024 bit hashes, which is a touch large.

 - 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. But
   which one? This would be a much easier choice after mid-August,
   when the finalists in the competition are expected to be announced
   - but that would push everything back quite significantly, perhaps
   too much so for a sucessful completion of the overall project.

   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.

 - 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 - 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?

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.

-Jack