[tahoe-dev] Fwd: implementing Comb4P for serious use

[Zooko O'Whielacronx]

---------- Forwarded message ----------
From: Anja Lehmann <anja.lehmann at minicrypt.de>
Date: Wed, Apr 21, 2010 at 5:35 AM
Subject: Re: implementing Comb4P for serious use
To: Zooko O'Whielacronx <zookog at gmail.com>


Hi Zooko,

thanks for your email. It would indeed be great to see our combiners
used in practice or even in an IETF proposal! Just a few questions
from my side ... who is actually "behind" that project? Is is just an
open community or is there any company involved? And will all the
implementations be open-source?

I'm unfortunately quite busy these days, so I couldnt read all
discussions in full detail yet, but I can make some remarks:

i) There was the question on how to handle different output lengths of
H0,H1 in the Feistel part of the Comp4P combiner.

As the Feistel part is essential for the PRF property, one has to
ensure that the XOR-Combiner used as round function is a pseudorandom
function. Thus, when dealing with different output lengths, one has to
truncate the longer output to the size of the shorter one. Otherwise
the security could get lost, if there would be a PRF attack against
the longer hash function. As a theoretic counter example why for
instance padding the output of the shorter hash function (here H0),
i.e. (H0 || 0...0) xor H1
doesnt work, consider the case where H1 is an insecure PRF that always
ends with the '1' bit. Then also the XOR combination would be insecure
independent of the strength of H0. Thus, the padded XOR construction
is not a PRF anymore which is the necessary assumption for our Comp4P
Combiner to be PRF as well.

As it was already mentioned in the mailing list, the easiest way would
be to combine hash functions that already have the same output length.
(Or using SHA-3 candidiates, as they have to support variable output
lengths?)


i) Another issue was: It would also be interesting to find out/study
what properties Comb4P maintains under truncation of the final output.