[tahoe-dev] modification of "100 year cryptography" project proposal

[yu xue]

Hello, all the mentors and developers:
I have made some modifications about the GSOC proposal---"100 year
cryptography" according to the suggestions from Zooko and Jack. Thank you!!

The project that I’m interested in is “100 Year Cryptography”.

The cryptographic algorithm will be increasingly weaker because of the
constant cryptanalysis. An excellent public cryptographic algorithm is often
used widely all over the world and even becomes the standard, such as AES,
MD5, SHA-1 etc. These applications seem that put all eggs in a basket. Once
the algorithm were broken, the result will be very serious. The lessons have
been learnt from the broken of classic hash function such as MD5, SHA-1. Of
course, creating new secure algorithms is a good choice such as SHA-3
competition, but this procedure need some time. How can we improve the
security of applications based on the existing algorithms? Combiner is a
good choice. A black-box combiner for some cryptographic primitive is a
construction, which given black box access to two candidate schemes,
securely implements the primitive, if at least one of the two candidates
securely implements it [2]. For example, if we use a secure combiner of
MD5(SHA-512) and whirlpool, even if MD5(SHA-512) is not secure, the whole
combiner is still secure because of whirlpool is secure. A secure combiner
can provide better security. So implementing secure combiners is a good
complement.

Tahoe is a system for secure, distributed storage. It uses cryptography
heavily for confidentiality and integrity. For example, it uses Merkle hash
tree and encryption in immutable files and mutable files. In this project we
aim to implement the combiner of ciphers and hash function etc as a new
security primitive to provide better security.

Our basic development will adopt test-driven development. If there are some
difficulties using this method such as Comb4P part as pointed by Jack we
will flexibly adjust the development method, for instance using
independent-code-then-compare and third-party review.

The work I will do and the deliverables include as follows:

1. combiner of ciphers part ( about 4 weeks )

1)  Write the documentation concerning the specification and the API about
combiner  of ciphers.

2)   Write tests harness including unit tests, test vectors to exercise the
new components as much as possible. Build automated evaluation tools such as
valgrind, ctgrind, benchmarks and a buildbot farm.

3)  Implement the combiner of block cipher based on the tests cases. The
combiner is concerned about the symmetric ciphers such as block cipher and
stream cipher. Take two ciphers as underlying primitives. Generate
independent keys for each cipher. When encrypting, first encrypt using the
first cipher and then feed the ciphertext as the plaintext into the second
cipher. That is, C = E2(K2, E1(K1, M)), where K1 and K2 are independent
keys, E1 and E2 are two underlying ciphers. In particular, we will implement
a combiner of a block cipher AES and a stream cipher XSalsa 20. The
operation mode of AES will be CTR which has many benefit as pointed by Jack.
Another detail is about generating independent keys for each cipher. Zooko
has given a simple way to do this: let subkey1 be the first few bytes of the
keystream of XSalsa20 which uses masterkey and let subkey2 be the next few
bytes of the same keystream.

4)  It is very likely that we need to iterate the development, so in this
case we need to repeat the step 2) and 3). When modification occurs, it need
to modify documentation accordingly.

2.  combiner of hash function part (about 4-5 weeks)
As pointed by Jack, this part may be have difficulty in using TDD. So we use
conventional development procedure.

1) Write the documentation concerning the specification and the API about
combiner of hash function Comb4P.

2) Implement Comb4P hash function combiner which is presented in [2] by
Fischlin etc. A hash function combiner takes two hash functions H0, H1 and
combines them into a failure-tolerant function such that this function
remains secure as long as at least one of the two functions H0 or H1 is
secure. A hash combiner can provide better security and has practical
applications such as in TLS and SSL[1]. Comp4P combiner can preserve
properties including collision resistance(CR), target collision
resistance(TCR), message authentication (MAC), and pseudorandomness (PRF).
The basic structure of Comb4P is three round feistel and the round function
is composed of xoring of H0 and H1 with the help of round index i. At the
beginning two branches apply the H0 and H1 respectively. The property
preservation is proved secure in [2].

Due to the particular feistel structure and operations of Comb4P, a problem
as pointed by Jack is that how to properly handle hashes with different
sized outputs such as combiner of SHA-256 and whirlpool-512. A *half
thought* is that maybe it need to limit the equal digest size of the
underlying hash, otherwise it need to give a warning or error prompt. Since
many mainstream hash functions have multi-versions, commonly including 224,
256, 384 and 512, when incompatibility occurs it could prompt using another
compatible version. If unfortunately it doesn’t have compatible version,
then we need give an error prompt or using other methods such as truncation
etc.

3)  Compare the results of the random test cases with the results of mentor
until getting the consistent results. When particular situation occurs, we
may ask for help of third-party reviewers.

4)  Write tests harness including unit tests, test vectors to exercise the
new components as much as possible. Build automated evaluation tools such as
valgrind, ctgrind, benchmarks and a buildbot farm. Make modifications of doc
according to the modification of the implementation.

3. There are some areas which are interesting and worth our exploring when
the above parts are completed successfully, for example:
1)  Combiner of signature algorithm.
The half thought is that maybe implementing a combiner of signature
algorithms such as RSA and ECDSA signature. This part need further
discussed.

2)  Explore the possibility of Comp4P&IRO, Comp4P&OW, Comp6P. These
combiners have theoretical advantage, however, as pointed by Zooko, there
are many problems when implementing especially when using on tahoe. In these
cases, Comp4P&IRO etc. may be not a good choice because of their longer
output, code size and complexity, and possibility of concrete implementation
etc. After all, appropriation is the best. For tahoe, Comp4P is more
appropriate.

3)  Write up an internet draft for submission to the IETF giving a complete
specification of Comb4P with test vectors to help adoption of the combiner
and to encourage further analysis, as suggested by Jack.

Reference:
[1] M.Fischlin, A.Lehmann, D.Wagner, "Hash Function Combiners in TLS and
SSL", CT-RSA 2010
http://www.cdc.informatik.tu-darmstadt.de/~fischlin/publications/fischlin.ssl-combiners.2010.pdf

[2] M.Fischlin, A.Lehmann, K.Pietrzak, "Robust Multi-Property Combiners for
Hash Functions Revisites."
http://www.cdc.informatik.tu-darmstadt.de/~alehmann/publications/MPRCombinersRevisited.pdf

  Regards
      Yu Xue

-- 
    此致
敬礼!
                      薛宇

                  身前身后
                  是时间的深渊
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://allmydata.org/pipermail/tahoe-dev/attachments/20100419/e0e21975/attachment.htm