[tahoe-dev] Hashes in 100 year crypto

yu xue xueyu7452 at gmail.com
Tue Jul 20 14:59:11 UTC 2010

Hi, dear Zooko and Jack:

Thank you for your suggestions and discussions. Some of my personal
thoughts are as follows, if there are some wrong, please give me a
suggesion, thanks!

1. The tough problem about Comp4P is mainly the choosing of  two hash
algorithms. I also feel the SHA-3 candidates algorithms seem to be
better. Firstly, these will be more secure than the current common
hash algorithm such as SHA-2, ripemd etc. Secondly they could generate
all kinds of common digest length. Of course, the most important is
that it will be new hash standard. But the main problem is the time of
the final decision of SHA-3. I feel maybe one way is: implement the
Comp4P framework and test using the current well implemented hash
algorithms such as SHA-256 and ripemd-256 suggested by Jack. When the
time is appropriate, e.x. the final round algorithms have been
selected. I will try to integrate the appropriate algorithms into
Comp4P. I am happy to do it even if at that time gsoc has been over.
But I don't know whether it will delay the development of tahoe. If
there is *confident and believable* sha-3 candidate, I could try to do
right now.

2. If you feel the method which is proposed by zooko at [1] can
replace Comp4P, I will implement it. Or implement both of them

3. I will try my best to get a complete implementation of combiner of
cipher(AES and xsalsa20) which is suggested by zooko. Frankly
speaking, I have never thought of these details.So I feel there are
some problems I should fixed.

Thank you again :)

   Yu Xue

[1] 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

2010/7/20 Jack Lloyd <lloyd at randombit.net>
> 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
> _______________________________________________
> tahoe-dev mailing list
> tahoe-dev at tahoe-lafs.org
> http://tahoe-lafs.org/cgi-bin/mailman/listinfo/tahoe-dev



More information about the tahoe-dev mailing list