[tahoe-dev] GSOC proposal---"100 year cryptography"

[Jack Lloyd]

On Fri, Apr 16, 2010 at 09:56:37AM -0600, Zooko O'Whielacronx wrote:

> Let's do this in the "test first" paradigm. The rule of test-first is:
> you're not allowed to write a line of code until you have a fully
> automated test case which runs and fails. Then you write code until
> you can get that test case to pass, at which point you have to stop
> writing code and go back to adding tests until you have some more test
> cases that fail.

One difficulty here is that the hash combiner in particular seems
difficult to do immediately in this way, since AFAICT there is no
existing implementation of Comb4P (or any of the other combiners in
Lehmann's thesis) to write a test on the basis of.

I just wrote up a quick implementation of Comb4P that currently may or
may not be correct. It uses a byte instead of two bits for the round
number, since handling all the bit offsets would be slow and obnoxious
in software, and numbers the rounds 0,1,2 instead of 0,2,3 as
Lehmann's thesis seems to do. I haven't quite figured out how to
properly handle hashes with different sized inputs, though, which does
seem like a very useful ability to have. (for instance for combining
SHA-256 + some 512 bit output from a SHA-3 candidate).

This implementation could serve as a useful check; Yu Xue could
implement Comb4P independently from me, and if it turns out that our
outputs match for a variety of input messages and hash pairings, then
we have reasonable confidence that we're both correct (or else that
Lehmann's description of the combiner is too vague, and we both
happened to make the same mistake in reading her thesis - we'll want
third party reviewers to help catch that problem).

> Likewise, let's move this up to the beginning. You should write the
> documentation concerning the specification and the API before writing
> the code. (This means you'll end up having to change the docs as you
> change the API.) You should write the documentation concerning the
> design of the code as you write the code itself.

Also on the documentation front (as an "if there is time" / bonus),
write up an internet draft for submission to the IETF giving a
complete specification of Comb4P with test vectors to help adoption
(and, importantly, to encourage further analysis) of the combiner.

-Jack